北大操作系统习题答案完整版 下载本文

2)没有运行进程,没有就绪进程或两者都没有是否可能?各是什么情况? 3)运行进程是否一定是自由进程中优先数最高的? 答:1)一定没有

2) 没有运行进程,一定没有就绪进程;没有就绪进程可能有等待进程,也可能有运行 进程;两者都没有,可能有等待进程

3)不一定,可能出现等待进程中优先级更高

29.对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T,一次进程切换 的需要的时间是S,实际上就是开销,对于采用的时间片长度为Q的时间片轮转法,请给出 1)Q=无穷,2)Q>T , 3)S

解:1)当Q=无穷时, CPU的利用率=T/(T+S)*100%(当进程运行完后,就切换,也就相当 于时间 片=T)

2)当Q>T时, CPU的利用率=T/(T+S)*100%(当进程运行完后,就切换,也就相当于时间 片=T )

3)当S

5)当Q趋于0,CPU的利用率=T/T+nS=0 (n趋于无穷)

30,大多数时间片轮转调度程序使用一个固定大小的时间片,请给出选择小时间片的理由 ,然后再给出选择大时间片的理由

答:选择小时间片:I/O密集型,可以缩短响应时间,满足短的交互需求

选择大时间片:CPU密集型,可以防止过多的进程切换,提高CPU效率

31.有5个批处理作业A到E几乎同时到达一计算中心。他们估计运行时间分别为10,6,2,4和

8分钟,其优先数(由外部设定)分别为3,5,2,1,4其中5级为最高优先级,对于下列每 种调度算法,计算其平均周转时间,可忽略进程切换的开销。 1) 时间片轮转法 2) 优先级调度法

3) 先来先服务法(按照次序10,6,2,4,8运行) 4) 最短作业优先 对1),假设系统具有多道处理能力,每个作业均获得公平的CPU时间,对(2) 和(4)假设 任一时刻只有一个作业运行,直到结束,所有作业都是CPU密集型作业! 答:1) 和时间片的长短有关,比较繁琐!

2)运行顺序是(6,8,10,2,4) (6+14+24+26+30)/4=100/4=25 3)(10+16+18+22+30)/4=96/4=24

4) (2+(2+4)+(2+4+6)+(2+4+6+8)+( 2+4+6+8+10))/4=17.5

32:有5个待运行的作业,他们的估计运行时间分别是9,6,3,5,采用哪中次序运行各个 作业将得到最短的平均响应时间?答案依赖于X

答:由于5个作业同时到达,所以按最短作业优先调度会得到最短的响应时间: 9≤x 3 5 6 9 x 6≤x≤9 3 5 6 x 9 5≤x≤6 3 5 x 8 9 3≤x≤5 3 x 5 8 9 x≤3 x 3 5 8 9

33,在一间酒吧里有三个音乐爱好者队列,第一列音乐爱好者只有随身听,第二列只 有音乐

磁带,第三列只有电池,而要听音乐就必须有随身听,音乐磁带和电池这三中物品 。酒吧老板一次出售这三种物品中的任意两种,当一名音乐爱好者得到这三种物品 并听完乐曲后,酒吧老板才能再一次出售这三种物品中任意两种,于是第二名音乐 爱好者得到这三种物品。并开始听乐曲,全部买卖九这样进行下去。 使用P,V操作正确解决这一买卖。

解:买方有三个进程,卖方有1个进程

卖方,和买方的同步信号量 S1,S2 ,初值为0,1. 听音乐时的互斥信号量;mutex 卖方进程

P(S1) (没有音乐爱好者,等待) 卖物品 P(mutex) 放音乐 V(mutex) V(S2) 买方进程 P(S2) 买物品

V(S1) {老板可以卖东西}

34.巴拿马运河建在太平洋和大西洋之间,由于太平洋和大西洋水面高度不同,有巨大落 差,所以运河中建有T(T≥2)级船闸,并且只能允许单向通行,船闸依次编号为1,2,?,T ,由大西洋来的船需要经过船闸T,T-1.,,,2,1通过运河到达太平洋,由太平洋来的船需要 经由船闸1,2,?,T-1,T通过运河到达大西洋。

