Chapter1 Computer System Overview

Operating System

  • Exploits the hardware resources of one or more processors 利用处理器硬件资源
  • Provides a set of services to system users 为系统用户提供服务
  • Manages secondary memory and I/O devices 为用户管理辅存、I/O设备

1.1 A Computer’s Basic Elements

  • Processor


  • MainMemory


  • I/OModules


  • SystemBus


At a top level, a computer consists of processor, memory, and I/O components, with one or more modules of each type.

These components are interconnected in some fashion to achieve the main function of the computer, which is to execute programs.

Top-level View
Top-level View

1.2 Processor Registers

  • User-visibleregisters用户可见寄存器

    –Enableprogrammer to minimize main memory refer. by optimizing register use通过优化寄存器使用,可减少内存访问

  • Controland status registers控制&状态寄存器

    –Usedby processor to control operating of the processor用来控制处理器的操作

    –Usedby privilegedOS routines to control the execution ofprograms特权OS例程访问

A processor includes a set of registers that provide memory that is faster andsmaller than main memory.

Processor registers serve two functions:

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 OS routines to control the execution of programs.

NOTE:There is not a clean separation of registers into these two categories.

• For example, on some processors, the program counter is user visible, but on many it is not.

• For purposes of the following discussion, however, it is convenient to use these categories.

1.User-Visible Registers

  • Maybe referenced by machine language可通过机器语言来引用

    –Availableto all programs – application programs and system programs所有程序可用

  • Typesof registers typically available are:


    –Address register地址寄存器

    –Condition code register条件码寄存器

A user-visible register may be referenced by means of the machine language that the processor executes and is generally available to all programs, including application programs as well as system programs.

Types of registers that are typically available are


•address, and

•condition code registers

Data and Address Registers

  • DataRegister

    –Oftengeneral purpose通用寄存器

    –Butsome restrictions may apply也有限制

  • AddressRegister




Data registers can be assigned to a variety of functions by the programmer.

•Usually they are general purpose in nature and can be used with any machine instruction that performs operations on data.

•Often, however, there are restrictions. E.g. there may be dedicated registers for floating-point operations and others for integer operations.

Address registers contain:

• main memory addresses of data and instructions,

• or they contain a portion of the address that is used in the calculation of the complete or effective address.

These registers may themselves be general purpose, or may be devoted to a particular way, or mode, of addressing memory.

Examples include:

Index register: Indexed addressing is a common mode of addressing that involves adding an index to a base value to get the effective address.

Segment pointer: With segmented addressing, memory is divided into segments, which are variable-length blocks of words.

• A memory reference consists of a reference to a particular segment and an offset within the segment.

• In this mode of addressing, a register is used to hold the base address (starting location) of the segment.

•There may be multiple registers; for example, one for the OS (i.e., when OS code is executing on the processor) and one for the currently executing application.

Stack pointer: If there is user-visible stack addressing, then there is a dedicated register that points to the top of the stack.

• This allows the use of instructions that contain no address field, such as push and pop.

2.Control and Status Registers

  • Programcounter (PC)程序计数器

    –Containsthe address of an instruction to be fetched下条要读取的指令地址

  • Instructionregister (IR)指令寄存器

    –Containsthe instruction most recently fetched最近读取的指令

  • Programstatus word (PSW)程序状态字

    –Containsstatus information:条件码、中断位等

A variety of processor registers are employed to control the operation of the processor.

On most processors, most of these are not visible to the user.

• Some of them may be accessible by machine instructions executed in what is referred to as a control or kernel mode.

Different processors will have different register organizations and use different terminology.

In addition to the MAR,MBR, I/OAR, and I/O BR the following are essential to instruction execution:

Programcounter (PC): Contains the address of the next instruction to be fetched

Instruction register (IR): Contains the instruction most recently fetched

Theprogram status word (PSW), contains status information.

• The PSW typically contains condition codes plus other status information, such as an interrupt enable/disable bit and a kernel/user mode bit.


  • 通常OS引入程序状态字PSW来区别处理器工作状态





  • 程序基本状态




  • 中断码:保存程序执行时当前发生的中断事件
  • 中断屏蔽位:指明程序执行中发生中断事件时,是否响应出现的中断事件。


