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

Preview (16 of 143 Pages)

100%

Purchase to unlock

Loading page image...

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

Loading page image...

-5-CHAPTER1COMPUTERSYSTEMOVERVIEWANSWERS TOQUESTIONS1.1A processor, which controls the operation of the computer and performsits data processing functions ; amain memory, which stores both dataand instructions;I/O modules, which move data between thecomputer and its external environment; and the system bus, whichprovides for communication among processors, main memory, and I/Omodules.1.2 User-visible registers:Enable the machine- or assembly-languageprogrammer to minimize main memory references by optimizingregister use. For high-level languages, an optimizing compiler willattempt to make intelligent choices of which variables to assign toregisters and which to main memory locations. Some high-levellanguages, such as C, allow the programmer to suggest to the compilerwhich variables should be held in registers.Control and statusregisters:Used by the processor to control the operation of theprocessor and by privileged, operating system routines to control theexecution of programs.1.3These actions fall into four categories:Processor-memory:Data maybe transferred from processor to memory or from memory to processor.Processor-I/O:Data may be transferred to or from a peripheral deviceby transferring between the processor and an I/O module.Dataprocessing:The processor may perform some arithmetic or logicoperation on data.Control:An instruction may specify that thesequence of execution be altered.1.4An interrupt is a mechanism by which other modules (I/O, memory)may interrupt the normal sequencing of the processor.1.5Two approaches can be taken to dealing with multiple interrupts. Thefirst is to disable interrupts while an interrupt is being processed. Asecond approach is to define priorities for interrupts and to allow aninterrupt of higher priority to cause a lower-priority interrupt handler tobe interrupted.

Loading page image...

-6-1.6The three key characteristics of memory are cost, capacity, and accesstime.1.7Cache memory is a memory that is smaller and faster than mainmemory and that is interposed between the processor and mainmemory. The cache acts as a buffer for recently used memory locations.1.8A multicore computer is a special case of a multiprocessor, in which allof the processors are on a single chip.1.9 Spatial localityrefers to the tendency of execution to involve anumber of memory locations that are clustered.Temporal localityrefers to the tendency for a processor to access memory locations thathave been used recently.1.10 Spatial localityis generally exploited by using larger cache blocksand by incorporating prefetching mechanisms (fetching items ofanticipated use) into the cache control logic.Temporal localityisexploited by keeping recently used instruction and data values incache memory and by exploiting a cache hierarchy.ANSWERS TOPROBLEMS1.1Memory (contents in hex): 300: 3005;301: 5940;302: 7006Step 1:3005→IR;Step 2:3→ACStep 3:5940→IR;Step 4:3 + 2 = 5→ACStep 5:7006→IR;Step 6:AC→Device 61.2 1.a.The PC contains 300, the address of the first instruction. Thisvalue is loaded in to the MAR.b.The value in location 300 (which is the instruction with the value1940 in hexadecimal)is loaded into the MBR, and the PC isincremented. 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 value5941)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 addedand the result is stored in the AC.

Loading page image...

-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 value2941)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.3a.224= 16 MBytesb.(1)If the local address bus is 32 bits, the whole address can betransferred at once and decoded in memory. However, since the databus is only 16 bits, it will require 2 cycles to fetch a 32-bit instructionor operand.(2)The 16 bits of the address placed on the address bus can'taccess the whole memory. Thus a more complex memory interfacecontrol is needed to latch the first part of the address and then thesecond part (since the microprocessor will end in two steps). For a32-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 bitinstruction/operand.c.The program counter must be at least 24 bits. Typically, a 32-bitmicroprocessor will have a 32-bit external address bus and a 32-bitprogram counter, unless on-chip segment registers are used thatmay work with a smaller program counter. If the instruction registeris to contain the whole instruction, it will have to be 32-bits long; if itwill contain only the op code (called the op code register) then it willhave to be 8 bits long.1.4In cases(a)and(b), the microprocessor will be able to access 216=64K bytes; the only difference is that with an 8-bit memory eachaccess will transfer a byte, while with a 16-bit memory an access maytransfer a byte or a 16-byte word. For case(c), separate input andoutput instructions are needed, whose execution will generateseparate "I/O signals" (different from the "memory signals" generatedwith the execution of memory-type instructions); at a minimum, oneadditional output pin will be required to carry this new signal. For case(d), it can support 28= 256 input and 28= 256 output byte ports andthe same number of input and output 16-bit ports; in either case, thedistinction between an input and an output port is defined by thedifferent signal that the executed input or output instructiongenerated.

Loading page image...

