操作系统作业 下载本文

semaphore Wmutex,Rmutex=1;int Rcount=0;semaphore mutex=1;void reader( ){while (true) { P(mutex); P(Rmutex); if (Rcount==0) P(Wmutex); Rcount=Rcount+1; V(Rmutex); V(mutex); ...; read; ...; P(Rmutex); Rcount=Rcount-1; if(Rcount==0) V(Wmutex); V(Rmutex); }}void writer( ) {while (true) { P(mutex); P(Wmutex); ...; write; ...; V(Wmutex); V(mutex); }}

13

9.写一个用信号量解决哲学家进餐问题不产生死锁的算法。 答:书上所提供的方法可能导致哲学家都只拿一只筷子而导致死锁且无法唤醒所有阻塞的进程。考虑引入一个互斥信号量mutex使哲学家一个个的进餐这样就不会引起死锁现象。 新设计的进程如下:

semaphore chopstick[5]={1,1,1,1,1};semaphore mutex=1;void philosopher (int i){while (true) { P(mutex); P(chopstick[i]); P(chopsick[(i+1)%5]); ...; eat; ...; V(mutex); V(chopstick[i]); V(chopstick[(i+1)%5]); ...; think; ...; }}10.一个文件可有若干个不同进程所共享,每个进程具有唯一的编码。假定文件可由满足下列限制的若干个进程同时访问,并发访问该文件的那些进程的编号的总和不得大于n,设计一个协调对该文件访问的管程。 答:

11.用管程解决读者—写者问题,并采用公平原则。

14

第四章

思考与练习题

1.某进程被唤醒后立即投入运行,能说明该系统采用的是可剥夺调度算法吗?

答:不能说明该系统采用的是可剥夺调度算法。当进程被唤醒时,此时就绪队列没有一个进程,则调度程序将它投入运行。

2.在哲学家进餐问题中,如果将先拿起左边筷子的哲学家称为左撇子,将先拿起右边筷子的哲学家称为右撇子。请说明在同时存在左、右撇子的情况下,任何的就座安排都不能产生死锁。

答:产生死锁,有以下四个必要条件:互斥、请求与保持、不可剥夺、环路。

此时哲学家进餐的问题,满足互斥、请求与保持和不可剥夺这三个条件。但是要满足环路条件,哲学家就需同时拿起左边或右边的筷子,即哲学家要么是左撇子,要么是右撇子。可是此时同时存在左、右撇子则不满足环路条件,任何就座安排都不产生死锁。

3.系统中有5个资源被4个进程所共享,如果每个进程最多需要2个这种资源,试问系统是否会产生死锁。

答:当资源数小于请求改种资源的进程数,就有可能产生死锁。现在由题可知每个进程最多需要2个资源,例如此时每个进程都先使用一个资源,则只剩下一个资源可供一个进程使用,这时一个进程申请资源,其他进程阻塞。这个进程运行完以后释放资源,此时唤醒其他阻塞进程运行,则不会造成进程阻塞而且还无法被唤醒。系统不产生死锁。

4.计算机系统有8台磁带机,由N个进程竞争使用,每个进程最多需要3台。问:当N为多少时,系统没有死锁的危险?

答:当N=1时,一个进程最多需要3台磁带机,此时不会产生死锁现象。当N=2时,两个进程申请6台,也足够使用,也不出现死锁现象。当N=3时,此时有进程不能完全得到3台,可是其他进程运行完以后释放磁带机,则此时阻塞的进程可以运行,也不会出现死锁的危险。当N=4时,可能出现每个进程都抢占到2台的情况,此时每个进程都不能运行下去,就出现了死锁。于是可以得出结论:当N<4时,系统不会出现死锁的危险。

5.假设系统有5个进程,它们的到达时间和服务时间如表4–8所示。新进程(没有运行过)与老进程(运行过的进程)的条件相同时,假定系统选新进程运行。

表4-8 进程情况

进程名 A B C D E 到达时间 0 2 4 6 8 服务时间 3 6 4 5 2 若按先来先服务(FCFS),时间片轮转法(时间片q=1),短进程优先(SPN)、最短剩余时间优先(SRT,时间片q=1)、响应比高者优先(HRRN)及多级反馈队列(MFQ,第一队列的时间片为1,第 i (i > 1) 个队列的时间片q=2(i-1)算法进行CPU调度,请给出各个进程的完成时间、周转时间、带权周转时间,及所有进程的平均周转时间和平均带权周转时间。

平均周转时间为

15

1nT=?Ti

ni?1其中Ti是每个作业的周转时间,n是作业的个数。

平均带权周转时间为

1nWi??Wi

ni?1其中Wi为带权周转时间,n是作业的个数。

以下是六种调度算法周转时间、平均周转时间、带权周转时间和平均带权周转时间的表格 进程名 到达时间 服务时间 完成时间 先来先 服务 周转时间 带权周转时间 完成时间 时间片 轮转法 q=1 周转时间 带权周转时间 完成时间 短进程 优先 周转时间 带权周转时间 完成时间 最短剩 余时间 优先 周转时间 带权周转时间 3 3 3 1 4 4 1.3 3 3 1 3 3 1 6 9 7 1.17 18 16 2.67 9 7 1.17 15 13 2.17 4 13 9 2.25 17 13 3.25 15 11 2.75 8 4 1 5 18 12 2.4 20 14 2.8 20 14 2.8 20 14 2.8 2 20 12 6 15 7 3.5 11 3 1.5 10 2 1 8.6 2.56 10.8 2.71 7.6 1.84 7.2 1.59 A 0 B 2 C 4 D 6 E 8 平均 16