Transcript 1.01 - Computer Science at Rutgers

Lecture 2: Computer Systems
Overview
Adapted from slides ©2005 Silberschatz, Galvin, and Gagne and
from @2005 Stallings
Announcements
 http:///www.cs.rutgers.edu/~iftode/cs416_08.html

Lecture slides available

Link to xv6 source code: print and bring it to class
 Office Hours

Iftode: Thursday, 5:30PM-6:30PM

Smaldone: Thursday, 7PM-8PM
 Homework on cache measurements: to be posted on Monday
Rutgers University, CS 416, Spring 2008
.2
Lecture Objectives
 To refresh the basics of computer system organization
 To overview the major operating systems components
Rutgers University, CS 416, Spring 2008
.3
What is a Computer System?
Rutgers University, CS 416, Spring 2008
.4
Computer System Organization
Rutgers University, CS 416, Spring 2008
.5
Inside Computer Components
6
Rutgers University, CS 416, Spring 2008
.6
Processor
 Internal registers

Memory address register (MAR)


Specifies the address for the next read or write
Memory buffer register (MBR)

Contains data written into memory or receives data read
from memory

I/O address register

I/O buffer register
7
Rutgers University, CS 416, Spring 2008
.7
Processor Registers
 User-visible registers

Enable programmer to minimize main-memory references by
optimizing register use
 Control and status registers
 Used by processor to control operating of the processor
 Used by privileged operating-system routines to control the
execution of programs
8
Rutgers University, CS 416, Spring 2008
.8
User-Visible Registers
 May be referenced by machine language
 Available to all programs - application programs and system
programs
 Types of registers
 Data
 Address

Index
Segment pointer
 Stack pointer

9
Rutgers University, CS 416, Spring 2008
.9
User-Visible Registers
 Address Registers

Index


Segment pointer


When memory is divided into segments, memory is
referenced by a segment and an offset
Stack pointer


Involves adding an index to a base value to get an address
Points to top of stack
Base pointer

Points to the base of the stack frame
10
Rutgers University, CS 416, Spring 2008
.10
Control and Status Registers

Program Counter (PC)


Instruction Register (IR)


Contains the address of an instruction to be fetched
Contains the instruction most recently fetched
Program Status Word (PSW)

Condition codes

Interrupt enable/disable

Supervisor/user mode
11
Rutgers University, CS 416, Spring 2008
.11
Control and Status Registers
 Condition Codes or Flags

Bits set by the processor hardware as a result of operations

Examples

Positive result

Negative result

Zero

Overflow
12
Rutgers University, CS 416, Spring 2008
.12
Instruction Cycle
13
Rutgers University, CS 416, Spring 2008
.13
Interrupts
 Suspends the normal sequence of execution
 Used to improve processor utilization
14
Rutgers University, CS 416, Spring 2008
.14
Interrupt Cycle
15
Rutgers University, CS 416, Spring 2008
.15
Classes of Interrupts
16
Rutgers University, CS 416, Spring 2008
.16
Interrupt Timeline
Rutgers University, CS 416, Spring 2008
.17
Simple Interrupt Processing
18
Rutgers University, CS 416, Spring 2008
.18
Changes in Memory and Registers for an
Interrupt
19
Rutgers University, CS 416, Spring 2008
.19
Return From Interrupt
20
Rutgers University, CS 416, Spring 2008
.20
Multiple Interrupts
 Disable interrupts while an interrupt is being processed
21
Rutgers University, CS 416, Spring 2008
.21
Multiple Interrupts
 Define priorities for interrupts
22
Rutgers University, CS 416, Spring 2008
.22
Multiple Interrupts
23
Rutgers University, CS 416, Spring 2008
.23
Data transfer on the bus
CPU
cache
Memory
memory bus
I/O bus
disk
Net interface

cache-memory: cache misses, write-through/write-back

memory-disk: swapping, paging, file accesses

memory-network Interface : packet send/receive

I/O devices to the processor: interrupts
Rutgers University, CS 416, Spring 2008
.24
I/O Operation: Synchronous vs. Asynchronous
 After I/O starts, control returns to user program only upon I/O
completion.
 Wait instruction idles the CPU until operation completes
 Wait loop (contention for memory access?).
 At most one I/O request is outstanding at a time, no
simultaneous I/O processing.
 After I/O starts, control returns to user program without waiting
for I/O completion.
 System call – request to the operating system to allow user
to wait for I/O completion.
 Device-status table contains entry for each I/O device
indicating its type, address, and state.
 Operating system indexes into I/O device table to determine
device status and to modify table entry to include interrupt.
Rutgers University, CS 416, Spring 2008
.25
Two I/O Methods
Synchronous
Rutgers University, CS 416, Spring 2008
Asynchronous
.26
Programmed I/O
 I/O module performs the action, not the
processor
 Sets appropriate bits in the I/O status
register
 No interrupts occur
 Processor checks status until operation is
complete
Rutgers University, CS 416, Spring 2008
.27
Interrupt-Driven I/O
 Processor is interrupted when I/O
module ready to exchange data
 Processor is free to do other work
 No needless waiting
 Consumes a lot of processor time
because every word read or written
passes through the processor
Rutgers University, CS 416, Spring 2008
.28
Direct Memory Access (DMA)
 Used for high-speed I/O devices able to transmit information at
close to memory speeds.
 Device controller transfers blocks of data from buffer storage
