• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

计算机操作系统题库之进程与线程(十)

极客题库 Geekerstar 11个月前 (06-07) 564次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

以批处理方式下作业的管理为例,说明作业调度的主要任务、目标、计价作业调度算法优劣的性能指标、主要作业调度算法及作业调度的时机是什么?


作业调度的主要任务是:按照某种调试算法,从后备作业中挑选一批合理搭配的作业进入运行状态;

同时,为选中的作业分配内存和外部设备资源,为其建立相关的进程;当作业执行结束进入完成状态时,做好释放资源等善后工作。

作业调度的目标:1、响应时间快;2、周转时间或加权周转时间短;3、均衡的资源利用率;4、吞吐量大;5、系统反应时间短。

评价作业调度算法优劣的性能指标:1、作业平均周转时间;2、作业平均带权周转时间

主要作业调度算法有:1、先来先服务法;2、短作业优先算法;3、最高响应比优先算法;4、资源搭配算法;5、多队列循环算法。

作业调试时机:一般当输入井中有一道作业建立,或内存中的一道作业运行结束时,系统启动作业调试工作。

在信号量机制中,若P(S)操作是可中断的,则会有什么问题?

P(S)的操作如下:BeginS.Value:= S.Value-1; ①If S.Value<0 Then ②BeginInsert(*,S.L);Block(*) ③EndEnd. 若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,是不应该被阻塞的,现在却被阻塞了。

何谓临界区?下面给出的两个进程互斥的算法是安全的吗?为什么?

#define true; 
# define false;
int flag[2]; 
flag[1]=flag[2]=false; 
enter-crtsec(i) 
int i; 
{ 
While(flag[1-i]) 
flag[i]=true; 
} 
leave-crtsec(i) 
int i; 
{ 
flag[i]=false; 
} 
process I; 
… 
Enter-crtsec(i); 
In critical section; 
Leave-crtsec(i);

一次仅允许一个进程使用的资源称为临界资源,在进程中对临界资源访问的程序段称为临界区。

从概念上讲,系统中各进程在逻辑上是独立的,它们可以按各自的速度向前推进。

但由于它们共享某些临界资源,因而产生了临界区问题。

对于具有临界区问题的并发进程,它们之间必须互斥,以保证不会同时进入临界区。

这种算法不是安全的。

因为,在进入临界区的enter-crtsec()不是一个原语操作,如果两个进程同时执行完其循环(此前两个flag均为false),则这两个进程可同时进入临界区。

某车站售票厅,任何时刻最多可容纳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为某一时刻需要进入售票厅的最多人数。

在批处理系统、分时系统和实时系统中,各采用哪几个进程(作业)调度算法?

(1)批处理系统中的作业调度算法有:先来先服务算法(FCFS)、短作业优先算法(SJF)、优先级调度算法(HPF)和高响应比优先算法(RF)。

批处理系统的进程调度算法有:先进先出算法(FIFO)、短进程优先算法(SPF)、优先级调度算法(HPF)和高响应比优先算法(RF)。

(2)分时系统中只设有进程调度(不设作业调度),其进程调度算法只有轮转法(RR)一种。

(3)实时系统中只设有进程(不设作业调度),其进程调度算法调度有:轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统;后者用于时间要求严格的实时系统。

后者又可细分为:非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。

注意,一个纯粹的实时系统是针对特定应用领域设计的专用系统。

作业提交的数量不会超过系统规定的多道程序的道数,因而可全部进入内存。

若将实时系统与批处理系统结合的话,就可以让作业量超过多道程序道数,使优先级低的作业呆在外存的后备队列上。

假设系统中有5个进程,它们的到达时间和服务时间见下表1,忽略I/O以及其他开销时间,若按先来先服务(FCFS)、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度,请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间,完成表2。

表1 进程到达和需要服务时间
进程 到达时间 服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2

表2 进程的完成时间和周转时间

进程 A B C D E 平均

FCFS 完成时间 3 9 13 18 20

周转时间 3 7 9 12 12 8.6

带权周转时间 1.00 1.17 2.25 2.40 6.00 2.56

SPF(非抢占) 完成时间 3 9 15 20 11

周转时间 3 7 11 14 3 7.6

带权周转时间 1.00 1.17 1.75 2.80 1.50 1.84

SPF(抢占) 完成时间 3 15 8 20 10

周转时间 3 13 4 14 2 7.2

带权周转时间 1.00 2.16 1.00 2.80 1.00 1.59

试证明:如果系统作业几乎同时到达,则使系统平均作业周转时间最短的算法是短作业优先。

