Λύσεις Ασκήσεων για Operating Systems 2nd edition,Andrew Tanenbaum

[bujar]

Αν μπορειται και εδω ρε παιδια... θα ημουν υποχρεος

[christian-ago]

Θα μπορουσα να εχω τις λυσεις κι εγω? Εχω το βιβλιο την 3η εκδοση. Ευχαριστω.

[taleporos2006]

αν μπορεί καποιος να στείλει και σε μένα?

 

Ευχαριστώ!

[stefanos59]

παιδια και εγω θα ηθελα αν γινεται..

εχω την τριτη εκδοση και εγω!!!

[idemertzis]

Μήπως θα μπορούσατε να μου στείλετε και σε μένα το link με τις λύσεις των ασκήσεων του Tanenbaum (έχω την τρίτη έκδοση)!

Ευχαριστώ

[MitsakosGR]

 

Να δεις που ακόμα θα ζητάνε...!!!!!!

MODERN OPERATING SYSTEMS

SECOND EDITION

PROBLEM SOLUTIONS

ANDREW S. TANENBAUM

Vrije Universiteit Amsterdam, The Netherlands

PRENTICE HALL

UPPER SADDLE RIVER, NJ 07458

SOLUTIONS TO CHAPTER 1 PROBLEMS 1. 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. Multiprogramming is the rapid switching of the CPU between multiple processes in memory. It is commonly used to keep the CPU busy while one or more processes are doing I/O. 3. 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. 4. The prime reason for multiprogramming is to give the CPU something to do while waiting for I/O to complete. If there is no DMA, the CPU is fully occupied doing I/O, so there is nothing to be gained (at least in terms of CPU utilization) by multiprogramming. No matter how much I/O a program does, the CPU will be 100 percent busy. This of course assumes the major delay is the wait while data are copied. A CPU could do other work if the I/O were slow for other reasons (arriving on a serial line, for instance). 5. Second generation computers did not have the necessary hardware to protect the operating system from malicious user programs. 6. It is still alive. For example, Intel makes Pentium I, II, and III, and 4 CPUs with a variety of different properties 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. A 25 80 character monochrome text screen requires a 2000-byte buffer. The 1024 768 pixel 24-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. Choices (a), ©, and (d) should be restricted to kernel mode. 9. Personal computer systems are always interactive, often with only a single user. 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. 10. Every nanosecond one instruction emerges from the pipeline. This means the machine is executing 1 billion instructions per second. It does not matter at all how many stages the pipeline has. A 10-stage pipeline with 1 nsec per

2

PROBLEM SOLUTIONS FOR CHAPTER 1

stage would also execute 1 billion instructions per second. All that matters is how often a nished instructions pops out the end of the pipeline. 11. The manuscript contains 80 50 700 = 2.8 million characters. This is, of course, impossible to t into the registers of any currently available CPU and is too big for a 1-MB cache, but if such hardware were available, 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 27 seconds, and from tape 2 minutes 7 seconds. Of course, these times are just to read the data. Processing and rewriting the data would increase the time. 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 address and the base register can start simultaneously with the comparison and then can run in parallel. If physical addresses are used, the comparison cannot start until the addition is complete, increasing the access time. 13. Maybe. If the caller gets control back and immediately overwrites the data, when the write nally occurs, the wrong data will be written. However, if the driver rst copies the data to a private buffer before returning, then the caller can be allowed to continue immediately. Another possibility is to allow the caller to continue and give it a signal when the buffer may be reused, but this is tricky and error prone. 14. A trap is caused by the program and is synchronous with it. If the program is run again and again, the trap will always occur at exactly the same position in the instruction stream. An interrupt is caused by an external event and its timing is not reproducible. 15. Base = 40,000 and limit = 10,000. An answer of limit = 50,000 is incorrect for the way the system was described in this book. It could have been implemented that way, but doing so would have required waiting until the address + base calculation was completed before starting the limit check, thus slowing down the computer. 16. The process table is needed to store the state of a process that is currently suspended, either ready or blocked. It is not needed in a single process system because the single process is never suspended. 17. Mounting a le system makes any les already in the mount point directory inaccessible, so mount points are normally empty. However, a system administrator might want to copy some of the most important les normally located in the mounted directory to the mount point so they could be found in their normal path in an emergency when the mounted device was being checked or repaired.

PROBLEM SOLUTIONS FOR CHAPTER 1

3