-8-1.5Clock cycle =18 MHz=125 nsBus cycle = 4×125 ns = 500 ns2 bytes transferred every 500 ns; thus transfer rate = 4 MBytes/secDoubling the frequency may mean adopting a new chip manufacturingtechnology (assuming each instructions will have the same number ofclock cycles); doubling the external data bus means wider (maybenewer) on-chip data bus drivers/latches and modifications to the buscontrol logic. In the first case, the speed of the memory chips will alsoneed to double (roughly) not to slow down the microprocessor; in thesecond case, the "word length" of the memory will have to double to beable to send/receive 32-bit quantities.1.6a.Input from the Teletype is stored in INPR. The INPR will only acceptdata from the Teletype when FGI=0. When data arrives, it is storedin 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 to0.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 thecontents of the AC to OUTR and sets FGO to 0. The Teletype sets FGIto 1 after the word is printed.b.The process described in(a)is very wasteful. The CPU, which ismuch faster than the Teletype, must repeatedly check FGI and FGO.If interrupts are used, the Teletype can issue an interrupt to the CPUwhenever it is ready to accept or send data. The IEN register can beset by the CPU (under programmer control)1.7If a processor is held up in attempting to read or write memory, usuallyno damage occurs except a slight loss of time. However, a DMA transfermay 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 isheld up (denied continuing access to main memory), data will be lost.1.8Let us ignore data read/write operations and assume the processor onlyfetches instructions. Then the processor needs access to main memoryonce every microsecond. The DMA module is transferring characters at arate of 1200 characters per second, or one every 833μs. The DMAtherefore "steals" every 833rd cycle. This slows down the processorapproximately1833×100%=0.12%

Loading page image...

-9-1.9a.The processor can only devote 5% of its time to I/O. Thus themaximum I/O instruction execution rate is 106×0.05 = 50,000instructions per second. The I/O transfer rate is therefore 25,000words/second.b.The number of machine cycles available for DMA control is106(0.05×5 + 0.95×2) = 2.15×106If we assume that the DMA module can use all of these cycles, andignore any setup or status-checking time, then this value is themaximum I/O transfer rate.1.10a.A reference to the first instruction is immediately followed by areference to the second.b.The ten accesses toa[i]within the inner for loop which occurwithin a short interval of time.1.11DefineCi=Average cost per bit, memory level iSi=Size of memory level iTi=Time to access a word in memory level iHi=Probability that a word is in memory i and in no higher-levelmemoryBi=Time to transfer a block of data from memory level (i + 1) tomemory leveliLet cache be memory level 1; main memory, memory level 2; and soon, for a total of N levels of memory. ThenCs=CiSii=1N∑Sii=1N∑The derivation of Tsis more complicated.We begin with the result fromprobability theory that:Expected Value ofx=iPrx=1[]i=1N∑We can write:Ts=TiHii=1N∑

Loading page image...

-10-We need to realize that if a word is in M1(cache), it is read immediately.If it is in M2but not M1, then a block of data is transferred from M2toM1and then read. Thus:T2= B1+ T1FurtherT3= B2+ T2= B1+ B2+ T1Generalizing:Ti=Bj+T1j=1i−1∑SoTs=BjHi()j=1i−1∑i=2N∑+T1Hii=1N∑ButHii=1N∑=1FinallyTs=BjHi()j=1i−1∑i=2N∑+T11.12a.Cost = Cm×8×106= 8×103¢ = $80b.Cost = Cc×8×106= 8×104¢ = $800c.From Equation 1.1 : 1.1×T1= T1+ (1 – H)T2(0.1)(100) = (1 – H)(1200)H = 1190/1200

Loading page image...

-11-1.13There are three cases to consider:Location of referencedwordProbabilityTotal time for accessin nsIn cache0.920Not in cache, but in mainmemory(0.1)(0.6) = 0.0660 + 20 = 80Not in cache or mainmemory(0.1)(0.4) = 0.0412ms + 60 + 20 =12,000,080So the average access time would be:Avg = (0.9)(20) + (0.06)(80) + (0.04)(12000080) = 480026 ns1.14Yes, if the stack is only used to hold the return address. If the stack isalso used to pass parameters, then the scheme will work only if it isthe control unit that removes parameters, rather than machineinstructions. In the latter case, the processor would need both aparameter and the PC on top of the stack at the same time.

Loading page image...