设有n个作业j1,j2,j3,…,jn,其运行时间分别为t1,t2,t3,…,tn。不妨假设t1<=t2<=t3<=...<=tn,则短作业优先的作业调度算法的平均周转时间为:T=(t1+(t1+t2)+(t1+t2+t3)+....(t1+t2+t3+...+tn))/n=(n*t1+(n-1)*t2+...+tn)/n考虑其他不同调度算法,设在此调度算法下的作业调度次序为ji1,ji2,...jin,其中(i1,i2,...,in)是(1,2,3,...,n)的一个排列,则类似上面可以得出:T1=((n*ti1+(n-1)*ti2+...+tin)/n)根据不等式结论:如果有a1<=a2<=...<=an 且b1<=b2<=...<=bn,则a1bn+a2bn-1+...+anb1<=a1bi1+a2bi2+...+anbn<=a1b1+a2b2+...+anbn其中(i1,i2,...,in)是(1,2,3,...,n)的一个排列,不难得出T<=T1。

有两个用户进程A和B,在运行过程中都要使用系统中的一台打印机输出计算结果。

(1)试说明A、B两进程之间存在什么样的制约关系?

(2)为保证这两个进程能正确地打印出各自的结果,请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。

A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源,必须一个进程使用完之后另一个进程才能使用。
mutex:用于互斥的信号量,因为只有一台打印机,所以初值为1
进程A 进程B
… …
P(mutex); P(mutex);
申请打印机; 申请打印机;
使用打印机; 使用打印机;
V(mutex); V(mutex);

设 input进程不断向缓冲区Q写入信息,output进程不断地将刚由input进程写入的信息读出。试问:

(1)这两个进程有何相互制约关系?
(2)试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。

这两个进程的相互制约关系为同步关系;
设两个信号量S1和S2。其中S1表示Q是否为空,初值为1,表示Q是空的;S2表示Q中是否有信息,初值为0,表示Q中无信息。
两进程的代码段如下:
input进程 output进程
…… ……
While 信息未处理完毕 While 信息未处理完毕
{ 加工一个信息; { P(S2);
P(S1); 从Q中读出一个信息;
将信息放入Q中; V(S1);}
V(S2);} ……

假定在单道批处理环境下有5个作业,各作业进入系统的时间和估计运行时间如下表所示:

作业 进入系统时间 估计运行时间/分钟
1 8:00 40
2 8:20 30
3 8:30 12
4 9:00 18
5 9:10 5
如果应用先来先服务和应用最短作业优先的作业调度算法,试将下面表格填写完整。

作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟

(1) 如果应用先来先服务的作业调度算法,试将下面表格填写完整。
作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟
1 8:00 40 8:00 8:40 40
2 8:20 30 8:40 9:10 50
3 8:30 12 9:10 9:22 52
4 9:00 18 9:22 9:40 40
5 9:10 5 9:40 9:45 35
作业平均周转时间T= 43.4 217
2)如果应用最短作业优先的作业调度算法,试将下面表格填写完整。
作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟
1 8:00 40 8:00 8:40 40
2 8:20 30 8:52 9:22 62
3 8:30 12 8:40 8:52 22
4 9:00 18 9:27 9:45 45
5 9:10 5 9:22 9:27 17
作业平均周转时间T= 37.2 186

两个并发执行的进程A和B的程序如下:


    进程A
      Repeat
         N=N+5;
     Until false;
    进程B
      Repeat
         打印N的值;
         N=0;
      Until false;

其中N为整数,初值为4。若进程A先执行了三个循环后,进程A和进程B又并发执行了一个循环,写出可能出现的打印值。正确的打印值应该是多少?请用P、V操作进行管理,使进程A和B并发执行时不会出现与时间有关的错误。

因为N初值为4,若进程A先执行了三个循环,此时N的值为19。当进程A和进程B并发执行时可能会有如下两种执行次序,即进程A先执行一次循环,然后再进程B执行一次循环,此时打印的是正确值24,执行后N中的值为0。但若进程B先执行一次循环,然后再进程A执行一次循环,则打印的值是19,执行后N中的值是5。这是错误的,即发生了与时间有关的错误。用P、V操作进行管理,使进程A和B并发时不会出现与时间有关的错误的程序如下:(S为互斥信号量,初值为1),

 进程A
       Repeat
         P(S);
         N=N+5;
         V(S);
       Until false;
    进程B
      Repeat
        P(S);
        打印N的值;
        N=0;
        V(S);
      Until false;

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:计算机操作系统题库之进程与线程(十)
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00