18. Fork can fail if there are no free slots left in the process table (and possibly if there is no memory or swap space left). Exec can fail if the le name given does not exist or is not a valid executable le. Unlink can fail if the le to be unlinked does not exist or the calling process does not have the authority to unlink it. 19. If the call fails, for example because fd is incorrect, it can return 1. It can also fail because the disk is full and it is not possible to write the number of bytes requested. On a correct termination, it always returns nbytes. 20. It contains the bytes: 1, 5, 9, 2. 21. Block special les consist of numbered blocks, each of which can be read or written 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. 22. System calls do not really have names, other than in a documentation sense. When the library procedure read traps to the kernel, it puts the number of the system call in a register or on the stack. This number is used to index into a table. There is really no name used anywhere. On the other hand, the name of the library procedure is very important, since that is what appears in the program. 23. Yes it can, especially if the kernel is a message-passing system. 24. As far as program logic is concerned it does not matter whether a call to a library procedure results in a system call. But if performance is an issue, if a task can be accomplished without a system call the program will run faster. Every system call involves overhead time in switching from the user context to the kernel context. Furthermore, on a multiuser system the operating system may schedule another process to run when a system call completes, further slowing the progress in real time of a calling process. 25. Several UNIX calls have no counterpart in the Win32 API: Link: a Win32 program cannot refer to a le by an alternate name or see it in more than one directory. Also, attempting to create a link is a convenient way to test for and create a lock on a le. Mount and umount: a Windows program cannot make assumptions about standard path names because on systems with multiple disk drives the drive name part of the path may be different. Chmod: Windows programmers have to assume that every user can access every le. Kill: Windows programmers cannot kill a misbehaving program that is not cooperating.

4

PROBLEM SOLUTIONS FOR CHAPTER 1

