操作系统思考题答案.docx

操作系统思考题答案.docx

《操作系统思考题答案.docx》由会员分享，可在线阅读，更多相关《操作系统思考题答案.docx（16页珍藏版）》请在冰点文库上搜索。

操作系统思考题答案

【思考题】

1．如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？

解：

我们考虑在微机的操作系统中：

系统的调度管理进程至少是在运行状态。

当有N个用户进程启动后，那么我们可以说用户的进程最多有一个在运行状态，最少有0个？

有了这个条件，我们不难推出就绪进程和等待进程可能的数量。

b5E2RGbCAP

如果我们讨论的多CPU平台的使用的操作系统，就是另外一种情况了。

所以我想题目应该给出一个系统的运行环境。

2.有没有这样的状态转换，为什么？

等待—运行；就绪—等待

解：

进程状态转换：

在进程运行过程中，由于进程自身进展情况及外界环境的变化，

这三种基本状态可以依据一定的条件相互转换

就绪—运行调度程序选择一个新的进程运行

运行—就绪运行进程用完了时间片，运行进程被中断，因一高优先级进程处于就绪状态

运行—等待当一进程必须等待时

•OS尚未完成服务

•对一资源的访问尚不能进行

•初始化I/O且必须等待结果

•等待某一进程提供输入（IPC>

等待—就绪当所等待的事件发生时

观察下面答案就明确了――>

3.一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能

解：

一般情况下，当一个状态发生转换，系统调度会将当前进程置入相应状态队列，再从相应的队列中唤醒相关进程…p1EanqFDPw

4.举3个日常生活中类似进程的例子

医院看病的过程：

等待医院开门――挂号――看病――划价――付钱――医院关门

5．要不要对缓冲区<临界资源）进行互斥操作？

解：

对于是“只读”的临界资源，我们可以认为不需要互斥操作。

但，一定有一个对“只读”临界资源进行维护的“写”操作，那么必须要考虑缓冲区的互斥操作。

DXDiTa9E3d

6.用P.V操作解决下图之同步问题:

G

get

复制一个记录:

Cobegin

get。

copy。

put。

Coend

fstg

初始状态3,4,...,m22（1,2>

g,c,p4,5,...,m33（1,2,3>Ö

设信息长度为m

f[1..m]ofarray

Smutex,Sempty,Sfull:

=1,1,0。

//（f，s，t，g均为单缓冲区，不需要互斥量Smutex，Tmutex>RTCrpUDGiT

Tmutex,Tempty,Tfull:

=1,1,0

Intx,y=1,1。

//设有m个记录长度，一次get一个记录

Processget

{。

。

。

wait（Sempty>。

wait（f>。

wait（Smutex>。

//wait（s>。

和copy互斥

get过程，f[x]→s（x号记录>；

x++。

signal（Smutex>。

//signal（s>。

signal（f>。

signal（Sfull>。

。

。

。

}

processcopy

{…

wait（Sfull>。

wait（Tempty>。

wait（Smutex>。

//和get互斥

wait（Tmutex>。

//和put互斥

copy过程，s→t（y号记录>

y++。

signal

signal

signal（Tfull>。

signal（Sempty>。

…}

processput

{…

wait（Tfull>。

wait（g>。

wait（Tmutex>。

//和copy互斥

put过程t→g[y]

signal（Tmutex>。

signal（g>。

signal（Tempty>。

…}

解决下面的问题，首先你要掌握P

【作业】

1.推广例子中的消息缓冲问题。

消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次，若有m个发送进程呢？

5PCzVD7HxA

解：

：

）这是一个典型的题目，在我们设计网络上的“聊天室”时所必须要解决的问题。

为了便于理解，我们也可以把这个问题先类比成一个读者优先的“读者写者”问题，即：

先考虑只有一个消息缓冲区<单缓冲区）

1.当消息缓冲区空时，n个读者<接收进程）等待，一个写者<发送进程）允许写入

2．当消息缓冲区满时，n个读者进行阅读<接收），此时和写者进程互斥，直到所有读者阅读完毕。

释放读写互斥量和缓冲区。

