电子科大00级操作系统试卷有答案.doc

0016-0020操作系统试卷A一、名词解释（10分）1、操作系统 2、进程3、设备无关性4、数组多路通道 5、死锁二、简答题（15分）1、一台计算机有8台磁带机，他们由N个进程竞争使用，每个进程可能需要3台磁带机。请问N为多少时，系统没有死锁危险。请说明其原因。2、叙述设备分配时需要的数据结构，及其分配方法。3、请你简述段页式虚拟存储系统使用的数据结构及地址变换过程。4、请简述SPOOLING 系统的组成及各部分的功能5、假定一个处理器正在执行两道作业，一道以计算为主，一道以输入输出为主，你将怎样赋予它们占有处理器的优先级？为什么？三、现要求从输入机（速度为6400字符/秒）输入1000个字符，经处理（费时37毫秒）后，将结果（仍假设为1000字符）存到磁带上（磁带机速度为10万字符/秒），然后，再读1000个字符处理，直到所有的输入数据全部处理完毕。假定处理器具有与外围设备并行工作的能力，请计算处理器的利用率。 （5分）四、在一个支持虚拟分页并采用请求页式调度的存储管理系统中，有一用户程序，它访问其地址空间的字地址序列是：70，74，135，276，400，300，700，266，148，560，284，172 问：若分配给该作业的内存大小为384字，初始为空，页大小为128字，试按FIFO、LRU页面淘汰算法，分别计算页面访问的缺页率。 （10分）五、假定UNIX系统V中磁盘块大小为1K,每个磁盘块当用于做间接块时最多可登记256个块号，现要对一个大小为200000字节的文件检索一边，问将要发生多少次磁盘传输中断？为什么？（10分）六、某系统中采用银行家算法避免死锁。设其资源集合为A，B，C，其中资源类A含有5个资源实例，资源类B含有10个资源实例，资源类C含有9个资源实例。又设系统中进程集合为P1，P2，P3，P4。在时刻T0系统状态如下： Max Allocation Need Available A B C A B C A B C A B C P1 4 9 3 2 3 2 2 6 1 1 4 1 P2 3 0 3 2 0 2 1 0 1 P3 1 7 5 0 2 3 1 5 2 P4 3 2 1 0 1 1 3 1 0试回答当前状态是否是安全的，为什么？（10分）七、设某移动磁盘上共有200个磁道，由内向外依次编号为0199。又设该磁盘仅配有一个读写磁头，且磁头在完成对于第127号磁道的I/O请求后，正在为第140号磁道的I/O请求服务。假定此时I/O队列中有九个读写请求，所访问磁道列表如下： 到达次序：1 2 3 4 5 6 7 8 9 访问磁盘：83 148 91 178 94 150 102 175 130对于短距离优先、电梯调度磁盘调度算法分别求出为这九个请求服务所需的磁头移动量（以跨越磁道为单位）。 （10分）八、请用PV操作解决读者和写者问题。有两组并发进程：读者和写者，共享一个文件，要求：（1）允许多个读者同时执行读操作（2）在任意写者在完成写操作之前，不允许其他任意的读者和写者工作（3）写者预工作，但在它之前已有读者在执行读操作，那么，待现有读者完成读操作后在执行写操作，新的读者和写者均被拒绝。（10分）九、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，作业序列如表所示（表中所列作业优先数即为进程优先数，数值越小优先级越高）。 （10分） 列出所有作业进入内存时间及结束时间。 计算平均周转时间。作业的执行时间 作业名 到达时间 估计运行时间 优先数 A 10：00 40分 5 B 10：20 30分 3 C 10：30 50分 4 D 10：50 20分 6 0016-0020操作系统试卷A答案一、（10分）1.OS:是一组程序的集合,用于管理计算机系统的资源,方便用户的使用.2.进程:是一个程序段在其数据集合上的运行过程.3.设备无关性:用户在使用设备时,选用逻辑设备,而不必面对一种设备一种接口.设备管理实现逻辑设备到物理设备的映射,这就是设备无关性.4.数组多路通道:是指连接多台设备.同时为多台设备服务,每次输入/输出一个数据块.这样的通道叫数组多路通道.5.死锁:一组并发进程,因争夺彼此占用的资源而无法执行下去,这种僵局叫死锁.二、（15分）1.N循环测试方式2中断方式3DMA方式4通讯方式3.死锁产生的必要条件:1互斥条件2请求保持条件3部分分配条件4循环等待条件4.在段页式管理中,由于每段分成若干页,所以需要在段表中给出页表长度,以便检查逻辑地址中的页号是否越界.5.在进程通信中有共享存储器方式,消息缓冲方式及共享文件方式,其中共享存储器方式又分为直接通信与间接通信.(信箱通信)三（10分）序列 主存页面 2 3 中断 次缺页率1275%四、（15分）分解前：目录文件块数=254*64/512=32块 平均访盘次数为（1+32）/2=16.5分解后：符号目录块数=254*10/512=5块 基本目录文件块数为254*56/512平均访问次4次。五、（10分）Work Allocation Need FlagP0 622 032 011 TP3 654 332 652 TP1 986 000 750 TP2 986 354 356 TP4 12 13 10 014 656 T存在一安全通路p0p3p1p2p4.故当前时刻是安全的。六（15分）Semapher s=1/*用于缓冲区共享*/S1=k/*空位置*/S2=0/*产品*/Producer ConsumerRepeat RepeatProduce a product p(S2);P(S1); p(S);P(S0); get a product;Put a product; V(S);V(S2); V(S1);V(S); forever;Forever;七、（10分）作业 到达时间 开始处理时间 处理完成时间 周转时间J1 15 18 22 7J2 18 21 23 5J3 17 19 21 4平均周转时间为（7+51-4）/3=16/3时八、（10分）FCFS: 访问顺序为：83 148 91 178 94 150 102 175 130移动距离=（140-83）+（148-83）+（148-91）+（178-91）+（178-94）+（150-102）+（175-102）+（175-130）=571乘电梯调度算法：方向为：由内向外。访问顺序为：140 148 150 175 178 130 102 94 91 83移动距离为：（148-140）+（150-148）+（175-150）+（178-175）+（178-130）+（130-102）+（102-94）+（94-91）+（91-83）=1330025-0026试题Anum12345678910111213141516scores25325103105531010121051.What are the two main functions of an operating system?2.Which of the following instructions should be privileged?(a) Change memory management registers(b) Write the program counter(c) Read the time-of-day clock(d) Set the time-of-day clock(e) Change processor priority3.Name hardware features designed to explicitly assist the operating system.4.What is the principal advantage of multiprogramming?5. For each of the following transitions between process states, indicate whether the transition is possible. If it is possible, give an example of one thing that would cause it.(a) Run -ready;(b) Run - blocked; (c) Run - terminated(d) Run - swapped-blocked;(e) Blocked - run6.For the processes listed in Table 1,(1)draw a chart illustrating their execution .(2)what is the average turnaround time?(3) what is the wait time？using:(a) First-Come First-Served;(b) Shortest Job First;(c) Round Robin (quantum = 2)Table 1Processarrive time Processing TimeA03B1.56C4.54D6.527.Is a non-preemptive scheduling algorithm a good choice for an interactive system? Briefly why?8.Sleeping Barber Problem: There is a barber shop with n chairs for waiting customers, one barbers chair and one barber. If a customer enters the store and there are no free chairs, the customer leaves. If a customer enters the store and the barber is seeping, the customer wakes up the barber and gets a haircut. Otherwise, a customer enters the store, takes a seat, and waits. If the barber finishes a haircut and there are waiting customers, the barber cuts the hair of the next customer. Otherwise, the barber goes to sleep in his chair. Using semaphores, write the functions to control the actions of customers and the barber.9.Is the state described in Table 2 safe or unsafe?Table 2ProcessCurrentAllocationMaximumAllocationResources AvailableR1R2R1R2R1R2P1124211P20112P31013P4203210.Show that by assigning a unique priority number to each resource, and prohibiting a process from requesting a resource with a priority less than or equal to the priority of any held resource, deadlock can be avoided.11.On a simple paged system, associative registers hold the most active page entries and the full page table is stored in the main memory. If references satisfied by the associative registers take 60 ns, and references through the main memory page table take l80 ns, what must the hit ratio be to achieve an effective access time of 80 ns?12.On a system using simple segmentation, compute the physical address for each of the logical addresses, given the following segment table. If the address generates a segment fault,indicate so.(a) 0, 109(b) 2, 100(c) 1, 210(d) 3, 222(e) 0, 130SegmentBaseLength038011018002112500200340030213.In this problem, use binary values, a page size of 26 bytes, and the following page table. Which of the following virtual addresses would generate a page fault? For those that do not generate a page fault,to what physical address would they translate?(a) 0001001101001(b) 0000010010010(c) 0001100010101(b) 0000001110101Present Bit(1 in/ 0 out)Frame00010110000101101111101001000111010101100010010114.Given references to the following pages by a program:0,9,0, 1, 8, l,8,7, 8,7, l,2,7,2,7, 8,2,3,8,3,(1)how many page faults will occur if the program has three page frames available to it and uses:(a) FIFO replacement?(b) LRU replacement?(2)what is the working set W(t,l), with t equals to the time between the 15th and l6th references, and l equals to 6 references?15.A file system uses 256-byte physical blocks. Each file has a directory entry giving the file name, location of the first block, length of file, and last block position. Assume last physical block read and the directory entry are already in main memory. For the following, indicate how many physical blocks must be read to access the specified block (including the reading of the specified block) on a system(1)using contiguous allocation;(2) using linked allocation.(a) Last block read: l0; block to be read: 500(b) Last block read: 500; block to be read:10016.In computer system, why buffers are needed?Answer to 0025-0026试题A1.What are the two main functions of an operating system?The two main functions of an operating system are managing system resources and providing application programs with a set of primitives that provide higher-level services.2.Which of the following instructions should be privileged?(a) Change memory management registers(b) Write the program counter(c) Read the time-of-day clock(d) Set the time-of-day clock(e) Change processor priority(a) Yes. Changing memory management registers would allow a process to access memory locations it was not authorized to access.(b) No. Writing the program counter is no different than executing on unconditional branch.(c) No. Although direct access to devices is usually unwise, read access of the clocks should not be harmful.(d) Yes. Changing the clock could disrupt scheduled events and is typically not a right granted to a user process.(e) Yes. Changing the processors priority could cause interrupts to be lost.3.Name hardware features designed to explicitly assist the operating system.(l) Kernel/user mode operation(2) Privileged instructions(3) Supervisor call instructions4.What is the principal advantage of multiprogramming?It increases CPU utilization. While one process is blocked, waiting for I/O to complete, the CPU may execute another process.5. For each of the following transitions between process states, indicate whether the transition is possible. If it is possible, give an example of one thing that would cause it.(a) Run -ready;(b) Run - blocked; (c) Run - terminated(d) Run - swapped-blocked;(e) Blocked - run(a) Possible, when a processs time quantum expires(b) Possible, when a process issues an I/O request(c)Possible, when a process terminates itself(d) Not possible, although Process could first go to the blocked state, then the swapped-blocked(e) Not possible, although process could first go to the ready state, then to the run state6.For the processes listed in Table 1,(1)draw a chart illustrating their execution .(2)what is the average turnaround time?(3) what is the wait time？using:(a) First-Come First-Served;(b) Shortest Job First;(c) Round Robin (quantum = 2)Table 1Processarrive time Processing TimeA03B1.56C4.54D6.52(a) Frit-Come First-Served AAABBBBBBCCCCDD 0123456789101112131415 c1c2c3c4c5c6c7ProcessarriveProcessing startendwaiting(c4-c2)turnaround(c5-c2)A030303B1.56391.57.5C4.549134.58.5D6.5213156.58.5average 3.1256.875(b) Shortest Job FirstAAABBBBBBDDCCCC 0123456789101112131415c1c2c3c4c5c6c7ProcessArrivalProcessing startendwaiting(c4-c2)turnaround(c5-c2)A030303B1.56391.57.5C4.5411156.510.5D6.529112.54.5average 2.6256.375(C) Round Robin (quantum = 2)AABBABBCCDDBBCC 0123456789101112131415 | | | 1.5 4.5 6.5 B C D c1c2c3c4c5c6c7ProcessArrivalProcessing startendwaiting(c4-c2)turnaround(c5-c2)A030505B1.562130.511.5C4.547152.510.5D6.529112.54.5average 1.3757.7857.Is a non-preemptive scheduling algorithm a good choice for an interactive system? Briefly why?No. Once a process gains control of the CPU, it retains control until it blocks or it terminates. A Process could execute for an extended period of time doing neither.Other processes on the system would not be able to execute, producing unacceptable response time.8.Sleeping Barber Problem: There is a barber shop with n chairs for waiting customers, one barbers chair and one barber. If a customer enters the store and there are no free chairs, the customer leaves. If a customer enters the store and the barber is seeping, the customer wakes up the barber and gets a haircut. Otherwise, a customer enters the store, takes a seat, and waits. If the barber finishes a haircut and there are waiting customers, the barber cuts the hair of the next customer. Otherwise, the barber goes to sleep in his chair. Using semaphores, write the functions to control the actions of customers and the barber.semaphore cuthair = 0;semaphore waiting = 0;semaphore countmutex = l;intcount = 0;void barber ()whi1e (true )P (cuthair );GiveHaircut ();void customer ()P (countmutex );if (count = n+1 ) V(countmutex );exit ();count = count + l;if (count l )Take a chair;V(countmutex );P(waiting);e1seV(countMutex);V(cuthair);ReceiveHaircut ();P (countmutex );count = count - l;lf (count 0)V (waiting);V (countmutex);9.Is the state described in Table 2 safe or unsafe?Table 2ProcessCurrentAllocationMaximumAllocationResources AvailableR1R2R1R2R1R2P1124211P20112P31013P42032The state is safe. Allocating both available resources allows P2 to run to completion, leaving one R1 available and two R2s. This allows P4 to run, leaving three R1s and two R2s. Pl may now run, leaving four R1s and four R2s. P3 may now run, so the state is safe.10.Show that by assigning a unique priority number to each resource, and prohibiting a process from requesting a resource with a priority less than or equal to the priority of any held resource, deadlock can be avoided.Assume Pl, P2,., Pn are an ordered list of the deadlocked processes such that Pi is wa