directly to main memory without CPU intervention.
 Only one interrupt is generated per block, rather than the one
interrupt per byte.
 Programming a DNA transfer

address of the I/O buffer
 starting location in memory
 number of bytes
 direction of transfer (read/write from/to memory)
 bus arbitration between cache-memory and DMA transfers
 memory cache must be consistent with DMA
Rutgers University, CS 416, Spring 2008
.29
Multiprogramming
 Even when interrupts are used, processor may not be used
efficiently
 Processor has more than one program to execute
 After starting a synchronous I/O, switch to another program
 The sequence the programs are executed depend on their relative
priority and whether they are waiting for I/O
 After an interrupt handler completes, control may not return to the
program that was executing at the time of the interrupt
30
Rutgers University, CS 416, Spring 2008
.30
Storage Structure
 Main memory – only large storage media that the CPU can access
directly.
 Secondary storage – extension of main memory that provides large
nonvolatile storage capacity.
 Magnetic disks – rigid metal or glass platters covered with
magnetic recording material

Disk surface is logically divided into tracks, which are
subdivided into sectors.

The disk controller determines the logical interaction between
the device and the computer.
Rutgers University, CS 416, Spring 2008
.31
Storage Hierarchy
 Storage systems organized in hierarchy.

Speed

Cost

Volatility
 Caching – copying information into faster storage system; main
memory can be viewed as a last cache for secondary storage.
Rutgers University, CS 416, Spring 2008
.32
Storage-Device Hierarchy
Rutgers University, CS 416, Spring 2008
.33
Going Down the Hierarchy
 Decreasing cost per bit
 Increasing capacity
 Increasing access time
 Decreasing frequency of access of the memory by the processor

Locality of reference
 Increase size of the transfer unit
34
Rutgers University, CS 416, Spring 2008
.34
Caching
 Important principle, performed at many levels in a computer (in
hardware, operating system, software)
 Based on the principle of locality: the Working Set Model
[Denning,1968]
 Information in use copied from slower to faster storage temporarily
 Inclusion property
 Faster storage (cache) checked first to determine if information is
there
 If it is, information used directly from the cache (fast)
 If not, data copied to cache and used there
 Cache smaller than storage being cached

Cache management important design problem
 Cache size and replacement policy
 Cache coherence
 What about writes?
Rutgers University, CS 416, Spring 2008
.35
Secondary Memory
 Nonvolatile
 Auxiliary memory
 Used to store program and data files
36
Rutgers University, CS 416, Spring 2008
.36
Disk Cache/Buffer Cache
 A portion of main memory used as a buffer to temporarily to hold
data for the disk
 Disk writes are clustered
 Some data written out may be referenced again. The data are
retrieved rapidly from the software cache instead of slowly from
disk
37
Rutgers University, CS 416, Spring 2008
.37
Cache Memory

motivated by the mismatch between processor and memory speed

closer to the processor than the main memory

smaller and faster than the main memory



act as “attraction memory”: contains the value of main memory
locations which were recently accessed (temporal locality)
transfer between caches and main memory is performed in units
called cache blocks/lines
caches contain also the value of memory locations which are close
to locations which were recently accessed (spatial locality)

Physical vs. virtual addressing

Cache performance: miss ratio, miss penalty, average access time

invisible to the OS
Rutgers University, CS 416, Spring 2008
.38
Cache-Memory Transfers
39
Rutgers University, CS 416, Spring 2008
.39
Cache/Main Memory System
40
Rutgers University, CS 416, Spring 2008
.40
Cache Read Operation
41
Rutgers University, CS 416, Spring 2008
.41
Cache Design
 Cache size

Small caches have a significant impact on performance
 Capacity misses
 Block size

The unit of data exchanged between cache and main memory
 Larger block size more hits until probability of using newly
fetched data becomes less than the probability of reusing data
that have to be moved out of cache
42
Rutgers University, CS 416, Spring 2008
.42
Cache Design
 Mapping function

Determines which cache location the block will occupy

Direct-mapped vs. set-associative

Conflict misses
 Replacement algorithm

Determines which block to replace

Least-Recently-Used (LRU) algorithm
43
Rutgers University, CS 416, Spring 2008
.43
Cache Design
 Write policy

When the memory write operation takes place

Can occur every time block is updated: write through

Can occur only when block is replaced: write back

Minimizes memory write operations

Leaves main memory in an obsolete state
44
Rutgers University, CS 416, Spring 2008
.44
Performance of Various Levels of Storage
 Movement between levels of storage hierarchy can be explicit or
implicit
Rutgers University, CS 416, Spring 2008
.45
Multiprocessors
CPU
cache
CPU
cache
Memory
memory bus
I/O bus
disk
Net interface

simple scheme: more than one processor on the same bus

memory is shared among processors-- cache coherency

goal: performance speedup

single-image operating systems

Today: Multi-core processors (chip-level multiprocessors/CMP)
Rutgers University, CS 416, Spring 2008
.46
Clusters of Computers
CPU
cache
CPU
cache
Memory
Memory
memory bus
memory bus
I/O bus
I/O bus
network
disk
Net interface
Net interface

network of computers: “share-nothing”

communication through message-passing

fast interconnects: memory-to-memory communication

goals: performance and availability

each system runs its own operating system
Rutgers University, CS 416, Spring 2008
.47
disk
Next Time
 Silberschatz, chapter 2
 Stallings, chapter 2
Rutgers University, CS 416, Spring 2008
.48