操作系统精髓与设计原理

1、Chapter 2Operating Sy stemOverviewReview Questi onsConvenience: An operating system makes a computer more convenient to use. Efficiency: An operating system allows the computer system resources to be used in an efficie nt manner. Ability to evolve: An opera ting system should be con structed in such

2、 a way as to perm 让 the effective developme nt, test ing, and in troductio n of new system fun cti ons without in terferi ng with service.2.5 The executi on con text, or process state, is the internal data by which the operat ing system is able to supervise and con trol the process - This internal i

3、n formati on is separated from the process, because the operat ing system has in formati on not permit ted to the process. The con text in cludes all of the in formati on that the operati ng system n eeds to man age the process and that the processor n eeds to execute the process properl y. The con

4、text in cludes the contents of the various processor registers, such as the program coun ter and data registers .It also in cludes in formati on of use to the operating system, such as the prior 让 y of the process and whether the process is wagi ng for the completi on of a particular I/O eve nt.Prob

5、lems(ii) The answers are the same for (a) and (b). Assume that although processor operatio ns cannot overlap, I/O operati ons can.1 Job:TAT=NTProcessor utilizati on=50%2 Jobs:TAT=NTProcessor utilizati on=100%4 Jobs:TAT=(2N 1)NTProcessor utilizati on=100%A system call is used by an applicati on progr

6、am to in voke a fun cti on provided by the operati ng syste m. Typically, the system call results in tran sfer to a system program that runs in kernel mode.Review Questions3-5 Swapping involves moving part or all of a process from main memory to disk. When none of the processes in main memory is in

7、the Ready state, the operating system swaps one of the blocked processes out onto disk into a suspend queue, so that another process may be brought into main memory to execute.3-10 The user mode has restrictions on the instructions that can be executed and the memory areas that can be accessed. This

8、 is to protect the operating system from damage or alteration. In kernel mode, the operating system does not have these restrictions, so that 让 can perform 让 s tasks.Problems3-1 ? Creation and deletion of both user and system processes. Theprocesses in the system can execute concurrently for informa

9、tion sharing, computation speedup, modularity, and convenience. Concurrent execution requires a mechanism for process creation and deletion. The required resources are given to the process when让 iscreated, or allocated to it while 让 is running. When the process terminates, the OS needs to reclaim an

10、y reusable resources.? Suspension and resumption of processes. In process scheduling, the OS needs to change the process's state to wa 让 ing or ready state when 让 is waiting for some resources- When the required resources are available, OS needs to change its state to running state to resume its

11、 execution.? Provision of mechanism for process synchronization.Cooperatingprocesses may share data. Concurrent access to shared data may result in data inconsistency. OS has to provide mechanisms for processes synchronization to ensure the orderly execution of cooperating processes, so that data co

12、nsistency is maintained ? Provision of mechanism for process communication.The processesexecuting under the OS may be either independent processes or cooperating processes- Cooperating processes must have the means to communicate w 让 h each other.? Provision of mechanisms for deadlock handling.In am

13、ultiprogramming environment, several processes may compete for a finite number of resources. If a deadlock occurs, all waiting processes will never change their waiting state to running state again, resources are wasted and jobs will never be completed.3.3 Figure 9.3 shows the result for a single bl

14、ocked queue- The figure readily generalizes to multiple blocked queues-Review Questions4.2 Less state information is involved.Address space, file resources, execution privileges are examples.1. Thread switching does not require kernel mode privileges because all of the thread management data structu

15、res are w 让 hin the user address space of a single process. Therefore, the process does not sw 让 ch to the kernel mode to do thread management. This saves the overhead of two mode sw 让 ches (user to kernel; kernel back to user). 2. Scheduling can be application specific. One application may benefit

16、most from a simple round-robin scheduling algorithm, while another might benefit from a priolity ? based scheduling algorithm. The scheduling algor让 hm can betailored to the application without disturbing the underlying OS scheduler. 3. ULTs can run on any operating system. No changes are required t

17、o the underlying kernel to support ULTs. The threads library is a set of application-level utilities shared by all applications.1. In a typical operating system, many system calls are blocking. Thus, when a ULT executes a system call, not only is that thread blocked, but also all of the threads w 让

