当前位置：文档之家 › 操作系统经典习题

操作系统经典习题

  • 格式：doc
  • 大小：1.54 MB
  • 文档页数：9

习题： 1. 进程同步，信号量机制实现 设有6个程序s1,…, s6，它们在并发系统中执行时如图所示的制约关系，试用wait和signal原语来实现它们之间的同步。（10分）

Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0;

begin

parbegin begin S1; signal(a); signal(b);signal(c); end; begin wait(a); S2; signal(d); end; begin wait(b); S3; signal(f); end; begin wait(c); S4; signal(g); end; begin wait(d); S5; signal(e); end; begin wait(e); wait(f); wait(g); S6; end; parend end

2. 进程同步，信号量机制实现。详见上课讲的例题

3. 有如下进程，后一个依次比前一个晚一个时间单位到达， 作业 运行时间 优先级 A 3 3 B 1 1 C 2 5

S1 S2 S4 S3 S5

S6 D 1 4 E 5 6 （1）画出下列调度算法下的调度时间图：FCFS、抢占式\非抢占式SPF、抢占式\非抢占式HPF、HRRN和RR（q=1,q=2） （2）对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？ （3）对于上述每种算法，各个作业的带权周转时间和平均带权周转时间各是多少？ 相应比=【(等待时间=现在时刻减去到达时间)+服务时间】/服务时间

算法 作业 A B C D E 平均 到达时间 0 1 2 3 4 服务时间 3 1 2 1 5

FCFS 完成时间 3 4 6 7 12 周转时间 3 3 4 4 8 4.4 带权周转时间 1 3 2 4 1.6 2.32

SPF(非) 完成时间 3 4 7 5 12 周转时间 3 3 5 2 8 4.2 带权周转时间 1 3 2.5 2 1.6 2.02

SPF(抢) 完成时间 3 11 5 12 10 周转时间 3 10 3 9 6 6.2 带权周转时间 1 10 1.5 9 1.2 4.54 HPF（非) 完成时间 3 11 5 12 10 周转时间 3 10 3 9 6 6.2 带权周转时间 1 10 1.5 9 1.2 4.54

HPF（抢) 完成时间 11 12 4 10 9 周转时间 11 11 2 7 5 7.2 带权周转时间 11/3 11 1 7 1 4.72

HRRN 完成时间 3 4 6 7 12 周转时间 3 3 4 4 8 4.4 带权周转时间 1 3 2 4 1.6 2.32

RR（r=1） 完成时间 7 2 8 5 12 周转时间 7 1 6 2 8 4.8 带权周转时间 7/3 1 3 2 1.6 1.92 4. 作出页式存储管理系统中地址变换机构图。已知某作业页表如下： 0 2 1 5 2 9 3 8 试借助地址变换机构图求出逻辑地址对应的物理地址（1页为1024字节） (1) 2968 （2）4599 （3）0FCCH 解：分析逻辑地址除以页面大小=商是页号：余数是页内地址偏移 根据页号查找页表中的页号判断是（缺页中断，越界中断...） 物理地址=块号*块大小+地址偏移 其中十六进制的直接转换为四位二进制计算 1.2968/1024=2...920 物理地址：9*1024+920=10136 2.4599/1024=4...503 越界中断 3.0FCCH二进制为：111111001100/2^10=11...111001100 物理地址：8*1024+972=9164 5. 有一虚拟存储系统，某作业运行中使用的操作数所在的页号依次为：4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 在内存中为该作业进程开辟3个物理块。分别采用FIFO、LRU页面淘汰算法，图示该作业运行的置换情况，并计算相应的缺页率？ 1.最佳置换算法是置换以后永不使用的页面即“向后看”

2.FIFO是淘汰最先进入的页面 缺页率：(7/20)*100%=35% LRU算法是淘汰选择最近久未使用的页面就是“向前看” 4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 4 4 4 1 1 1 5 2 2 2 2 2 2 4 4 4 3 3 3 4 4 4 4 5 5 4 4 3 3 3 5 2 2 2 3 3 3 3 1 1 5 5 5 1 1 缺页率：(4/20)*100%=20%

6. 假设磁盘有200个磁道（编号为0～199）的移动头磁盘，在完成

4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 4 4 4 1 1 1 5 5 5 4 4 4 1 3 3 3 4 4 4 2 2 2 5 5 5 2 2 2 3 3 3 1 1 1 3 3 了磁道125处的请求后，当前正在磁道号为143的磁道处为一个请求服务。若请求队列以FIFO次序存放，即86，147，91，177，94，150，102，175，130。对下列每一中磁盘调度算法，若要满足这些要求，则总的磁头移动次数为多少 (后两种要求，读写头朝着磁道号增大的方向移动) ？ （1）FCFS (2)SSTF (3)SCAN (4)CSCAN 首先根据题意可知：磁头正由低磁道号向高磁道号方向移动。

