Chinaunix首页 | 论坛 | 博客
  • 博客访问: 452983
  • 博文数量: 73
  • 博客积分: 1170
  • 博客等级: 少尉
  • 技术积分: 720
  • 用 户 组: 普通用户
  • 注册时间: 2012-02-20 15:48
文章分类

全部博文(73)

文章存档

2013年(9)

2012年(64)

我的朋友

分类: LINUX

2012-08-29 16:01:08

3章 处理机调度与死锁习题

三、名词解释

高级调度: 又称作业调度,用于决定把外存上处于后备队列中的哪些作业调入内存,并为之创建进程,排在就绪对列上。

低级调度: 又称进程调度,用于选择就绪队列上哪个进程可以获得处理机执行。

中级调度: 又称对换调度,用于将那些暂时不能运行的进程由内存调至外存,排在挂起对列

中,待这些进程重又具备运行条件,且内存又有空闲,将其重新由外存调入内存,排在就绪

队列中。

死锁: 指在多道程序系统中,多个进程在运行过程中因争夺资源造成的一种僵局。

死锁避免: 不需事先采用各种限制措施去破坏产生死锁的必要条件,而是在资源的动态分配过程中,用某种方式去防止系统进入不安全状态,从而避免发生死锁。

进程同步: 程间共同完成一项任务时直接发生相互作用的关系,也就是说,这些具有伙伴关系的进程在执行时间次序上必须遵循确定的规律。

进程互斥: 逻辑上本来完全独立的若干进程,由于竞争同一个资源而产生的相互制约关系。

四、问答题

1、设在单道批处理系统中有四道作业,它们提交的时刻及运行时间如下:

作业号

提交时刻(h

运行时间(h

1

8.0

1.0

2

8.5

0.5

3

9.0

0.2

4

9.1

0.1

 请分别给出在算法FCFSSJFHRN中这组作业的调度顺序、平周转时间和平均带权周转时间。

 解答】

FCFS算法调度顺序:1234,作业运行情况如下表

作业号

开始时间

完成时间

周转时间

带权周转时间

1

8.0

9.0

1.0

1.0

2

9.0

9.5

1.0

2.0

3

9.5

9.7

0.7

3.5

4

9.7

9.8

0.7

7.0

平均周转时间T=(1.0+1.0+0.7+0.7)/4=0.85

平均带权周转时间W=(1.0+2.0+3.5+7.0)/4=3.375

SJF算法调度顺序:1342,作业运行情况如下表

作业号

开始时间

完成时间

周转时间

带权周转时间

1

8.0

9.0

1.0

1.0

2

9.3

9.8

1.3

2.6

3

9.0

9.2

0.2

1.0

4

9.2

9.3

0.2

2.0

平均周转时间T=(1.0+1.3+0.2+0.2)/4=0.675

平均带权周转时间W=(1.0+2.6+1.0+2.0)/4=1.65

 HRN算法调度顺序:1243,作业运行情况如下表

作业号

开始时间

完成时间

周转时间

带权周转时间

1

8.0

9.0

1.0

1.0

2

9.0

9.5

1.0

2.0

3

9.6

9.8

0.8

4.0

4

9.5

9.6

0.5

5.0

平均周转时间T=(1.0+1.0+0.8+0.5)/4=0.825

平均带权周转时间W=(1.0+2.0+4.0+5.0)/4=3.0

2、有一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法,有如下表所示的作业序列,数值越小优先级越高。

作业名

到达时间

运行时间

优先数

A

10:00

40min

5

B

10:20

30min

3

C

10:30

50min

4

D

10:50

20min

6

① 列出所有作业进入内存的时间和结束时间。

     计算平均周转时间。

【解答】 每个作业的运行将经历两级调度:作业调度和进程调度。只有当作业装入内存后,方能参与进程调度。每次只能有两道作业进入系统内存。

1)作业进入内存时间和结束时间如下表

作业号

进入内存时间

结束时间

A

10:00

11:10

B

10:20

10:50

C

11:10

12:00

D

10:50

12:20

2)各作业执行时的周转时间为:

作业A70分钟 作业    B30分钟   作业C90分钟     作业D90分钟  

作业的平均周转时间T=(70+30+90+90)/4=70分钟。

3、假定某计算机系统有R1R2两类可再使用资源,其中R12个单位,R21个单位。它们被进程P1P2所共享,且已知两个进程均以如下顺序使用两类资源。-->申请R1-->申请R2-->申请R1-->释放R1-->释放R2-->释放R1-->

试求出系统运行过程中可能到达的死锁点,并画出死锁点的资源分配图。

答:当两个进程都执行完第1步(都占有了资源R1)时,系统进入不安全状态。这时,无论哪个进程执行完第2步,系统都将进入死锁状态。可能到达的死锁点是:进程P1占有一个单位的R1和一个单位的R2,而进程P2占有一个单位的R1。或者,正好相反。此时系统已无空闲资源,而P1P2两个进程都不释放自己的资源并申请对方的资源,从而造成死锁。
死锁点的资源分配图(进程资源图)如图所示。

4某系统有同类互斥资源m个,供n个进程共享使用。如果每个进程最多申请x个资源(1xm),试证明:当n(x-1)+1m时,系统不会发生死锁。

