操作系统习题课

操作系统习题课1.何谓操作系统？配置操作系统的主要目的是什么？答：操作系统是管理系统资源、控制程序执行，改善人机界面，提供各种服务，合理组织计算机工作流程和为用户使用计算机提供良好运行环境的一种系统软件。配置操作系统的主要目标可归结为：Q方便用户使用：OS通过提供用户与计算机之间的友善接口来方便用户使用。Q扩大机器功能：OS通过扩充改造硬件设施和提供新的服务来扩大机器功能。Q管理系统资源：OS有效管理好系统中所有硬件软件资源，使之得到充分利用。Q提高系统效率：OS合理组织好计算机的工作流程，以改进系统性能和提高系统效率。Q构筑开放环境：OS遵循有关国际标准来设计和构造，以构筑出一个开放环境。其含义主要是指：遵循有关国际标准(如开放的通信标准、开放的用户接口标准、开放的线程库标准等)；支持体系结构的可伸缩性和可扩展性；支持应用程序在不同平台上的可移植性和可互操作性。2.操作系统的主要特性有哪些？答：0并发性。并发性(concurrence)是指两个或两个以上的事件或活动在同一时间间隔内发生。操作系统是一个并发系统，并发性是它的重要特征，操作系统的并发性指它应该具有处理和调度多个程序同时执行的能力。多个I/O设备同时在输入输出；设备I/O和CPU计算同时进行；内存中同时有多个系统和用户程序被启动交替、穿插地执行，这些都是并发性的例子。发挥并发性能够消除计算机系统中部件和部件之间的相互等待，有效地改善系统资源的利用率，改进系统的吞吐率，提高系统效率。例如，一个程序等待I/O时，就出让CPU，而调度另一个程序占有CPU执行运行。这样，在程序等待C/O时，CPU便不会空闲，这就是并发技术。并发性虽然能有效改善系统资源的利用率，但却会引发一系列的问题，使操作系统的设计和实现变得复杂化。如：怎样从一个运行程序切换到另一个运行程序？以什么样的策略来选择下一个运行的程序?怎样将各个运行程序隔离开来，使之互不干扰，免遭对方破坏？怎样让多个运行程序互通消息和协作完成任务？怎样协调多个运行程序对资源的竞争？多个运行程序共享文件数据时，如何保证数据的一致性？操作系统必须具有控制和管理程序并发执行的能力，为了更好的解决上述问题，操作系统必须提供机制和策略来进行协调，以使各个并发进程能顺利推进，并获得正确的运行结果。另外，操作系统还要合理组织计算机工作流程，协调各类硬软件设施工作，充分提高资源的利用率，充分发挥系统的并行性，这些也都是在操作系统的统一指挥和管理下进行的。采用了并发技术的系统又称为多任务系统(multitaskingsystem)，计算机系统中，并发实际上是一个物理CPU在若干道程序之间多路复用，这样就可以实现运行程序之间的并发，以及CPU与I/O设备、I/O设备与I/O设备之间的并行，并发性的实质是对有限物理资源强制行使多用户共享以提高效率。在多处理器系统中，程序的并发性不仅体现在宏观上，而且体现在微观上(即在多个CPU上)也是并发的，又称并行的。并行性(parallelism)是指两个或两个以上事件或活动在同一时刻发生。在多道程序环境下，并行性使多个程序同一时刻可在不同CPU上同时执行。而在分布式系统中，多台计算机的并存使程序的并发性得到了更充分的发挥。可见并行性是并发性的特例，而并发性是并行性的扩展。由于并发技术的本质思想是：当一个程序发生事件(如等待I/O)时出让其占用的CPU而由另一个程序运行，据此不难看出，实现并发技术的关键之一是如何对系统内的多个运行程序(进程)进行切换的技术。Q共享性(sharing)。共享性是操作系统的另一个重要特性。共享指操作系统中的资源(包括硬件资源和信息资源)可被多个并发执行的进程共同使用，而不是被一个进程所独占。出于经济上的考虑，一次性向每个用户程序分别提供它所需的全部资源不但是浪费的，有时也是不可能的。现实的方法是让操作系统和多个用户程序共用一套计算机系统的所有资源，因而，必然会产生共享资源的需要。资源共享的方式可以分成两种：第一种是互斥访问。系统中的某些资源如打印机、磁带机、卡片机，虽然它们可提供给多个进程使用，但在同一时间内却只允许一个进程访问这些资源，即要求互相排斥地使用这些资源。当一个进程还在使用该资源时，其他欲访问该资源的进程必须等待，仅当该进程访问完毕并释放资源后，才允许另一进程对该资源访问。这种同一时间内只允许一个进程访问的资源称临界资源，许多物理设备，以及某些数据和表格都是临界资源，它们只能互斥地被共享。第二种是同时访问。系统中还有许多资源，允许同一时间内多个进程对它们进行访问，这里“同时”是宏观上的说法。典型的可供多进程同时访问的资源是磁盘，可重入程序也可被同时访问。与共享性有关的问题是资源分配、信息保护、存取控制等，必须要妥善解决好这些问题。共享性和并发性是操作系统两个最基本的特性，它们互为依存。一方面，资源的共享是因为程序的并发执行而引起的，若系统不允许程序并发执行，自然也就不存在资源共享问题。另一方面，若系统不能对资源共享实施有效管理，必然会影响到程序的并发执行，甚至程序无法并发执行，操作系统也就失去了并发性，导致整个系统效率低下。Q异步性(asynchronism)。操作系统的第三个特性是异步性，或称随机性。在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况，进程的执行不是一贯到底，而是“走走停停”。例如，一个进程在CPU上运行一段时间后，由于等待资源满足或事件发生，它被暂停执行，CPU转让给另一个进程执行。系统中的进程何时执行？何时暂停？以什么样的速度向前推进？进程总共要化多少时间执行才能完成？这些都是不可预知的，或者说该进程是以异步方式运行的，其导致的直接后果是程序执行结果可能不唯一。异步性给系统带来了潜在的危险，有可能导致进程产生与时间有关的错误，但只要运行环境相同，操作系统必须保证多次运行进程，都会获得完全相同的结果。操作系统中的随机性处处可见，例如，作业到达系统的类型和时间是随机的；操作员发出命令或按按钮的时刻是随机的；程序运行发生错误或异常的时刻是随机的；各种各样硬件和软件中断事件发生的时刻是随机的等等，操作系统内部产生的事件序列有许许多多可能，而操作系统的一个重要任务是必须确保捕捉任何一种随机事件，正确处理可能发生的随机事件，正确处理任何一种产生的事件序列，否则将会导致严重后果。Q虚拟性(virtual)。虚拟性是指操作系统中的一种管理技术，它是把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。显然，前者是实际存在的而后者是虚构假想的，采用虚拟技术的目的是为用户提供易于使用、方便高效的操作环境。例如，在多道程序系统中，物理2PU可以只有一个，每次也仅能执行一道程序，但通过多道程序和分时使用CPU技术，宏观上有多个程序在执行，就好像有多个CPU在为各道程序工作一样，物理上的一个CPU变成了逻辑上的多个CPU。Spooling技术可把物理上的一台独占设备变成逻辑上的多台虚拟设备；窗口技术可把一个物理屏幕变成逻辑上的多个虚拟屏幕；通过时分或频分多路复用技术可以把一个物理信道变成多个逻辑信道；IBM的VM技术把物理上的一台计算机变成逻辑上的多当进程对信号量S执行P、V操作时，S的值发生变化，当S>0、S=0、和SvO时，其物理意义是什么？(注：P、V操作有时又称为wait，signal)答：P操作相当于申请一个资源，得不到阻塞；V操作相当于归还一个资源，如有等待该资源的进程，则唤醒。S>0时S表示可使用的资源数或表示可使用资源的进程数；S=0时S表示无资源可供使用或表示不允许进程再进入临界区；SvO时S表示等待使用资源的进程个数或表示等待进入临界区的进程个数。作业调度和进程调度各自的主要功能是什么？答：作业调度的主要功能是：记录系统中各个作业的情况；按照某种调度算法从后备作业队列中挑选作业；为选中的作业分配内存和外设等资源；为选中的作业建立相应的进程；作业结束后进行善后处理工作。进程调度的主要功能是：保存当前运行进程的现场；从就绪队列中挑选一个合适进程；为选中的进程恢复现场。5•有三个用户进程A、B和C,在运行过程中都要使用系统中的一台打印机输出计算结果。⑴试说明A、B、C进程之间存在什么样的制约关系？(2)为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。答：(1)A、B、C三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。(2)mutex:用于互斥的信号量，初值为1。各进程的代码如下：进程A进程B进程CP(mutex)P(mutex)P(mutex)申请打印机申请打印机申请打印机使用打印机使用打印机使用打印机V(mutex)V(mutex)V(mutex)6•设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后再搬到缓冲区B2中，并在打印机上打印结果(假定缓冲区仅能容纳一张卡片信息)。问：系统要设几个进程来完成这个任务？各自的工作是什么？这些进程间有什么样的相互制约关系？用P、V操作写出这些进程的同步算法。分析我们画一个草图来帮助我们理解这道题：输处输从图中可以看出，从“卡片机”到“打印机”共需要3个操作，即输入、处理、输出。这3个动作就是完成任务的3个进程。下面我们看看这些进程之间有什么样的制约关系。可以看出，这3个进程之间是同步关系，合作完成从输入到输出的工作任务。对其中任何一个进程，要处理好与其关联的两端设备的协调工作。以“输入进程”为例，它与卡片机和缓冲区B1关联，将卡片机的卡片输入到缓冲区B1,在不考虑卡片机的情况下，就要考虑缓冲区的情况，即是满还是空，是空缓冲区，输入进程就可以输入信息，如果缓冲区满，则要等待“处理进程”将B1中的信息取走，使之为空，输入进程才能继续工作。依此类推，可以找出另外2个进程的制约关系。一般来说，处理进程同步需要2个信号量，“输入进程”和“处理进程”同步，需要2个信号量，解决缓冲区B1的协调操作问题；而“处理进程”和“输出进程”同步，还需要2个信号量，解决缓冲区B2的协调操作问题。因此，共需要4个信号量。本题中“处理进程”的算法有一些难度，因为它需要协调两个缓冲区的工作，考虑的因素比较多，算法复杂些。答案系统可设三个进程来完成这个任务：Input进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；Process进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；Print进程负责从缓冲区B2中取出信息，并在打印机上印出。Input进程受Process进程影响，B1放满信息后Input进程要等待：等Process进程将其中信息全部取走，才能继续读入信息；Process进程受Input进程和Print进程的约束：B1中信息放满后Process进程才可从中取出它们，且B2被取空后，Process进程才可将加工结果送入其中；Print进程受Process进程的约束：B2中信息放满后Print进程才可从中取出它们，进行打印。信号量含义及初值：B1full——缓冲区B1满，初值为0;B1empty——缓冲区B1空，初值为1；B2full——缓冲区B2满，初值为0；B2empty——缓冲区B2空，初值为1；Input：while(1){wait(B1empty);读卡片中的信息，并将其放入缓冲区1中;signal(B1full);}Process:while(1){wait(B1full);从缓冲区1中取走数据，存放在临时变量tmp中；signal(B1empty);处理tmp中的数据，将处理结果存放在变量result中；wait(B2empty)；将result中的结果放入缓冲区2;signal(B2full)；}Print:while(1){wait(B2full)；从缓冲区2中取走数据，存放在临时变量tmp中；signal(B2empty)；打印tmp中的数据；}注：如果改变缓冲区的数量或者改变缓冲区的大小，题目的答案要做相应地变化：假定缓冲区B1的大小为m，缓冲区B2的大小为n。则上述问题就演变为同步互斥问题了。Bifull缓冲区B1满，初值为0;Biempty缓冲区B1空，初值为m;B2full——缓冲区B2满，初值为0;B2empty——缓冲区B2空，初值为n;mutexi--缓冲区B1的互斥信号量，初值为1；mutex2--缓冲区B2的互斥信号量，初值为1；Input：while(1){wait(B1empty);wait(mutex1);读卡片中的信息，并将其放入缓冲区1中;signal(mutex1);signal(B1full);}Process:while(1){wait(B1full);wait(mutex1);从缓冲区1中取走数据，存放在临时变量tmp中；signal(mutex1);signal(B1empty)；处理tmp中的数据，将处理结果存放在变量result中;wait(B2empty)；wait(mutex2);将result中的结果放入缓冲区2;signal(mutex2);signal(B2full);}Print:while(1){wait(B2full);wait(mutex2);从缓冲区2中取走数据，存放在临时变量tmp中；signal(mutex2);signal(B2empty);打印tmp中的数据；}对于如图所示的交通图，驳船在运河里单向航行，汽车在公路上也是单向行驶。由于汽车要两次跨越运河。为了让汽车和驳船能正常地行驶，在运河上架设了两座吊桥，当汽车要跨越运河时，吊桥必须放下；而当驳船要航行时，吊桥必须吊起。试设计一种方案，保证汽车和驳船均能正常行驶。

/运河路公CZ1IZJIZJ叵枢槨归出虻/运河路公CZ1IZJIZJ叵枢槨归出虻答：根据题目告诉我们的条件，可以画出这个交通系统如下图所示的一种通行状态。在这种状态下，吊桥A吊起，驳船正在通过吊桥A,船头已抵达吊桥B。由于吊桥B上正有汽车通行，因此驳船等待吊桥B上的汽车下桥。而公路上的汽车又在等待驳船通过吊桥A,这时吊桥B上的汽车处于等待吊桥A放下的状态。由此可见，此时驳船和汽车相互等待对方所占用的资源，显然是发生了死锁。用信号量的办法可以有效地解决这个交通系统的死锁问题。这里，首先将驳船和汽车抽象为并发进程，吊桥A、B是并发进程所共享的资源。为吊桥A、B分别设置一个信号量，信号量的值为1表示吊桥未被占用；信号量的值为0表示吊桥上正有汽车通行，或吊桥正被吊起、桥下有驳船通过。具体的解决方案有多种，其中最简单的是当并发进程要通过吊桥时，首先检测这两个信号量是否同时为1，若是的话，则将这两个信号量同时获取，通过两座吊桥，然后将两个信号量释放。如果进程检测到两个信号量不同时为1，则等待，直至它们的值同时都为1。这个简单方法能有效地解决死锁问题，但并不能保证这个交通系统具有高的通行效率。对于这个交通系统，人们实际上通常采用的调度方法是：当船首接近吊桥A时鸣笛，这时要通过吊桥A、但还未上桥的汽车不再上桥，等桥上的汽车下桥后，吊桥A吊起，让驳船通过。当船首接近吊桥B时，同样应先鸣笛，如吊桥B上没有汽车，吊桥B吊起，让驳船通过。对于汽车来说，在接近吊桥B时，应判断吊桥B是否处于放下状态，如果是的话，还应进一步判断吊桥A是否是吊起的。如果吊桥A是处在放下状态，那么整条公路是通畅的，因此汽车可以上桥。如果此时吊桥A吊起，则应判断运河对岸的公路上是否已经排满了汽车，如果是的话，则汽车不能上桥，原因在于如果汽车上了桥，由于前面的公路上已经塞满了汽车在等待吊桥A放下，因此汽车上了吊桥B后将无法下桥，此时会发生死锁。我们根据这样的调度方法写出如下程序。/*programBargeAndAutomobile*/intbridge_A_up=0,bridge_A_up=0;//起先吊桥A、B都是放下的semaphoremutex_A=1,mutex_B=1;semaphoreload_num=K;//两桥之间的公路上最多能容纳K辆汽车voidbarge(inti)//驳船的程序{ApproachingBridgeA;//驳船驶近吊桥ABlowingawhistle;//鸣笛P(mutex_A);if(bridge_A_up==0)bridge_A_up=1;//吊桥A吊起ApproachingBridgeB;//驳船驶近吊桥BBlowingawhistle;//鸣笛P(mutex_B);if(bridge_B_up==0)bridge_B_up=1;//吊桥B吊起bargepassingBridgeA;//驳船通过吊桥AV(mutex_A);bargepassingBridgeB;//驳船通过吊桥BV(mutex_B);}voidautomobile(inti)//汽车i的程序{ApproachingBridgeB;//汽车驶近吊桥BP(load_num);P(mutex_B);if(bridge_B_up==1)//若吊桥B吊起bridge_B_up==0;//吊桥B放下GoontobridgeB;//汽车驶上吊桥BPassbridgeB;///汽车驶过吊桥BV(mutex_B);Goahead;P(mutex_A);if(bridge_A_up==1)//若吊桥A吊起bridge_A_up==0;//吊桥A放下GoontobridgeA;//汽车驶上吊桥AV(load_num);PassbridgeA;///汽车驶过吊桥AV(mutex_A);}voidmain(){parbegin(barge(1),barge(2),„,automobile(1),automobile(2),„);}下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位小时，以十进制进行计算。）作业号提交时间运行时间10.08.020.44.031.01.0分析解此题关键是要清楚系统中各道作业随时间的推进情况。我们用一个作业执行时间图来表示作业的执行情况，帮助我们理解此题。采用先来先服务调度策略，其作业执行时间图如下：作业11作业3作业2f作业1二时间00.41.08.012.013.0时间作业提交时间各作业陆续完成时间采用短作业优先调度策略，其作业执行时间图如下:作业作业3作业2章作业1二00.41.08.09.013.0时间作业提交时间各作业陆续完成时间另外，作业i的周转时间片=作业完成时间一作业提交时间系统中n个作业的平均周转时间T=QT）x1，其中Ti为作业i的周转时ini=1间。解：采用先来先服务调度策略，则调度次序为l、2、3。作业号提交时间运行时间开始时间完成时间周转时间10.08.00.08.08.020.44.08.012.011.631.01.012.013.012.0平均周转时间T=（8＋11.6＋12）73=10.53采用短作业优先调度策略，则调度次序为l、3、2。作业号提交时间运行时间开始时间完成时间周转时间10.08.00.08.08.031.01.08.09.08.020.44.09.013.012.6平均周转时间T=(8+8+12.6)13=9.53今有三个批处理作业。第一个作业10:00到达，需要执行2小时；第二个作业在10:10到达，需要执行1小时；第三个作业在10:25到达，需要执行25分钟。分别采取如下两种作业调度算法：调度算法1：作业号到达时间开始执行时间执行结束时间110:0010:0012:00210:1012:0013:00310:2513:0013:25调度算法2：作业号到达时间开始执行时间执行结束时间110:0011:5013:50210:1010:5011:50310:2510:2510;50计算各调度算法下的作业平均周转时间。调度算法1是什么作业调度算法？分析作业的周转时间=作业完成时间－作业提交时间。以调度算法1的作业2为例，其周转时间=作业完成时间13:00－作业提交时间10:10，得到结果为2小时50分钟，转换为小时为2.83小时。转换的目的是为了方便计算平均周转时间。解：(1)采用调度算法1时：作业1的周转时间为2小时；作业2的周转时间为2.83小时；作业3的周转时间为3小时；平均周转时间为：(2+2.83+3)／3=2.61小时。采用调度算法2时：作业1的周转时间为3.83小时；作业2的周转时间为1.67小时；作业3的周转时间为0.42小时；平均周转时间为：(3.83+1.67+0.42)/3=1.97小时。(2)调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：(1)逻辑地址需要多少二进制位表示？(2)物理地址需要多少二进制位表示？解因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示(32=25)。页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。分析在分页存储管理中，逻辑地址结构如下图所示。页号p页内地址d它由两个部分组成：前一部分表示该地址所在页面的页号p;后一部分表示页内地址(页内位移)d。页号的地址位数决定了页的多少，假设页号有20位，则地址空间中最多可容纳的页面数为220，即1MB个页面。页内地址位数确定了每页的大小，若页内地址为12位，则每页大小为212，即2KB。同理，物理地址中块号的地址位数决定了块的多少，由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。页号块号02132136解本题中，为了描述方便，设页号为P，页内位移为d,贝U：对于逻辑地址1011,p=int(1011/1024)=0,d=1011mod1024=1011。查页表第0页在第2块，所以物理地址为1024x2+1011=3059。对于逻辑地址2148，p=int(2148/1024)=2，d=2148mod1024=100。查页表第2页在第1块，所以物理地址为1024+100=1124。对于逻辑地址4000，p=int(4000/1024)=3，d=4000mod1024=928。查页表第3页在第6块，所以物理地址为1024x6+928=7072。对于逻辑地址5012，p=int(5012/1024)=4，d=5012mod1024=916。因页号超过页表长度，该逻辑地址非法。12．考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少？解使用FIFO算法，缺页次数是16;使用LRU算法，缺页次数是15;使用OPT算法，缺页次数是11。分析所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。当内存块数量为3时：FIFO1,234,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6块11114446663332226块2222111222777111块333355511166633缺页xxxxxxxxxxxxxxxx因此，FIFO算法发生缺页中断的次数为16。在FIFO算法中，先进入内存的页面被先换出。例如，当页6要调入时，内存的状态为4、1、5,考查页6之前调入的页面，分别为5、1、2、4、…，可见4为最先进入内存的，本次应换出，然后把页6调入内存。LRU1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3，6

块1块2块3缺页1114块1块2块3缺页111422233XXXX452211XX551666122XXX132X773326XX223361XX236X因此，LRU算法发生缺页中断的次数为15。在LRU算法中，最近最少使用