第1页 / 共60页
第2页 / 共60页
第3页 / 共60页
第4页 / 共60页
第5页 / 共60页
第6页 / 共60页
第7页 / 共60页
第8页 / 共60页
操作系统第二版\操作系统第二版（答案）.pdf
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 finished,
there will be work waiting for the CPU. Output spooling consists of first
copying printable files 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 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 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), (c), 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
efficient 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 finished 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 fit into the registers of any currently available CPU and
is too big for a 1-MB cache, but
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 scan-
ning 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.
if such hardware were available,
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 finally occurs, the wrong data will be written. However, if the
driver first 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 imple-
mented that way, but doing so would have required waiting until the address
+ base calculation was completed before starting the limit check, thus slow-
ing 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 sys-
tem because the single process is never suspended.
17. Mounting a file system makes any files 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 files 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 file name given
does 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 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 files 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 files.
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 sys-
tem 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 file 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 file.
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 file.
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.
(b) 1000 meters or 1 km.
(c) 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 proc-
ess is blocked on I/O and the I/O finishes. If the CPU is otherwise idle, the
process could go directly from blocked to running. The other missing transi-
tion, 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 manipu-
late 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 find out information about other processes.
5. It would be difficult, if not impossible, to keep the file system consistent.
Suppose that a client process sends a request to server process 1 to update a
file. This process updates the cache entry in its memory. Shortly thereafter,
another client process sends a request to server 2 to read that file. Unfor-
tunately, if the file is also cached there, server 2, in its innocence, will return
obsolete data. If the first process writes the file through to the disk after cach-
ing 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 yield-
ing 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 individu-
ally. 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 dif-
ferent 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 mul-
tithreaded 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 tele-
phone 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 floating-point
numbers.
If the value were stored, one would have to give the size to
create3global, which is all right, but what type should the second parameter
of set3global be, and what type should the value of read3global 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 flag when the run-
time system is entered. The clock handler would see this and set its own flag,
6
PROBLEM SOLUTIONS FOR CHAPTER 2
then return. When the runtime system finished, it would check the clock flag,
see that a clock interrupt occurred, and now run the clock handler.
15. Yes it is possible, but inefficient. A thread wanting to do a system call first
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
first. If one of the processes goes first, everything works, but if another one
goes first, 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 simu-
lated clock tick happens and process B runs. It also reads out the same vari-
able. 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 first. It will just loop for-
ever and never release the CPU.
22. Yes it can. The memory word is used as a flag, 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 flag in memory.
PROBLEM SOLUTIONS FOR CHAPTER 2
7
23. To do a semaphore operation, the operating system first disables interrupts.
Then it reads the value of the semaphore. If it is doing a down and the sema-
phore 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 first 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 proc-
ess 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, first 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 finished 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 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.
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 sig-
nal primitive.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