psw of IBM370
psw of IBM370

4.Condition codes条件码

  • Usually part of the control register,also called flags
  • Bits set by processor hardware as a result of operations根据运算结果由硬件设置

    –Read only, intended for feedback regarding the results of instruction execution.只读,跟据指令执行结果提供反馈

Intel Pentium EFLAGS

Intel Pentium EFLAGS

Bits typically set by the processor hardware as the result of operations.

For example, an arithmetic operation may produce a positive, negative, zero, or overflow result.

• In addition to the result itself being stored in a register or memory, a condition code is also set following the execution of the arithmetic instruction.

• Thecondition code may subsequently be tested as part of a conditional branchoperation.

•Condition code bits are collected into one or more registers.

Usually,they form part of a control register.

Generally,machine instructions allow these bits to be read by implicit reference, but they cannot be altered by explicit reference because they are intended for feedback regarding the results of instruction execution.

1.3 Instruction Execution

  • 机器指令的集合称指令系统,指令种类:

    –Processor-memory处理器 数据 内存

    –processor-I/O处理器 数据 I/O模块

    –Dataprocessing 数据处理(算术、逻辑)


  • 特权指令与非特权指令


A program to be executed by a processor consists of a set of instructions stored in memory.

In its simplest form, instruction processing consists of two steps:

• The processor reads (fetches) instructions from memory one at a time

• and executes each instruction.

Program execution consists of repeating the process of instruction fetch and instruction execution.

1.Basic Instruction Cycle 指令周期

  • Processorreads (fetches) instructions from memory处理器←指令←内存


  • Processorexecutes each instruction执行指令

Basic Instruction Cycle

Basic Instruction Cycle
Basic Instruction Cycle

The two steps are referred to as the fetch stage and the execute stage.

Instruction execution may involve several operations and depends on the nature of the instruction.

•The processing required for a single instruction is called an instruction

Program execution halts only if the processor is turned off, some sort of unrecoverable error occurs, or a program instruction that halts the processor is encountered.

2.Characteristics of a Hypothetical Machine

Consider a simple example using a hypothetical processor

The processor contains a single data register, called the accumulator (AC).

Both instructions and data are 16 bits long, and memory is organized as a sequence of 16-bit words.

• The instruction format provides 4 bits for the opcode, allowing as many as 24 = 16 different opcodes

•represented by a single hexadecimal digit.

The opcode defines the operation the processor is to perform.

With the remaining 12 bits of the instruction format, up to 212 = 4096 (4 K) words of memory can be directly addressed.

•denoted by three hexadecimal digits.

Example of Program Execution

This figure illustrates a partial program execution, showing the relevant portions of memory and processor registers.

The program fragment shown adds the contents of the memory word at address 940 to the contents of the memory word at address 941 and stores the result in the latter location.

Three instructions, which can be described as three fetch and three execute stages,
are required:

  1. The PC contains 300, the address of the first instruction.

•This instruction (the value 1940 in hexadecimal) is loaded into the IR and the PC is incremented.

•Note that this process involves the use of a memory address register (MAR) and a memory buffer register (MBR).

• For simplicity, these intermediate registers are not shown.

2.The first 4 bits (first hexadecimal digit) in the IR indicate that the AC is to be loaded from memory.

• There maining 12 bits (three hexadecimal digits) specify the address, which is 940.

3.The next instruction (5941) is fetched from location 301 and the PC is incremented.

4.The old contents of the AC and the contents of location 941 are added and the result is stored in the AC.

5.The next instruction (2941) is fetched from location 302 and the PC is incremented.

6.The contents of the AC are stored in location 941.

1.4 Interrupts中断

  • 中断是指程序执行过程中,当发生某个事件时,中止CPU上现行程序的运行,引出处理该事件的程序执行的过程。
  • Providedto improve processor utilization提高处理器的利用率

    –MostI/O devices are slower than the processor多数I/O设备比处理器慢

    –Processormust pause to wait for device处理器暂停等设备

Virtually all computers provide a mechanism by which other modules (I/O, memory) may interrupt the normal sequencing of the processor.

Interrupts are provided primarily as a way to improve processor utilization.