『注意』这里我们不能简单的按照例子中的那样，将readcount简单的计数。

可以用下面的方法：

为了保证n个读者<接收进程）都必须读一次，我们可以用nbit二进制位来作为n个读者<接收进程）是否接收的标志<0－未读，1－已读），直到所有的位翻转成1后，释放读写互斥量

jLBHrnAILg

在具体写代码时，我们可以使用一个数组readcount[n]来表示nbit

arrayreadcount[1..n]={0,…,0}//n个接收进程已读标志

Wmutex=1。

//允许发送进程写数据到临界缓冲区

Rmutex=1。

//允许接收进程修改已读标志

读者i（接收进程i>：

while（true>{

P（Rmutex>。

For（intj:

=1。

j<=n。

j++>

{if（readcount[j]==1>break。

}

if（j>n>P（RWmutex>。

//nbit全0，第一个读者<接收进程）启动，禁止接收xHAQX74J0X

readcount[i]=1。

V（Rmutex>。

读<接收）

P（Rmutex>。

For（j:

=1。

j<=n。

j++>

{if（readcount[j]==0>break。

}

if（j>n>V（RWmutex>。

//nbit全1,所有读者<接收进程）都读过了，

//释放写互斥信号量

V（Rmutex>。

}。

写者（发送进程>：

while（true>{

P（RWmutex>。

写

V（RWmutex>。

}。

―――――――――――――――

现在我们再来考虑若有m个发送进程呢？

如果还使用单缓冲区，那么问题变得简单了，上面的程序可以不加修改的应用在这种情况下。

―――――――――――――――

再进一步，我们有m个发送进程，缓冲区为k个，n个接收进程，问题变的复杂些了。

如果我们还是沿用上面“读者－写者”的思路，在发送进程写数据时不允许接收进程读<读时也不允许写），显然执行的效率大大下降。

LDAYtRyKfE

所以我们要换一个思路，你可以先读懂我后面『附』中的“经典的生产者─消费者问题”的

n个缓冲区、m个生产者和k个消费者的实现方法，那么这个问题也就明了许多。

我们只要把这个算法的消费者Q进程改进成“每个缓冲区buffer[j]”被所有n个接收进程都接收后再j=（j+1>%n读下一个缓冲即可。

shouZzz6ZB2Ltk

2.第二类读者写者问题：

读者优先算法：

设置两个互斥信号量：

rwmutex用于写者与其他读者/写者互斥的访问共享数据

rmutex用于读者互斥的访问读者计数器readcount

varrwmutex,rmutex：

semaphore:

=1,1；

intreadcount=0。

cobegin

readeribegin//i=1,2,….

P（rmutex>。

Readcount++。

If（readcount==1>P（rwmutex>。

V（rmutex>。

读数据；

P（rmutex>。

Readcount--。

If（readcount==0>V（rwmutex>。

V（rmutex>。

End

Writerjbegin//j=1,2,….

P（rwmutex>。

写更新；

V（rwmutex>。

End

Coend

写者优先

条件：

1）多个读者可以同时进行读

2）写者必须互斥<只允许一个写者写，也不能读者写者同时进行）

3）写者优先于读者<一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）

解1：

如果读者数是固定的，我们可采用下面的算法：

rwmutex：

用于写者与其他读者/写者互斥的访问共享数据

rmutex：

该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作

varrwmutex,rmutex：

semaphore:

=1,10；

cobegin

readeribegin//i=1,2,….

P（rwmutex>。

//读者、写者互斥

P（rmutex>。

V（rwmutex>。

//释放读写互斥信号量，允许其它读、写进程访问资源

读数据；

V（rmutex>。

End

Writerjbegin//j=1,2,….

P（rwmutex>。

For（i=1。

i<=10。

i++>P（rmutex>。

//禁止新读者，并等待已进入的读者退出

写更新；

For（i=1。

i<=10。

i++>V（rmutex>。

//恢复允许rmutex值为10

V（rwmutex>。

End

Coend

解2：

如果读者数不固定，采用下面的算法：

设置三个互斥信号量：

rwmutex用于写者与其他读者/写者互斥的访问共享数据