-12-CHAPTER2OPERATINGSYSTEMOVERVIEWANSWERS TOQUESTIONS2.1 Convenience:An operating system makes a computer moreconvenient to use.Efficiency:An operating system allows thecomputer system resources to be used in an efficient manner.Abilityto evolve:An operating system should be constructed in such a way asto permit the effective development, testing, and introduction of newsystem functions without interfering with service.2.2The kernel is a portion of the operating system that includes the mostheavily used portions of software. Generally, the kernel is maintainedpermanently in main memory. The kernel runs in a privileged mode andresponds to calls from processes and interrupts from devices.2.3Multiprogramming is a mode of operation that provides for theinterleaved execution of two or more computer programs by a singleprocessor.2.4A process is a program in execution. A process is controlled andscheduled by the operating system.2.5Theexecution context,orprocess state,is the internal data bywhich the operating system is able to supervise and control the process.This internal information is separated from the process, because theoperating system has information not permitted to the process. Thecontext includes all of the information that the operating system needsto manage the process and that the processor needs to execute theprocess properly. The context includes the contents of the variousprocessor registers, such as the program counter and data registers. Italso includes information of use to the operating system, such as thepriority of the process and whether the process is waiting for thecompletion of a particular I/O event.2.6 Process isolation:The operating system must prevent independentprocesses from interfering with each other's memory, both data andinstructions.Automatic allocation and management:Programs

Loading page image...

-13-should be dynamically allocated across the memory hierarchy asrequired. Allocation should be transparent to the programmer. Thus, theprogrammer is relieved of concerns relating to memory limitations, andthe operating system can achieve efficiency by assigning memory tojobs 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 andaccess control:Sharing of memory, at any level of the memoryhierarchy, creates the potential for one program to address the memoryspace of another. This is desirable when sharing is needed by particularapplications. At other times, it threatens the integrity of programs andeven of the operating system itself. The operating system must allowportions of memory to be accessible in various ways by various users.Long-term storage:Many application programs require means forstoring information for extended periods of time, after the computer hasbeen powered down.2.7Avirtual addressrefers to a memory location in virtual memory. Thatlocation is on disk and at some times in main memory. A real address isan address in main memory.2.8Round robin is a scheduling algorithm in which processes are activatedin a fixed cyclic order; that is, all processes are in a circular queue. Aprocess that cannot proceed because it is waiting for some event (e.g.termination of a child process or an input/output operation) returnscontrol to the scheduler.2.9Amonolithic kernelis a large kernel containing virtually the completeoperating system, including scheduling, file system, device drivers, andmemory management. All the functional components of the kernel haveaccess to all of its internal data structures and routines. Typically, amonolithic kernel is implemented as a single process, with all elementssharing the same address space. Amicrokernelis a small privilegedoperating system core that provides process scheduling, memorymanagement, and communication services and relies on other processesto perform some of the functions traditionally associated with theoperating system kernel.2.10Multithreading is a technique in which a process, executing anapplication, is divided into threads that can run concurrently.2.11Simultaneous concurrent processes or threads; scheduling;synchronization; memory management; reliability and fault tolerance.ANSWERS TOPROBLEMS

Loading page image...

-14-2.1The answers are the same for(a)and(b). Assume that althoughprocessor operations cannot overlap, I/O operations can.Number of jobsTATThroughputProcessor utilization1NT1/N50%2NT2/N100%4(2N – 1)T4/(2N – 1)100%2.2I/O-bound programs use relatively little processor time and aretherefore favored by the algorithm. However, if a processor-boundprocess is denied processor time for a sufficiently long period of time,the same algorithm will grant the processor to that process since it hasnot used the processor at all in the recent past. Therefore, a processor-bound process will not be permanently denied access.2.3With time sharing, the concern is turnaround time. Time-slicing ispreferred because it gives all processes access to the processor over ashort period of time. In a batch system, the concern is with throughput,and the less context switching, the more processing time is available forthe processes. Therefore, policies that minimize context switching arefavored.2.4A system call is used by an application program to invoke a functionprovided by the operating system. Typically, the system call results intransfer to a system program that runs in kernel mode.2.5The system operator can review this quantity to determine the degreeof "stress" on the system. By reducing the number of active jobsallowed on the system, this average can be kept high. A typicalguideline is that this average should be kept above 2 minutes. This mayseem like a lot, but it isn't.2.6a.If a conservative policy is used, at most 20/4 = 5 processes can beactive simultaneously. Because one of the drives allocated to eachprocess can be idle most of the time, at most 5 drives will be idle at atime. In the best case, none of the drives will be idle.b.To improve drive utilization, each process can be initially allocatedwith three tape drives. The fourth one will be allocated on demand.In this policy, at most⎣20/3⎦= 6 processes can be activesimultaneously. The minimum number of idle drives is 0 and themaximum number is 2.

