发布时间 : 星期日 文章北大操作系统课后题参考答案更新完毕开始阅读
2)运行顺序是(6,8,10,2,4) (6+14+24+26+30)/4=100/4=25 3)(10+16+18+22+30)/4=96/4=24
4) (2+(2+4)+(2+4+6)+(2+4+6+8)+( 2+4+6+8+10))/4=17.5
32：有5个待运行的作业，他们的估计运行时间分别是9,6,3,5，采用哪中次序运行各个 作业将得到最短的平均响应时间？答案依赖于X
答：由于5个作业同时到达，所以按最短作业优先调度会得到最短的响应时间： 9≤x 3 5 6 9 x 6≤x≤9 3 5 6 x 9 5≤x≤6 3 5 x 8 9 3≤x≤5 3 x 5 8 9 x≤3 x 3 5 8 9
33,在一间酒吧里有三个音乐爱好者队列，第一列音乐爱好者只有随身听，第二列只 有音乐
磁带，第三列只有电池，而要听音乐就必须有随身听，音乐磁带和电池这三中物品 。酒吧老板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品 并听完乐曲后，酒吧老板才能再一次出售这三种物品中任意两种，于是第二名音乐 爱好者得到这三种物品。并开始听乐曲，全部买卖九这样进行下去。
使用P,V操作正确解决这一买卖。
解：买方有三个进程，卖方有1个进程
卖方，和买方的同步信号量 S1,S2 ,初值为0,1. 听音乐时的互斥信号量;mutex 卖方进程
P(S1) (没有音乐爱好者，等待) 卖物品 P(mutex) 放音乐 V(mutex)
V(S2)
买方进程 P(S2) 买物品
V(S1) {老板可以卖东西}
34.巴拿马运河建在太平洋和大西洋之间，由于太平洋和大西洋水面高度不同，有巨大落 差，所以运河中建有T(T≥2)级船闸，并且只能允许单向通行，船闸依次编号为1,2,…,T ，由大西洋来的船需要经过船闸T,T-1.,,,2,1通过运河到达太平洋，由太平洋来的船需要 经由船闸1,2,…,T-1,T通过运河到达大西洋。
使用P,V操作正确解决大西洋和太平洋的船只通航问题。
答：答：Array: S1[T] of Semaphore {为每个船闸设置的信号量初值都为1}
Array: count1[T] of INTEGER {为每个船闸设置通往大西洋的船的计数值,初值都为 0}
Array: count2[T] of INTEGER {为每个船闸设置通往太平洋的船的计数值,初值都为 0}
对count设置互斥信号量 mutex 去大西洋的进程: int j
for(j=0;j if(count1[j]==0) P(S[j]) count[j]++ 过第j+1个船闸 P(mutex) count[j]-- if(count[j]==0) V(S[j]) V(mutex) } 去太平洋的进程： int k for(k=T-1;k≥T,k++){ P(mutex) if(count2[k]==0) P(S[k]) count[k]++ 过第k+1个船闸 P(mutex) count[k]-- if(count[k]==0) V(S[k]) V(mutex) } 35.某银行有人民币储蓄业务，由n个柜员负责，每个顾客进入银行后，先取一个号，并且 等着叫号，当一个柜员人员空闲下来，就叫上一个号，使用P,V操作正确编写柜台人员和 顾客进程的程序！ 解; 取号的互斥信号量 mutex,叫号的互斥信号量mutex1 柜台人员和顾客进程的同步信号量为 S1,S2, 初值分别为n,0 柜台人员进程： P(S2) (无顾客则等待) P(mutex1) 叫号 V(mutex1) 服务 V(S1) 顾客进程 P(mutex) 取号 V(mutex) P(S1) 享受服务 V(S2) 36,设A,B,C三个进程共享一个存储资源F,A对F只读不写，B对F只写不读，C对F先读后写。 （当一个进程写F时，其他进程既不能读F，也不能写F,但多个进程同时读F是允许的）试 利用管程的方法或者P,V操作，写出A,B,C三个进程的框架，要求：（1）执行正确 （2）正常运行时不产生死锁；(3)使用F的并发度高 37,某系统如此定义P,V操作 P(S) S=S-1 若S<1本进程进入等待队列末尾，否则继续进行 V(S) S=S+1 若S≤0,释放等待队列中末尾的进程，否则继续运行。 现有四个进程P1,P2,P3,P4竞争使用某一需要互斥使用的资源（每个进程可能反复使用多 次），使用这样的P,V操作来正确的实现互斥。 解: S:ARRAY[0,,,3] OF Semaphore{初值为s[i]=i,i=0,1,2,3 } 访问进程 for i:=3 downto 1 do P(s[i]) 临界区操作 for i:=1 To N-1 Do V(S[i]) 38,请用进程通信的办法解决生产者，消费者问题 39,请用管程实现哲学家就餐问题 进程管理（笔记） 1).多道程序设计和并发 内存允许多个程序进入，操作系统能够同时执行这些程序 CPU在多个进程之间调度，切换 系统有时有进程，有线程 对CPU的管理： 每个实体都有一个环境，多个实体间存在一个切换 从顺序执行开始，到并发执行，会产生许多特征 顺序执行----并发执行(不可再现性)------与时间有关的错误 并发执行的结果，不可再现，由于每个程序执行的速度不同，会带来不一致性。 与时间有关的错误，即包括互斥（飞机订票系统，一张票卖给两个顾客，竞争条件）， 这是由于并发执行，且资源共享引起的。 2).进程模型 进程：正在执行的程序，系统中同时会有许多程序在执行 进程有创建，有撤销 从以下几个方面考虑进程模型： 2.1 进程的组成，进程有动态，有静态，从动态的角度讲叫做进程映像。 一个系统中与进程有关的实体和空间 1.程序的地址 2.进程所需的数据 3.进程运行过程中所遗留的痕迹（栈） 栈是进程运行过程中临时性的信息存放的地方。 栈分为系统栈和用户栈 用户空间和系统空间时分开的。 用户地址空间包括：程序，数据和栈 PCB(进程控制块)是由系统来管理的，进程所需的信息都放在此数据结构中。 上下文环境，PCB,数据结构是进程存在的痕迹。 地址越界：用户只能在用户的地址空间活动，不能进入其他用户地址空间和系统空间 2.2进程状态以及状态转换 2.2.1进程控制块PCB,系统管理进程时，修改PCB 进程在运行时，通用寄存器要保存现场信息，不运行的时候，这些信息都要保存下 来 比如，指针等，现场要保存在自己的空间中，文件系统中。 现场信息包括很多内容。 进程控制块PCB时贯穿始终的 2.2.2状态的设置与进程的控制有关系，什么时候创建进程，什么时候中止进程，完全 由 原语来将进程从一个状态转变为另一个状态 最主要的就是了解进程的控制 3.进程的同步和互斥 这部分与 \与时间有关的错误\有关 同步是开发人员有意识安排的：在完成一个特定功能的软件中，由多个进程协作，这 些进程间有时序关系，互相配合完成，而这些时序是事先安排好的，OS不知道这些关系， 用 户通过OS提供的原语来维持这种时序。 同步：第一个进程执行道某一点后能否继续执行取决于另一个进程能够给它发消息。 进程的互斥：各个进程间要求共享资源，竞争使用资源。 书上讲解了“竞争条件”这一概念。 4.临界区：只允许一个进程使用的资源叫临界资源 竞争使用同一个资源的 不是一个进程的，而是以上进程 对于临界区的要求 1)任何两个进程不能同时处于临界区，即两段程序是不能交叉的 临界区的程序是可以中断执行的 2）如果想进入临界区，又进不去，则阻塞“有空让进，无空等待，有限等待” 3）不应对进程的速度和进程的数目作假设 解决互斥的问题： *1 用户关闭中断会出现问题（忘了开中断，怎么办？） *2 锁变量在解决互斥问题时，也可以引入新得互斥 *3 严格轮换法 以上三种方法都不能解决互斥。 以下两个都不考： #1 Peterson Delker 知道算法，但不考 #2 用硬件法解决互斥也不考 重点：5. 掌握信号量以及PV操作 5.1 信号量和PV操作 down --up (首选) P---V (也对) wait--signal（错误) 原理：在执行过程中，不可分割. down操作:对信号量：-1,若小于1，则阻塞，送到等待队列 up 操作：+1,若小于等于0，相应的信号量等于等待队列上的进程。 重点中重点：必有P V操作的题： 解题的要素：1)设置好每个信号量（每道题的分数由若干部分组成） 列出所有的信号量及其初值就给分 2）写PV，操作时，PV操作部分不能用自然语言，其余的部分 可用伪码，自然语言均可 begin ---end , repeat --until(搞清楚 2分) 读者---写者(循环) 生产---消费（不循环） 6.几个典型模型（考试不会超过此类模型） 6.1 生产者---消费者类型 思想：由一些 buffer,一些进程向Buffer 中写，另一些向Buffer中读 回家总结： *1 一个生产者，一个消费者，一个buffer *2 一个生产者，一个消费者，一些buffer *3 一个生产者，多个消费者，一个或者多个buffer *4 多个生产者，多个消费者，一个或者多个buffer(最复杂，不考！0) 6.2 哲学家进餐问题(认真读书上的每句话) 对于多个竞争进程互斥访问资源是非常有用的！ 6.3 读者---写者问题(P42) 对共享资源的操作 读有许多读者，但写时只有一个写。 若是两组读者问题，第二个读者将第一个得拷贝过来，变量改变一下 2003年的考研题，运河问题均是读者---写者问题 2003年考研题思路： 如何限制只有3个过，第四个不能过。 关键在于问题如何分解 树上这种读者，写者会出现饥饿，但本题要求不出现饥饿 大船方向：写者，小船方向：写者 把原来程序的框架写出，将细节只允许3个船过（不允许出现饥饿）补充进去 6.4 理发师问题(P43) 6.5 吸烟者模型 小的问题：eg:银行叫号, 阅览室问题，（来一个申请一个资源，若干个进程对资 源的使用问题），考场问题（同步关系，比较简单） 做题套路：1）先写出程序 2)找出进程间的关系(分解开找，先找互斥，再找同步，一 个关系设置一个信号量) 3）P,V嵌入到相应的位置，信号量是在找关系的时候定好的！一 个一个关系找，不要嫌麻烦 4）赋好初值 5）注意细节（是否需要循环） PV匹配，但存在 if--else 语局时会有问题，信号量的操作，只能出现在P V中，而不会 出现在P,V语句之外，且不要写出有死锁的程序。 五. 进程通信 进程通信包括同步，互斥，本部分是高级的进程通信，P,V是简单进程通信！ linux中，信号量，共享内存，消息队列，Socket，管道均是通信机制 Windows中，互斥队列，信号量对象等均是通信机制。 分为如下几类： 1. 共享内存 与读--写者问题是同一模型，若P个进程互相通信（重点），要了解实现和设计细节 1.1 设置共享内存存取方式 读者如何互斥，写者如何互斥 1.2消息传递方式(OS 中用的多) 设计要点： 1)两个进程间收发消息模型 send-receive的操作来完成 消息的传递会产生如下问题：发送的消息会不会丢失，解决方案：作一个回答 ； 应答会不会丢！ 重发一条消息，接受道两个同一信息所带来的问题！ 消息本身会不会有差错！ 2） 给谁发消息，进程的命名会不会产生二义性！ 3）