证明:因为每个进程最多申请x个资源,所以最坏情况是每个进程都得到了(x-1)个资源,并且现在均需申请最后一个资源。此时,系统剩余资源数为m-n(x-1),于是只要系统中至少还有一个资源可供使用,就可以使这n个进程中某个进程得到其所需要的全部资源,并能够继续执行到完成,归还资源可供其他进程使用。因而不会发生死锁。即只要 m-n(x-1)≥1时,系统就一定不会发生死锁。亦即当n(x-1)+1≤m时,系统不会发生死锁。

5n个进程共享某种资源R(该资源共有m个可分配单位),每个进程一次一个地申请或释放资源单位。假设每个进程对该资源的最大需求量均小于m,且各进程最大需求量之和小于m+n,试证明该系统中不可能发生死锁。

解:设maxi)表示第i个进程的最大资源需求量,needi)表示第i个进程还需要的资源量,alloci)表示第i个进程已分配的资源量。由题中所给条件可知:

max1)+…+maxn=need1)+…+needn))+(alloc1+…+allocn))n如果在这个系统中发生了死锁,那么一方面m个资源应该全部分配出去,即

alloc1)+…+allocn= m

另一方面所有进程将陷入无限等待状态。

由上述两式可得:need1)+…+needn

上式表示死锁发生后,n个进程还需要的资源量之和小于n,这意味着此刻至少存在一个进程ineedi=0,即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源,那么它就能执行完成并释放它占有的资源,这与前面的假设矛盾,从而证明在这个系统中不可能发生死锁。

6、下表给出系统某时刻的资源分配情况。

   资源

进程

Allocation

Need

Available

R1

R2

R3

R1

R2

R3

R1

R2

R3

A

3

1

1

1

0

0

1

2

0

B

0

0

0

0

1

2

C

1

1

0

3

0

0

D

1

0

1

0

1

0

E

0

0

0

2

1

0

试问:(1)该状态是否安全?

2)若进程B提出请求RequestB010),系统能否将资源分配给它?

   资源

进程

Allocation

Need

work

Work+ Allocation

Finish

R1

R2

R3

R1

R2

R3

R1

R2

R3

R1

R2

R3

A

3

1

1

1

0

0

1

2

0

4

3

1

TRUE

C

1

1

0

3

0

0

4

3

1

5

4

1

TRUE

D

1

0

1

0

1

0

5

4

1

6

4

2

TRUE

E

0

0

0

2

1

0

6

4

2

6

4

2

TRUE

B

0

0

0

0

1

2

6

4

2

6

4

2

TRUE

(1)能找到安全序列存在,其中之一为:A->C->D->E->B,所以该系统处于安全状态。

2)①:RequestB010NeedB0,1,2

     ②:RequestB010Available1,2,0

     ③:假设可将资源分配给B,并修改有关数据:

   资源

进程

Allocation

Need

Available

R1

R2

R3

R1

R2

R3

R1

R2

R3

A

3

1

1

1

0

0

1

1

0

B

0

1

0

0

0

2

C

1

1

0

3

0

0

D

1

0

1

0

1

0

E

0

0

0

2

1

0

进入安全检查,发现任有安全序列存在,其中之一为:D->A->C->E->B。所以,当进程B提出请求RequestB010),系统能将资源分配给它。

7什么是死锁?产生死锁的原因和必要条件?

死锁是指在多道程序系统中,多个进程在运行过程中因争夺资源造成的一种僵局。

产生原因:1)竞争资源 2)进程推进顺序不当。

产生的必要条件:

1、互斥条件。进程对所分配的资源进行排它性控制,即在一段时间内某资源仅为一进程所占有。

2、请求和保持条件。当进程因请求资源而阻塞时,对已获得的资源保持不放。

3、不剥夺条件。进程已获得的资源,在未使用完前,不能被剥夺,只能在使用完时由自己释放。

4、环路等待条件。在发生死锁时,必然存在一个进程-资源的环形链,即进程集合{P1P2,。。。,PN}中的P1等待一个P2占用的资源,P2正在等待一个P3占用的资源,。。。,Pn正在等待已被P1所占用的资源。

85个待运行的作业为ABCDE,各自估计运行时间为9635x。试问采用哪种运行次序使得平均响应时间为最短?

响应时间=等待时间+要求服务时间       相等          周转时间=结束时间-到达时间

答:由于短作业优先调度算法会使一组作业的平均周转时间最短,

所以:当0x3时,应该采用的运行顺序为:E, C, D, B, A

3≤x≤5时,应该采用的运行顺序为:CEDBA

5x6时,应该采用的运行顺序为:CDEBA

6≤x≤9时,应该采用的运行顺序为:CDBEA

9x时,应该采用的运行顺序为:CDBAE

9在操作系统中引入并发可提高系统效率。若有两个程序ABA程序执行时所做的工作依次需要用CPU10sDEV15sCPU5sDEV210sCPU10sB程序执行时所做的工作依次需要用DEV110sCPU10sDEV25sCPU5sDEV210s。请计算在顺序环境和并发环境下执行AB两个程序,CPU的利用率分别是多少?

答:①在顺序环境下执行AB两个程序,CPU的利用率是50%

        顺序,一共用时80sCPU用时40 40/80=50%

②在并发环境下执行AB两个程序,CPU的利用率是89%假设A程序先执行)

并发A10s(CPU)5s(DEV1)5s (Wait)5s(CPU)10s(DEV2)10s(CPU)

B10s(DEV)10s(CPU)5s(DEV2)5s(CPU)5s (Wait)10s(DEV2)
用时45sCPU40s40/45=8/9=89%

阅读(2324) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~