使用P,V操作正确解决大西洋和太平洋的船只通航问题。

答:答:Array: S1[T] of Semaphore {为每个船闸设置的信号量初值都为1}

Array: count1[T] of INTEGER {为每个船闸设置通往大西洋的船的计数值,初值都为 0}

Array: count2[T] of INTEGER {为每个船闸设置通往太平洋的船的计数值,初值都为 0}

对count设置互斥信号量 mutex 去大西洋的进程: int j

for(j=0;j

if(count1[j]==0) P(S[j]) count[j]++

过第j+1个船闸 P(mutex) count[j]--

if(count[j]==0) V(S[j])

V(mutex) }

去太平洋的进程: int k

for(k=T-1;k≥T,k++){ P(mutex)

if(count2[k]==0) P(S[k]) count[k]++

过第k+1个船闸 P(mutex) count[k]--

if(count[k]==0) V(S[k]) V(mutex) }

35.某银行有人民币储蓄业务,由n个柜员负责,每个顾客进入银行后,先取一个号,并且 等着叫号,当一个柜员人员空闲下来,就叫上一个号,使用P,V操作正确编写柜台人员和 顾客进程的程序!

解; 取号的互斥信号量 mutex,叫号的互斥信号量mutex1

柜台人员和顾客进程的同步信号量为 S1,S2, 初值分别为n,0 柜台人员进程:

P(S2) (无顾客则等待) P(mutex1) 叫号

V(mutex1) 服务 V(S1) 顾客进程 P(mutex) 取号 V(mutex) P(S1) 享受服务 V(S2)

36,设A,B,C三个进程共享一个存储资源F,A对F只读不写,B对F只写不读,C对F先读后写。

(当一个进程写F时,其他进程既不能读F,也不能写F,但多个进程同时读F是允许的)试 利用管程的方法或者P,V操作,写出A,B,C三个进程的框架,要求:(1)执行正确 (2)正常运行时不产生死锁;(3)使用F的并发度高 37,某系统如此定义P,V操作 P(S) S=S-1

若S<1本进程进入等待队列末尾,否则继续进行 V(S) S=S+1

若S≤0,释放等待队列中末尾的进程,否则继续运行。

现有四个进程P1,P2,P3,P4竞争使用某一需要互斥使用的资源(每个进程可能反复使用多 次),使用这样的P,V操作来正确的实现互斥。 解:

S:ARRAY[0,,,3] OF Semaphore{初值为s=i,i=0,1,2,3 } 访问进程

for i:=3 downto 1 do P(s)

临界区操作

for i:=1 To N-1 Do V(S)

38,请用进程通信的办法解决生产者,消费者问题 39,请用管程实现哲学家就餐问题 进程管理(笔记)

1).多道程序设计和并发

内存允许多个程序进入,操作系统能够同时执行这些程序 CPU在多个进程之间调度,切换

系统有时有进程,有线程 对CPU的管理:

每个实体都有一个环境,多个实体间存在一个切换 从顺序执行开始,到并发执行,会产生许多特征

顺序执行----并发执行(不可再现性)------与时间有关的错误

并发执行的结果,不可再现,由于每个程序执行的速度不同,会带来不一致性。 与时间有关的错误,即包括互斥(飞机订票系统,一张票卖给两个顾客,竞争条件), 这是由于并发执行,且资源共享引起的。 2).进程模型

进程:正在执行的程序,系统中同时会有许多程序在执行 进程有创建,有撤销 从以下几个方面考虑进程模型:

2.1 进程的组成,进程有动态,有静态,从动态的角度讲叫做进程映像。

一个系统中与进程有关的实体和空间

1.程序的地址 2.进程所需的数据 3.进程运行过程中所遗留的痕迹(栈) 栈是进程运行过程中临时性的信息存放的地方。 栈分为系统栈和用户栈

用户空间和系统空间时分开的。 用户地址空间包括:程序,数据和栈

PCB(进程控制块)是由系统来管理的,进程所需的信息都放在此数据结构中。 上下文环境,PCB,数据结构是进程存在的痕迹。

地址越界:用户只能在用户的地址空间活动,不能进入其他用户地址空间和系统空间