综合题 多个进程共享一个文件,其中只读文件的称为读者,只写文件的称为写者。读者可以同时读,但写者只能独立写。
问答题     说明进程问的相互制约关系,应设置哪些信号量?
 
【正确答案】进程间的相互制约关系有三类: 一是读者之间允许同时读; 二是读者与写者之间须互斥; 三是写者之间须互斥。 为了解决读者、写者之间的同步,应设置两个信号量和一个共享变量;读互斥信号量rmutex,用于使读者互斥地访问共享变量count。其初值为1;写互斥信号量wmutex,用于实现写者与读者的互斥及写者与写者的互斥,其初值为1;共享变量count,用于记录当前正在读文件的读者数目,初值为0。
【答案解析】
问答题     用P、V操作写出其同步算法。
 
【正确答案】进程间的控制算法如下所示: int rmutex=1; int wmutex=1; int count=0; main() { cobegin reader(); writer(); coend } reader() { while(1) { P(rmutex); if(count==0)P(wmutex);//当第一个读者读文件时,阻止写 count++; V(rmutex); 读文件; P(rmutex); count--; if(count==0)V(wmutex);//当最后一个读者读文件时,允许写 V(rmutex); } } writer() { while(1) { P(wmutex); 写文件; V(wmutex); } }
【答案解析】
问答题     修改上述的同步算法。使得它对写者优先,即一旦有写者到达,后续的读者必须等待。而无论是否有读者在读文件。
 
【正确答案】为了提高写者的优先级,增加一个信号量S,用于在写进程到达后封锁后续的读者。其控制流程如下: int rmutex=1; int wmutex=1; int count=0; int s=1; main() { cobegin reader(); writer(); coend } reader() { while(1) { P(s); P(rmutex); if(count==0)P(wmutex);//当第一个读者读文件时,阻止写 count++; V(rmutex); V(s); 读文件; P(rmutex); count--; if(count==0)V(wmutex);//当最后一个读者读文件时,允许写 V(rmutex); } } writer() { while(1) { P(s); P(wmutex); 写文件; V(wmutex); V(s); } }
【答案解析】
问答题   假定有一组作业(或进程),它们提交时间及要求运行的时间如下表所示(单位为小时,并以十进制计)。
   
【正确答案】不对。理由如下: 采用最短作业(或进程)优先调度算法,则作业的执行顺序是1、3、4、2。 (1)作业i的周转时间Ti=Tei-Tsi,其中,Tei为作业i的完成时间,Tsi为作业i的提交时间。 平均周转时间T,是指多个作业的周转时间的平均值。所以,T=(2.0+1.1+0.8+2.3)/4=1.55。 (2)带权周转时间Wi=Ti/Tri,其中,Ti为作业i的周转时间,Tri为作业i的实际运行时间。 平均带权周转时间W=(2.0/2.0+1.1/0.1+0.8/0.2+2.3/0.5)/4=5.15。
【答案解析】
问答题   假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中,写出计算该算术表达式值的算法。
 
【正确答案】以二叉树表示算术表达式,根结点用于存储运算符。若能先分别求出左子树和右子树表示的子表达式的值,最后就可以根据根结点的运算符的要求,计算出表达式的最后结果。
【答案解析】