操作系统算法题

操作系统

1. 在信号量机制中，若P（S）操作是可中断的，则会有什么问题？

答：P（S）的操作如下： Begin

S.Value:= S.Value-1; ① If S.Value<0 Then ② Begin

Insert(*,S.L);

Block(*) ③ End End.

若P（S）可中断的，例如进程A在执行了语句①之后从CPU上退下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误：本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。

2. 何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？ ＃define true; # define false; Int flag[2];

flag[1]=flag[2]=false; enter-crtsec(i) int i; {

While(flag[1-i]) flag[i]=true; }

feave-crtsec(i) Int i; {

flag[i]=false; }

process I; …

Enter-crtsec(i); In critical section; Leave-crtsec(i);

答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。 从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。

操作系统

这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。

3. 当进程X和进程Y共享某个资源r，进程并发执行时的程序如下： Begin

S:semaphore:=1; Cobegin

Process X Begin

L1:P(S); 使用资源r; V(S); Goto L1; End; Process Y Begin

L2:P(S); 使用资源r; V(S); Goto L2; End; Coend; End; 请回答：

（1）两个进程并发执行时，能否保证互斥地使用资源？为什么？

（2）若要使用两个进程交替使用资源，仍使用P、V操作来进行管理，写出应定义的信号量及其初值。

（3）修改上述程序，使两个进程能交替使用资源r。

答：当进程X和进程Y共享某个资源r，回答各问如下：

（1）能保证互斥使用资源。因为在两个进程中，"使用资源r"都是作为临界区，由于P(S) 和V(S)操作保证了互斥执行，S的初值定义为1，符合要求。

（2）要使两个进程交替使用资源，仅仅保证互斥使用是不够的，必须要两个进程互相等待互相通知。为此，必须定义新的信号量。定义两个私有信号量S1和S2。假定进程X先使用资源，那么进程X的私有信号量S1的初值定义为1，进程Y的私有信号量S2的初值定义为0。轮流使用可以保证互斥，因此信号量S可以不要。 （3）两个进程可以改写为： Begin

S1:semaphore:=1; S2:semaphore:=1; Cobegin

Process X Begin

L1:P(S1);

操作系统

使用资源r; V(S2); Goto L1; End; Process Y Begin

L2:P(S2); 使用资源r; V(S1); Goto L2; End; Coend; End;

4. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

（1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。

Cobegin PROCESS Pi(i=1,2,…) Begin

进入售票厅； 购票； 退出； End; Coend

(3)若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。

答：售票厅问题解答如下：

（1）定义一信号量S，初始值为20。

S>0 S的值表示可继续进入售票厅的人数； S=0 表示售票厅中已有20名购票者； S<0 |S|的值为等待进入售票厅中的人数。 （2）上框为P(S)，下框为V(S)。

（3）S的最大值为20，S的最小值为20－N，N为某一时刻需要进入售票厅的最多人数。

5. 已经系统中有四个缓冲池M0，M1，M2，M3。其容量分别为3、2、3、2，现各缓冲区分别存在0、1、0、2个数据。现同时有四个进程P0、P1、P2、P3分别在各缓冲区间不断地移动数据（见图3.5）。例如，P0进程从M0向M1移动数据。试用信号量及其P、V（或signal，wait）操作及类Pasic/C语言描述各进程之间的同步关系，并给出各信号量的含义和初值。 答：（1）互斥信号量和初值

M(0)=1，M(1)=1，M(2)=1，M(3)=1，

操作系统

（2）同步信号量

Full(i)表示buffer(i)是否有数据；

初值为full(0)=0，full(1)=1，full(2)=0，full(3)=2； Empty(i)表示buffer(i)是否有空间；

初值为empty(0)=3，empty(1)=1，empty(2)=3，empty(3)=0 （3）进程i的程序 Process Proc(i) { p(full(i));

p(empty(i+1) mod 5); p(m(i)); move; v(m(i));

v(m(full(i+1) mod 5)); v(empty (i)); }

6. 设有两个优先级相同的进程P1和P2如下，信号量S1和S2的初值均为0。试问P1、P2并发执行结束后，x=?,y=?,z=? <进程P1> Y:=1; Y:=y+2; V(S1); Z:=y+1; P(S2); Y:=z+y;

＜进程P2＞ X:=1; X:=x+1; P(S1); X:=x+y; V(S2); Z:=x+z;

答：因为P1和P2是两个并发进程，所以进程调度程序调度P1 和P2的顺序是不确定的。

这里不妨假设P1先执行。进程P1执行到语句P(S2)时，S2＝－1，进程P1阻塞。此时y=3,z=4。当进程调度程序调度到进程P2时，由于进程P1已执行了V(S1)，进程P2在执行P(S1)时并未阻塞而继续执行，当执行到 V(S2)时，将P1唤醒，然后执行最后一个语句z:=x+z，此时x=5,z=9。当进程P1再次被调度时，继续执行P1的最后一个语句，此时y=12，最终结果是：x=5,y=12,z=9。 如果当P2进程执行到 V(S2)时，将P1唤醒，然后P2进程被中断，此时x=5,y=3,z=4。P1进程开始执行然后执行最后一个语句y:=z+y，此时x=5,y=3,z=7。然后P2进程被调度，执行z:=x+z，此时x=5,y=3,z=12。

如果P2先执行，则执行结果与上面相同。

操作系统

7. 在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？ 答：（1）批处理系统中的作业调度算法有：先来先服务算法（FCFS）、短作业优先算法（SJF）、优先级调度算法（HPF）和高响应比优先算法（RF）。批处理系统的进程调度算法有：先进先出算法（FIFO）、短进程优先算法（SPF）、优先级 …… 此处隐藏：12256字，全部文档内容请下载后查看。喜欢就下载吧 ……