Skip to content
Textbook Guides

Solution Manual for Operating Systems: Internals and Design Principles, 9th Edition

Get quick and accurate answers to your textbook questions with Solution Manual for Operating Systems: Internals and Design Principles, 9th Edition, a detailed guide to solving every exercise.

Preview 16 of 143 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    SOLUTIONS MANUAL O PERATING S YSTEMS N INTH E DITION C HAPTERS 1–9 W ILLIAM S TALLINGS Copyright 2017: William Stallings

  2. Page 2
  3. Page 3
    Read page 3 as text

    -4- Chapter 1 Computer System Overview ....................................... 5 Chapter 2 Operating System Overview ...................................... 12 Chapter 3 Process Description and Control ................................. 15 Chapter 4 Threads .................................................................. 21 Chapter 5 Mutual Exclusion and Synchronization ......................... 25 Chapter 6 Deadlock and Starvation ........................................... 42 Chapter 7 Memory Management ............................................... 54 Chapter 8 Virtual Memory ........................................................ 60 Chapter 9 Uniprocessor Scheduling ........................................... 69 TABLE OF CONTENTS

  4. Page 4
    Read page 4 as text

    -5- C HAPTER 1 C OMPUTER S YSTEM O VERVIEW A NSWERS TO Q UESTIONS 1.1 A processor, which controls the operation of the computer and performs its data processing functions ; a main memory , which stores both data and instructions; I/O modules , which move data between the computer and its external environment; and the system bus, which provides for communication among processors, main memory, and I/O modules. 1.2 User-visible registers: Enable the machine- or assembly-language programmer to minimize main memory references by optimizing register use. For high-level languages, an optimizing compiler will attempt to make intelligent choices of which variables to assign to registers and which to main memory locations. Some high-level languages, such as C, allow the programmer to suggest to the compiler which variables should be held in registers. Control and status registers: Used by the processor to control the operation of the processor and by privileged, operating system routines to control the execution of programs. 1.3 These actions fall into four categories: Processor-memory: Data may be transferred from processor to memory or from memory to processor. Processor-I/O: Data may be transferred to or from a peripheral device by transferring between the processor and an I/O module. Data processing: The processor may perform some arithmetic or logic operation on data. Control: An instruction may specify that the sequence of execution be altered. 1.4 An interrupt is a mechanism by which other modules (I/O, memory) may interrupt the normal sequencing of the processor. 1.5 Two approaches can be taken to dealing with multiple interrupts. The first is to disable interrupts while an interrupt is being processed. A second approach is to define priorities for interrupts and to allow an interrupt of higher priority to cause a lower-priority interrupt handler to be interrupted.

  5. Page 5
    Read page 5 as text

    -6- 1.6 The three key characteristics of memory are cost, capacity, and access time. 1.7 Cache memory is a memory that is smaller and faster than main memory and that is interposed between the processor and main memory. The cache acts as a buffer for recently used memory locations. 1.8 A multicore computer is a special case of a multiprocessor, in which all of the processors are on a single chip. 1.9 Spatial locality refers to the tendency of execution to involve a number of memory locations that are clustered. Temporal locality refers to the tendency for a processor to access memory locations that have been used recently. 1.10 Spatial locality is generally exploited by using larger cache blocks and by incorporating prefetching mechanisms (fetching items of anticipated use) into the cache control logic. Temporal locality is exploited by keeping recently used instruction and data values in cache memory and by exploiting a cache hierarchy. A NSWERS TO P ROBLEMS 1.1 Memory (contents in hex): 300: 3005; 301: 5940; 302: 7006 Step 1: 3005 → IR; Step 2: 3 → AC Step 3: 5940 → IR; Step 4: 3 + 2 = 5 → AC Step 5: 7006 → IR; Step 6: AC → Device 6 1.2 1. a. The PC contains 300, the address of the first instruction. This value is loaded in to the MAR. b. The value in location 300 (which is the instruction with the value 1940 in hexadecimal) is loaded into the MBR, and the PC is incremented. These two steps can be done in parallel. c. The value in the MBR is loaded into the IR. 2. a. The address portion of the IR (940) is loaded into the MAR. b. The value in location 940 is loaded into the MBR. c. The value in the MBR is loaded into the AC. 3. a. The value in the PC (301) is loaded in to the MAR. b. The value in location 301 (which is the instruction with the value 5941) is loaded into the MBR, and the PC is incremented. c. The value in the MBR is loaded into the IR. 4. a. The address portion of the IR (941) is loaded into the MAR. b. The value in location 941 is loaded into the MBR. c. The old value of the AC and the value of location MBR are added and the result is stored in the AC.

  6. Page 6
    Read page 6 as text

    -7- 5. a. The value in the PC (302) is loaded in to the MAR. b. The value in location 302 (which is the instruction with the value 2941) is loaded into the MBR, and the PC is incremented. c. The value in the MBR is loaded into the IR. 6. a. The address portion of the IR (941) is loaded into the MAR. b. The value in the AC is loaded into the MBR. c. The value in the MBR is stored in location 941. 1.3 a. 2 24 = 16 MBytes b. (1) If the local address bus is 32 bits, the whole address can be transferred at once and decoded in memory. However, since the data bus is only 16 bits, it will require 2 cycles to fetch a 32-bit instruction or operand. (2) The 16 bits of the address placed on the address bus can't access the whole memory. Thus a more complex memory interface control is needed to latch the first part of the address and then the second part (since the microprocessor will end in two steps). For a 32-bit address, one may assume the first half will decode to access a "row" in memory, while the second half is sent later to access a "column" in memory. In addition to the two-step address operation, the microprocessor will need 2 cycles to fetch the 32 bit instruction/operand. c. The program counter must be at least 24 bits. Typically, a 32-bit microprocessor will have a 32-bit external address bus and a 32-bit program counter, unless on-chip segment registers are used that may work with a smaller program counter. If the instruction register is to contain the whole instruction, it will have to be 32-bits long; if it will contain only the op code (called the op code register) then it will have to be 8 bits long. 1.4 In cases (a) and (b) , the microprocessor will be able to access 2 16 = 64K bytes; the only difference is that with an 8-bit memory each access will transfer a byte, while with a 16-bit memory an access may transfer a byte or a 16-byte word. For case (c) , separate input and output instructions are needed, whose execution will generate separate "I/O signals" (different from the "memory signals" generated with the execution of memory-type instructions); at a minimum, one additional output pin will be required to carry this new signal. For case (d) , it can support 2 8 = 256 input and 2 8 = 256 output byte ports and the same number of input and output 16-bit ports; in either case, the distinction between an input and an output port is defined by the different signal that the executed input or output instruction generated.

  7. Page 7
    Read page 7 as text

    -8- 1.5 Clock cycle = 1 8 MHz = 125 ns Bus cycle = 4 × 125 ns = 500 ns 2 bytes transferred every 500 ns; thus transfer rate = 4 MBytes/sec Doubling the frequency may mean adopting a new chip manufacturing technology (assuming each instructions will have the same number of clock cycles); doubling the external data bus means wider (maybe newer) on-chip data bus drivers/latches and modifications to the bus control logic. In the first case, the speed of the memory chips will also need to double (roughly) not to slow down the microprocessor; in the second case, the "word length" of the memory will have to double to be able to send/receive 32-bit quantities. 1.6 a. Input from the Teletype is stored in INPR. The INPR will only accept data from the Teletype when FGI=0. When data arrives, it is stored in INPR, and FGI is set to 1. The CPU periodically checks FGI. If FGI =1, the CPU transfers the contents of INPR to the AC and sets FGI to 0. When the CPU has data to send to the Teletype, it checks FGO. If FGO = 0, the CPU must wait. If FGO = 1, the CPU transfers the contents of the AC to OUTR and sets FGO to 0. The Teletype sets FGI to 1 after the word is printed. b. The process described in (a) is very wasteful. The CPU, which is much faster than the Teletype, must repeatedly check FGI and FGO. If interrupts are used, the Teletype can issue an interrupt to the CPU whenever it is ready to accept or send data. The IEN register can be set by the CPU (under programmer control) 1.7 If a processor is held up in attempting to read or write memory, usually no damage occurs except a slight loss of time. However, a DMA transfer may be to or from a device that is receiving or sending data in a stream (e.g., disk or tape), and cannot be stopped. Thus, if the DMA module is held up (denied continuing access to main memory), data will be lost. 1.8 Let us ignore data read/write operations and assume the processor only fetches instructions. Then the processor needs access to main memory once every microsecond. The DMA module is transferring characters at a rate of 1200 characters per second, or one every 833 μ s. The DMA therefore "steals" every 833rd cycle. This slows down the processor approximately 1 833 × 100% = 0.12%

  8. Page 8
    Read page 8 as text

    -9- 1.9 a. The processor can only devote 5% of its time to I/O. Thus the maximum I/O instruction execution rate is 10 6 × 0.05 = 50,000 instructions per second. The I/O transfer rate is therefore 25,000 words/second. b. The number of machine cycles available for DMA control is 10 6 (0.05 × 5 + 0.95 × 2) = 2.15 × 10 6 If we assume that the DMA module can use all of these cycles, and ignore any setup or status-checking time, then this value is the maximum I/O transfer rate. 1.10 a. A reference to the first instruction is immediately followed by a reference to the second. b. The ten accesses to a[i] within the inner for loop which occur within a short interval of time. 1.11 Define C i = Average cost per bit, memory level i S i = Size of memory level i T i = Time to access a word in memory level i H i = Probability that a word is in memory i and in no higher-level memory B i = Time to transfer a block of data from memory level (i + 1) to memory level i Let cache be memory level 1; main memory, memory level 2; and so on, for a total of N levels of memory. Then C s = C i S i i = 1 N ∑ S i i = 1 N ∑ The derivation of T s is more complicated. We begin with the result from probability theory that: Expected Value of x = i Pr x = 1 [ ] i = 1 N ∑ We can write: T s = T i H i i = 1 N ∑

  9. Page 9
    Read page 9 as text

    -10- We need to realize that if a word is in M 1 (cache), it is read immediately. If it is in M 2 but not M 1 , then a block of data is transferred from M 2 to M 1 and then read. Thus: T 2 = B 1 + T 1 Further T 3 = B 2 + T 2 = B 1 + B 2 + T 1 Generalizing: T i = B j + T 1 j = 1 i − 1 ∑ So T s = B j H i ( ) j = 1 i − 1 ∑ i = 2 N ∑ + T 1 H i i = 1 N ∑ But H i i = 1 N ∑ = 1 Finally T s = B j H i ( ) j = 1 i − 1 ∑ i = 2 N ∑ + T 1 1.12 a. Cost = C m × 8 × 10 6 = 8 × 10 3 ¢ = $80 b. Cost = C c × 8 × 10 6 = 8 × 10 4 ¢ = $800 c. From Equation 1.1 : 1.1 × T 1 = T 1 + (1 – H)T 2 (0.1)(100) = (1 – H)(1200) H = 1190/1200

  10. Page 10
    Read page 10 as text

    -11- 1.13 There are three cases to consider: Location of referenced word Probability Total time for access in ns In cache 0.9 20 Not in cache, but in main memory (0.1)(0.6) = 0.06 60 + 20 = 80 Not in cache or main memory (0.1)(0.4) = 0.04 12ms + 60 + 20 = 12,000,080 So the average access time would be: Avg = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns 1.14 Yes, if the stack is only used to hold the return address. If the stack is also used to pass parameters, then the scheme will work only if it is the control unit that removes parameters, rather than machine instructions. In the latter case, the processor would need both a parameter and the PC on top of the stack at the same time.

  11. Page 11
    Read page 11 as text

    -12- C HAPTER 2 O PERATING S YSTEM O VERVIEW A NSWERS TO Q UESTIONS 2.1 Convenience: An operating system makes a computer more convenient to use. Efficiency: An operating system allows the computer system resources to be used in an efficient manner. Ability to evolve: An operating system should be constructed in such a way as to permit the effective development, testing, and introduction of new system functions without interfering with service. 2.2 The kernel is a portion of the operating system that includes the most heavily used portions of software. Generally, the kernel is maintained permanently in main memory. The kernel runs in a privileged mode and responds to calls from processes and interrupts from devices. 2.3 Multiprogramming is a mode of operation that provides for the interleaved execution of two or more computer programs by a single processor. 2.4 A process is a program in execution. A process is controlled and scheduled by the operating system. 2.5 The execution context, or process state, is the internal data by which the operating system is able to supervise and control the process. This internal information is separated from the process, because the operating system has information not permitted to the process. The context includes all of the information that the operating system needs to manage the process and that the processor needs to execute the process properly. The context includes the contents of the various processor registers, such as the program counter and data registers. It also includes information of use to the operating system, such as the priority of the process and whether the process is waiting for the completion of a particular I/O event. 2.6 Process isolation: The operating system must prevent independent processes from interfering with each other's memory, both data and instructions. Automatic allocation and management: Programs

  12. Page 12
    Read page 12 as text

    -13- should be dynamically allocated across the memory hierarchy as required. Allocation should be transparent to the programmer. Thus, the programmer is relieved of concerns relating to memory limitations, and the operating system can achieve efficiency by assigning memory to jobs only as needed. Support of modular programming: Programmers should be able to define program modules, and to create, destroy, and alter the size of modules dynamically. Protection and access control: Sharing of memory, at any level of the memory hierarchy, creates the potential for one program to address the memory space of another. This is desirable when sharing is needed by particular applications. At other times, it threatens the integrity of programs and even of the operating system itself. The operating system must allow portions of memory to be accessible in various ways by various users. Long-term storage: Many application programs require means for storing information for extended periods of time, after the computer has been powered down. 2.7 A virtual address refers to a memory location in virtual memory. That location is on disk and at some times in main memory. A real address is an address in main memory. 2.8 Round robin is a scheduling algorithm in which processes are activated in a fixed cyclic order; that is, all processes are in a circular queue. A process that cannot proceed because it is waiting for some event (e.g. termination of a child process or an input/output operation) returns control to the scheduler. 2.9 A monolithic kernel is a large kernel containing virtually the complete operating system, including scheduling, file system, device drivers, and memory management. All the functional components of the kernel have access to all of its internal data structures and routines. Typically, a monolithic kernel is implemented as a single process, with all elements sharing the same address space. A microkernel is a small privileged operating system core that provides process scheduling, memory management, and communication services and relies on other processes to perform some of the functions traditionally associated with the operating system kernel. 2.10 Multithreading is a technique in which a process, executing an application, is divided into threads that can run concurrently. 2.11 Simultaneous concurrent processes or threads; scheduling; synchronization; memory management; reliability and fault tolerance. A NSWERS TO P ROBLEMS

  13. Page 13
    Read page 13 as text

    -14- 2.1 The answers are the same for (a) and (b) . Assume that although processor operations cannot overlap, I/O operations can. Number of jobs TAT Throughput Processor utilization 1 NT 1/N 50% 2 NT 2/N 100% 4 (2N – 1)T 4/(2N – 1) 100% 2.2 I/O-bound programs use relatively little processor time and are therefore favored by the algorithm. However, if a processor-bound process is denied processor time for a sufficiently long period of time, the same algorithm will grant the processor to that process since it has not used the processor at all in the recent past. Therefore, a processor- bound process will not be permanently denied access. 2.3 With time sharing, the concern is turnaround time. Time-slicing is preferred because it gives all processes access to the processor over a short period of time. In a batch system, the concern is with throughput, and the less context switching, the more processing time is available for the processes. Therefore, policies that minimize context switching are favored. 2.4 A system call is used by an application program to invoke a function provided by the operating system. Typically, the system call results in transfer to a system program that runs in kernel mode. 2.5 The system operator can review this quantity to determine the degree of "stress" on the system. By reducing the number of active jobs allowed on the system, this average can be kept high. A typical guideline is that this average should be kept above 2 minutes. This may seem like a lot, but it isn't. 2.6 a. If a conservative policy is used, at most 20/4 = 5 processes can be active simultaneously. Because one of the drives allocated to each process can be idle most of the time, at most 5 drives will be idle at a time. In the best case, none of the drives will be idle. b. To improve drive utilization, each process can be initially allocated with three tape drives. The fourth one will be allocated on demand. In this policy, at most ⎣ 20/3 ⎦ = 6 processes can be active simultaneously. The minimum number of idle drives is 0 and the maximum number is 2.

  14. Page 14
    Read page 14 as text

    -15- C HAPTER 3 P ROCESS D ESCRIPTION AND C ONTROL A NSWERS TO Q UESTIONS 3.1 An instruction trace for a program is the sequence of instructions that execute for that process. 3.2 New batch job; interactive logon; created by OS to provide a service; spawned by existing process. See Table 3.1 for details. 3.3 Running: The process that is currently being executed. Ready: A process that is prepared to execute when given the opportunity. Blocked: A process that cannot execute until some event occurs, such as the completion of an I/O operation. New: A process that has just been created but has not yet been admitted to the pool of executable processes by the operating system. Exit: A process that has been released from the pool of executable processes by the operating system, either because it halted or because it aborted for some reason. 3.4 Process preemption occurs when an executing process is interrupted by the processor so that another process can be executed. 3.5 Swapping involves moving part or all of a process from main memory to disk. When none of the processes in main memory is in 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.6 There are two independent concepts: whether a process is waiting on an event (blocked or not), and whether a process has been swapped out of main memory (suspended or not). To accommodate this 2 × 2 combination, we need two Ready states and two Blocked states. 3.7 1. The process is not immediately available for execution. 2. The process may or may not be waiting on an event. If it is, this blocked condition is independent of the suspend condition, and occurrence of the blocking event does not enable the process to be executed. 3. The process was placed in a suspended state by an agent; either itself, a

  15. Page 15
    Read page 15 as text

    -16- parent process, or the operating system, for the purpose of preventing its execution. 4. The process may not be removed from this state until the agent explicitly orders the removal. 3.8 The OS maintains tables for entities related to memory, I/O, files, and processes. See Table 3.10 for details. 3.9 Process identification, processor state information, and process control information. 3.10 The user mode has restrictions on the instructions that can be executed and the memory areas that can be accessed. This is to protect the operating system from damage or alteration. In kernel mode, the operating system does not have these restrictions, so that it can perform its tasks. 3.11 1. Assign a unique process identifier to the new process. 2. Allocate space for the process. 3. Initialize the process control block. 4. Set the appropriate linkages. 5. Create or expand other data structures. 3.12 An interrupt is due to some sort of event that is external to and independent of the currently running process, such as the completion of an I/O operation. A trap relates to an error or exception condition generated within the currently running process, such as an illegal file access attempt. 3.13 Clock interrupt, I/O interrupt, memory fault. 3.14 A mode switch may occur without changing the state of the process that is currently in the Running state. A process switch involves taking the currently executing process out of the Running state in favor of another process. The process switch involves saving more state information. A NSWERS TO P ROBLEMS 3.1 RUN to READY can be caused by a time-quantum expiration READY to NONRESIDENT occurs if memory is overcommitted, and a process is temporarily swapped out of memory READY to RUN occurs only if a process is allocated the CPU by the dispatcher RUN to BLOCKED can occur if a process issues an I/O or other kernel request. BLOCKED to READY occurs if the awaited event completes (perhaps I/O completion) BLOCKED to NONRESIDENT - same as READY to NONRESIDENT.

  16. Page 16
    Read page 16 as text

    -17- 3.2 At time 22: P1: blocked for I/O P3: blocked for I/O P5: ready/running P7: blocked for I/O P8: ready/running At time 37 P1: ready/running P3: ready/running P5: blocked suspend P7: blocked for I/O P8: ready/running At time 47 P1: ready/running P3: ready/running P5: ready suspend P7: blocked for I/O P8: exit 3.3 a. New → Ready or Ready/Suspend : covered in text Ready → Running or Ready/Suspend : covered in text Ready/Suspend → Ready : covered in text Blocked → Ready or Blocked/Suspend : covered in text Blocked/Suspend → Ready /Suspend or Blocked : covered in text Running → Ready, Ready/Suspend, or Blocked : covered in text Any State → Exit : covered in text b. New → Blocked, Blocked/Suspend, or Running : A newly created process remains in the new state until the processor is ready to take on an additional process, at which time it goes to one of the Ready states. Ready → Blocked or Blocked/Suspend: Typically, a process that is ready cannot subsequently be blocked until it has run. Some systems may allow the OS to block a process that is currently ready, perhaps to free up resources committed to the ready process. Ready/Suspend → Blocked or Blocked/Suspend: Same reasoning as preceding entry. Ready/Suspend → Running: The OS first brings the process into memory, which puts it into the Ready state. Blocked → Ready /Suspend : this transition would be done in 2 stages. A blocked process cannot at the same time be made ready and suspended, because these transitions are triggered by two different causes.

127 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.