fcfs: 顺序是：143--86--147--91--177--94--150--102--175--130 (143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565

sstf:顺序是：143--147--150--130--102--94--91--86--175--177 (147-143)+(150-147)+(150-130)+(130-102)+(102-94)+(94-91)+(91-86)+(175-86)+(177-175)=162

scan:顺序是：先移动到最大柱面号(199)再移动到最小柱面号(0)再移动到130 (199-143)+(199-0)+(130-0)=385

例:假定某磁盘共有200个柱面，编号为0-199，如果在为访问143号柱面的请求者服务后，当前正在为访问125号柱面的请求服务，同时有若干请求者在等待服务，它们每次要访问的柱面号为 86，147，91，177，94，150，102，175，130 1、先来先服务算法（FCFS）First Come First Service 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 先来先服务 （125）86.147.91.177.94.150.102.175.130 2、最短寻道时间优先算法（SSTF） Shortest Seek Time First 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。 最短寻道时间优先（125）130.147.150.175.177.102.94.91.86

3、扫描算法（SCAN）电梯调度 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。 电梯调度（125）102.94.91.86.130.147.150.175.177

4、循环扫描算法（CSCAN） 循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。 循环扫描 （125）130.147.150.175.177.86.91.94.102

7. 说明文件物理结构中显式链接的原理，并计算一个200M的硬盘（盘

合集下载

操作系统第六章练习题

操作系统第六章练习题

操作系统第六章练习题一、选择题1. 在操作系统中，下列关于进程状态的描述，错误的是（）。

A. 运行态是指进程正在占用CPUB. 阻塞态是指进程因等待某事件而暂时停止运行C. 就绪态是指进程已经具备运行条件，等待CPU调度D. 空闲态是指进程已经执行完毕，等待被系统回收2. 在操作系统中，下列关于进程调度算法的描述，正确的是（）。

A. 先来先服务（FCFS）调度算法可能导致饥饿现象B. 短作业优先（SJF）调度算法是非抢占式的C. 优先级调度算法中，优先级高的进程一定能立即获得CPUD. 时间片轮转调度算法适用于分时系统3. 在操作系统中，下列关于进程同步与互斥的描述，错误的是（）。

A. 临界区是指进程中访问共享资源的代码段B. 信号量是一种用于实现进程同步与互斥的机制C. Peterson算法可以保证两个进程互斥进入临界区D. 生产者消费者问题可以通过信号量机制解决二、填空题1. 在操作系统中，进程的五大状态包括：____、____、____、____和____。

2. 在进程同步与互斥中，信号量的值表示了____资源的使用情况。

3. 在操作系统中，死锁产生的四个必要条件是：____、____、____和____。

三、简答题1. 请简述进程与线程的区别。

2. 请说明进程调度的主要目标。

3. 请阐述银行家算法的基本思想及其应用场景。

四、编程题1. 编写一个程序，实现进程的创建、撤销和切换。

2. 编写一个程序，使用信号量机制解决生产者消费者问题。

3. 编写一个程序，模拟进程的优先级调度算法。

五、案例分析题进程最大需求量已分配资源量P1 R1=3, R2=2 R1=1, R2=0P2 R2=2, R3=2 R2=1, R3=1P3 R3=2, R4=2 R3=1, R4=0P4 R1=4, R4=3 R1=2, R4=2（1）系统当前可用资源为：R1=1, R2=1, R3=1, R4=1（2）系统当前可用资源为：R1=0, R2=1, R3=1, R4=12. 假设有一个系统采用时间片轮转调度算法，时间片长度为50ms。

操作系统-进程同步-信号量练习题

操作系统-进程同步-信号量练习题

1【单选题】用P、V操作管理临界区时,互斥信号量的初值应定义为( A)。

•A，1•B，0•C，-1•D，任意值2【单选题】在操作系统中,对信号量S的P原语操作定义中,使进程进入相应等待队列等待的条件是( )。

•A，S>0•B，S = 0•C，S<0•D，S<>0我的答案：C3【单选题】信号量S的初值为8,在S上执行了10次wait 操作,6次signal操作后,S的值为(D )。

•A，10•B，8•C，6•D，4P操作每执行一次,信号量减1；V操作每执行一次,信号量加1.所以答案为8-10+6 = 44【单选题】用V操作唤醒一个等待进程时,被唤醒进程的状态应变成( B)状态。

•A，执行•B，就绪•C，阻塞•D，挂起被唤醒的进程由等待状态变为就绪状态。

5【单选题】利用Wait和signal操作可以( )。

•A，实现进程互斥和同步•B，检测死锁•C，解除死锁•D，防止死锁我的答案：A6【单选题】两个并发进程,设互斥信号量mutex(初值为1),若信号量=0;则(B )•A，表示没有进程进入临界区•B，表示有一个进程进入临界区•C，表示有一个进程进入临界区,另一个进程等待进入•D，表示两个进程进入临界区临界区不允许两个进程同时进入，D选项明显错误。

mutex初值为1，表示允许一个进程进入临界区，当有一个进程进入临界区且没有进程等待进入时，mutex值减1，变为0。

7【单选题】V操作是对信号量执行加1操作,意味着释放一个单位资源,加1后如果信号量的值等于零,则从等待队列中唤醒一个进程,现进程变为等待状态,否则现进程继续进行。

•A，对•B，错我的答案：B8【单选题】有3个进程,两台打印机,用wait和sigual操作来实现互斥访问打印机,则信号量S的取值范围是( )•A，2,1,0,-1•B，3,2,1,0•C，2,1,0,-1,-2•D，1,0,-1,-2我的答案：如果n个进程共享两个打印机，信号量取值范围：-(n-2)~2;9【单选题】设与某资源相关的资源信号量K,初值为3,当前值为1,则可用资源个数为( ),等待资源的进程数为( )。

操作系统习题及答案

操作系统习题及答案

CH4 应用题参考答案1 在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是：1 、2 、3 、4 、2 、1 、5 、6 、2 、1 、2 、3 、7 、6 、3 、2 、1 、2 、3 、6 。

分别用FIFO 、OPT 和LRU 算法，对分配给程序3 个页框、4 个页框、5 个页框和6 个页框的情况下，分别求出缺页中断次数和缺页中断率。

答：只要把表中缺页中断次数除以20，便得到缺页中断率。

2 在一个请求分页虚拟存储管理系统中，一个作业共有5 页，执行时其访问页面次序为：( 1 ) 1 、4 、3 、1 、2 、5 、1 、4 、2 、1 、4 、5( 2 ) 3 、2 、1 、4 、4 、5 、5 、3 、4、3、2、1、5若分配给该作业三个页框，分别采用FIFO和LRU 面替换算法，求出各自的缺页中断次数和缺页中断率。

答：( 1 ）采用FIFO 为9 次，9 / 12 = 75 ％。

采用LRU 为8 次，8 / 12 = 67 ％。

( 2 ）采用FIFO 和LRU 均为9 次，9 / 13 = 69 ％。

3 一个页式存储管理系统使用FIFO 、OPT 和LRU 页面替换算法，如果一个作业的页面走向为：( l ) 2 、3 、2 、l 、5 、2 、4 、5 、3 、2 、5 、2 。

( 2 ) 4 、3 、2 、l 、4 、3 、5 、4 、3 、2 、l 、5 。

( 3 ) 1 、2 、3 、4 、1 、2 、5 、l 、2 、3 、4 、5 。

当分配给该作业的物理块数分别为3 和4 时，试计算访问过程中发生的缺页中断次数和缺页中断率。

答：( l ）作业的物理块数为3 块，使用FIFO 为9 次，9 / 12 = 75 ％。

使用LRU 为7 次，7 / 12 = 58 ％。

使用OPT 为6 次，6 / 12 = = 50 ％。

作业的物理块数为4 块，使用FIFO 为6 次，6 / 12 = 50 ％。

操作系统练习题2

操作系统练习题2

操作系统练习题2一、选择题1.操作系统是计算机系统的核心软件。

按功能特征的不同，可把操作系统分为[1]_________________、[2]___________________、[3]_____________________、网络操作系统和分布式操作系统几种基本类型。

其中[1]的主要目的是提高系统的吞吐量和效率，而[2]是一旦有处理请求和要求处理的数据时，就立即应该处理该数据并将结果及时送会，例如[4]________________________等。

供选择的答案：[1][2][3] A、单用户系统B、批处理系统C、分时系统D、微机操作系统E、实时系统[4] A、计算机激光照排系统B、办公自动化系统C、计算机辅助设计系统D、航空售票系统2.操作系统是用户和计算机之间的接口，用户通过________________________、________________________与操作系统取得联系。

A、输入/输出设备B、命令接口C、中断服务程序D、系统调用3.常用的作业调度算法有____________________、____________________、____________________和____________________。

A、先来先服务法B、先进先出法C、最短作业优先法D、优先数法E、响应比高者优先法F、最近最少使用淘汰法4.文件的存储方法依赖于____________________和____________________。

A、文件的物理结构B、存放文件的存储设备的特性C、文件类型D、文件的逻辑结构5.设备管理的主要程序之一是设备分配程序，当进程请求在主存和外设之间传送信息时，设备分配程序分配设备的过程通常是____________________。

A、先分配设备，再分配控制器，最后分配通道B、先分配控制器，再分配设备，最后分配控制器C、先分配通道，再分配设备，最后分配控制器D、先分配通道，再分配控制器，最后分配设备6.进程执行时的间断性，决定了进程可能具有多种状态。