下载文档原格式
操作系统设计与实现课后习题答案（英⽂）OPERATING SYSTEMS: DESIGN AND IMPLEMENTATIONTHIRD EDITIONPROBLEM SOLUTIONSANDREW S.TANENBAUMVrije UniversiteitAmsterdam,The NetherlandsALBERT S.WOODHULLAmherst,MassachusettsPRENTICE HALLUPPER SADDLE RIVER,NJ07458SOLUTIONS TO CHAPTER1PROBLEMS1.An operating system must provide the users with an extended(i.e.,virtual)machine,and it must manage the I/O devices and other system resources.2.In kernel mode,every machine instruction is allowed,as is access to all theI/O devices.In user mode,many sensitive instructions are prohibited.Operating systems use these two modes to encapsulate user programs.Run-ning user programs in user mode keeps them from doing I/O and prevents them from interfering with each other and with the kernel.3.Multiprogramming is the rapid switching of the CPU between multipleprocesses in memory.It is commonly used to keep the CPU busy while one or more processes are doing I/O.4.Input spooling is the technique of reading in jobs,for example,from cards,onto the disk,so that when the currently executing processes are?nished, there will be work waiting for the CPU.Output spooling consists of?rst copying printable?les to disk before printing them,rather than printing directly as the output is generated.Input spooling on a personal computer is not very likely,but output spooling is.5.The prime reason for multiprogramming is to give the CPU something to dowhile waiting for I/O to complete.If there is no DMA,the CPU is fully occu-pied doing I/O,so there is nothing to be gained(at least in terms of CPU utili-zation)by multiprogramming.No matter how much I/O a program does,the CPU will be100percent busy.This of course assumes the major delay is the wait while data is copied.A CPU could do other work if the I/O were slow for other reasons(arriving on a serial line,for instance).6.Second generation computers did not have the necessary hardware to protectthe operating system from malicious user programs.7.Choices(a),(c),and(d)should be restricted to kernel mode.8.Personal computer systems are always interactive,often with only a singleuser.Mainframe systems nearly always emphasize batch or timesharing with many users.Protection is much more of an issue on mainframe systems,as is ef?cient use of all resources.9.Arguments for closed source are that the company can vet the programmers,establish programming standards,and enforce a development and testing methodology.The main arguments for open source is that many more people look at the code,so there is a form of peer review and the odds of a bug slip-ping in are muchsmaller with so much more inspection.2PROBLEM SOLUTIONS FOR CHAPTER110.The?le will be executed.11.It is often essential to have someone who can do things that are normally for-bidden.For example,a user starts up a job that generates an in?nite amount of output.The user then logs out and goes on a three-week vacation to Lon-don.Sooner or later the disk will?ll up,and the superuser will have to manu-ally kill the process and remove the output?le.Many other such examples exist.12.Any?le can easily be named using its absolute path.Thus getting rid ofworking directories and relative paths would only be a minor inconvenience.The other way around is also possible,but trickier.In principle if the working directoryis,say,/home/ast/projects/research/proj1one could refer to the password?le as../../../../etc/passwd,but it is very clumsy.This would not be a practical way of working.13.The process table is needed to store the state of a process that is currentlysuspended,either ready or blocked.It is not needed in a single process sys-tem because the single process is never suspended.14.Block special?les consist of numbered blocks,each of which can be read orwritten independently of all the other ones.It is possible to seek to any block and start reading or writing.This is not possible with character special?les.15.The read works /doc/d0db25e29b89680203d82542.html er2’s directory entry contains a pointer to thei-node of the?le,and the reference count in the i-node was incremented when user2linked to it.So the reference count will be nonzero and the?le itself will not be removed when user1removes his directory entry for it.Only when all directory entries for a?le have been removed will its i-node and data actually vanish.16.No,they are not so essential.In the absence of pipes,program1could writeits output to a?le and program2could read the?le.While this is less ef?cient than using a pipe between them,and uses unnecessary disk space,in most circumstances it would work adequately.17.The display command and reponse for a stereo or camera is similar to theshell.It is a graphical command interface to the device.18.Windows has a call spawn that creates a new process and starts a speci?cprogram in it.It is effectively a combination of fork and exec.19.If an ordinary user could set the root directory anywhere in the tree,he couldcreate a?le etc/passwd in his home directory,and then make that the root directory.He could then execute some command,such as su or login that reads the password?le,and trick the system into using his password?le, instead of the real one.PROBLEM SOLUTIONS FOR CHAPTER13 20.The getpid,getuid,getgid,and getpgrp,calls just extract a word from the pro-cess table and return it.They will execute very quickly.They are all equally fast.21.The system calls can collectively use500million instructions/sec.If eachcall takes1000instructions,up to500,000system calls/sec are possible while consuming only half the CPU.22.No,unlink removes any?le,whether it be for a regular?le or a special?le.23.When a user program writes on a?le,the data does not really go to the disk.It goes to the buffer cache.The update program issues SYNC calls every30 seconds to force the dirty blocks in the cache onto the disk,in order to limit the potential damage that a system crash could cause.24.No.What is the point of asking for a signal after a certain number of secondsif you are going to tell the system not to deliver it to you?25.Yes it can,especially if the system is a message passing system.26.When a user program executes a kernel-mode instruction or does somethingelse that is not allowed in user mode,the machine must trap to report the attempt.The early Pentiums often ignored such instructions.This made them impossible to fully virtualize and run an arbitrary unmodi?ed operating sys-tem in user mode. SOLUTIONS TO CHAPTER2PROBLEMS1.It is central because there is so much parallel or pseudoparallel activity—multiple user processes and I/O devices running at once.The multiprogram-ming model allows this activity to be described and modeled better.2.The states are running,blocked and ready.The running state means the pro-cess has the CPU and is executing.The blocked state means that the process cannot run because it is waiting for an external event to occur,such as a mes-sage or completion of I/O.The ready state means that the process wants to run and is just waiting until the CPU is available.3.You could have a register containing a pointer to the current process tableentry.When I/O completed,the CPU would store the current machine state in the current process table entry.Then it would go to the interrupt vector for the interrupting device and fetch a pointer to another process table entry(the service procedure).This process would then be started up.4.Generally,high level languages do not allow one the kind of access to CPUhardware that is required.For instance,an interrupt handler may be required to enable and disable the interrupt servicing a particular device,or to4PROBLEM SOLUTIONS FOR CHAPTER2manipulate data within a process’stack area.Also,interrupt service routines must execute as rapidly as possible.5.The?gure looks like this6.It would be dif?cult,if not impossible,to keep the?le system consistent usingthe model in part(a)of the?gure.Suppose that a client process sends a request to server process1to update a?le.This process updates the cache entry in its memory.Shortly thereafter,another client process sends a request to server2to read that?le.Unfortunately,if the?le is also cached there, server2,in its innocence,will return obsolete data.If the?rst process writes the? le through to the disk after caching it,and server2checks the disk on every read to see if its cached copy is up-to-date,the system can be made to work,but it is precisely all these disk accesses that the caching system is try-ing to avoid.7.A process is a grouping of resources:an address space,open?les,signalhandlers,and one or more threads.A thread is just an execution unit.8.Each thread calls procedures on its own,so it must have its own stack for thelocal variables,return addresses,and so on.9.A race condition is a situation in which two(or more)process are about toperform some action.Depending on the exact timing,one or other goes?rst.If one of the processes goes?rst,everything works,but if another one goes ?rst,a fatal error occurs.10.One person calls up a travel agent to?nd about price and availability.Thenhe calls the other person for approval.When he calls back,the seats are gone.11.A possible shell script might be:if[!–f numbers];echo0>numbers;?count=0while(test$count!=200)docount=‘expr$count+1‘PROBLEM SOLUTIONS FOR CHAPTER25n=‘tail–1numbers‘expr$n+1>>numbersdoneRun the script twice simultaneously,by starting it once in the background (using&)and again in the foreground.Then examine the?le numbers.It will probably start out looking like an orderly list of numbers,but at some point it will lose its orderliness,due to the race condition created by running two copies of the script.The race can be avoided by having each copy of the script test for and set a lock on the?le before entering the critical area,and unlocking it upon leaving the critical area.This can be done like this: if ln numbers numbers.lockthenn=‘tail–1numbers‘expr$n+1>>numbersrm numbers.lockThis version will just skip a turn when the?le is inaccessible,variant solu-tions could put the process to sleep,do busy waiting,or count only loops in which the operation is successful.12.Yes,at least in MINIX3.Since LINK is a system call,it will activate serverand task level processes,which,because of the multi-level scheduling of MINIX3,will receive priority over user processes.So one would expect that from the point of view of a user process,linking would be equivalent to an atomic act,and another user process could not interfere.Also,even if another user process gets a chance to run before the LINK call is complete,perhaps because the disk task blocks looking for the inode and directory,the servers and tasks complete what they are doing before accepting more work.So, even if two processes try to make a LINK call at the same time,whichever one causes a software interrupt?rst should have its LINK call completed?rst.13.Yes,it still works,but it still is busy waiting,of course.14.Yes it can.The memory word is used as a?ag,with0meaning that no one isusing the critical variables and1meaning that someone is using them.Put a 1in the register,and swap the memory word and the register.If the register contains a0after the swap,access has been granted.If it contains a1,access has been denied.When a process is done,it stores a0in the?ag in memory.15.To do a semaphore operation,the operating system?rst disables interrupts.Then it reads the value of the semaphore.If it is doing a DOWN and the semaphore is equal to zero,it puts the calling process on a list of blocked processes associated with the semaphore.If it is doing an UP,it must check6PROBLEM SOLUTIONS FOR CHAPTER2to see if any processes are blocked on the semaphore.If one or more processes are blocked,one of then is removed from the list of blocked processes and made runnable.When all these operations have been com-pleted,interrupts can be enabled again.16.Associated with each counting semaphore are two binary semaphores,M,used for mutual exclusion,and B,used for blocking.Also associated with each counting semaphore is a counter that holds the number of UP s minus the number of DOWN s,and a list of processes blocked on that semaphore.To implement DOWN,a process?rst gains exclusive access to the semaphores, counter,and list by doing a DOWN on M.It then decrements the counter.If it is zero or more,it just does an UP on M and exits.If M is negative,the pro-cess is put on the list of blocked processes.Then an UP is done on M and a DOWN is done on B to block the process.To implement UP,?rst M is DOWN ed to get mutual exclusion,and then the counter is incremented.If it is more than zero,no one was blocked,so all that needs to be done is to UP M.If,however,the counter is now negative or zero,some process must be removed from the list.Finally,an UP is done on B and M in that order.17.With round robin scheduling it works.Sooner or later L will run,and eventu-ally it will leave its critical region.The point is,with priority scheduling,L never gets to run at all;with round robin,it gets a normal time slice periodi-cally,so it has the chance to leave its critical region.18.It is very expensive to implement.Each time any variable that appears in apredicate on which some process is waiting changes,the run-time system must re-evaluate the predicate to see if the process can be unblocked.With the Hoare and Brinch Hansen monitors,processes can only be awakened on a SIGNAL primitive. 19.The employees communicate by passing messages:orders,food,and bags inthis case.In MINIX terms,the four processes are connected by pipes.20.It does not lead to race conditions(nothing is ever lost),but it is effectivelybusy waiting.21.If a philosopher blocks,neighbors can later see that he is hungry by checkinghis state,in test,so he can be awakened when the forks are available.22.The change would mean that after a philosopher stopped eating,neither of hisneighbors could be chosen next.With only two other philosophers,both of them neighbors,the system woulddeadlock.With100philosophers,all that would happen would be a slight loss of parallelism.23.Variation1:readers have priority.No writer may start when a reader isactive.When a new reader appears,it may start immediately unless a writer is currently active.When a writer?nishes,if readers are waiting,they are allPROBLEM SOLUTIONS FOR CHAPTER 27started,regardless of the presence of waiting writers.Variation 2:Writers have priority.No reader may start when a writer is waiting.When the last active process ?nishes,a writer is started,if there is one,otherwise,all the readers (if any)are started.Variation 3:symmetric version.When a reader is active,new readers may start immediately.When a writer ?nishes,a new writer has priority,if one is waiting.In other words,once we have started reading,we keep reading until there are no readers left.Similarly,once we have started writing,all pending writers are allowed to run.24.It will need nT sec.25.If a process occurs multiple times in the list,it will get multiple quanta percycle.This approach could be used to give more important processes a larger share of the CPU.26.The CPU ef?ciency is the useful CPU time divided by the total CPU time.When Q ≥T ,the basic cycle is for the process to run for T and undergo a pro-cess switch for S .Thus (a)and (b)have an ef? ciency of T /(S +T ).When the quantum is shorter than T ,each run of T will require T /Q process switches,wasting a time ST /Q .The ef?ciency here is thenT +ST /QT which reduces to Q /(Q +S ),which is the answer to (c).For (d),we just sub-stitute Q for S and ?nd that the ef?ciency is50percent.Finally,for (e),as Q →0the ef?ciency goes to 0.27.Shortest job ?rst is the way to minimize average response time.0<x ≤3:x="" ,3,5,6,9.<="" p="" bdsfid="201">。
第1章计算机系统概述1.1、图1.3中的理想机器还有两条I/O指令：0011 = 从I/O中载入AC0111 = 把AC保存到I/O中在这种情况下，12位地址标识一个特殊的外部设备。
请给出以下程序的执行过程（按照图1.4的格式）：1.从设备5中载入AC。
2.加上存储器单元940的内容。
3.把AC保存到设备6中。
假设从设备5中取到的下一个值为3940单元中的值为2。
答案：存储器（16进制内容）：300：3005；301：5940；302：7006步骤1：3005－>IR；步骤2：3－>AC步骤3：5940－>IR；步骤4：3＋2＝5－>AC步骤5：7006－>IR：步骤6：AC－>设备61.2、本章中用6步来描述图1.4中的程序执行情况，请使用MAR和MBR扩充这个描述。
答案：1. a. PC中包含第一条指令的地址300，该指令的内容被送入MAR中。
b. 地址为300的指令的内容（值为十六进制数1940）被送入MBR，并且PC增1。
这两个步骤是并行完成的。
c. MBR中的值被送入指令寄存器IR中。
2. a. 指令寄存器IR中的地址部分（940）被送入MAR中。
b. 地址940中的值被送入MBR中。
c. MBR中的值被送入AC中。
3. a. PC中的值（301）被送入MAR中。
b. 地址为301的指令的内容（值为十六进制数5941）被送入MBR，并且PC增1。
c. MBR中的值被送入指令寄存器IR中。
4. a. 指令寄存器IR中的地址部分（941）被送入MAR中。
b. 地址941中的值被送入MBR中。
c. AC中以前的内容和地址为941的存储单元中的内容相加，结果保存到AC中。
5. a. PC中的值（302）被送入MAR中。
b. 地址为302的指令的内容（值为十六进制数2941）被送入MBR，并且PC增1。
c. MBR中的值被送入指令寄存器IR中。
6. a. 指令寄存器IR中的地址部分（941）被送入MAR中。
操作系统精髓与设计原理第五版课后题答案C HAPTER 2O PERATING S YSTEMO VERVIEWReview Questions2.1 Convenience: An operating system makes a computer more convenientto use. Efficiency: An operating system allows the computer systemresources to be used in an efficient manner. Ability to evolve: Anoperating system should be constructed in such a way as to permit theeffective development, testing, and introduction of new systemfunctions without interfering with service.2.5 The execution context, or process state, is the internal data by which theoperating system is able to supervise and control the process. Thisinternal information is separated from the process, because theoperating system has information not permitted to the process. Thecontext includes all of the information that the operating system needsto manage the process and that the processor needs to execute theprocess properly. The context includes the contents of the variousprocessor registers, such as the program counter and data registers. Italso includes information of use to the operating system, such as thepriority of the process and whether the process is waiting for thecompletion of a particular I/O event.Problems2.1 The answers are the same for (a) and (b). Assume that althoughprocessor operations cannot overlap, I/O operations can.1 Job: TAT = NT Processor utilization = 50%2 Jobs: TAT = NT Processor utilization = 100%4 Jobs: TAT = (2N – 1)NT Processor utilization = 100% 2.4 A system call is used by an application program to invoke a functionprovided by the operating system. Typically, the system call results intransfer to a system program that runs in kernel mode.C HAPTER 3P ROCESS D ESCRIPTION ANDC ONTROLReview Questions3.5 Swapping involves moving part or all of a process from main memoryto disk. When none of the processes in main memory is in 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 executedand the memory areas that can be accessed. This is to protect theoperating system from damage or alteration. In kernel mode, theoperating system does not have these restrictions, so that it canperform its tasks.Problems3.1 •Creation and deletion of both user and system processes. Theprocesses in the system can execute concurrently for informationsharing, computation speedup, modularity, and convenience.Concurrent execution requires a mechanism for process creation and deletion. The required resources are given to the process when it iscreated, or allocated to it while it is running. When the processterminates, the OS needs to reclaim any reusable resources.•Suspension and resumpti on of processes. In process scheduling, theOS needs to change the process's state to waiting or ready state when it is waiting for some resources. When the required resources areavailable, OS needs to change its state to running state to resume itsexecution.•Provision of mechanism for process synchronization. Cooperatingprocesses may share data. Concurrent access to shared data mayresult in data inconsistency. OS has to provide mechanisms forprocesses synchronization to ensure the orderly execution ofcooperating processes, so that data consistency is maintained.•Provision of mechanism for process communication. The processesexecuting under the OS may be either independent processes orcooperating processes. Cooperating processes must have the meansto communicate with each other.•Provision of mechanisms for deadlock handling. In amultiprogramming environment, several processes may compete fora finite number of resources. If a deadlock occurs, all waitingprocesses will never change their waiting state to running state again, resources are wasted and jobs will never be completed.3.3Figure 9.3 shows the result for a single blocked queue. The figurereadily generalizes to multiple blocked queues.C HAPTER 4P ROCESS D ESCRIPTION ANDC ONTROLReview Questions4.2 Less state information is involved.4.5 Address space, file resources, execution privileges are examples.4.6 1. Thread switching does not require kernel mode privileges becauseall of the thread management data structures are within the useraddress space of a single process. Therefore, the process does notswitch to the kernel mode to do thread management. This saves theoverhead of two mode switches (user to kernel; kernel back to user). 2.Scheduling can be application specific. One application may benefit most from a simple round-robin scheduling algorithm, while another might benefit from a priority-based scheduling algorithm. Thescheduling algorithm can be tailored to the application withoutdisturbing the underlying OS scheduler. 3. ULTs can run on anyoperating system. No changes are required to the underlying kernel to support ULTs. The threads library is a set of application-level utilities shared by all applications.4.7 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 within the process are blocked. 2. In a pure ULT strategy, a multithreaded application cannot take advantage ofmultiprocessing. A kernel assigns one process to only one processor ata time. Therefore, only a single thread within a process can execute at atime.Problems4.2Because, with ULTs, the thread structure of a process is not visible to theoperating system, which only schedules on the basis of processes.C HAPTER 5C ONCURRENCY:M UTUALE XCLUSION ANDS YNCHRONIZATIONReview Questions5.1 Communication among processes, sharing of and competing forresources, synchronization of the activities of multiple processes, and allocation of processor time to processes.5.9 A binary semaphore may only take on the values 0 and 1. A generalsemaphore may take on any integer value.Problems5.2 ABCDE; ABDCE; ABDEC; ADBCE; ADBEC; ADEBC;DEABC; DAEBC; DABEC; DABCE5.5Consider the case in which turn equals 0 and P(1) sets blocked[1] totrue and then finds blocked[0] set to false. P(0) will then setblocked[0] to true, find turn = 0, and enter its critical section. P(1) will then assign 1 to turn and will also enter its critical section.C HAPTER 6C ONCURRENCY:D EADLOCK ANDS TARVATIONReview Questions6.2 Mutual exclusion. Only one process may use a resource at a time. Holdand wait. A process may hold allocated resources while awaitingassignment of others. No preemption. No resource can be forciblyremoved from a process holding it.6.3 The above three conditions, plus: Circular wait. A closed chain ofprocesses exists, such that each process holds at least one resourceneeded by the next process in the chain.Problems6.4 a. 0 0 0 00 7 5 06 6 2 22 0 0 20 3 2 0b. to d. Running the banker's algorithm, we see processes can finishin the order p1, p4, p5, p2, p3.e. Change available to (2,0,0,0) and p3's row of "still needs" to (6,5,2,2).Now p1, p4, p5 can finish, but with available now (4,6,9,8) neitherp2 nor p3's "still needs" can be satisfied. So it is not safe to grantp3's request.6.5 1. W = (2 1 0 0)2. Mark P3; W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0)3. Mark P2; W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1)4. Mark P1; no deadlock detectedReview Questions7.1 Relocation, protection, sharing, logical organization, physicalorganization.7.7 A logical address is a reference to a memory location independent ofthe current assignment of data to memory; a translation must be made to a physical address before the memory access can be achieved. A relative address is a particular example of logical address, in which the address is expressed as a location relative to some known point, usually the beginning of the program. A physical address, or absolute address, is an actual location in main memory.Problems7.6 a. The 40 M block fits into the second hole, with a starting address of80M. The 20M block fits into the first hole, with a starting address of 20M. The 10M block is placed at location 120M.40M 40M 60M 40M 40M 40M 30Mb. The three starting addresses are 230M, 20M, and 160M, for the 40M, 20M, and 10M blocks, respectively. 40M 60M 60M 40M 40M 40M 30Mc. The three starting addresses are 80M, 120M, and 160M, for the 40M,20M, and 10M blocks, respectively. C HAPTER 7M EMORY M ANAGEMENT7.12 a. The number of bytes in the logical address space is (216 pages) (210bytes/page) = 226 bytes. Therefore, 26 bits are required for the logical address.b. A frame is the same size as a page, 210 bytes.c. The number of frames in main memory is (232 bytes of mainmemory)/(210 bytes/frame) = 222 frames. So 22 bits is needed tospecify the frame.d. There is one entry for each page in the logical address space.Therefore there are 216 entries.e. In addition to the valid/invalid bit, 22 bits are needed to specify theframe location in main memory, for a total of 23 bits.30M40M40M60M40M40M40Md. The three starting addresses are 80M, 230M, and 360M, for the 40M,20M, and 10M blocks, respectively.C HAPTER 8V IRTUAL M EMORYReview Questions8.1 Simple paging: all the pages of a process must be in main memory forprocess to run, unless overlays are used. Virtual memory paging: not all pages of a process need be in main memory frames for the process to run.; pages may be read in as needed8.2 A phenomenon in virtual memory schemes, in which the processorspends most of its time swapping pieces rather than executinginstructions.Problems8.1 a. Split binary address into virtual page number and offset; use VPNas index into page table; extract page frame number; concatenateoffset to get physical memory addressb. (i) 1052 = 1024 + 28 maps to VPN 1 in PFN 7, (7 ⨯ 1024+28 = 7196)(ii) 2221 = 2 ⨯ 1024 + 173 maps to VPN 2, page fault(iii) 5499 = 5 ⨯ 1024 + 379 maps to VPN 5 in PFN 0, (0 ⨯ 1024+379 =379)8.4 a. PFN 3 since loaded longest ago at time 20b. PFN 1 since referenced longest ago at time 160c. Clear R in PFN 3 (oldest loaded), clear R in PFN 2 (next oldestloaded), victim PFN is 0 since R=0d. Replace the page in PFN 3 since VPN 3 (in PFN 3) is used furthestin the futuree. There are 6 faults, indicated by **4 0 0 0 *2*4 2*1**3 2VPN of pages in memory in LRU order 32143243434242241241243122Review Questions9.1 Long-term scheduling: The decision to add to the pool of processes tobe executed. Medium-term scheduling: The decision to add to thenumber of processes that are partially or fully in main memory.Short-term scheduling: The decision as to which available process willbe executed by the processor9.3 Turnaround time is the total time that a request spends in the system(waiting time plus service time. Response time is the elapsed timebetween the submission of a request until the response begins toappear as output.Problems9.1 Each square represents one time unit; the number in the square refersto the currently-running process.FCFS A A A B B B B B C C D D D D D E E E E E RR, q = 1 A B A B C A B C B D B D E D E D E D E E RR, q = 4 A A A B B B B C C B D D D D E E E E D E SPN A A A C C B B B B B D D D D D E E E E E SRT A A A C C B B B B B D D D D D E E E E E HRRN A A A B B B B B C C D D D D D E E E E E Feedback, q = 1 A B A C B C A B B D B D E D E D E D E EFeedback, q = 2i A B A A C B B C B B D D E D D E E D E EC HAPTER 9U NIPROCESSORS CHEDULINGA B C D ET a0 1 3 9 12T s 3 5 2 5 5 FCFS T f 3 8 10 15 20T r 3.00 7.00 7.00 6.00 8.00 6.20T r/T s 1.00 1.40 3.50 1.20 1.60 1.74 RR qT f 6.00 11.00 8.00 18.00 20.00= 1T r 6.00 10.00 5.00 9.00 8.00 7.60T r/T s 2.00 2.00 2.50 1.80 1.60 1.98RR qT f 3.00 10.00 9.00 19.00 20.00= 4T r 3.00 9.00 6.00 10.00 8.00 7.20T r/T s 1.00 1.80 3.00 2.00 1.60 1.88 SPN T f 3.00 10.00 5.00 15.00 20.00T r 3.00 9.00 2.00 6.00 8.00 5.60T r/T s 1.00 1.80 1.00 1.20 1.60 1.32SRT T f 3.00 10.00 5.00 15.00 20.00T r 3.00 9.00 2.00 6.00 8.00 5.60T r/T s 1.00 1.80 1.00 1.20 1.60 1.32 HRRT f 3.00 8.00 10.00 15.00 20.00NT r 3.00 7.00 7.00 6.00 8.00 6.20T r/T s 1.00 1.40 3.50 1.20 1.60 1.74FB qT f7.00 11.00 6.00 18.00 20.00= 1T r7.00 10.00 3.00 9.00 8.00 7.40T r/T s 2.33 2.00 1.50 1.80 1.60 1.85 FB T f 4.00 10.00 8.00 18.00 20.00q = 2i T r 4.00 9.00 5.00 9.00 8.00 7.00 T r/T s 1.33 1.80 2.50 1.80 1.60 1.819.16 a. Sequence with which processes will get 1 min of processor time:1 2 3 4 5 Elapsed timeA A A A A A A A A A A A A A BBBBBBBBCCDDDDDEEEEEEEEEEE1015192327303336384042434445The turnaround time for each process:A = 45 min,B = 35 min,C = 13 min,D = 26 min,E = 42 minThe average turnaround time is = (45+35+13+26+42) / 5 = 32.2 min b.Priority Job Turnaround Time3 4 6 7 9 BEACD99 + 12 = 2121 + 15 = 3636 + 3 = 3939 + 6 = 45The average turnaround time is: (9+21+36+39+45) / 5 = 30 min c.Job Turnaround TimeA B C D E 1515 + 9 = 24 24 + 3 = 27 27 + 6 = 33 33 + 12 = 45The average turnaround time is: (15+24+27+33+45) / 5 = 28.8 min d.RunningTimeJob Turnaround Time6 9 12 15 DBEA3 + 6 = 99 + 9 = 1818 + 12 = 3030 + 15 = 45The average turnaround time is: (3+9+18+30+45) / 5 = 21 minC HAPTER 10M ULTIPROCESSOR AND R EAL-T IMES CHEDULINGReview Questions10.1 Fine: Parallelism inherent in a single instruction stream. Medium: Parallelprocessing or multitasking within a single application. Coarse:Multiprocessing of concurrent processes in a multiprogrammingenvironment. Very Coarse: Distributed processing across network nodes toform a single computing environment. Independent: Multiple unrelatedprocesses.10.4 A hard real-time task is one that must meet its deadline; otherwise it willcause undesirable damage or a fatal error to the system. A soft real-timetask has an associated deadline that is desirable but not mandatory; it stillmakes sense to schedule and complete the task even if it has passed itsdeadline.Problems10.1 For fixed priority, we do the case in which the priority is A, B, C. Eachsquare represents five time units; the letter in the square refers to thecurrently-running process. The first row is fixed priority; the secondrow is earliest deadline scheduling using completion deadlines.A AB B A AC C A A B B A A C C A AA AB B AC C A C A A B B A A C C C A AFor fixed priority scheduling, process C always misses its deadline.10.4normal executionexecution in critical sectionT 1T 2T 3s locked by T 3s unlockeds locked by T 1Once T 3 enters its critical section, it is assigned a priority higher than T1. When T3 leaves its critical section, it is preempted by T 1.C HAPTER 11I/O M ANAGEMENT AND D ISK S CHEDULING Review Questions11.1 Programmed I/O: The processor issues an I/O command, on behalf of aprocess, to an I/O module; that process then busy-waits for theoperation to be completed before proceeding. Interrupt-driven I/O:The processor issues an I/O command on behalf of a process,continues to execute subsequent instructions, and is interrupted by the I/O module when the latter has completed its work. The subsequent instructions may be in the same process, if it is not necessary for that process to wait for the completion of the I/O. Otherwise, the process is suspended pending the interrupt and other work is performed. Direct memory access (DMA): A DMA module controls the exchange of data between main memory and an I/O module. The processor sends arequest for the transfer of a block of data to the DMA module and is interrupted only after the entire block has been transferred.11.5 Seek time, rotational delay, access time.Problems11.1 If the calculation time exactly equals the I/O time (which is the mostfavorable situation), both the processor and the peripheral devicerunning 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 timewith buffering is max(C, T), while the running time without buffering is C + T; and of course ((C + T)/2) ≤ max(C, T) ≤ (C + T). Source:[KNUT97].11.3 Disk head is initially moving in the direction of decreasing tracknumber:FIFO SSTF SCAN C-SCANNext track accessed Numberof trackstraversedNexttrackaccessedNumberof trackstraversedNexttrackaccessedNumberof trackstraversedNexttrackaccessedNumberof trackstraversed27 73 110 10 64 36 64 36129 102 120 10 41 23 41 23 110 19 129 9 27 14 27 14 186 76 147 18 10 17 10 17 147 39 186 39 110 100 186 17641 106 64 122 120 10 147 3910 31 41 23 129 9 129 1864 54 27 14 147 18 120 9120 56 10 17 186 39 110 10 Average 61.8 Average 29.1 Average 29.6 Average 38If the disk head is initially moving in the direction of increasing tracknumber, only the SCAN and C-SCAN results change:SCAN C-SCANNext track accessed Numberof trackstraversedNexttrackaccessedNumberof trackstraversed110 10 110 10120 10 120 10129 9 129 9147 18 147 18186 39 186 3964 122 10 17641 23 27 1727 14 41 1410 17 64 23 Average 29.1 Average 35.1Review Questions12.1 A field is the basic element of data containing a single value. A recordis a collection of related fields that can be treated as a unit by some application program.12.5 Pile: Data are collected in the order in which they arrive. Each recordconsists of one burst of data. Sequential file: A fixed format is used for records. All records are of the same length, consisting of the same number of fixed-length fields in a particular order. Because the length and position of each field is known, only the values of fields need to be stored; the field name and length for each field are attributes of the file structure. Indexed sequential file: The indexed sequential file maintains the key characteristic of the sequential file: records are organized in sequence based on a key field. Two features are added; an index to the file to support random access, and an overflow file. The index provides a lookup capability to reach quickly the vicinity of a desired record. The overflow file is similar to the log file used with a sequential file, but is integrated so that records in the overflow file are located by following a pointer from their predecessor record. Indexed file: Records are accessed only through their indexes. The result is that there is now no restriction on the placement of records as long as a pointer in at least one index refers to that record. Furthermore,variable-length records can be employed. Direct, or hashed, file: The direct file makes use of hashing on the key value.Problems12.1 Fixed blocking: F = largest integer B RWhen records of variable length are packed into blocks, data formarking the record boundaries within the block has to be added to separate the records. When spanned records bridge block boundaries, some reference to the successor block is also needed. One possibility is a length indicator preceding each record. Another possibility is a special separator marker between records. In any case, we can assume that each record requires a marker, and we assume that the size of a marker is about equal to the size of a block pointer [WEID87]. For spanned blocking, a block pointer of size P to its successor block may C HAPTER 12F ILE M ANAGEMENTbe included in each block, so that the pieces of a spanned record can easily be retrieved. Then we haveVariable-length spanned blocking: F=B-P R+PWith unspanned variable-length blocking, an average of R/2 will be wasted because of the fitting problem, but no successor pointer is required:Variable-length unspanned blocking: F=B-R2 R+P12.3 a. Indexedb. Indexed sequentialc. Hashed or indexed。
第1章计算机系统概述1.1、图1.3中的理想机器还有两条I/O指令：0011 = 从I/O中载入AC0111 = 把AC保存到I/O中在这种情况下，12位地址标识一个特殊的外部设备。
请给出以下程序的执行过程（按照图1.4的格式）：1.从设备5中载入AC。
2.加上存储器单元940的内容。
3.把AC保存到设备6中。
假设从设备5中取到的下一个值为3940单元中的值为2。
答案：存储器（16进制内容）：300：3005；301：5940；302：7006步骤1：3005－>IR；步骤2：3－>AC步骤3：5940－>IR；步骤4：3＋2＝5－>AC步骤5：7006－>IR：步骤6：AC－>设备61.2、本章中用6步来描述图1.4中的程序执行情况，请使用MAR和MBR扩充这个描述。
答案：1. a. PC中包含第一条指令的地址300，该指令的内容被送入MAR中。
b. 地址为300的指令的内容（值为十六进制数1940）被送入MBR，并且PC增1。
这两个步骤是并行完成的。
c. MBR中的值被送入指令寄存器IR中。
2. a. 指令寄存器IR中的地址部分（940）被送入MAR中。
b. 地址940中的值被送入MBR中。
c. MBR中的值被送入AC中。
3. a. PC中的值（301）被送入MAR中。
b. 地址为301的指令的内容（值为十六进制数5941）被送入MBR，并且PC增1。
c. MBR中的值被送入指令寄存器IR中。
4. a. 指令寄存器IR中的地址部分（941）被送入MAR中。
b. 地址941中的值被送入MBR中。
c. AC中以前的内容和地址为941的存储单元中的内容相加，结果保存到AC中。
5. a. PC中的值（302）被送入MAR中。
b. 地址为302的指令的内容（值为十六进制数2941）被送入MBR，并且PC增1。
c. MBR中的值被送入指令寄存器IR中。
6. a. 指令寄存器IR中的地址部分（941）被送入MAR中。
操作系统一精髓与设计原理第五版选择题与答案英文版第一到第十一章第一章The general role of an operating system is to: da. None of the aboveb. Manage files for application programsc. Act as an interface between various computersd. Provide a set of services to system usersInformation that must be saved prior to the processor transferring control to theinterrupt handler routine includes:ba. None of the aboveb. Processor Status Word (PSW) & Location of next instructionc. Processor Status Word (PSW)d. Processor Status Word (PSW) & Contents of processor registersOne accepted method of dealing with multiple interrupts is to: 选择一个答案aa. Define priorities for the interruptsb. None of the abovec. Disable all interrupts except those of highest priorityd. Service them in round-robin fashionIn a uniprocessor system, multiprogramming increases processor efficiencyby:选择一个答案da. Increasing processor speedb. Eliminating all idle processor cyclesc. All of the aboved. Taking advantage of time wasted by long wait interrupt handlingAs one proceeds down the memory hierarchy (i.e., from inboard memory to offlinestorage), the following condition(s) apply: c选择一个答案a. Decreasing capacityb. Increasing cost per bitc. Increasing access timed. All of the aboveSmall, fast memory located between the processor and main memory is called 选择一个答案ba. None of the aboveb. Cache memoryc. WORM memoryd. CD-RW memoryWhen a new block of data is written into cache memory, the following determines whichcache location the block will occupy: 选择一个答案aa. None of the aboveb. Write policyc. Cache sized. Block sizeThe four main structural elements of a computer system are:选择一个答案ba. Processor, Registers, I/O Modules & Main Memoryb. Processor, Main Memory, I/O Modules & System Busc. None of the aboved. Processor, Registers, Main Memory & System BusThe two basic types of processor registers are:选择一个答案aa. User-visible and Control/Status registersb. User-visible and user-invisible registersc. None of the aboved. Control and Status registersAddress registers may contain选择一个答案ca. Memory addresses of datab. Memory addresses of instructionsc. All of the aboved. Partial memory addressesA Control/Status register that contains the address of the next instruction to be fetched iscalled the:选择一个答案ca. All of the aboveb. Program Status Word (PSW)c. Program Counter (PC)d. Instruction Register (IR)The two basic steps used by the processor in instruction processing are:选择一个答案ca. Instruction and Execute cyclesb. Fetch and Instruction cyclesc. Fetch and Execute cyclesd. None of the aboveA fetched instruction is normally loaded into the:选择一个答案ca. Program Counter (PC)b. None of the abovec. Instruction Register (IR)d. Accumulator (AC)A common class of interrupts is选择一个答案da. Programb. I/Oc. Timerd. All of the aboveWhen an external device becomes ready to be serviced by the processor, the devicesends this type of signal to the processor:选择一个答案ba. None of the aboveb. Interrupt signalc. Halt signald. Handler signal第二章A primary objective of an operating system is:选择一个答案aa. All of the aboveb. Conveniencec. Ability to evolved. EfficiencyThe paging system in a memory management system provides for dynamic mappingbetween a virtual address used in a program and:选择一个答案aa. A real address in main memoryb. None of the abovec. A virtual address in main memoryd. A real address in a programRelative to information protection and security in computer systems, accesscontrol typically refers to:选择一个答案da. Proving that security mechanisms perform according to specificationb. None of the abovec. The flow of data within the systemd. Regulating user and process access to various aspects of the systemA common problem with full-featured operating systems, due to their size anddifficulty of the tasks they address, is:选择一个答案da. Latent bugs that show up in the fieldb. Chronically late in deliveryc. Sub-par performanced. All of the aboveA technique in which a process, executing an application, is divided intothreads that can run concurrently is called:选择一个答案da. None of the aboveb. Symmetric multiprocessing (SMP)c. Multiprocessingd. MultithreadingWIN2K supports several types of user applications, including: 选择一个答案ca. None of the aboveb. Linuxc. WIN32d. System 10Key to the success of Linux has been it’s character as a free software packageavailable under the auspices of the:选择一个答案ca. None of the aboveb. Berkeley Software Distributionc. Free Software Foundationd. World Wide Web ConsortiumThe operating system provides many types of services to end-users, programmers andsystem designers, including:选择一个答案ba. Built-in user applicationsb. Error detection and responsec. All of the aboved. Relational database capabilities with the internal file systemThe operating system is unusual in it’s role as a control mechanism, in that:选择一个答案ca. None of the aboveb. It runs on a special processor, completely separated from therest of thesystemc. It frequently relinquishes control of the system processor and mustdepend on the processor to regain control of the systemd. It never relinquishes control of the system processorOperating systems must evolve over time because选择一个答案aa. New hardware is designed and implemented in the computer systemb. Hardware must be replaced when it failsc. All of the aboved. Users will only purchase software that has a current copyright dateA major problem with early serial processing systems was:选择一个答案aa. Setup timeb. Inability to get hardcopy outputc. All of the aboved. Lack of input devicesAn example of a hardware feature that is desirable in a batch-processingsystem is选择一个答案aa. Privileged instructionsb. None of the abovec. A completely accessible memory aread. Large clock cyclesA computer hardware feature that is vital to the effective operation of a multiprogrammingoperating system is:选择一个答案ba. All of the aboveb. I/O interrupts and DMAc. Very large memoryd. Multiple processorsThe principle objective of a time sharing, multiprogramming system is to 选择一个答案ca. Maximize processor useb. Maximize response timec. None of the aboved. Provide exclusive access to hardwareWhich of the following major line of computer system development created problems intiming and synchronization that contributed to the development of the concept of theprocess?选择一个答案ca. Multiprogramming batch operation systemsb. Real time transaction systemsc. All of the aboved. Time sharing systems第三章The behavior of a processor can be characterized by examining: 选择一个答案ba. Multiple process tracesb. The interleaving of the process tracesc. All of the aboved. A single process traceThe Process Image element that contains the modifiable part of the user space is calledthe:a进程镜像=PCB+程序+STACK+可修改的DATAa. None of the aboveb. Process Control Blockc. System Stackd. User Program分数: 7/7The processor execution mode that user programs typically execute in is referred to as:a选择一个答案a. User modeb. None of the abovec. Kernel moded. System modeOne step in the procedure for creating a new process involves:步骤:b选择一个答案a. Allocating space for the processb. All of the abovec. Initializing the process control blockd. Assigning a unique identifierA process switch may occur when the system encounters an interruptcondition, such as that generated by a: 进程切换:TRAP(异常)+系统调用 +INTERRUPT选择一个答案ca. Trapb. Supervisor callc. All of the aboved. Memory fault##操作系统仅仅是一组程序，并被处理器执行，是进程吗,如何控制它, 。
1 3 4 9 7 8 11 12 6章第10章多CPU调度，实时调度第1章作业：习题P25 1.3 1.8 1.9（更正印刷错误106）1.3操作系统的大神求解答假设有一个32位微处理器，其32位的指令由两个域组成：第一个字节包含操作码，其余部分为一个直接操作数或一个操作数地址。
如果微处理器总线具有如下特征，分析a、最大可直接寻址的存储器能力为多少？以字节为单位如果微处理器总线具有如下特征，分析对系统速度的影响：b、（1）一个32位局部地址总线和一个16位局部数据总线，或者（2）一个16位局部地址总线和一个16位局部数据总线。
C、程序计数器和指令寄存器分别需要多少位答案：没必要全写捡重点(定长)指令32位，1字节操作码，则后3字节为立即数或内存地址(a) 最大可直接寻址直接寻址是一种基本的寻址方法，其特点是：在指令格式的地址的字段中直接指出操作数在内存的地址。
由于操作数的地址直接给出而不需要经过某种变换，所以称这种寻址方式为直接寻址方式。
2^24(b) 总线问题地址总线32位，数据总线16位直接寻址存储器24位，bus32位，地址传送一次即可；但指令32位，操作数32位(因为是32位微处理器)，要两次传送地址总线16位，数据总线16位传送地址，传送指令/数据全部需要2次。
地址可视作：先行地址后列地址(c) PC和IR 至少：PC24位，IR8位一般：PC32bit IR 32bit更现实复杂情形：是否分段，使用段寄存器; 直接寻址中逻辑地址/位移/偏移offset，与有效地址effective address区别OS中，逻辑地址与物理地址1.8一个DMA模块从外部设备给内存传送字节，传送速度为9600位每秒（b/s)。
处理器可以每秒100万次的速度取指令，由于DMA活动，处理器的速度将会减慢多少？答案：没必要全写捡重点看清楚题干：每秒100万次取指令，即1M/s取一次指令，不是100M！该CPU主频多少不知，是否使用cache不知，执行一条指令多少时钟周期不知，此题中无需知道还假设，此CPU只取指令要访问内存，执行指令不需要读写数据，不访内存. 还假设DMA 一次访问内存传送1个字节凭什么如此假设？9600b/s=1200B/s 即1s中要传送1200次，而原本CPU要1M次访存，现在因DMA要减少1200次，所以影响是1200/1M=0.12%1.9一台计算机包括一个CPU和一台I/O设备D，通过一条共享总线连接到主存储器M，数据总线的宽度为1个字。
第1章计算机系统概述1.1、图1.3中的理想机器还有两条I/O指令：0011 = 从I/O中载入AC0111 = 把AC保存到I/O中在这种情况下，12位地址标识一个特殊的外部设备。
请给出以下程序的执行过程（按照图1.4的格式）：1.从设备5中载入AC。
2.加上存储器单元940的内容。
3.把AC保存到设备6中。
假设从设备5中取到的下一个值为3940单元中的值为2。
答案：存储器（16进制内容）：300：3005；301：5940；302：7006步骤1：3005－>IR；步骤2：3－>AC步骤3：5940－>IR；步骤4：3＋2＝5－>AC步骤5：7006－>IR：步骤6：AC－>设备61.2、本章中用6步来描述图1.4中的程序执行情况，请使用MAR和MBR扩充这个描述。
答案：1. a. PC中包含第一条指令的地址300，该指令的内容被送入MAR中。
b. 地址为300的指令的内容（值为十六进制数1940）被送入MBR，并且PC增1。
这两个步骤是并行完成的。
c. MBR中的值被送入指令寄存器IR中。
2. a. 指令寄存器IR中的地址部分（940）被送入MAR中。
b. 地址940中的值被送入MBR中。
c. MBR中的值被送入AC中。
3. a. PC中的值（301）被送入MAR中。
b. 地址为301的指令的内容（值为十六进制数5941）被送入MBR，并且PC增1。
c. MBR中的值被送入指令寄存器IR中。
4. a. 指令寄存器IR中的地址部分（941）被送入MAR中。
b. 地址941中的值被送入MBR中。
c. AC中以前的内容和地址为941的存储单元中的内容相加，结果保存到AC中。
5. a. PC中的值（302）被送入MAR中。
b. 地址为302的指令的内容（值为十六进制数2941）被送入MBR，并且PC增1。
c. MBR中的值被送入指令寄存器IR中。
6. a. 指令寄存器IR中的地址部分（941）被送入MAR中。
