发布时间 : 星期六 文章操作系统练习题更新完毕开始阅读
内存，对磁带机和打印机采用静态分配方式，并假设输入/输出操作的时间忽略不计。现有一作业序列如表2-12所示：
表2-12 作业时间表
作业号 1 2 3 4 5 到达时刻 8:00 8:20 8:20 8:30 8:35 要求计算时间/min 25 10 20 20 15 要求内存量/KB 15 30 60 20 10 申请磁带机数/台 1 0 1 1 1 申请打印机数/台 1 1 0 0 1 假设作业调度采用先来先服务算法，优先分配内存的低地址区域，且不准移动已在内存中的作业，在内存中的作业平分CPU
时间，试问： （1） （2） （3） 5.
作业调度选中作业的次序是什么？
如果把一个作业的周转时间定义为到达系统至计算完成的时间，则最大和最小的作业周转时间是多少？ 作业全部执行结束的时间是多少？
设有两个生产者进程A、B和一个销售者进程C，他们共享一个无限大的仓库，生产者每次循环生产一个产品，然后入库供销售者销售；销售者每次循环从仓库中取出一个产品进行销售。如果不允许同时入库，也不允许边入库边出库，而且要求生产和销售A产品和B产品的件数都满足以下关系：-n<=A的件数-B的件数<=m,其中n、m都是正整数。请用信号量机制写出A、B、C三个进程的工作流程。
6. 考虑有三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷。做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌子上，具有另一种元料的吸烟者就可以做烟卷并抽烟，且在做完后给经销商发信号，然后经销商在拿出两种原料放在桌上，如此反复，试设计一个同步算法来描述他们的活动。
解：设整型变量r，s表示每个吸烟者进程所需要的两种原料，其取值范围在0到2之间。同步算法如下： begin
a：array[0..2] OF semaphore； a：=0； agent：=1； r，s：INTEGER； Cobegin Process A Begin Repeat
Set I,j to value between 0 and 2; P(agent); V(a[i]); V(a[j]); Until false; End;
Process B Begin Repeat P(a[r]); P(a[s]); Smoking;
第 13 页 共 26 页
V(agent); Until false; End; Coend; End. 7.
在测量控制系统中，数据采集任务把所采集到的数据送入一个单缓冲区：计算任务从单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。
在本题中采集任务与计算任务共用一个单缓冲区．当采集 任务采集到一个数据后，只有当缓冲区为空时才能将数据送入缓冲区中存放，否则应等待缓冲区腾空;当缓冲区中有数据时，计算任务才能从缓冲区中取出数据进行计算，否则也应等待。 本题实际上是一个生产者—消费者问题。将生产者—消费者问题抽象出来，以另外 一种形式描述是一种常见的试题形式．只要对生产者—消费者问题有了深入的理 解，就不难解决此类试题。
解;在本题中，应设置两个信号量Sf,Se，信号量Sf表示缓冲区中是否有可供打印的计算结果，其初值为0;信号量Se用于表示缓冲区有无空位置存放新的信息，其初值为1。 本题的同步描述如下： int Se=l; int Sf=0; main() { cobegin get();
compute();
coend } get() { while (采集工作未完成) { 采集一个数据： p(Se); 将数据送入缓冲区中; v(Sf); } }
compute() { while(计算工作未完成) { p(Sf); 从缓冲区中取出数据; v(Se); 进行数据计算; } }
图2．7给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关
系，并用P、V操作描述它。P35
第 14 页 共 26 页
图2．7 四个合作进程的前趋图
解：图2．7说明任务启动后S1先执行。当S1结束后，S2、S3可以开始执行。S2、S3 完成后，S4才能开始执行。为了确保这一执行顺序，设三个同步信号量b2、b3、b4分别 表示进程S2、S3、S4是否可以开始执行，其初值均为0。这四个进程的同步描述如下： int b2=0; /*表示进程S2是否可以开始执行*／ int b3=0; /*表示进程S3是否可以开始执行*／ int b4=0; /*表示进程S4是否可以开始执行*／ main() { cobegin S1 ( ); S2 ( ); S3 ( ); S4 ( ); coend }
S1 ( ) { ┇ v(b2); v(b3); }
S2 ( ) { p(b2); ┇ v(b4); }
S3 ( ) { p(b3)： ┇ v(b4); }
S4 ( ) { p(b4); p(b4); /*因在S2及S3完成时均对b4做了v操作，因此这里要用两个p操作*／ ┇ } 8.
桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。 [分析及相关知识] 在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果．当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待;若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者—消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。
解：在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值 为1;信号量So表示盘中是否有桔子，其初值为0;信号量Sa表示盘中是否有苹果，其初
第 15 页 共 26 页
值为0。同步描述如下： int S=1; int Sa=O： int So=O： main( ) { cobegin father(); son(); daughter()： coend }
father() { while (1) { p(S); 将水果放入盘中; if(放入的是桔子) v(So)： else v(Sa); } )
son( ) { while(1) { p(So); 从盘中取出桔子; v(S); 吃桔子; } }
dau[shter() { while(1) { p(Sa); 从盘中取出苹果; v(S)： 吃苹果; } } 9.
有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。 1）P、V操作是两条原语，定义如下：
P操作：P操作记为P(S)，其中S为一信号量，它执行时主要完成下述动作： S=S-1
若S>=0，则进程继续运行。
若S<0，则该进程被阻塞，并将它插入该信号量的等待队列中。
V操作：V操作记为V(S)，其中S为一信号量，它执行时主要完成下述动作： S=S+1
若S>0，则进程继续运行。
若S<=0，则从信号量的等待队列中移出队首进程。使其变为就绪状态。
（2）描述如下：
Var empty1,empty2,full1,full2:semaphore:=1,1,0,0; begin parbegin
第 16 页 共 26 页