rmutex用于读者互斥的访问读者计数器readcount

nrmutex用于写者等待已进入读者退出，所有读者退出前互斥写操作

varrwmutex,rmutex，nrmutex：

semaphore:

=1，1，1；

intreadcount=0。

cobegin

readeribegin//i=1,2,….

P（rwmutex>。

P（rmutex>。

Readcount++。

If（readcount==1>P（nrmutex>。

//有读者进入，互斥写操作

V（rmutex>。

V（rwmutex>。

//及时释放读写互斥信号量，允许其它读、写进程申请资源

读数据；

P（rmutex>。

Readcount--。

If（readcount==0>V（nrmutex>。

//所有读者退出，允许写更新

V（rmutex>。

End

Writerjbegin//j=1,2,….

P（rwmutex>。

//互斥后续其它读者、写者

P（nrmutex>。

//如有读者正在读，等待所有读者读完

写更新；

V（nrmutex>。

//允许后续新的第一个读者进入后互斥写操作

V（rwmutex>。

//允许后续新读者及其它写者

End

Coend

［附］

经典的生产者─消费者问题

同步问题：

P进程不能往“满”的缓冲区中放产品，设置信号量为S1

Q进程不能从“空”的缓冲区中取产品，设置信号量S2

P：

Q：

while（true>{while（true>{

生产一个产品。

P（s2>。

P（s1>。

从缓冲区取产品。

送产品到缓冲区。

V（s1>。

V（s2>。

消费产品。

}。

}。

S1初值为1，S2初值为0

多个缓冲区的生产者和消费者：

dvzfvkwMI1

n个缓冲区、m个生产者和k个消费者：

rqyn14ZNXI

SPOOLing技术原理

答：

SPOOLing技术就是用于将一台独占设备改造成共享设备的一种行之有效的技术。

详见书P219

管道

<见第3章第10题作业）

Windows2000体系结构

1）系统采用分层结构设计

2）保护模式—HAL

3）户用模式—子系统集

a>仿真不同操作系统环境的子系统

b>提供安全功能的保护子系统

用信号量机制实现写者优先的读者－写者算法。

解：

<见思考题2.第二类读者写者问题）

假定某系统有进程{P0,P1,P2,P3},资源{A,B,C}，每类资源的数量分别为10,5,7；若在T0时刻每个进程已分配的资源分别为（2,0,0>、（2,1,1>、（0,0,2>、（3,1,1>；试用银行家算法判断T0时刻系统是否安全？

SixE2yXPq5

解：

系统还有可用资源为：

<3,3,3）

分情况判定？

在一个请求分页系统中，假定为某进程分配3个物理块且该进程的页面引用次序为：

0,4,1,4,1,5,1,6,2,6,3,6,2,6,4,5；试计算页面置换算法分别为最佳、FIFO、LRU时的缺页次数。

6ewMyirQFL

解：

最佳算法是一种理论上的算法：

被淘汰的是永不使用或者是最长时间不再被访问的页面

最佳OPT0414151626362645kavU42VRUs

页10011111666666645y6v3ALoS89

页2400055522222222M2ub6vSTnP

页3444444443333330YujCfmUCw

xxxxxxxxx

共缺页中断9次

先进先出页面置换算法：

淘汰最先进入内存的页面

FIFO0414151626362645eUts8ZQVRd

页10411155622333345sQsAEJkW5T

页2044411566222234GMsIasNXkA

页300044155666623TIrRGchYzg

xxxxxxxxx

共缺页中断9次

最近最久未使用置换算法：

每个页面有一个记录自上次被访问以来所经历的时间的字段

LRU04141516263626457EqZcWLZNX

栈顶0014151626362645lzq7IGf02E

401415162636264

栈底40044511223326zvpgeqJ1hk

xxxxxxxxx

共缺页中断9次

假定某计算机系统有3，000个空闲磁盘块并用成组链接法对之进行管理<每组200个盘块），试画出相应的链接图，并说明空闲盘块的分配与回收过程。

NrpoJac3v1

解：

（见第9章第11题作业>

申明：

所有资料为本人收集整理，仅限个人学习使用，勿做商业用途。