18、hin the process are blocked ? 2. In a pure ULT strategy, a multithreaded application cannot take advantage of multiprocessing. A kernel assigns one process to only one processor at a time. Therefore, only a single thread within a process can execute at a time.ProblemsBecause, w 让 h ULTs, the thread

19、structure of a process is not visible to the operating system, which only schedules on the basis of processes.Chapter 5CONCURRENCY : MUTUALExclusion andSy nchronizationReview Questi ons5-1 Communi cati on among processes, shari ng of and competi ng for resources, syn chr oni zati on of the activitie

20、s of multiple processes, and allocatio n of processor time to processes.5.9 A binary semaphore may only take on the values 0 and 1. A gen eral semaphore may take on any in teger value.ProblemsABCDE; ABDCE; ABDEC; ADBCE; ADBEC; ADEBC;DEABC; DAEBC; DABEC; DABCECon sider the case in which tur n equals

21、0 and P (1) sets blocked 1 to true and the n finds blocked 0 set to false. P (0) will the n setblocked 0 to true, find tur n = 0, and en ter its critical secti on. P (1) will then assign 1 to turn and will also enter让 s critical section.Chapter 6CONCURRENCY : DEADLOCK ANDStarvationReview Questi ons6

22、.2 Mutual exclusi on>Only one process may use a resource at a time.Holdand wait A process may hold allocated resources while awaiting assignment of others. No preemption.No resource can be forciblyremoved from a process holdi ng 让？63 The above three con diti ons, plus: Circular wait A closed cha

23、in of processes exists, such that each process holds at least one resource n eeded by the n ext process in the chairuProblems 6.4 a. 0 0 0 00750 66222002 0320b. to d. Running the bankerA algorithm, we see processes can finish in the order pl, p4, p5, p2 z p3?e. Change available to (2,0,0 z0)and p3&#

24、39;s row of "still needs" to (6,5,2 z2).Now pl z p4, p5 can finish, but with available now (469,8) neither p2 nor p3's Mstill n eeds' 1 can be satisfied. So it is not safe to gra nt p3s1. W = (2100)Mark P3;Mark P2;Mark Pl;request.W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0)W = (2 2 2 0) +

25、 (2 0 0 1) = (4 2 2 1) no deadlock detectedChapter 7Memory ManagementReview Questi ons7.1 Relocatio n, protecti on, shari ng, logical orga ni zati on, physical orga ni zati on.7.7 A logical address is a reference to a memory location independent of the curre nt assig nment of data to memory; a tran

26、slatio n must be made to a physical address before the memory access can be achieved ? A relative address is a particular example of logical address, i n which the address is expressed as a locati on relative to some known point, usually the begi nning of the progra m. A physical address, or absolut

27、e address, is an actual locati on in mai n memory.Problems7.6 a-The 40 M block fits into the second hole, w让 h a startingaddress of0M.The 20M block Sts into the first hole, with a starting address of 20M. The40M10M block isplaced at location 120M.be The three starting addresses are 230M, 20M, and 16

28、0M, for the 40M,60M40M2 30M40M40M20M, and 10M blocks, respectively.c. The three starting addresses are0M,120Mz and 160M, for the 40M z5 540M60M W 三 60M40M g 30M40M40MS 2&20M, and 10M blocks, respectively.bytes/page) = 2 26 bytes. Therefore, 26 b 让 s are required for the logical address.b< A f

29、rame is the same size as a page, 2 10 bytes.c? The number of frames in main memory is (232 bytes of mainmemory)/(2 10 bytes/frame) = 2 22 frames. So 22 b 让 s is needed to specify the frame.d. There is one entry for each page in the logical address space.Therefore there are 2 16 en tries.e- In additi

30、 on to the valid/i nvalid bit, 22 bits are n eeded to specify the frame location in main memory, for a total of 23 b 让 s.d< The three starti ng addresses are0M, 230Mz and 360M, for the 40M,40M40M三月三60M40M g 30M40M40M20M, and 10M blocks, respectively.Chapter 8Virtual MemoryReview Questi onsSimple

