试卷(002)B.doc

操作系统试题(002) B卷num12345678910111213141516scores25325103105531010121051.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:(1) First-Come First-Served;(b) Shortest Job First; (c) Round Robin (quantum = 2)Table 1Processarrive time Processing TimeA04B2.55C3.53D5.517.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 barberschair 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 2ProcessCurrentAllocationMaximumAllocationResourcesAvailableR1R2R1R2R1R2P1729521P21326P31122P4305010.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, 130SegmentBaseLength0300110185521122002003458302 13.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) 0000101101001(b) 0000010010010(c) 0000100010101(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 9th and l0th references, and lequals 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 andthe directory entry are already in main memory. For the following, indicate how many physical blocks mustbe 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: 800(b) Last block read: 500; block to be read: 10016.In computer system, why buffers are needed?Answer to操作系统试题(002) B卷1.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 notauthorized 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 beharmful.(d) Yes. Changing the clock could disrupt scheduled events and is typically not a right granted to a userprocess.(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: First-Come First-Served; (b) Shortest Job First; (c) Round Robin (quantum = 2)Table 1Processarrive time Processing TimeA04B2.55C3.53D5.51(a) Frit-Come First-Served AAAABBBBBCCCD0123456789101112131415c1c2c3c4c5c6c7Processarrival Processing startendwaiting(c4-c2)turnaround(c5-c2)A040404B2.55491.56.5C3.539125.58.5D5.5112136.57.5average3.3756.625(b) Shortest Job FirstAAAACCCDBBBBB0123456789101112131415c1c2c3c4c5c6c7ProcessArrival Processing startendwaiting(c4-c2)turnaround(c5-c2)A040404B2.558135.510.5C3.53470.53.5D5.51781.52.5average1.8755.125(C) Round Robin (quantum = 2)AABBABBCCDDBBCC0123456789101112131415|BCDc1c2c3c4c5c6c7ProcessArrival Processing startendwaiting(c4-c2)turnaround(c5-c2)A040404B2.554131.510.5C3.536122.58.5D5.51892.53.5average1.6256.6257.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. AProcess 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 2ProcessCurrentAllocationMaximumAllocationResourcesAvailableR1R2R1R2R1R2P1729521P21326P31122P43050The state is unsafe. Allocating one R1and oneR2 allows P3 to run to completion, leaving three R1 available and two R2s. This allows P4 to run, leaving six R1s and two R2s. Neither P1 nor P2 could runby lack of resource of R2, so the state is unsafe.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 waiting on a resource, Ri, held by Pi+1 (P0 is holding the resource requested by Pn). Thus, Pi is holding resource Ri-1 while requesting Ri. Let Si be the selection priority number of resource Ri. We know Si-1 Si. So S0 S1 . Sn S0. But this is impossible, so our assumption must be false.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?If h is the hit ratio, then 60h + l80 x (l - h) = 80. Solving for h,h=83.33%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. answer(a)0, 109409SegmentBaseLength(b)2, 100fault0300124(c) 1, 21010651855211(d) 3, 222680220199(e) 0, 130fault3458302(a) 409.Offset 109is less than the segment length of 124. Segment 0 begins at location 300, so offset 109is at physical address 109 + 300 = 409.(b) Fault.Offset 100 is greater than the segment length of 99.This address results in a segment fault.(c)1065.Offset 210 is less than the segment length of 211.Segment 1 begins at location 855,so offset 210is at physical address 210+855=1065(d) 680.Offset 222 is less than the segment length of 302. Segment 3 begins at location 458, so offset 222 is at Physical address 222 + 458 = 680.(e) Fault.Offset 130 is greater than the segment length of l24.This address results in a segment fault.13.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) 0000101101001(b) 0000010010010(c) 0000100010101(d) 0000001110101Present Bit(1 in/ 0 out)Frame000101000100001001011011010111010011010001100110101101011000110100101111page numberoffsetframephysical address(a) 00001011010011011010011010110101101001(b)000001001001010010010outfault(c)0000100010101100010101outfault(d)00000011101011110101000010000111010114.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 lequals to 6 references?FIFO replacementLRU replacementPageFaultAfterPageFaultAfter00*0,-,-0*0,-,-19*9,0,-9*9,0,-209,0,-00,9, -31*1,9,01*1, 0,948*8,1,98*8,1,0518,1,911,8, 0688,1,988,1,077*7,8,17*7,8,1887,8,188,7, 1977,8,177,8,11017,8,111,7,8112*2,7,82*2,1,71272.7.877,2,11322,7,822, 7,11472,7,877,2, 11582,7,88*8,7,21622,7,822, 8,7173*3,2,73*3,2,8188*8,3,288,3,21938,3,233,8, 28Faults8FaultsThe 6 references before the l6th reference are l, 2, 7, 2,7 and 8 . Thus,W(t,l) = 1, 2, 7, 8.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 andthe directory entry are already in main memory. For the following, indicate how many physical blocks mustbe 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