答：由于图为： C1 5 A1 10 B1 15 ，因而采用EDF算法一定可以调度，其Gantt
A2 10 B2 15 C2 5 0 5 15 30 40 55 60 A1 10 0 10 B1 15 C1 A2 5 10 B2 15 C2 A3 5 55 60 10 B3 A4 C3 15 10 5 95 105 110 120 25 30 40 70 80 由于
28. 分析Linux进程调度算法的调度效果。
，因而采用RMS算法不可调度。
答：Linux在调度级别上考虑三种特征进程：Real-time FIFO, Real-time Round Robin, Timesharing. 调度基于Goodness度量指标，涉及如下一些参量：
Priority: 1~40(缺省值20)，可通过nice系统调用调整，nice(value)中value的取值范围为(-20,20)之间，以与经典UNIX保持兼容，但在内部对value值进行反向，取
priority=20-value。Quantum: 进程尚可运行的剩余时间．对于运行进程来说，每个时钟间隔(10ms，称为一个jiffy)，将quantum减1，当所有就绪进程的quantum配额下降到0时，重新计算所有进程(包括等待进程)的quantum值。Goodness值的计算方法如下： If(Real-time)Goodness=1000 + priority; If(Timesharing && quantum=0))Goodness=0;
If(Timesharing && quantum>0)Goodness=quantum + priority.
调度发生在如下时刻：(1)运行进程的quantum减至0；(2)运行进程执行系统调用exit；(3)运行进程因等待I/O、信号灯而被封锁；(4)原来具有高goodness的进程被解除封锁。容易看出调度效果：实时优先于分时，交互和I/O进程优先于CPU进程。 四、 同步与互斥习题及解答:
1． 何谓与时间有关的错误? 举例说明之。
答：并发进程的执行实际上是进程活动的某种交叉，某些交叉次序可能得到错误结果。由于具体交叉的形成与进程的推进速度有关，而速度是时间的函数，因而将这种错误称为与时间有关的错误。
16
例如，两个并发进程的程序如下： int n=0; main( ){ 创建进程A； 创建进程B； }； A( ){ while(1){ n++; } };
B( ){ while(1){
睡眠一段时间； printf(“%d”,n); n=0; } };
假设进程A被部署在公园入口的终端上，用来记录一段时间内进入公园的人数，进程B被部署在公园的控制中心，用来输出一段时间内进入公园的总人数。进程A和进程B共享全局变量n，n表示记录下的人数。如果在进程B执行完打印语句后被进程A打断，进程A执行了若干次变量自增语句，之后进程B接着执行清0语句，那么进程A对n的累加丢失了，相当于进程B被打断的这段时间内进入公园的人没有被记录下来。发生与时间有关的错误。 2． 有人说，假设两个进程之间没有共享内存，则二者之间没有公共变量，这种说法准确吗? 说明原因。
答：如果只从用户空间考虑，这种说法是正确的。但从操作系统的角度来说并不准确。两个没有公共内存的用户进程可能同时（宏观）进入操作系统，并访问操作系统空间中的公共变量。
3．何谓忙式等待? 是否还有其它方式的等待? 比较它们之间的联系和差别。
答：不进入等待状态的等待称为忙式等待。另一种等待方式是阻塞式等待，进程得不到共享资源时将进入阻塞状态，让出CPU给其他进程使用。忙等待和阻塞式等待的相同之处在于进程都不具备继续向前推进的条件，不同之处在于处于忙等待的进程不主动放弃CPU，尽管CPU可能被剥夺，因而是低效的；而处于阻塞状态的进程主动放弃CPU，因而是高效的。 4．下列进程互斥方法哪些存在忙式等待问题?
（1）软件: 面包店算法(2) 硬件: TS指令(3) 关中断指令
答：（1）、（2）存在忙等待问题。
5．为何开关中断进程互斥方法仅在单CPU系统中是有效的？
答：关中断方法不适用于多CPU系统，因为关中断只能保证CPU不由一个进程切换到另外一个进程，从而防止多个进程并发地进入公共临界区域。但即使关中断后，不同进程仍可以在不同CPU上并行执行关于同一组共享变量的临界区代码.
17
6．在多处理机系统中，软件互斥方法是否有效？为什么？
答：依然有效。多处理机并行与单处理并发之间的差别在于程序交叉的粒度，单处理机机环境中进程交叉发生在指令之间，多处理机环境中进程交叉发生在指令周期之间。由于纯软件互斥算法并不依赖特殊的硬件指令(如test_and_set)，指令之间的交叉与指令周期之间的交叉结果相同。
7．试分析临界区域的大小与系统并发性之间的关系。
答：关于同一组变量的临界区域是不能并发执行的代码，临界区越大，并发性越差，因而编写并发程序应尽量缩小临界区域范围。
8．设CR1是关于一组共享变量SV1的临界区域，CR2是关于另外一组共享变量SV2的临界区域，当进程P1进入CR1时，进程P2是否可以进入CR2? 为什么?
答：可以。因为互斥是在变量级别上的，多个进程同时进入关于不同变量的临界区不会引起与时间有关的错误。
9．Lamport面包店互斥算法是否会出现饿死情况?
不会，该算法是公平的。假定系统中共有n个进程，每个想要进入临界区域的进程(线程)在最坏的情况下需要等待其它n-1个进程进入并离开临界区域之后即可获得进入临界区域的机会，因而存在(忙式)等待的上界。 10．试用信号灯和PV操作实现临界区语句: region <共享变量> do <语句> 变量类型<共享变量> 答：
semaphore s=1; P(s); <语句> V(s);
11. 由V操作唤醒的进程是否一定能够直接进入运行状态? 举例说明之。
答：否。一般来说，唤醒是将进程状态由等待状态变成就绪状态，而就绪进程何时获得处理机则是由系统的处理机调度策略确定的。如果采用抢占式优先级调度算法，并且被唤醒的进程是当前系统中优先级最高的进程，那么该进程将被调度执行，其状态变成运行态。如果该进程不是系统中优先级最高的进程或系统采用其它调度算法，那么该进程不会被调度执行，其状态将维持在就绪态。
12. 设S1和S2为两个信号灯变量，下列八组P、V操作哪些可以同时进行? 哪些不能同时进行? 为什么?
(1)P(S1)，P(S2) (2)P(S1)，V(S2)
18
(3)V(S1)，P(S2) (4)V(S1)，V(S2) (5)P(S1)，P(S1) (6)P(S2)，V(S2) (7)V(S1)，P(S1) (8)V(S2)，V(S2)
答：能同时进行的包括：(1)、(2)、(3)、(4)。这些操作涉及不同信号灯变量，属于关于不同组共享变量的临界区。不能同时进行的包括：(5)、(6)、(7)、(8)。这些操作涉及相同的信号灯变量，属于关于同一组共享变量的临界区。
13. 对于生产者—消费者问题，假设缓冲区是无界的，试用信号灯与PV操作给出解法。 答：由于是无界缓冲区，所以生产者不会因得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以去掉在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。 semaphore mutex_in=1; semaphore mutex_out=1; semaphore empty=0; int in=0，out=0;
生产者活动： while(1){
produce next product; P(mutex_in);
add the product to buffer[in]; in++;
v(mutex_in); V(empty); }
消费者活动： while(1){ P(empty); P(mutex_out);
take the product from buffer[out]; out++;
V(mutex_out); }
14. 设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式: -M≤A物品数量－B物品数量≤N
其中M和N为正整数。 试用信号灯和PV操作描述A、B两种物品的入库过程。 答：已知条件 -M≤A物品数量－B物品数量≤N 可以拆成两个不等式，即
A物品数量－B物品数量≤N， B物品数量－A物品数量≤M。
这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个；Ｂ物品可以比A物品多，但不能超过M个。
19
semaphore a=n; semaphore b=m; void main(){
createprocess(A,?); createprocess(B,?); }
A物品入库： void A(){ while(1){ P(a);
A物品入库; V(b); } }
B物品入库： void B(){ while(1){ P(b);
B物品入库; V(a); } }
15. 试用信号灯与PV操作实现司机与售票员之间的同步问题。设公共汽车上有一个司机和一个售票员，其活动如下图 所示。
为了安全起见，显然要求: (1)关车门后方能启动车辆；(2)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。
解：如果进程P2尚未推进到②处时，进程P1已经推进到①处，则P1应等待直到P2推进到②处为止；同样，如果进程P1尚未推进到③处时，进程P2已经推进到④处，则P2应等待直到P1推进到③处为止。如果进程P1在①处发生了等待，则当进程P2执行到②处时应将P1唤醒；同样，如果进程P2在④处发生了等待，则当进程P2执行到③处时应将P1唤醒。用信号量和P、V操作解决这一问题，需要定义两个信号量，一个信号量start表示是否允许司机启动车辆，另一个信号量open表示是否允许售票员开车门。初始状态是车停在始发站，车门开着，等待乘客上车。因此，两个信号量的初值都是0。 semaphore start=0; semaphore open=0;
20