Chapter 2

Chapter 2: Computer-System Structures
􀂄 Computer System Operation
􀂄 I/O Structure
􀂄 Storage Structure
􀂄 Storage Hierarchy
􀂄 Hardware Protection

Computer-System Architecture
CPU and device controllers can execute concurrently, competing for memory access.

Interrupts
􀂄 Modern operating systems are interrupt driven.
􀂄 An interrupt can be from hardware (i.e., completion of I/O) or software
􀂄 A software-generated interrupt (also called trap) is caused either by an error or a system call
􀂄 For each type of interrupt, OS provides an interrupt service routine
􀂄 When CPU is interrupted:
􀀩 Complete current instruction
􀀩 Transfer execution to interrupt service routine (ISR)
􀀩 When ISR completes, resume interrupted computation

Interrupt Handling
How to locate an ISR?
􀂄 Use interrupt vector - an array of pointers to ISRs
􀂄 Interrupt vector indexed by device number
􀂄 Interrupt vector stored at fixed location, usually in low memory

How to resume?
􀂄 Save return address
􀂄 If ISR needs to use registers, save old values in registers
􀂄 After completing, ISR restores register values and load return address into program counter

I/O Interrupts
A device controller
􀂄 is in charge of a specific type of device
􀂄 maintain some local buffer and a set of special-purpose registers
􀂄 is responsible for moving data between device and buffer
􀂄 To start an I/O operation:
􀀩 CPU loads registers in device controller
􀀩 Device controller examines registers and takes appropriate action
􀂄 When device controller completes I/O, triggers interrupt

Two I/O Methods
Synchronous I/O: kernel returns control to user program only upon I/O completion.
Asynchronous I/O: kernel returns control to user program without waiting for I/O completion

I/O Structure
􀂄 How does kernel wait for I/O completion?
􀀩 Use wait instruction or wait loop
􀂄 If kernel always waits for I/O completion, at most one I/O request is outstanding at a time
􀀩 Advantage: when an interrupt occurs, OS knows which device is interrupting
􀀩 Disadvantage: can’t overlap I/O with I/O, I/O with computation
􀂄 A better approach: kernel continues processing after starting I/O
􀀩 If there are user programs ready to run, execute one
􀀩 If nothing else to do: use wait instruction or wait loop
􀀩 Can have multiple I/O requests outstanding
􀃎use device status table to keep track
􀀗 If device busy, type of request and other parameters stored in table entry for device
􀀗 Each device has a wait queue

I/O Structure (cont’d)
􀂄 When an I/O device interrupts:
􀀩 Operating system indexes into device-status table to determine device status and modify table entry
􀀩 If the interrupt signals I/O completion, kernel processes next request if wait queue not empty

Direct Memory Access (DMA) Structure
􀂄 Used for high-speed I/O devices
􀂄 Device driver sets up source/destination addresses and transfer length in registers of DMA controller
􀂄 DMA controller transfers a block of data between I/O device and memory without CPU intervention.
􀂄 DMA controller generates an interrupt when entire block is transferred.

Storage Structure
􀂄 Registers
􀂄 Main memory
􀂄 Magnetic disks
􀂄 Magnetic tapes

Registers and Main Memory
􀂄 Registers and main memory are the only storage CPU can access directly
􀀩 Instruction in execution and data used by instructions must be in main memory
􀂄 Registers
􀀩 Built into CPU
􀀩 Accessible by CPU within one clock cycle
􀂄 Main memory
􀀩 Array of words, each word has own address
􀀩 Memory speeds much slower than CPU speeds: memory access may take many CPU cycles to complete
􀀗 Remedy: add fast memory (cache) between CPU and main memory
Secondary Storage
􀂄 Not possible to have programs and date reside in main memory permanently because:
􀀩 Main memory is too small
􀀩 Main memory is volatile, loses contents without power
􀂄 Secondary storage – extension of main memory that provides large nonvolatile storage capacity.

Magnetic Disks
􀂄 Magnetic disk – most common secondary-storage device
􀀩 Two surfaces of a disk platter covered with magnetic recording material
􀀩 Surface of a platter logically divided into circular tracks, which are subdivided into sectors.
􀂄 Magnetic disk speed
􀀩 Positioning time/random access time (several ms): seek time + rotational latency
􀀗 Seek time: time to move the disk arm to the desired cylinder
􀀗 Rotational latency: time for the desired sector to rotate to the disk head
􀀩 Transfer rate (megabytes per sec): rate data flow between the disk drive and the computer