26. The conversions are straightforward: (a) A micro year is 10 6 365 24 3600 = 31.536 sec. ( 1000 meters or 1 km. © There are 240 bytes, which is 1,099,511,627,776 bytes. (d) It is 6 1024 kg.

SOLUTIONS TO CHAPTER 2 PROBLEMS 1. The transition from blocked to running is conceivable. Suppose that a process is blocked on I/O and the I/O nishes. If the CPU is otherwise idle, the process could go directly from blocked to running. The other missing transition, from ready to blocked, is impossible. A ready process cannot do I/O or anything else that might block it. Only a running process can block. 2. You could have a register containing a pointer to the current process table entry. 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. 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 a particular device, or to manipulate data within a process stack area. Also, interrupt service routines must execute as rapidly as possible. 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 for enough stack space. Second, if the kernel leaves stack data in a user program s memory space upon return from a system call, a malicious user might be able to use this data to nd out information about other processes. 5. It would be dif cult, if not impossible, to keep the le system consistent. Suppose that a client process sends a request to server process 1 to update a le. This process updates the cache entry in its memory. Shortly thereafter, another client process sends a request to server 2 to read that le. Unfortunately, if the le is also cached there, server 2, in its innocence, will return obsolete data. If the rst process writes the le through to the disk after caching it, and server 2 checks 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 trying to avoid.

PROBLEM SOLUTIONS FOR CHAPTER 2

5

6. When a thread is stopped, it has values in the registers. They must be saved, just as when the process is stopped the registers must be saved. Timesharing threads is no different than timesharing processes, so each thread needs its own register save area. 7. No. If a single-threaded process is blocked on the keyboard, it cannot fork. 8. A worker thread will block when it has to read a Web page from the disk. If user-level threads are being used, this action will block the entire process, destroying the value of multithreading. Thus it is essential that kernel threads are used to permit some threads to block without affecting the others. 9. Threads in a process cooperate. They are not hostile to one another. If yielding is needed for the good of the application, then a thread will yield. After all, it is usually the same programmer who writes the code for all of them. 10. User-level threads cannot be preempted by the clock uless the whole process quantum has been used 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 a different thread from the same process to run next if it so desires. 11. In the single-threaded case, the cache hits take 15 msec and cache misses take 90 msec. The weighted average is 2/3 15 + 1/3 90. Thus the mean request takes 40 msec and the server can do 25 per second. For a multithreaded server, all the waiting for the disk is overlapped, so every request takes 15 msec, and the server can handle 66 2/3 requests per second. 12. Yes. If the server is entirely CPU bound, there is no need to have multiple threads. It just adds unnecessary 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, the entire database takes 64 megabytes, and can easily be kept in the server s memory to provide fast lookup. 13. The pointers are really necessary because the size of the global variable is unknown. It could be anything from a character to an array of oating-point numbers. If the value were stored, one would have to give the size to create global, which is all right, but what type should the second parameter of set global be, and what type should the value of read global be? 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 clock interrupt handler to begin inspecting those queues to see if it was time to do thread switching, since they might be in an inconsistent state. One solution is to set a ag when the runtime system is entered. The clock handler would see this and set its own ag,

6

PROBLEM SOLUTIONS FOR CHAPTER 2

then return. When the runtime system nished, it would check the clock ag, see that a clock interrupt occurred, and now run the clock handler. 15. Yes it is possible, but inef cient. A thread wanting to do a system call rst sets an alarm timer, then does the call. If the call blocks, the timer returns control to the threads package. Of course, most of the time the call will not block, and the timer has to be cleared. Thus each system call that might block has to be executed as three system calls. If timers go off prematurely, all kinds of problems can develop. This is not an attractive way to build a threads package. 16. The priority inversion problem occurs when a low-priority process is in its critical region and suddenly 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 a high-priority thread run. There is no preemption. With kernel-level threads this problem can arise. 17. Each thread calls procedures on its own, so it must have its own stack for the local variables, return addresses, and so on. This is equally true for user-level threads as for kernel-level threads. 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 rst. If one of the processes goes rst, everything works, but if another one goes rst, a fatal error occurs. 19. Yes. The simulated computer could be multiprogrammed. For example, while process A is running, it reads out some shared variable. Then a simulated clock tick happens and process B runs. It also reads out the same variable. Then it adds 1 to the variable. When process A runs, if it also adds one to the variable, we have a race condition. 20. Yes, it still works, but it still is busy waiting, of course. 21. It certainly works with preemptive scheduling. In fact, it was designed for that case. When scheduling is nonpreemptive, it might fail. Consider the case in which turn is initially 0 but process 1 runs rst. It will just loop forever and never release the CPU. 22. Yes it can. The memory word is used as a ag, with 0 meaning that no one is using the critical variables and 1 meaning that someone is using them. Put a 1 in the register, and swap the memory word and the register. If the register contains a 0 after the swap, access has been granted. If it contains a 1, access has been denied. When a process is done, it stores a 0 in the ag in memory.

PROBLEM SOLUTIONS FOR CHAPTER 2

7

23. 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 check to 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 completed, interrupts can be enabled again. 24. 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 ups minus the number of downs, 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 process 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 downed 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. 25. If the program operates in phases and neither process may enter the next phase until both are nished with the current phase, it makes perfect sense to use a barrier. 26. With round-robin scheduling it works. Sooner or later L will run, and eventually 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 periodically, so it has the chance to leave its critical region. 27. With kernel threads, a thread can block on a semaphore and the kernel can run some other thread in the same process. Consequently, there is no problem using semaphores. With user-level threads, when one thread blocks on a semaphore, the kernel thinks the entire process is blocked and does not run it ever again. Consequently, the process fails. 28. It is very expensive to implement. Each time any variable that appears in a predicate on which some process is waiting changes, the runtime 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.

8

PROBLEM SOLUTIONS FOR CHAPTER 2

29. The employees communicate by passing messages: orders, food, and bags in this case. In UNIX terms, the four processes are connected by pipes. 30. It does not lead to race conditions (nothing is ever lost), but it is effectively busy waiting. 31. If a philosopher blocks, neighbors can later see that he is hungry by checking his state, in test, so he can be awakened when the forks are available. 32. The change would mean that after a philosopher stopped eating, neither of his neighbors could be chosen next. In fact, they would never be chosen. Suppose that philosopher 2 nished eating. He would run test for philosophers 1 and 3, and neither would be started, even though both were hungry and both forks were available. Similary, if philosopher 4 nished eating, philosopher 3 would not be started. Nothing would start him. 33. Variation 1: readers have priority. No writer may start when a reader is active. 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 all started, 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. 34. It will need nT sec. 35. If a process occurs multiple times in the list, it will get multiple quanta per cycle. This approach could be used to give more important processes a larger share of the CPU. But when the process blocks, all entries had better be removed from the list of runnable processes. 36. In simple cases it may be possible to determine whether I/O will be limiting by looking at source code. For instance a program that reads all its input les into buffers at the start will probably not be I/O bound, but a problem that reads and writes incrementally to a number of different les (such as a compiler) is likely to be I/O bound. If the operating system provides a facility such as the UNIX ps command that can tell you the amount of CPU time used by a program , you can compare this with total time to complete execution of the program. This is, of course, most meaningful on a system where you are the only user. 37. For multiple processes in a pipeline, the common parent could pass to the operating system information about the ow of data. With this information

PROBLEM SOLUTIONS FOR CHAPTER 2

9

the OS could, for instance, determine which process could supply output to a process blocking on a call for input. 38. 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 process switch for S. Thus (a) and ( 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 then T T + ST /Q which reduces to Q /(Q + S), which is the answer to ©. For (d), we just substitute Q for S and nd that the ef ciency is 50 percent. Finally, for (e), as Q 0 the ef ciency goes to 0. 39. Shortest job rst is the way to minimize average response time. 0 X 3: X, 3, 5, 6, 9. 3 X 5: 3, X, 5, 6, 9. 5 X 6: 3, 5, X, 6, 9. 6 X 9: 3, 5, 6, X, 9. X 9: 3, 5, 6, 9, X. 40. For round robin, during the rst 10 minutes each job gets 1/5 of the CPU. At the end of 10 minutes, C nishes. During the next 8 minutes, each job gets 1/4 of the CPU, after which time D nishes. Then each of the three remaining jobs gets 1/3 of the CPU for 6 minutes, until B nishes, and so on. The nishing times for the ve jobs are 10, 18, 24, 28, and 30, for an average of 22 minutes. For priority scheduling, B is run rst. After 6 minutes it is nished. The other jobs nish at 14, 24, 26, and 30, for an average of 18.8 minutes. If the jobs run in the order A through E, they nish at 10, 16, 18, 22, and 30, for an average of 19.2 minutes. Finally, shortest job rst yields nishing times of 2, 6, 12, 20, and 30, for an average of 14 minutes. 41. The rst time it gets 1 quantum. On succeeding runs it gets 2, 4, 8, and 15, so it must be swapped in 5 times. 42. A check could be made to see if the program was expecting input and did anything with it. A program that was not expecting input and did not process it would not get any special priority boost. 43. The sequence of predictions is 40, 30, 35, and now 25. 44. The fraction of the CPU used is 35/50 + 20/100 + 10/200 + x/250. To be schedulable, this must be less than 1. Thus x must be less than 12.5 msec. 45. Two-level scheduling is needed when memory is too small to hold all the ready processes. Some set of them is put into memory, and a choice is made

10

PROBLEM SOLUTIONS FOR CHAPTER 2

from that set. From time to time, the set of in-core processes is adjusted. This algorithm is easy to implement and reasonably ef cient, certainly a lot better than say, round robin without regard to whether a process was in memory or not. 46. The kernel could schedule processes by any means it wishes, but within each process it runs threads strictly in priority order. By letting the user process set the priority of its own threads, the user controls the policy but the kernel handles the mechanism. 47. A possible shell script might be

if [ ! f numbers ]; then echo 0 numbers; count=0 while (test $count != 200 ) do count= expr $count + 1 n= tail 1 numbers expr $n + 1 numbers done

Run 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.lock then n= tail 1 numbers expr $n + 1 numbers rm numbers.lock

This version will just skip a turn when the le is inaccessible, variant solutions could put the process to sleep, do busy waiting, or count only loops in which the operation is successful.

SOLUTIONS TO CHAPTER 3 PROBLEMS 1. In the U.S., consider a presidential election in which three or more candidates are trying for the nomination of some party. After all the primary elections

PROBLEM SOLUTIONS FOR CHAPTER 3

11

are nished, when the delegates arrive at the party convention, it could happen that no candidate has a majority and that no delegate is willing to change his or her vote. This is a deadlock. Each candidate has some resources (votes) but needs more to get the job done. In countries with multiple political parties in the parliament, it could happen that each party supports a different version of the annual budget and that it is impossible to assemble a majority to pass the budget. This is also a deadlock. 2. If the printer starts to print a le before the entire le has been received (this is often allowed to speed response), the disk may ll with other requests that can t be printed until the rst le is done, but which use up disk space needed to receive the le currently being printed. If the spooler does not start to print a le until the entire le has been spooled it can reject a request that is too big. Starting to print a le is equivalent to reserving the printer; if the reservation is deferred until it is known that the entire le can be received, a deadlock of the entire system can be avoided. The user with the le that won t t is still deadlocked of course, and must go to another facility that permits printing bigger les. 3. The printer is nonpreemptable; the system cannot start printing another job until the previous one is complete. The spool disk is preemptable; you can delete an incomplete le that is growing too large and have the user send it later, assuming the protocol allows that 4. Yes. It does not make any difference whatsoever. 5. Yes, illegal graphs exist. We stated that a resource may only be held by a single process. An arc from a resource square to a process circle indicates that the process owns the resource. Thus a square with arcs going from it to two or more processes means that all those processes hold the resource, which violates the rules. Consequently, any graph in which multiple arcs leave a square and end in different circles violates the rules. Arcs from squares to squares or from circles to circles also violate the rules. 6. A portion of all such resources could be reserved for use only by processes owned by the administrator, so he or she could always run a shell and programs needed to evaluate a deadlock and make decisions about which processes to kill to make the system usable again. 7. Neither change leads to deadlock. There is no circular wait in either case. 8. Voluntary relinquishment of a resource is most similar to recovery through preemption. The essential difference is that computer processes are not expected to solve such problems on their own. Preemption is analogous to the operator or the operating system acting as a policeman, overriding the normal rules individual processes obey.

12

PROBLEM SOLUTIONS FOR CHAPTER 3

9. The process is asking for more resources than the system has. There is no conceivable way it can get these resources, so it can never nish, even if no other processes want any resources at all. 10. If the system had two or more CPUs, two or more processes could run in parallel, leading to diagonal trajectories. 11. Yes. Do the whole thing in three dimensions. The z-axis measures the number of instructions executed by the third process. 12. The method can only be used to guide the scheduling if the exact instant at which a resource is going to be claimed is known in advance. In practice, this is rarely the case. 13. A request from D is unsafe, but one from C is safe. 14. There are states that are neither safe nor deadlocked, but which lead to deadlocked states. As an example, suppose we have four resources: tapes, plotters, scanners, and CD-ROMs, as in the text, and three processes competing for them. We could have the following situation: Has A: 2 0 0 0 B: 1 0 0 0 C: 0 1 2 1 Needs 1020 0131 1010 Available 0121

This state is not deadlocked because many actions can still occur, for example, A can still get two printers. However, if each process asks for its remaining requirements, we have a deadlock. 15. The system is deadlock free. Suppose that each process has one resource. There is one resource free. Either process can ask for it and get it, in which case it can nish and release both resources. Consequently deadlock is impossible. 16. If a process has m resources it can nish and cannot be involved in a deadlock. Therefore, the worst case is where every process has m 1 resources and needs another one. If there is one resource left over, one process can nish and release all its resources, letting the rest nish too. Therefore the condition for avoiding deadlock is r p(m 1) + 1. 17. No. D can still nish. When it nishes, it returns enough resources to allow E (or A) to nish, and so on. 18. With three processes, each one can have two drives. With four processes, the distribution of drives will be (2, 2, 1, 1), allowing the rst two processes to nish. With ve processes, the distribution will be (2, 1, 1, 1, 1), which still allows the rst one to nish. With six, each holding one tape drive and wanting another, we have a deadlock. Thus for n 6 the system is deadlock-free.

PROBLEM SOLUTIONS FOR CHAPTER 3

13

19. Comparing a row in the matrix to the vector of available resources takes m operations. This step must be repeated on the order of n times to nd a process that can nish and be marked as done. Thus marking a process as done takes on the order or mn steps. Repeating the algorithm for all n processes means that the number of steps is then mn 2 . 20. The needs matix is as follows: 01002 02100 10300 00111 If x is 0, we have a deadlock immediately. If x is 1, process D can run to completion. When it is nished, the available vector is 1 1 2 2 1. Unfortunately we are now deadlocked. If x is 2, after D runs, the available vector is 1 1 3 2 1 and C can run. After it nishes and returns its resources the available vector is 2 2 3 3 1, which will allow B to run and complete, and then A to run and complete. Therefore, the smallest value of x that avoids a deadlock is 2. 21. Yes. Suppose that all the mailboxes are empty. Now A sends to B and waits for a reply, B sends to C and waits for a reply, and C sends to A and waits for a reply. All the conditions for deadlock are now ful lled. 22. Suppose that process A requests the records in the order a, b, c. If process B also asks for a rst, one of them will get it and the other will block. This situation is always deadlock free since the winner can now run to completion without interference. Of the four other combinations, some may lead to deadlock and some are deadlock free. The six cases are as follows: abc acb bac bca cab cba deadlock free deadlock free possible deadlock possible deadlock possible deadlock possible deadlock

Since four of the six may lead to deadlock, there is a 1/3 chance of avoiding a deadlock and a 2/3 chance of getting one. 23. Two-phase locking eliminates deadlocks, but introduces potential starvation. A process has to keep trying and failing to acquire all of its records. There is no upper bound on how long it may take. 24. To avoid circular wait, number the resources (the accounts) with their account numbers. After reading an input line, a process locks the lower-numbered

14

PROBLEM SOLUTIONS FOR CHAPTER 3

account rst, then when it gets the lock (which may entail waiting), it locks the other one. Since no process ever waits for an account lower than what it already has, there is never a circular wait, hence never a deadlock. 25. Change the semantics of requesting a new resource as follows. If a process asks for a new resource and it is available, it gets the resource and keeps what it already has. If the new resource is not available, all existing resources are released. With this scenario, deadlock is impossible and there is no danger that the new resource is acquired but existing ones lost. Of course, the process only works if releasing a resource is possible (you can release a scanner between pages or a CD recorder between CDs). 26. I d give it an F (failing) grade. What does the process do? Since it clearly needs the resource, it just asks again and blocks again. This is no better than staying blocked. In fact, it may be worse since the system may keep track of how long competing processes have been waiting and assign a newly freed resource to the process that has been waiting longest. By periodically timing out and trying again, a process loses its seniority. 27. If both programs ask for Woofer rst, the computers will starve with the endless sequence: request Woofer, cancel request, request Woofer, cancel request, etc. If one of them asks for the doghouse and the other asks for the dog, we have a deadlock, which is detected by both parties and then broken, but it is just repeated on the next cycle. Either way, if both computers have been programmed to go after the dog or the doghouse rst, either starvation or deadlock ensues. There is not really much difference between the two here. In most deadlock problems, starvation does not seem serious because introducing random delays will usually make it very unlikely. That approach does not work here. SOLUTIONS TO CHAPTER 4 PROBLEMS 1. The chance that all four processes are idle is 1/16, so the CPU idle time is 1/16. 2. If each job has 50% I/O wait, then it will take 20 minutes to complete in the absence of competition. If run sequentially, the second one will nish 40 minutes after the rst one starts. With two jobs, the approximate CPU utilization is 1 0.52 . Thus each one gets 0.375 CPU minute per minute of real time. To accumulate 10 minutes of CPU time, a job must run for 10/0.375 minutes or about 26.67 minutes. Thus running sequentially the jobs nish after 40 minutes, but running in parallel they nish after 26.67 minutes. 3. Almost the entire memory has to be copied, which requires each word to be read and then rewritten at a different location. Reading 4 bytes takes 10 nsec,

PROBLEM SOLUTIONS FOR CHAPTER 4

15

so reading 1 byte takes 2.5 nsec and writing it takes another 2.5 nsec, for a total of 5 nsec per byte compacted. This is a rate of 200,000,000 bytes/sec. To copy 128 MB (227 bytes, which is about 1.34 108 bytes), the computer needs 227 /200,000,000 sec, which is about 671 msec. This number is slightly pessimistic because if the initial hole at the bottom of memory is k bytes, those k bytes do not need to be copied. However, if there are many holes and many data segments, the holes will be small so k will be small and the error in the calculation will also be small. 4. The bitmap needs 1 bit per allocation unit. With 227 /n allocation units, this is 224 /n bytes. The linked list has 227 /216 or 211 nodes, each of 8 bytes for a total of 214 bytes. For small n, the linked list is better. For large n, the bitmap is better. The crossover point can be calculated by equating these two formulas and solving for n. The result is 1 KB. For n smaller than 1 KB, a linked list is better. For n larger than 1 KB, a bitmap is better. Of course, the assumption of segments and holes alternating every 64 KB is very unrealistic. Also, we need n = 64 KB if the segments and holes are 64 KB. 5. First t takes 20 KB, 10 KB, 18 KB. Best t takes 12 KB, 10 KB, and 9 KB. Worst t takes 20 KB, 18 KB, and 15 KB. Next t takes 20 KB, 18 KB, and 9 KB. 6. Real memory uses physical addresses. These are the numbers that the memory chips react to on the bus. Virtual addresses are the logical addresses that refer to a process address space. Thus a machine with a 16-bit word can generate virtual addresses up to 64K, regardless of whether the machine has more or less memory than 64 KB. 7. For a 4-KB page size the (page, offset) pairs are (4, 3616), (8, 0), and (14, 2656). For an 8-KB page size they are (2, 3616), (4, 0), (7, 2656). 8. (a) 8212 ( 4100 © 24684 9. They built an MMU and inserted it between the 8086 and the bus. Thus all 8086 physical addresses went into the MMU as virtual addresses. The MMU then mapped them onto physical addresses, which went to the bus. 10. The total virtual address space for all the processes combined is nv so this much storage is needed for pages. However an amount r can be in RAM, so the amount of disk storage required is only nv r. This amount is far more than is ever needed in practice because rarely will there be n processes actually running and even more rarely will all of them need the maximum allowed virtual memory. 11. A page fault every k instructions adds an extra overhead of n /k sec to the average, so the average instruction takes 10 + n /k nsec.

16

PROBLEM SOLUTIONS FOR CHAPTER 4

12. The page table contains 232 /213 entries, which is 524,288. Loading the page table takes 52 msec. If a process gets 100 msec, this consists of 52 msec for loading the page table and 48 msec for running. Thus 52 percent of the time is spent loading page tables. 13. Twenty bits are used for the virtual page numbers, leaving 12 over for the offset. This yields a 4-KB page. Twenty bits for the virtual page implies 220 pages. 14. The number of pages depends on the total number of bits in a, b, and c combined. How they are split among the elds does not matter. 15. For a one-level page table, there are 232 /212 or 1M pages needed. Thus the page table must have 1M entries. For two-level paging, the main page table has 1K entries, each of which points to a second page table. Only two of these are used. Thus in total only three page table entries are needed, one in the top-level table and one in each of the lower-level tables. 16. The code and reference string is as follows LOAD 6144,R0 PUSH R0 CALL 5120 JEQ 5152 1(I), 12(D) 2(I), 15(D) 2(I), 15(D) 10(I)

The code (I) indicates an instruction reference, whereas (D) indicates a data reference. 17. The effective instruction time is 1h + 5(1 h), where h is the hit rate. If we equate this formula with 2 and solve for h, we nd that h must be at least 0.75. 18. The R bit is never needed in the TLB. The mere presence of a page there means the page has been referenced; otherwise it would not be there. Thus the bit is completely redundant. When the entry is written back to memory, however, the R bit in the memory page table is set. 19. An associative memory essentially compares a key to the contents of multiple registers simultaneously. For each register there must be a set of comparators that compare each bit in the register contents to the key being searched for. The number of gates (or transistors) needed to implement such a device is a linear function of the number of registers, so expanding the design gets expensive linearly. 20. With 8-KB pages and a 48-bit virtual address space, the number of virtual pages is 248 /213 , which is 235 (about 34 billion). 21. The main memory has 228 /213 = 32,768 pages. A 32K hash table will have a mean chain length of 1. To get under 1, we have to go to the next size,

PROBLEM SOLUTIONS FOR CHAPTER 4

17

65,536 entries. Spreading 32,768 entries over a 65,536 table slots will give a mean chain length of 0.5, which ensures fast lookup. 22. This is probably not possible except for the unusual and not very useful case of a program whose course of execution is completely predictable at compilation time. If a compiler collects information about the locations in the code of calls to procedures, this information might be used at link time to rearrange the object code so procedures were located close to the code that calls them. This would make it more likely that a procedure would be on the same page as the calling code. Of course this would not help much for procedures called from many places in the program. 23. The page frames for FIFO are as follows: x017 2333300 xx017222233 x x x0 1777722 x x x x0111177 The page frames for LRU are as follows: x0172327103 xx01 7232710 x x x0 1773271 x x x x0111327 FIFO yields 6 page faults; LRU yields 7. 24. The rst page with a 0 bit will be chosen, in this case D. 25. The counters are Page 0: 0110110 Page 1: 01001001 Page 2: 00110111 Page 3: 10001011 26. The rst page with R = 0 and age will be chosen. Since the scan starts at the bottom, the very rst page (1620) gets evicted. 27. The age of the page is 2204 1213 = 991. If = 400, it is de nitely out of the working set and it was not recently referenced so it will be evicted. The = 1000 the situation is different. Now the page falls within the working set (barely), so it is not removed. 28. The seek plus rotational latency is 20 msec. For 2-KB pages, the transfer time is 1.25 msec, for a total of 21.25 msec. Loading 32 of these pages will take 680 msec. For 4-KB pages, the transfer time is doubled to 2.5 msec, so the total time per page is 22.50 msec. Loading 16 of these pages takes 360 msec. 29. NRU removes page 2. FIFO removes page 3. LRU removes page 1. Second chance removes page 2. 30. The PDP-1 paging drum had the advantage of no rotational latency. This saved half a rotation each time memory was written to the drum.

18

PROBLEM SOLUTIONS FOR CHAPTER 4

31. The text is eight pages, the data are ve pages, and the stack is four pages. The program does not t because it needs 17 4096-byte pages. With a 512byte page, the situation is different. Here the text is 64 pages, the data are 33 pages, and the stack is 31 pages, for a total of 128 512-byte pages, which ts. With the small page size it is ok, but not with the large one. 32. If pages can be shared, yes. For example, if two users of a timesharing system are running the same editor at the same time and the program text is shared rather than copied, some of those pages may be in each user s working set at the same time. 33. It is possible. Assuming that segmentation is not present, the protection information must be in the page table. If each process has its own page table, each one also has its own protection bits. They could be different. 34. The program is getting 15,000 page faults, each of which uses 2 msec of extra processing time. Together, the page fault overhead is 30 sec. This means that of the 60 sec used, half was spent on page fault overhead, and half on running the program. If we run the program with twice as much memory, we get half as memory page faults, and only 15 sec of page fault overhead, so the total run time will be 45 sec. 35. It works for the program if the program cannot be modi ed. It works for the data if the data cannot be modi ed. However, it is common that the program cannot be modi ed and extremely rare that the data cannot be modi ed. If the data area on the binary le were overwritten with updated pages, the next time the program was started, it would not have the original data. 36. The instruction could lie astride a page boundary, causing two page faults just to fetch the instruction. The word fetched could also span a page boundary, generating two more faults, for a total of four. If words must be aligned in memory, the data word can cause only one fault, but an instruction to load a 32-bit word at address 4094 on a machine with a 4-KB page is legal on some machines (including the Pentium). 37. Internal fragmentation occurs when the last allocation unit is not full. External fragmentation occurs when space is wasted between two allocation units. In a paging system, the wasted space in the last page is lost to internal fragmentation. In a pure segmentation system, some space is invariably lost between the segments. This is due to external fragmentation. 38. No. The search key uses both the segment number and the virtual page number, so the exact page can be found in a single match.

PROBLEM SOLUTIONS FOR CHAPTER 5

19

SOLUTIONS TO CHAPTER 5 PROBLEMS 1. In the gure, we see a controller with two devices. The reason that a single controller is expected to handle multiple devices is to eliminate the need for having a controller per device. If controllers become almost free, then it will be simpler just to build the controller into the device itself. This design will also allow multiple transfers in parallel and thus give better performance. 2. Easy. The scanner puts out 400 KB/sec maximum. The bus and disk both run at 16.7 MB/sec, so neither the disk nor the bus comes anywhere near saturation. 3. It is not a good idea. The memory bus is surely faster than the I/O bus, otherwise why bother with it? Consider what happens with a normal memory request. The memory bus nishes rst, but the I/O bus is still busy. If the CPU waits until the I/O bus nishes, it has reduced memory performance to that of the I/O bus. If it just tries the memory bus for the second reference, it will fail if this one is an I/O device reference. If there were some way to instantaneously abort the previous I/O bus reference to try the second one, the improvement might work, but there is never such an option. All in all, it is a bad idea. 4. Each bus transaction has a request and a response, each taking 100 nsec, or 200 nsec per bus transaction. This gives 5 million bus transactions/sec. If each one is good for 4 bytes, the bus has to handle 20 MB/sec. The fact that these transactions may be sprayed over four I/O devices in round-robin fashion is irrelevant. A bus transaction takes 200 nsec, regardless of whether consecutive requests are to the same device or different devices, so the number of channels the DMA controller has does not matter. The bus does not know or care. 5. An interrupt requires pushing 34 words onto the stack. Returning from the interrupt requires fetching 34 words from the stack. This overhead alone is 680 nsec. Thus the maximum number of interrupts per second is no more than about 1.47 million, assuming no work for each interrupt. 6. It could have been done at the start. A reason for doing it at the end is that the code of the interrupt service procedure is very short. By rst outputting another character and then acknowledging the interrupt, if another interrupt happens immediately, the printer will be working during the interrupt, making it print slightly faster. A disadvantage of this approach is slightly longer dead time when other interrupts may be disabled. 7. Yes. The stacked PC points to the rst instruction not fetched. All instructions before that have been executed and the instruction pointed to and its successors have not been executed. This is the condition for precise

20

PROBLEM SOLUTIONS FOR CHAPTER 5

interrupts. Precise interrupts are not hard to achieve on machine with a single pipeline. The trouble comes in when instructions are executed out of order, which is not the case here. 8. The printer prints 50 80 6 = 24,000 characters/min, which is 400 characters/sec. Each character uses 50 sec of CPU time for the interrupt, so collectively in each second the interrupt overhead is 20 msec. Using interrupt-driven I/O, the remaining 980 msec of time is available for other work. In other words, the interrupt overhead costs only 2% of the CPU, which will hardly affect the running program at all. 9. Device independence means that les and devices are accessed the same way, independent of their physical nature. Systems that have one set of calls for writing on a le, but a different set of calls for writing on the console (terminal) do not exhibit device independence. 10. (a) Device driver. ( Device driver. © Device-independent software. (d) User-level software. 11. Based on the data in Fig. 5-17, for the oppy disk example, there are 9 512 8 = 36864 bits per track. At 200 msec per rotation the bit rate is 184,320 bits/sec. The hard disk has an average of 281 sectors per track, so there are 281 512 8 = 1,150,976 bits/track on the average. A rotation time of 8.33 msec corresponds to 120 rotation/sec (7200 rpm), so in one second the disk can transfer 120 1,150,976 bits. This is about 138 million bits/sec. The data rate of the oppy disk is roughly three times that of a 56Kbps modem. The data rate of the hard disk is about 38% faster than Fast Ethernet. However, these calculations underestimate the actual maximum data rates, because for every 512 bytes of data on a disk there are also a number of bytes of formatting information, to iden