•For example,most I/O devices are much slower than the processor.

Suppose that the processor is transferring data to a printer using the instruction cycle scheme described earlier.

•After each write operation, the processor must pause and remain idle until the printer catches up.

The length of this pause may be on the order of many thousands or even millions of instruction cycles.

•Clearly, this is a very wasteful use of the processor.

1.Common Classes of Interrupts

Table1.1 lists the most common classes of interrupts.

  • 按中断事件的性质和激活手段分为:



  • 按照中断信号的来源和实现:



  • 中断




  • 异常



2.Flow of Control 控制流

NB:Animated slide showing each stage one at a time.

A)No Interrupts

Figure 1.5a illustrates this previous printer example.

• The user program performs a series of WRITE calls interleaved with processing.

• The solid vertical lines represent segments of code in a program.

• Code segments 1, 2, and 3 refer to sequences of instructions that do not involve I/O.

• The WRITE calls are to an I/O routine that is a system utility and that will perform the actual I/O operation.

The I/O program consists of three sections:

• A sequence of instructions, labeled 4 in the figure, to prepare for the actual I/O operation.

• This may include copying the data to be output into a special buffer and preparing the parameters for a device command.

• The actual I/O command.

•Without the use of interrupts, once this command is issued, the program must wait for the I/O device to perform the requested function (or periodically check the status, or poll, the I/O device).

• The program might wait by simply repeatedly performing a test operation to determine if the I/O operation is done.

• A sequence of instructions, labeled 5 in the figure, to complete the operation.

• This may include setting a flag indicating the success or failure of the operation.

The dashed line represents the path of execution followed by the processor;

• i.e., this line shows the sequence in which instructions are executed.

•Thus, after the first WRITE instruction is encountered, the user program is interrupted and execution continues with the I/O program.

•After the I/O program execution is complete, execution resumes in the user program immediately following the WRITE instruction.

Because the I/O operation may take a relatively long time to complete, the I/O program is hung up waiting for the operation to complete;

•hence, the user program is stopped at the point of the WRITE call for some considerable period of time.

Transfer of Control via Interrupts


For the user program, an interrupt suspends the normal sequence of execution.

• When the interrupt processing is completed, execution resumes.

•Thus, the user program does not have to contain any special code to accommodate interrupts;

• the processor and the OS are responsible for suspending the user program and then resuming it at the same point.

Instruction Cycle with Interrupts

To accommodate interrupts, an interrupt stage is added to the instruction cycle,as shown here (compare Figure 1.2 earlier).

In the interrupt stage, the processor checks to see if any interrupts have occurred, indicated by the presence of an interrupt signal.

• If no interrupts are pending, the processor proceeds to the fetch stage and fetches the next instruction of the current program.

• If an interrupt is pending, the processor suspends execution of the current program and executes an interrupt-handler routine.

The interrupt-handler routine is generally part of the OS.

•Typically,this routine determines the nature of the interrupt and performs whatever actions are needed.

In the example we have been using, the handler determines which I/O module generated the interrupt and may branch to a program that will write more data out to that I/O module.

• When the interrupt-handler routine is completed, the processor can resume execution of the user program at the point of interruption.

Short I/O Wait

To appreciate the gain in efficiency, consider Figure 1.8, which is a timing diagram based on the flow of control in Figures 1.5 a and 1.5b.

Figures 1.5b and 1.8 assume that the time required for the I/O operation is relatively short:

• less than the time to complete the execution of instructions between write operations in the user program.

•The more typical case, especially for a slow device such as a printer, is that the I/O operation will take much more time than executing a sequence of user instructions.

Long I/O wait

Figure1.5 c indicates a more typical state of affairs.

In this case, the user program reaches the second WRITE call before the I/O operation spawned by the first call is complete.

• The result is that the user program is hung up at that point.

When the preceding I/O operation is completed, this new WRITE call may be processed,and a new I/O operation may be started.

Figure1.9 shows the timing for this situation with and without the use of interrupts.

• We can see that there is still a gain in efficiency because part of the time during which the I/O operation is underway overlaps with the execution of user instructions.