Magnetic Tapes
􀂄 Larger capacity than magnetic disks
􀂄 Random access much slower than magnetic disks, transfer rate similar to magnetic disks
􀂄 Mainly used for backup

Storage Hierarchy
􀂄 Storage systems organized in hierarchy.
􀀩 Different storage systems have different speed, cost, size, and volatility
􀂄 Caching – improve performance where a large access-time or transfer-rate disparity exists between two components
􀀩 Memory caching: add cache (faster and smaller memory) between CPU and main memory
􀀗When need some data, check if it’s in cache
􀀗 If yes, use the data from cache
􀀗 If not, use data from main memory and put a copy in cache
􀀩 Disk caching: main memory can be viewed as a cache for disks.
􀂄 Cache management: selection of cache size and replacement policy
􀂄 Must ensure data that is simultaneously stored in more than one level to be consistent.

Migration of A From Disk to Register
• An integer A is located in a file residing on magnetic disk
• Want increment A by 1

Cache Coherency and Consistency
􀂄 Cache coherency in multiprocessor systems
􀀩 Each CPU has a local cache
􀀩 A copy of X may exist in several caches􀃎must make sure that an update of X in one cache is immediately reflected in all other caches where X resides
􀀩 Hardware problem
􀂄 Cache consistency in distributed systems
􀀩 A master copy of the file resides at the server machine
􀀩 Copies of the same file scattered in caches of different client machines
􀀩 Must keep the cached copies consistent with the master file
􀀩 OS problem


Hardware Protection
􀂄 In multiprogramming systems, must protect OS and all other programs and their data from any erroneous program
􀂄 Programming errors are detected by hardware and handled by OS
􀂄 Hardware protection mechanisms:
􀀩 Dual-Mode Operation
􀀩 I/O Protection
􀀩 Memory Protection
􀀩 CPU Protection

Dual-Mode Operation
􀂄 Add a mode bit to computer hardware to indicate two modes of operations.
􀀩 User mode (1) – execution done on behalf of a user.
􀀩 Monitor mode (0) – execution done on behalf of operating system.
􀂄 User programs are executed in user mode
􀂄 When an interrupt or trap occurs, hardware switches to monitor
mode.
Monitor

Dual-Mode Operation
􀂄 Certain machine instructions that can harm system are designated as privileged instructions
􀂄 Hardware allows privileged instructions to be executed only in monitor mode
􀀩 If a user program executes a privileged instruction, hardware traps to OS
􀂄 User can ask OS to execute privileged instructions by executing a system call

Dual-Mode Operation
When a system call is executed:
􀂄 Control passes to a service routine, mode bit set to 0
􀂄 Determine if request is OK
􀂄 Execute request
􀂄 Return control to the instruction following the system call

I/O Protection
􀂄 Protect system from illegal I/O
􀂄 All I/O instructions are privileged instructions.
􀂄 I/O must be performed via system calls

Memory Protection
􀂄 Protect OS memory and memory of user programs
􀂄 Add two registers that determine the range of legal addresses a program may access:
􀀩 Base register – holds the smallest legal memory address.
􀀩 Limit register – contains the size of the range
􀂄 CPU hardware compares every address generated in user mode with the registers, trap to OS if address is illegal
􀂄 When executing in monitor mode, OS has unrestricted access to both monitor and user’s memory.
􀂄 Special privileged instructions used to load base and limit registers

CPU Protection
􀂄 Prevent a user program from never returning control to the OS
􀂄 Timer – interrupts computer after a specified period to ensure operating system maintains control.
􀀩 OS sets a counter
􀀩 Counter decremented every clock tick.
􀀩 When counter reaches 0, an interrupt occurs.
􀂄 OS sets timer before turning over control to the user
􀂄 Load-timer is a privileged instruction.

CPU Protection
Timer commonly used to implement time sharing:
􀂄 Each job gets a time slice of N ms
􀂄 Kernel sets timer for N ms, starts a job
􀂄 At end of time slice, kernel switches to next job (i.e., sets timer for N ms and starts job)