31、pagi ng: all the pages of a process must be in main memory for process to run, uni ess overlays are used. Virtual memory pagi ng:not allpages of a process n eed be in main memory frames for the process to run.; pages may be read in as n eededA phe nomenon in virtual memory schemes, i n which the pro

32、cessor spe nds most of 让 s time swapping pieces rather than executing instructions.Problems6.5 1 a. Split bin ary address into virtual page nu mber and offset; use VPN as in dex into page table; extract page frame nu mber; con cate nate offset to get physical memory addressb? (i)1052 = 1024 + 28 map

33、s to VPN 1 in PFN 7, (7 x 1024+28 = 7196)2221 = 2x 1024 + 173 maps to VPN 2, page fault5499 = 5x 1024 + 379 maps to VPN 5 in PFN 0, (0 x 1024+379 = 379).4 a. PFN 3 since loaded Ion gest ago at time 20be PFN 1 since referen ced Ion gest ago at time 160c. Clear R in PFN 3 (oldest loaded), clear R in P

34、FN 2 (n ext oldest loaded),victim PFN is 0 since R=0d? Replace the page in PFN 3 since VPN 3 (in PFN 3) is used furthest in the futuree. There are 6 faults, indicated by *400024000244440233021032210324210042142Chapter 9UniprocessorSchedulingReview Questi ons9-1 Long-term scheduli ng: The decisi on t

35、o add to the pool of processes to be executed. Mediu m-term scheduli ng:The decisi on to add to the nu mber of processes that arepartially or fully in main memory.Short-term scheduli ng:The decisi on as to whichavailable process will be executed by the processor93 Turnaround time is the total time t