3.Simple Interrupt Processing
  • 发现中断源
  • 保护现场
  • 启动中断和异常处理程序
  • 恢复现场

An interrupt triggers a number of events, both in the processor hardware and in software.

This figure shows a typical sequence.

When an I/O device completes an I/O operation, the following sequence of hardware events occurs:

1.The device issues an interrupt signal to the processor.

2.The processor finishes execution of the current instruction before responding to the interrupt.

3.The processor tests for a pending interrupt request, determines that there is one, and sends an acknowledgment signal to the device that issued the interrupt.

• The acknowledgment allows the device to remove its interrupt signal.

4.The processor next needs to prepare to transfer control to the interrupt routine.

5.The processor then loads the program counter with the entry location of the interrupt-handling routine that will respond to this interrupt.

6.At this point, the program counter and PSW relating to the interrupted program have been saved on the control stack.

• Next slide shows more detail on this step

7.The interrupt handler may now proceed to process the interrupt.

8.The saved register values are retrieved from the stack and restored to the registers

9.The final act is to restore the PSW and program counter values from the stack.

It is important to save all of the state information about the interrupted program for later resumption.

•Because the interrupt is not a routine called from the program.

•Rather, the interrupt can occur at any time and therefore at any point in the execution of a user program.

• Its occurrence is unpredictable.

Changes in Memory and Registers for an Interrupt

From step 6 in previous diagram

In this case, a user program is interrupted after the instruction at location N.

The contents of all of the registers plus the address of the next instruction (N +1), a total of M words, are pushed onto the control stack.

• The stack pointer is updated to point to the new top of stack, and the programcounter is updated to point to the beginning of the interrupt service routine.

4.Multiple Interrupts多个中断
  • Suppose an interrupt occurs while another interrupt is being processed.中断处理过程中又发生中断

    –E.g.printing data being received via communications line.

  • Two approaches:

    –Disable interrupts during interrupt processing中断处理过程中关中

    –Use a priority scheme.优先级方案

Suppose that one or more interrupts can occur while an interrupt is being processed.

E.G., a program may be receiving data from a communications line and printing results at the same time.

• The printer will generate an interrupt every time that it completes a print operation.

• The communication line controller will generate an interrupt every time a unit of data arrives.

Two approaches can be taken to dealing with multiple interrupts.

The first is to disable interrupts while an interrupt is being processed.

• A disabled interrupt simply means that the processor ignores any new interrupt request signal.

•If an interrupt occurs during this time, it generally remains pending and will be checked by the processor after the processor has re-enabled interrupts.

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.

Sequential Interrupt Processing 顺序中断处理

Simple sequential approach to multiple interrupts

Nested Interrupt Processing 嵌套中断处理

Using priorities to “nest” interrupt processing

Example of Nested Interrupts

As an example of this second approach, consider a system with three I/O devices:

• a printer (priority 2),

• a disk (priority 4), and

• a communications line (priority 5).

This figure illustrates a possible sequence.

1.A user program begins at t= 0.

2.At t=10, a printer interrupt occurs; user information is placed on the control stack and execution continues at the printer interrupt service routine (ISR)

3.While this routine is still executing, at t =15 a communications interrupt occurs. Because the communications line has higher priority than the printer, the interrupt request is honored.

4.The printer ISR is interrupted, its state is pushed onto the stack, and execution continues at the communications ISR.

5.While this routine is executing, a disk interrupt occurs (t=20).Because this interrupt is of lower priority, it is simply held, and the communications ISR runs to completion.

6.When the communications ISR is complete (t=25), the previous processor state is restored, which is the execution of the printer ISR.

7.However,before even a single instruction in that routine can be executed, the processor honors the higher-priority disk interrupt and transfers control to the diskISR.

8.Only when that routine is complete (t=35) is the printer ISR resumed.

9.When that routine completes (t=40), control finally returns to the user program.

1.5 Memory Hierarchy存储器的层次结构

  • Majorconstraints in memory




  • Fasteraccess time, greater cost per bit
  • Greatercapacity, smaller cost per bit
  • Greatercapacity, slower access speed

There is a trade off among the three key characteristics of memory:

• namely, capacity, access time, and cost.

A variety of technologies are used to implement memory systems, and across this spectrum of technologies, the following relationships hold:

• Faster access time, greater cost per bit

• Greater capacity, smaller cost per bit

• Greater capacity, slower access speed

The Memory Hierarchy
  • Goingdown the hierarchy

    –Decreasing cost per bit

    –Increasing capacity

    –Increasing access time

    –Decreasing frequency of access to the memory by the processor访问频率降低

NOTE:Onclick, Animated diagram slides to centre and grows

A typical hierarchy is illustrated in this figure.

As one goes down the hierarchy, the following occur:

a.Decreasing cost per bit

b.Increasing capacity

c.Increasing access time

d.Decreasing frequency of access to the memory by the processor

Thus,smaller, more expensive, faster memories are supplemented by larger, cheaper,slower memories.

The key to the success of this organization decreasing frequency of access at lower levels.

1.6 Cache Memory

  • Invisibleto the OS

    –Interactswith other memory management hardware与其他存储管理硬件交互

  • Processormust access memory at least once per instruction cycle处理器每个指令周期至少一次存储器访问

    –Processorfaster than memory access speed

  • Exploitthe principleof locality witha small fast memory利用局部性原理,配置cache

Although cache memory is invisible to the OS, it interacts with other memory management hardware.

On all instruction cycles, the processor accesses memory at least once,

• to fetch the instruction, and often one or more additional times, to fetch operands and/or store results.

The rate at which the processor can execute instructions is clearly limited by the memory cycle time

•i.e.the time it takes to read one word from or write one word to memory.

This limitation has been a significant problem because of the persistent mismatch between processor and main memory speeds:

• Over the years, processor speed has consistently increased more rapidly than memory access speed.

• We are faced with a tradeoff among speed, cost, and size.

Ideally,main memory should be built with the same technology as that of the processor registers, giving memory cycle times comparable to processor cycle times.

• This has always been too expensive a strategy.

• The solution is to exploit the principle of locality by providing a small, fast memory between the processor and main memory, namely the cache.

Cache and Main Memory

Cache memory is intended to provide memory access time approaching that of the fastest memories available and at the same time support a large memory size that has the price of less expensive types of semiconductor memories.

There is a relatively large and slow main memory together with a smaller, faster cache memory.

• The cache contains a copy of a portion of main memory.

Cache Principles高速缓存原理
  • Containscopy of a portion of main memory包括部分内存的副本
  • Processorfirst checks cache处理器先访问cache

    –If not found, block of memory read into cache如果没找到,将相应内存块读入cache

  • Because of locality of reference, likely future memory references are in that block根据局部性原理,将来可能的内存访问在读入的块中

When the processor attempts to read a byte or word of memory, a check is made to determine if the byte or word is in the cache.

• If so, the byte or word is delivered to the processor.

• If not, a block of main memory, consisting of some fixed number of bytes, is read into the cache and then the byte or word is delivered to the processor.

Because of the phenomenon of locality of reference, when a block of data is fetched into the cache to satisfy a single memory reference, it is likely that many ofthe near-future memory references will be to other bytes in the block.

Cache/Main-Memory Structure

Figure1.17 depicts the structure of a cache/main memory system.

Main memory consists of up to 2n addressable words, with each word having a uniquen-bit address.

For mapping purposes, this memory is considered to consist of a number offixed-length blocks of K words each.

•i.e.,there are M=2n/K blocks.

Cache consists of C slots (also referred to as lines) of K words each, and the number of slots is considerably less than the number of main memory blocks (C <<M).

Some subset of the blocks of main memory resides in the slots of the cache.

• If a word in a block of memory that is not in the cache is read, that block is transferred to one of the slots of the cache.

Because there are more blocks than slots, an individual slot cannot be uniquely and permanently dedicated to a particular block.

•Therefore, each slot includes a tag that identifies which particular block is currently being stored.

• The tag is usually some number of higher-order bits of the address and refers to all addresses that begin with that sequence of bits.

Cache Read Operation

Figure1.18 illustrates the read operation.

The processor generates the address, RA, of a word to be read.

If the word is contained in the cache,

• it is delivered to the processor.

•Otherwise, the block containing that word is loaded into the cache and the word is delivered to the processor.

Cache Design Issues
  • Maincategories are:

    –Cache size

    –Block size

    –Mapping function映射函数

    –Replacement algorithm置换算法

    –Write policy写策略

    –Number of cache levels

We will see that similar design issues must be addressed in dealing with virtual memory and disk cache design.

They fall into the following categories:

•Cache size

•Block size

•Mapping function

•Replacement algorithm

•Write policy

1.7 I/O Techniques

  • Whenthe processor encounters an instruction relating to I/O, it executes thatinstruction by issuing a command to the appropriate I/O module
  • Threetechniques are possible for I/O operations:

    –Programmed I/O程序控制I/O

    –Interrupt-driven I/O中断驱动I/O

    –Direct memory access (DMA)直接存储器访问

###### 1.Programmed I/O   程序控制I/O
  • TheI/O module performs the requested action I/O模块执行所请求操作

    –then sets the appropriate bits inthe I/O status register 将I/O状态寄存器适当位置位

    –but takes no further action toalert the processor.不告知处理器

  • Theprocessor periodically checks the status of the I/O module until it determinesthe instruction is complete处理器周期性检查I/O模块状态直到确定指令完成
  • Withprogrammed I/O the performance level of the entire system is severely degraded系统性能急剧下降

The I/O module performs the requested action and then sets the appropriate bits in the I/O status register but takes no further action to alert the processor.

In particular, it does not interrupt the processor.

•Thus, after the I/O instruction is invoked, the processor must take some activerole in determining when the I/O instruction is completed.

• So,the processor periodically checks the status of the I/O module until it finds that the operation is complete.

2.Interrupt-Driven I/O中断驱动I/O
  • Processorissues an I/O command to a module 处理器发出I/O命令

    –andthen goes on to do some other useful work.转去做其他有意义工作

  • TheI/O module will then interrupt the processor to request service when it isready to exchange data with the processor.当I/O模块准备好与处理器交换数据时,中断处理器请求服务

The processor to issues an I/O command to a module and then go on to do some other useful work.

• The I/O module will then interrupt the processor to request service when it is ready to exchange data with the processor.

• The processor then executes the data transfer, as before, and then resumes its former processing.

Interrupt-Driven I/O Drawbacks

  • Transferrate is limited by the speed with which the processor can test and service adevice
  • Theprocessor is tied up in managing an I/O transfer每次读写要通过处理器

    –a number of instructions must be executed for each I/O transfer

Interrupt-driven I/O is more efficient than programmed I/O because it eliminates need less waiting.

•However, interrupt-driven I/O still consumes a lot of processor time, because every word of data that goes from memory to I/O module or from I/O module to memory must pass through the processor.

Eliminates needless waiting消除了不必要的等待

But everything passes through processor.

3.Direct Memory Access直接存储器访问
  • Performed by a separate module on the system I/O由单独模块完成
  • When needing to R/W, processor issues a command to DMA module:给DMA发命令

    –Whethera read or write is requested 读/写?

    –Theaddress of the I/O device involved设备地址

    –Thestarting location in memory to read/write读写的内存起始地址

    –Thenumber of words to be read/written读写字节数

When large volumes of data are to be moved, a more efficient technique is required:direct memory access (DMA).

The DMA function can be performed by a separate module on the system bus or it can be incorporated into an I/O module.

When the processor wishes to read or write a block of data, it issues a command to the DMA module, by sending to the DMA module the following information:

•Whether a read or write is requested

•The address of the I/O device involved

•The starting location in memory to read data from or write data to

•The number of words to be read or written

Direct Memory Access

  • I/Ooperation delegated to DMA module读写操作委托DMA
  • Transfersthe entire block of data directly to and from memory without going through theprocessor整块数据的传输无需处理器

    –Processor only involved when beginning and endingtransfer.处理器仅在开始与结束时干预

  • Muchmore efficient.

The processor can continue with other work.

It has delegated this I/O operation to the DMA module, and that module will take care of it.

• The DMA module transfers the entire block of data, one word at a time, directly toor from memory without going through the processor.

When the transfer is complete, the DMA module sends an interrupt signal to the processor.

• Thus the processor is involved only at the beginning and end of the transfer