现代操作系统参考.pdf
SOLUTIONSSOLUTIONSSOLUTIONSSOLUTIONSTOTOTOTOCHAPTERCHAPTERCHAPTERCHAPTER 1 1 1 1PROBLEMSPROBLEMSPROBLEMSPROBLEMS1.1.1.1.An operating system must provide the users with an extended(i.e.,virtual)machine,and it mustmanage the I/O devices and other system resources.2.2.2.2.Multiprogramming is the rapid switching of the CPU between multiple processes in memory.It iscommonly used to keep the CPU busy while one or more processes are doing I/O.3.3.3.3.Input spooling is the technique of reading in jobs,for example,from cards,onto the disk,so that whenthe currently executing processes are finished,there will be work waiting for the CPU.Output spoolingconsists of first copying printable files to disk before printing them,rather than printing directly as theoutput is generated.Input spooling on a personal computer is not very likely,but output spooling is.4.4.4.4.The prime reason for multiprogramming is to give the CPU something to do while waiting for I/O tocomplete.If there is no DMA,the CPU is fully occupied doing I/O,so there is nothing to be gained(at leastin terms of CPU utilization)by multiprogramming.No matter how much I/O a program does,the CPU willbe 100 percent busy.This of course assumes the major delay is the wait while data are copied.A CPU coulddo other work if the I/O were slow for other reasons(arriving on a serial line,for instance).5.5.5.5.Second generation computers did not have the necessary hardware to protect the operating systemfrom malicious user programs.6.6.6.6.It is still alive.For example,Intel makes Pentium I,II,and III,and 4 CPUs with a variety of differentproperties including speed and power consumption.All of these machines are architecturally compatible.They differ only in price and performance,which is the essence of the family idea.7.7.7.7.A 25 80 character monochrome text screen requires a 2000-byte buffer.The 1024 768 pixel24-bit color bitmap requires 2,359,296 bytes.In 1980 these two options would have cost$10 and$11,520,respectively.For current prices,check on how much RAM currently costs,probably less than$1/MB.8.8.8.8.Choices(a),(c),and(d)should be restricted to kernel mode.9.9.9.9.Personal computer systems are always interactive,often with only a single user.Mainframe systemsnearly always emphasize batch or timesharing with many users.Protection is much more of an issue onmainframe systems,as is efficient use of all resources.10.10.10.10.Every nanosecond one instruction emerges from the pipeline.This means the machine is executing 1billion instructions per second.It does not matter at all how many stages the pipeline has.A 10-stagepipeline with 1 nsec per stage would also execute 1 billion instructions per second.All that matters is howoften a finished instructions pops out the end of the pipeline.11.11.11.11.The manuscript contains 80 50 700=2.8 million characters.This is,of course,impossible to fitinto the registers of any currently available CPU and is too big for a 1-MB cache,but if such hardware wereavailable,the manuscript could be scanned in 2.8 msec from the registers or 5.8 msec from the cache.There are approximately 2700 1024-byte blocks of data,so scanning from the disk would require about 27seconds,and from tape 2 minutes 7seconds.Of course,these times are just to read the data.Processingand rewriting the data would increase the time.12.12.12.12.Logically,it does not matter if the limit register uses a virtual address or a physical address.However,the performance of the former is better.If virtual addresses are used,the addition of the virtual addressand the base register can start simultaneously with the comparison and then can run in parallel.If physicaladdresses are used,the comparison cannot start until the addition is complete,increasing the access time.13.13.13.13.Maybe.If the caller gets control back and immediately overwrites the data,when the write finallyoccurs,the wrong data will be written.However,if the driver first copies the data to a private buffer beforereturning,then the caller can be allowed to continue immediately.Another possibility is to allow the callerto continue and give it a signal when the buffer may be reused,but this is tricky and error prone.14.14.14.14.A trap is caused by the program and is synchronous with it.If the program is run again and again,thetrap will always occur at exactly the same position in the instruction stream.An interrupt is caused by anexternal event and its timing is not reproducible.15.15.15.15.Base=40,000 and limit=10,000.An answer of limit=50,000 is incorrect for the way the system wasdescribed in this book.It could have been implemented that way,but doing so would have required waitinguntil the address+base calculation was completed before starting the limit check,thus slowing down thecomputer.16.16.16.16.The process table is needed to store the state of a process that is currently suspended,either ready orblocked.It is not needed in a single process system because the single process is never suspended.17.17.17.17.Mounting a file system makes any files already in the mount point directory inaccessible,so mountpoints are normally empty.However,a system administrator might want to copy some of the mostimportant files normally located in the mounted directory to the mount point so they could be found intheir normal path in an emergency when the mounted device was being checked or repaired18.18.18.18.Fork can fail if there are no free slots left in the process table(and possibly if there is no memory orswap space left).Execcan fail if the file name give ndoes not exist or is not a valid executable file.Unlink can fail if the file to be unlinked does not exist or the calling process does not have the authority tounlink it.19.19.19.19.If the call fails,for example becausefdis incorrect,it can return 1.It can also fail because the disk isfull and it is not possible to write the number of bytes requested.On a correct termination,it alwaysreturnsnbytes.20.20.20.20.It contains the bytes:1,5,9,2.21.21.21.21.Block special files consist of numbered blocks,each of which can be read or written independently ofall the other ones.It is possible to seek to any block and start reading or writing.This is not possible withcharacter special files.22.22.22.22.System calls do not really have names,other than in a documentation sense.When the libraryprocedurereadtraps to the kernel,it puts the number of the system call in a register or on the stack.Thisnumber is used to index into a table.There is really no name used anywhere.On the other hand,the nameof the library procedure is very important,since that is what appears in the program.23.23.23.23.Yes it can,especially if the kernel is a message-passing system.24.24.24.24.As far as program logic is concerned it does not matter whether a call to a library procedure results ina system call.But if performance is an issue,if a task can be accomplished without a system call theprogram will run faster.Every system call involves overhead time in switching from the user context to thekernel context.Furthermore,on a multiuser system the operating system may schedule another process torun when a system call completes,further slowing the progress in real time of a calling process.25.25.25.25.Several UNIX calls have no counterpart in the Win32 API:Link:a Win32 program cannot refer to a fileby an alternate name or see it in more than one directory.Also,attempting to create a link is a convenientway to test for and create a lock on a file.Mount and umount:a Windows program cannot makeassumptions about standard path names because on systems with multiple disk drives the drive name partof the path may be different.Chmod:Windows programmers have to assume that every user can accessevery file.Kill:Windows programmers cannot kill a misbehaving program that is not cooperating.26.26.26.26.The conversions are straightforward:(a)A micro year is 10-6 365 24 3600=31.536 sec.(b)1000 meters or 1 km.(c)There are 240bytes,which is 1,099,511,627,776 bytes.(d)It is 6 1024kg.SOLUTIONSSOLUTIONSSOLUTIONSSOLUTIONSTOTOTOTOCHAPTERCHAPTERCHAPTERCHAPTER 2 2 2 2PROBLEMSPROBLEMSPROBLEMSPROBLEMS1.1.1.1.The transition from blocked to running is conceivable.Suppose that a process is blocked on I/O andthe I/O finishes.If the CPU is otherwise idle,the process could go directly from blocked to running.Theother missing transition,from ready to blocked,is impossible.A ready process cannot do I/O or anythingelse that might block it.Only a running process can block.2.2.2.2.You could have a register containing a pointer to the current process table entry.When I/Ocompleted,the CPUwould store the current machine state in the current process table entry.Then itwould go to the interrupt vector forthe interrupting device and fetch a pointer to another process table entry(the service procedure).Thisprocess would then be started up.3.3.3.3.Generally,high-level languages do not allow one the kind of access to CPU hardware that is required.For instance,an interrupt handler may be required to enable and disable the interrupt servicing aparticular device,or to manipulate data within a process stack area.Also,interrupt service routines mustexecute as rapidly as possible.4.4.4.4.There are several reasons for using a separate stack for the kernel.Two of them are as follows.First,you do not want the operating system to crash because a poorly written user program does not allow forenough stack space.Second,if the kernel leaves stack data in a user programs memory space uponreturn from a system call,a malicious user might be able to use this data to find out information aboutother processes.5.5.5.5.It would be difficult,if not impossible,to keep the file system consistent.Suppose that a clientprocess sends a request to server process 1 to update a file.This process updates the cache entry in itsmemory.Shortly thereafter,another client process sends a request to server 2 to read that file.Unfortunately,if the file is also cached there,server 2,in its innocence,will return obsolete data.If thefirst process writes the file through to the disk after caching it,and server 2 checks the disk on every readto see if its cached copy is up-to-date,the system can be made to work,but it is precisely all these diskaccesses that the caching system is trying to avoid6.6.6.6.When a thread is stopped,it has values in the registers.They must be saved,just as when the processis stopped the registers must be saved.Timesharing threads is no different than timesharing processes,soeach thread needs itsown register save area.7.7.7.7.No.If a single-threaded process is blocked on the keyboard,it cannot fork.8.8.8.8.A worker thread will block when it has to read a Web page from the disk.If user-level threads arebeing used,this action will block the entire process,destroying the value of multithreading.Thus it isessential that kernel threads are used to permit some threads to block without affecting the others.9.9.9.9.Threads in a process cooperate.They are not hostile to one another.If yielding is needed for the goodof the application,then a thread will yield.After all,it is usually the same programmer who writes thecode for all of them.10.10.10.10.User-level threads cannot be preempted by the clock uless the whole process quantum has beenused up.Kernel-level threads can be preempted individually.In the latter case,if a thread runs too long,the clock will interrupt the current process and thus the current thread.The kernel is free to pick adifferent thread from the same process to run next if it so desires.11.11.11.11.In the single-threaded case,the cache hits take 15 msec and cache misses take 90 msec.Theweighted average is 2/3 15+1/3 90.Thus the mean request takes 40 msec and the servercan do 25 per second.For a multithreaded server,all the waiting for the disk is overlapped,so everyrequest takes 15 msec,and the server can handle 66 2/3 requests per second.12.12.12.12.Yes.If the server is entirely CPU bound,there is no need to have multiple threads.It just addsunnecessary complexity.As an example,consider a telephone directory assistance number(like 555-1212)for an area with 1 million people.If each(name,telephone number)record is,say,64 characters,theentire database takes 64 megabytes,and can easily be kept in the servers memory to provide fast lookup.13.13.13.13.The pointers are really necessary because the size of the global variable is unknown.It could beanything from a character to an array of floating-point numbers.If the value were stored,one would haveto give the size tocreate3global,which is all right,but what type should the second parameter ofset3globalbe,and what type should the value ofread3globalbe?14.14.14.14.It could happen that the runtime system is precisely at the point of blocking or unblocking a thread,and is busy manipulating the scheduling queues.This would be a very inopportune moment for the clockinterrupt handler to begin inspecting those queues to see if it was time to do thread switching,since theymight be in an inconsistent state.One solution is to set a flag when the runtime system is entered.Theclock handler would see this and set its own flag,then return.When the runtime system finished,it wouldcheck the clock flag,see that a clock interrupt occurred,and now run the clock handle15.15.15.15.Yes it is possible,but inefficient.A thread wanting to do a system call first sets an alarm timer,thendoes the call.If the call blocks,the timer returns control to the threads package.Of course,most of thetime the call will not block,and the timer has to be cleared.Thus each system call that might block has tobe executed as three system calls.If timers go off prematurely,all kinds of problems can develop.This isnot an attractive way to build a threads package.16.16.16.16.The priority inversion problem occurs when a low-priority process is in its critical region andsuddenly a high-priority process becomes ready and is scheduled.If it uses busy waiting,it will run forever.With user-level threads,it cannot happen that a low-priority thread is suddenly preempted to allow ahigh-priority thread run.There is no preemption.With kernel-level threads this problem can arise.17.17.17.17.Each thread calls procedures on its own,so it must have its own stack for the local variables,returnaddresses,and so on.This is equally true for user-level threads as for kernel-level threads.18.18.18.18.A race condition is a situation in which two(or more)processes are about to perform some action.Depending on the exact timing,one or the other goes first.If one of the processes goes first,everythingworks,but if another one goes first,a fatal error occurs.19.19.19.19.Yes.The simulated computer could be multiprogrammed.For example,while processAis running,itreads out some shared variable.Then a simulated clock tick happens and processBruns.It also reads outthe same variable.Then it adds 1 to the variable.When processAruns,if it also adds one to the variable,we have a race condition20.20.20.20.Yes,