Loading page image...

-15-CHAPTER3PROCESSDESCRIPTION ANDCONTROLANSWERS TOQUESTIONS3.1An instruction trace for a program is the sequence of instructions thatexecute for that process.3.2New 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:Aprocess that is prepared to execute when given the opportunity.Blocked:A process that cannot execute until some event occurs, suchas the completion of an I/O operation.New:A process that has justbeen created but has not yet been admitted to the pool of executableprocesses by the operating system.Exit:A process that has beenreleased from the pool of executable processes by the operating system,either because it halted or because it aborted for some reason.3.4Process preemption occurs when an executing process is interrupted bythe processor so that another process can be executed.3.5Swapping involves moving part or all of a process from main memory todisk. When none of the processes in main memory is in the Ready state,the operating system swaps one of the blocked processes out onto diskinto a suspend queue, so that another process may be brought intomain memory to execute.3.6There are two independent concepts: whether a process is waiting on anevent (blocked or not), and whether a process has been swapped out ofmain memory (suspended or not). To accommodate this 2×2combination, we need two Ready states and two Blocked states.3.7 1.The process is not immediately available for execution.2.Theprocess may or may not be waiting on an event. If it is, this blockedcondition is independent of the suspend condition, and occurrence of theblocking event does not enable the process to be executed.3.Theprocess was placed in a suspended state by an agent; either itself, a

Loading page image...

-16-parent process, or the operating system, for the purpose of preventingits execution.4.The process may not be removed from this state untilthe agent explicitly orders the removal.3.8The OS maintains tables for entities related to memory, I/O, files, andprocesses. See Table 3.10 for details.3.9Process identification, processor state information, and process controlinformation.3.10The user mode has restrictions on the instructions that can beexecuted and the memory areas that can be accessed. This is toprotect the operating system from damage or alteration. In kernelmode, the operating system does not have these restrictions, so that itcan perform its tasks.3.11 1.Assign a unique process identifier to the new process.2.Allocatespace for the process.3.Initialize the process control block.4.Set theappropriate linkages.5.Create or expand other data structures.3.12An interrupt is due to some sort of event that is external to andindependent of the currently running process, such as the completionof an I/O operation. A trap relates to an error or exception conditiongenerated within the currently running process, such as an illegal fileaccess attempt.3.13Clock interrupt, I/O interrupt, memory fault.3.14A mode switch may occur without changing the state of the processthat is currently in the Running state. A process switch involves takingthe currently executing process out of the Running state in favor ofanother process. The process switch involves saving more stateinformation.ANSWERS TOPROBLEMS3.1RUN to READY can be caused by a time-quantum expirationREADY to NONRESIDENT occurs if memory is overcommitted, and aprocess is temporarily swapped out of memoryREADY to RUN occurs only if a process is allocated the CPU by thedispatcherRUN to BLOCKED can occur if a process issues an I/O or other kernelrequest.BLOCKED to READY occurs if the awaited event completes (perhaps I/Ocompletion)BLOCKED to NONRESIDENT - same as READY to NONRESIDENT.

Loading page image...

-17-3.2At time 22:P1: blocked for I/OP3: blocked for I/OP5: ready/runningP7: blocked for I/OP8: ready/runningAt time 37P1: ready/runningP3: ready/runningP5: blocked suspendP7: blocked for I/OP8: ready/runningAt time 47P1: ready/runningP3: ready/runningP5: ready suspendP7: blocked for I/OP8: exit3.3a.New→Ready or Ready/Suspend: covered in textReady→Running or Ready/Suspend: covered in textReady/Suspend→Ready: covered in textBlocked→Ready or Blocked/Suspend: covered in textBlocked/Suspend→Ready /Suspend or Blocked: covered intextRunning→Ready, Ready/Suspend, or Blocked: covered in textAny State→Exit: covered in textb.New→Blocked, Blocked/Suspend, or Running: A newly createdprocess remains in the new state until the processor is ready to takeon an additional process, at which time it goes to one of the Readystates.Ready→Blocked or Blocked/Suspend:Typically, a process thatis ready cannot subsequently be blocked until it has run. Somesystems 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:Samereasoning as preceding entry.Ready/Suspend→Running:The OS first brings the process intomemory, which puts it into the Ready state.Blocked→Ready /Suspend: this transition would be done in 2stages. A blocked process cannot at the same time be made readyand suspended, because these transitions are triggered by twodifferent causes.

Preview Mode

This document has 143 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools