计算机操作系统复习要点.doc

操作系统复习要点操作系统：是一组控制和管理计算机硬件和软件资源，合理地组织计算工作流程，以及方便用户使用的程序集合。1操作系统目的/目标执行用户程序并使用户问题更易解决。使计算机系统更易于使用（方便性）。以一种效率的方式使用资源（有效性）.采用模块化结构,易于增、删、改（可扩充性）。要求统一开放的环境，能通过网络集成化并正确、有效地协同工作，实现应用程序的移植（开放性）2操作系统的作用 Os作为用户与计算机硬件系统之间的接口。OS作为计算机系统资源的管理者。OS用作扩充机器3操作系统的基本特征并发(concurrence)共享(sharing)虚拟(virtual)异步性(asynchronism)4并发(concurrence)并发：指在计算机系统中同时存在着多道运行的程序（进程）宏观上：多道程序同时在执行微观上：任何时刻只有一道程序在执行，即微观上多道程序在CPU上轮流（交替）执行（单机）并行(parallel)： 与并发相似，指多道程序在同一时刻执行，但需多个硬件支持。 注：1、程序的并发执行能有效改善系统资源的利用率，但使系统复杂化，因此操作系统必须对并发活动进行控制和管理。5批处理操作系统优缺点优点：作业流程自动化; 效率高；吞吐量高缺点：无交互手段；调试程序困难实现方法单道分时、前台和后台及多道分时6分时系统的特征人机交互性好共享主机（多路性、同时性）用户独立性 *及时性实时操作系统：指系统能及时（或即时）响应外部事件的请求，并控制所有实时任务协调一致地运行。实时操作系统的应用领域 有实时要求（有严格确定的时间限制）的领域（过程控制及事务处理）实时系统分类： （1）实时控制系统 （2）实时信息处理系统实时操作系统的主要特征：实时性和可靠性；多路性、独立性、交互性7三种基本的操作系统批处理操作系统、分时操作系统和实时操作系统通用操作系统如果一个操作系统兼有批处理、分时和实时系统三者或二者的功能 ，则称该操作系统为通过操作系统。8并行系统： 多于一个CPU的多处理机系统。并行系统的优点增大吞吐量：能在更短的时间内完成更多的工作。经济：共享许多设备（内存，总线等）提高可靠性：当一个CPU出故障时，会将部分工作分给其它CPU，从而不会使整个系统停机，只是降低了速度而已。1、 操作系统的三个主要目的是什么？1、要点：（1）、方便性（用户的观点）：提供一个用户与计算机硬件之间的接口，使计算机系统更容易使用。（良好、一致的用户界面） （2）、有效性（系统管理人员的观点）：为了对计算机的硬件、软件资源进行有效的管理和分配，使计算机资源得到有效利用。（3）、可扩充性（开放的观点）：合理地组织计算机系统的工作流程，从而改善系统性能，提高工作效率。（是硬件功能的首次扩充）2、 简述DOS、WINDOWS及UNIX操作系统的特点？ DOS：是一个单用户单任务的操作系统，曾广泛应用于IBM PC及其兼容机上，它的特点：（1）良好的兼容性 （2）较好的开放性 （3）使用方便 （4）功能丰富 WINDOWS：是一个单用户多任务的操作系统，是20世纪90年代初计算机操作系统技术进步的重要标志，也是DOS的换代产品，其特点：（1）图形化的工作环境和用户界面，（2）多任务操作环境 （3）有效地利用内存 （4）支持多媒体及多种字体 UNIX：是一个多用户多任务的分时操作系统，它已成为目前应用最广泛的操作系统，其特点：（1）内核和核外程序的有机结合 （2）移植性强 （3）是一个多任务任务系统 （4）良好的用户界面。 1、 假设有一台计算机，它有1M内存，操作系统占有用200K，每个用户进程也占用200K，用户进程等待I/O的时间为80%，若增加1M内存，则CPU的利用率将提高多少？解：1M内存的情况：1）支持用户进程数：（1024K-200K）/200K=4.12 所以4个用户进程。 2）CPU利用率： 先求CPU空闲（4个用户均处于等待I/O状态）概率P=（80%）4，然后再求CPU利用率1-P 1-P =1-（80%）4 = 1-0.84=59%增加1M内存的情况：1）支持用户进程数：（2*1024K-200K）/200K=9.24 所以9个用户进程。 2）CPU利用率： 先求CPU空闲（9个用户均处于等待I/O状态）概率P（80%）9，然后再求CPU利用率1-P 1-P =1-（80%）9 = 1 -0.89=87%87%-59%=28%28%/59%=47%增加1M内存，CPU的利用率将提高：87% / 59%= 147% 147% - 100%=47%所以若增加1M内存，则CPU的利用率将提高47%。2、 有两个程序，A程序按顺序使用CPU10S，使用设备甲5S，使用CPU5S，使用设备乙10S，最后使用CPU10S。B程序按顺序使用设备甲10S，CPU10S，使用设备乙5S，使用CPU5S，使用设备乙10S。在顺序环境下先执行A程序再执行B程序，CPU的利用率是多少？解： 程序A：执行时间10+5+5+10+10=40S使用CPU时间：10+5+10=25S程序B：执行时间10+10+5+5+10=40S使用CPU时间：10+5=15S 程序AB总执行时间：40+40=80S 使用CPU的时间为： 25+15=40S CPU的利用率： 40S/80S=50%3、 设某计算机系统有一台输入机、一台打印机。现有两道程序同时投入运行，且程序A先开始运行，程序B后运行。程序A的运行轨迹为：计算50MS，打印信息100MS，再计算50MS，打印信息100MS，结束。程序B的运行轨迹为计算50MS，输入数据80MS，再计算100MS。试说明：（1） 两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会空闲等待？（2） 程序A、B运行时有无等待现象？若有，在什么时候会发生等待现象？ 解： 0ms 50 100 150 180 200 300ms 程序A： 计算 打印 计算 打印 程序B： 计算 输入 计算 (1) 存在CPU空闲（在程序A运行后100ms-150ms之间，程序A正打印，程序B正输入）(2) 程序A运行后无等待现象，程序B运行后有等待现象（在A开始180ms-200ms之间；或程序B在运行后130ms-150ms之间）4、 假设就绪队列中有10个进程，系统将时间片设为200ms,CPU进行进程切换要花费用10ms，试问系统开销所占的比率约为多少？解： 10个进程以时间片轮转的方式使用CPU。系统总时间（200ms+10ms）系统开销所占的比率： 10/（200+10）= 4.8%5、 考虑5个进程P1，P2，P3，P4，P5，见表，规定进程的优先数越小，优先级越高，试描述在采用下述调度算法时各个进程运行过程，并计算采用每种算法时进程平均周转时间。假设忽略进程的调度时间。1） 先来先服务调度算法；2）时间片轮转调度算法（时间片为1ms）；3）非剥夺式优先级调度算法；4）剥夺式优先级调度算法。进程创建时刻ms运行时间ms优先数P1033P2265P3441P4652P5824解：画出各调度算法的甘特图列表算出各算法的平均周转时间：1）8.60 2)10.80 3) 8.60 4)7.80一、 解析题1、 在生产者和消费者问题中，如果对调生产者（消费者）进程中的两个P操作和V操作，可能发生什么情况？。2、 在测量控制系统中，数据采集任务把采集的数据送入一单缓冲区，计算任务从该单缓冲区中取出数据进行计算，试写出利用信号量机制实现两者共享单缓冲区的同步算法。（本题实际上是一个生产者/消费者问题，将生产者/消费者问题抽象出来，以另外一种形式描述是一种常见的试题形式）Int Se=1; /*信号量SE用于表示缓冲区有无空位置存放新的信息。*/Int SF=0; /*信号量SF用于表示缓冲区中有无可供计算的信息。*/Main()get();compute(): while(计算工作未完成) P（SF）；从缓冲区取出数据；V（SE）； :get() : while(采集工作未完成) 采集一个数据； P（SE）；将数据送入缓冲区；V（SF）； : compute();3、 *在视频通信系统中，由进程PA采集一帧图像信息并存入环形缓冲区buffer，进程PB从buffer中取一帧数据进行处理，假设buffer的大小为n，试用P、V操作实现PA和PB。（类似生产者-消费者）compute() :while(计算工作未完成) P（SF）；从缓冲区取出数据；V（SE）； :INT BUFFER-SIZE=N；INT SF=0；/*BUFFER中是否有可取的信息*/INT SE=N；/* BUFFER中是否有空位置以存放信息*/MAIN（） GET（） COMPUTE（）get(): while(采集工作未完成) 采集一个数据； P（SE）；将数据送入缓冲区；V（SF）；:4、5、6、7、8、9、10、11、12、 桌上有一空盘，允许存放一只水果，爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取出，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。INT SE=1；/* 盘中是否为空*/INT S0=0；/*盘中是否有可取的桔子*/INT SA=0；/*盘中是否有可取的苹果*/FATHER（） : P（SE）； 放水果； IF（水果为桔子） V（SO）； ELSE V（SA）；:MAIN（） COBEGIN FATHER（）；SON（）；DAUGHTER（）；COEND13、14、15、DAUGHTER（） : P（SA）； 取走苹果； V（SE）； 吃苹果 SON（） : P（SO）； 取走桔子； V（SE）； 吃桔子 16、17、18、 图给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。S1S3S2S4 int b2=0: /*表示进程S2是否可以开始执行*/int b3=0: /*表示进程S3是否可以开始执行*/int b4=0: /*表示进程S4是否可以开始执行*/s4() P(b4); /*因在S2及S3完成时均对b4做了V操作，故需两个P操作。*/P(b4);:; Main()s3() P(b3);: V(b4); s2() P(b2);: V(b4); s1() : V(b2); V(b3); : s1(); s2(); s3() s4()19、20、21、 读者/写者问题。有一数据区为多个进程所共享，假设一些进程只能对该数据区完成读操作（读者），而另一些进程只能对其完成写操作（写者），读者和写者要遵守以下的约束：（1） 允许多个读者同时从数据区中读数据；（2） 当有读者正在读数据时，不允许写者写数据；（3） 任何时候只允许一个写者向数据区中写数据；（4） 若有写者正在写数据区，不允许读者读数据。 试用P、V操作实现读者/写者问题解： INT MUTEX-COUNT；/*读进程之间互斥访问变量COUNT*/INT MUTEX-RW；/*读进程与写进程，写进程与写进程之间互斥访问DATA区*/*读者进程*/reader() P(mutex_count); Readcount+;If(readcount=1)P(mutex_rw);V(mutex_count)；Read data from data area; P(mutex_count);Readcount-；If(readcount=0)V(mutex_rw);V(mutex_count);INT COUNT=0；/*读进程数目*/MAIN（） COBEGIN READ（）； WRITE（）； COEND/*写者进程*/writer()P(mutex_rw);write data into data area;V (mutex_rw);22、 某数据库有一个写进程，多个读进程，它们之间读、写操作的互斥要求是：写进程正在写该数据库时不能有其他进程读数据库，也不能有其他进程写该数据库；读进程之间不互斥，可以同时读该数据库。请用信号量及P、V操作描述这一组进程的工作过程。（同上）丁23、 哲学家甲请哲学家乙、丙、丁至某处讨论问题，约定全体到齐后开始讨论：在讨论的间隙四位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如图，请用信号量及P、V操作说明四位哲学家的同步、互斥过程。 叉2刀1丙食物甲叉1乙刀2解：INT FORK1=1；/*资源叉1是否可用*/INT FORK2=1；/*资源叉2是否可用*/INT KNIFE1=1；/*资源刀1是否可用*/INT KNIFE2=1；/*资源刀2是否可用*/MAIN（） COBEGIN Pa（）；/*Pa表示哲学家甲的活动*/ Pb（）； Pc（）； Pd（）； COENDPa（） Pb（） Pc（） Pd（） ： ： ： ：P（KNIFE1）； P（KNIFE2）； P（KNIFE2）； P（KNIFE1）；P（FORK1）； P（FORK1）； P（FORK2）； P（FORK2）；进餐； 进餐； 进餐； 进餐；V（KNIFE1）； V（KNIFE2）； V（KNIFE2）； V（KNIFE1）；V（FORK1）； V（FORK1）； V（FORK2）； V（FORK2）；： ： ： ： 24、 设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆； 售票员的活动：关车门； 正常行车； 售票； 到站停车； 开车门；在汽车不断地到站、停车、行车过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。解：1）同步关系：售票员关车门后向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中，售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。 2）同步实现（用P、V操作）INT S1=0；/*是否允许司机开车*/INT S2=0；/*是否允许售票员开车门*/MAIN（） COBEGIN Driver（）；/* Driver表示司车的活动*/ Busman（）；/* Busman表示售票员的活动*/ COENDDriver（） Busman（） ： ：P（S1）； 关车门；启动车辆； V（S1）；正常行驶； 售票；到站停车； P（S2）；V（S2）； 开车门；： 上下乘客； ： 一、 解析题1、 为什么说采用有序资源分配法不会产生死锁？解：为了便于说明，不妨设系统中有M类资源，N个进程，分别用R1，R2，RM（1，2，M看作资源号）和P1，P2，Pn表示。根据有序资源分配法可知，进程申请资源时必须按照资源编号的升序进行，即任何进程在占有了Ri资源后，再申请的资源Rj的编号j一定大于I。因此在任一时刻，系统中至少存在一个进程Pk，它占有了较高编号的资源Rh，且它继续请求的资源必然是空闲的，因而Pk可以一直向前推进直至完成，当Pk运行完成后即会释放它占有的所有资源，在Pk;在Pk完成之后，剩下的进程集合中同样会存在一个进程，它占有了较高的资源，且它继续请求的资源必然是空闲的，因而它可以一直向前推进直至完成；以此类推，所有进程均可运行完成，故不会发生死锁。2、 N个进程共享某种资源R，该资源共有m个可分配单位，每个进程一次一个地申请或释放资源单位。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求之和小于m+n，试证明在这个系统中不可能发生死锁。解：设：max(i):表示第I进程的最大资源需求量 need(i): 表示第I进程的还需要的资源量allocation(i): 表示第I进程的已分配到的资源量由题中给定条件可知： max(1)+max(2)+max(n)=(allocation(1) +allocation(2)+allocation (n)+( need(1)+need(2)+need(n)=n （3） 则由（2）+（3）得： (allocation(1) +allocation(2)+allocation (n)+( need(1)+need(2)+need(n)=m+n这与（1）式相矛盾。3、 在哲学家进餐问题中，假定用一个信号量表示一支筷子，由这五个信号构成信号量数组：int stick5=1，1，1，1，1 第I个哲学家的活动描述如下所示，试问这五个哲学家的进餐活动是否发生死锁？ While(1) P(stickI) P(stick(I+1)mod 5) ) 进餐 V(stickI) V(stick(I+1)mod 5) ) 思考 解：这种描述虽然可以保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。这种情况发生在当五个哲学家几乎同时饥饿而各自拿起了左边的筷子时，这种五支筷子信号量值为0；当他们试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待，从而导致了死锁的产生。4、 在银行家算法中，若出现了下述资源分配情况： allocation need available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 试问：（1）该状态是否安全？ （2）如果进程P2提出请求Requst2（1，2，2，2）后，系统能否将资源分配给它？解： （1）安全。过程略 （2）不能分配与P2。过程略5、 有相同类型的5个资源被4个进程共享，且每个进程最多需要2个这样的资源就可以运行完毕。试问该系统是否由于对这种资源的竞争而产生死锁？解：该系统不会由于对这种资源的竞争而产生死锁。因为在最坏情况下，每个进程都需要2个这样的资源，且每个进程都已申请到了1个资源，那么系统中还剩下1个可用资源。无论系统为了满足哪个进程的资源申请而将资源分配给进程，都会因为该进程已经得了它所需要的全部资源而确保它运行完毕，从而可将它占有的2个资源归还给系统，这样就保证了其余三个进程能顺利运行。由此可知，该系统不会由于这种资源的竞争而产生死锁。1、 某操作系统采用可变分区分配存储管理方法，用户区为512K，且始址为0，用空闲分区管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户的512K空间空闲，对述申请序列：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K回答：（1）采用首次适应算法，空闲分区中有哪些空块（给出始址、大小）？ （2）采用最佳适应算法，空闲分区中有哪些空块（给出始址、大小）？ （3）如再申请100K，针对（1）和（2）各有什么结果？一、 解析题1、 什么是缓冲？为什么要引入缓冲？（1） 缓冲就是用来对数据传送速度不同的设备的传送速度进行匹配/缓冲的一种常用手段。其实现方法除在关键地方可采用硬件缓冲器外，大都采用软件缓冲来实现。软件缓冲区是指在I/O操作期间，专门用来临时存放输入/输出数据的一块存储区域。（2） 操作系统中，引入缓冲的主要原因有：1）缓冲CPU与I/O设备间速度不匹配的矛盾。因为一般情况下，程序的运行过程是时而计算，时而输出。2） 减少中断CPU的次数同时提高CPU与I/O设备的并行工作2、 什么是虚拟设备？为什么在操作系统中引入虚拟设备？虚拟设备是指通过虚拟技术将一台独占设备变换为若干台逻辑设备，供若干个用户进程使用，通常把这种经过虚拟技术处理后的设备称为虚拟设备。在操作系统中，引入虚拟设备是为了克服独占设备速度较慢、降低设备资源利用率的缺点，从而提高设备的利用率。3、 简述设备分配的过程/步骤。设备分配程序要用到系统设备表、设备控制表、控制器控制表和通道控制表。设备分配时要考虑到设备的固有属性、分配算法、防止死锁以及用户程序与