36、hat a request spends in the system (waHing time plus service time. Response time is the elapsed time between the submission of a request un til the resp onse begi ns to appear as output.Problems6.6 1 Each square represe nts one time un it; the nu mber in the square refers to the curre ntly-running p

37、rocess -FCFSRR, q = 1RR, q = 4SPNsrtHRRNFeedback, q = 1Feedback, q = 21AAABBBBBCCDDDDDEEEEEABABCABCBDBDEDEDEDEEAAABBBBCCBDDDDEEEEDEAAACCBBBBBDDDDDEEEEEAAACCBBBBBDDDDDEEEEEAAABBBBBCCDDDDDEEEEEABACBCABBDBDEDEDEDEEABAACBBCBBDDEDDEEDEETaTsA03B15c32D95E125FCFSTf38101520Tr3.007.007.006.008.006.20T/Ts1.001

38、.403.501.201.601.74RR q = 1Tf6.0011.008.0018.0020.00Tr6.0010.005.009.008.007.60T/Ts2.002.002.501.801.601.98RR <7 = 4Tf3.0010.009.0019.0020.00Tr3.009.006.0010.008.007.2051.001.803.002.001.601.88SPNTf3.0010.005.0015.0020.00Tr3.009.002.006.008.005.60T/Ts1.001.801.001.201.601.32SRTTf3.0010.005.0015.0

39、020.00Tr3.009.002.006.008.005.60T/Ts1.001.801.001.201.601.32HRRNTf3.008.0010.0015.0020.00Tr3.007.007.006.008.006.20T/Ts1.001.403.501.201.601.74FBq = 1Tf7.0011.006.0018.0020.00Tr7.0010.003.009.008.007.40T/Ts2.332.001.501.801.601.85FBTf4.0010.008.0018.0020.00q = 2Tr4.009.005.009.008.007.00T/Ts1.331.80

40、2.501.801.601.819.16 a. Seque nee with which processes will get 1 min of processor time:12345 Elapsed timeABCDE5ABCDE10ABCDE15ABDE19ABDE23ABDE27ABE30ABE33ABE36AE38AE40AE42A43A44A45The tur naround time for each process:A = 45 mi n, B = 35 mi n, C = 13 mi n, D = 26 mi n, E = 42 minThe average turnarou

41、 nd time is = (45+35+13+26+42) / 5 = 32.2 minb.Priority Job3467BEACTurnaround Time99 + 12 = 2121 + 15 = 3636 + 3 = 3939 + 6 = 45The average turnaround time is:(9+21+36+39+45)/5 = 30 minJobTurnaro und TimeA B C D E1515 + 9 = 2424 + 3 = 2727 + 6 = 3333 + 12 = 45The average turnarou nd time is: (15+24+

42、27+33+45) / 5 = 28.8 minRunning TimeJobTurnaround Time3c36D3 + 6 = 99B9 + 9 = 1812E18 + 12 = 3015A30 + 15 = 45The average turnarou nd time is:(3+9+18+30+45) / 5 = 21 minChapter 10M ULTIPROCESSOR AND REAL -TIMESCHEDULINGReview Questi ons10.1 Fine: Parallelism in here nt in a single in structi on stre

43、a m.Medium: Parallelprocess ing or multitask ing within a sin gle applicatio n.Coarse: Multiprocess ing ofcon curre nt processes in a multiprogram ming en vir onment.Very Coarse:Distributed process ing across n etwork no des to form a sin gle computi ngenvironment. Independent: Multiple unrelated pr

44、ocesses.4.2 A hard real-time task is one that must meet its deadline; otherwise it will cause un desirable damage or a fatal error to the syste m. Asoft real-time task has anassociated deadli ne that is desirable but not man datory; it still makes sense to schedule and complete the task eve n if it

45、has passed its deadli ne.Problems10.1 For fixed priority, we do the case in which the priority is A, B, C. Each square represents five time urdts; the letter in the square refers to the currently-running process. The first row is fixed priority; the sec ond row is earliest deadli ne scheduli ng usin

46、g completio n deadli nes.AABBAACCAABBAACCAAAABBACCACAABBAACCCAAFor fixed priority scheduling, process C always misses让 s deadline.6.7 4T2T3r/s locked byTTis uni ockeds lockeds uni ockedI I normal execution eecution in critical sectionOnce T3 enters 让 s critical section, it is assigned a priority hig

47、her than Tl.When T3 leaves 让 s critical section, it is preempted by T,I/O Management and Disk SchedulingReview Questi ons6.1 Programmed yoThe processor issues an I/O comma nd, on behalf of a process,to an I/O module; that process the n bus y-waits for the operati on to be completed before proceedi n

48、g. In terrupt-drive nI/O: The processor issues an I/O comma nd onbehalf of a process, con ti nues to execute subseque nt in structi ons, and is interrupted by the I/O module when the latter has completed 让 s work. The subsequent instructions may be in the same process, if 让 is not necessary for that

49、 process to wait for the completi on of the I/O. Otherwise, the process is suspe nded pending the in terrupt and other work is performed. Direct memory access (DMA): A DMA module con trols the excha nge of data betwee n main memory and an I/O module. The processor sends a request for the tran sfer o

50、f a block of data to the DMA module and is interrupted only after the entire block has been transferred. Seek time, rotati onal delay, access time.Problems11-1 If the calculati on time exactly equals the I/O time (which is the most favorable s 让 uation), both the processor and the peripheral device

51、running simultaneously will take half as long as if they ran separately ? Formally, let C be the calculation time for the entire program and let T be the total I/O time required. Then the best possible running time w 让 h buffering is max(C z T)z while the running time without buffering is C + T; and

52、 of course (C + T)/2) < max(C, T) < (C + T). Source: KNUT97 ?113 Disk head is in itially mov ing in the directi on of decreas ing track nu mber:FIFOSSTFSCANC-SCANNext tNumber of tracks traversedNext track accessedNumber of tracks traversedNext track accessedNumber of tracks traversedNext track

53、 accessedNumber of tracks traversed27731101064366436129102120104123412311019129271427141867614710171473918641101063164416454271205610Average61.Average39110100122120102312991414718171863929.1Average29.617110186176147129120110Average3910If the disk head is irdtially moving in the directi on of in creas ing track nu mber, only the SCAN and C-SCAN results cha nge:SCANC-SCANNumber of tracks traversedNext track accessedNumber of tracks traversed11010110101201012010186