Transcript Appendix 1A: performance of 2 level memories

Operating Systems
Béat Hirsbrunner
Lecture 2. Background: Computer System Overview
Main Reference: William Stallings, Operating Systems: Internals and Design Principles,
6th Edition, Prentice Hall 2009
University of Fribourg
Autumn Semester 2012
25 September 2012
1.1 Basic Elements
CPU
PC
Main Memory
MAR
0
1
2
System
Bus
Instruction
Instruction
IR
Instruction
MBR
I/O AR
Execution
unit
Data
Data
I/O BR
Data
Data
I/O Module
Buffers
n-2
n-1
PC
IR
MAR
MBR
I/O AR
I/O BR
=
=
=
=
=
=
Program counter
Instruction register
Memory address register
Memory buffer register
Input/output address register
Input/output buffer register
Figure 1.1 Computer Components: Top-Level View
1
1.2 Processor Registers
User-Visible Registers
 Data registers
 Address register
•
incl. index register, segment pointer, stack pointer
Control and status Registers




Program counter (PC)
Instruction register (IR)
Program status word (PSW)
Condition codes (flags)
Remark about the design of registers
 Should provide hardware support for particular OS features
Memory protection
• Switching between user programs
• Allocation of “control information” between registers and main memory
•
2
1.3 Instruction Execution
START
Fetch Stage
Execute Stage
Fetch Next
Instruction
Execute
Instruction
HALT
Figure 1.2 Basic Instruction Cycle
Four categories of instructions
Processor <–> Memory
Processor <–> I/O
Data Processing
Control (for conditionals or loops)
Special control instruction
DMA (direct memory access) :
main memory <–> I/O
3
1.3 Instruction Execution
0
3 4
15
Opcode
Address
(a) Instruction format
0
1
15
S
Magnitude
(b) Integer format
Program counter (PC) = Address of instruction
Instruction register (IR) = Instruction being executed
Accumulator (AC) = Temporary storage
(c) Internal CPU registers
0001 = Load AC from memory
0010 = Store AC to memory
0101 = Add to AC from memory
(d) Partial list of opcodes
Figure 1.3 Characteristics of a Hypothetical Machine
4
1.3 Instruction Execution
List of opcodes
0x1 = Load AC from Memory
0x2 = Store AC to Memory
0x5 Add to AC from Memory
5
1.4 Interrupts: most common classes
Table 1.1
Classes of Interrupts
Program
Generated by some condition that occurs as a result of an instruction
execution, such as arithmetic overflow, division by zero, attempt to execute
an illegal machine instruction, and reference outside a user's a llowed
memory space.
Timer
Generated by a timer within the processor. This allows the operating system
to perform certain functions on a regular basis.
I/O
Generated by an I/O controller, to signal normal completion of an operation
or to signal a variety of error conditions.
Hardware failure Generated by a failure, such as power failure or memory parity error.
6
1.4 Interrupts: control flow
User
Program
I/O
Program
4
1
I/O
Command
WRITE
User
Program
I/O
Program
4
1
WRITE
I/O
Command
User
Program
I/O
Program
4
1
WRITE
I/O
Command
5
2a
END
2
2
Interrupt
Handler
2b
WRITE
5
WRITE
Interrupt
Handler
5
WRITE
END
END
3a
3
3
3b
WRITE
WRITE
(a) No interrupts
(b) Interrupts; short I/O wait
WRITE
(c) Interrupts; long I/O wait
Figure 1.5 Program Flow of Control Without and With Interrupts
7
1.4 Interrupts: control transfer
User Program
Interrupt Handler
1
2
Interrupt
occurs here
i
i+1
M
The Interrupt Handler program
is generally part of the operating
system
Figure 1.6 Transfer of Control via Interrupts
8
1.4 Interrupts: instruction cycle
Fetch Stage
Execute Stage
Interrupt Stage
Interrupts
Disabled
START
Fetch next
instruction
Execute
instruction
Interrupts
Enabled
Check for
interrupt;
initiate interrupt
handler
HALT
Figure 1.7 Instruction Cycle with Interrupts
9
1.4 Interrupts: efficiency (cf. Figs 1.5a, 1.5b)
Time
1
1
4
4
Processor
wait
I/O
operation
5
2a
I/O
operation
With interrupts
I/O operations (often 1000 or more
cycles) are done in parallel to the
exection of program instructions
5
2b
2
4
4
Processor
wait
3a
I/O
operation
5
3
I/O
operation
5
3b
I/O CPU cycles
(in general 1 to 10)
(b) With interrupts
(circled numbers refer
to numbers in Figure 1.5b)
(a) Without interrupts
(circled numbers refer
to numbers in Figure 1.5a)
Figure 1.8
Program Timing: Short I/O Wait
10
1.4 Interrupts: efficiency (cf. Figs 1.5a, 1.5c)
Time
1
1
4
4
Processor
wait
I/O
operation
2
I/O
operation
Processor
wait
5
5
2
4
4
3
Processor
wait
I/O
operation
I/O
operation
Processor
wait
5
5
(b) With interrupts
(circled numbers refer
to numbers in Figure 1.5c)
3
(a) Without interrupts
(circled numbers refer
to numbers in Figure 1.5a)
Figure 1.9 Program Timing: Long I/O Wait
11
1.4 Interrupts: processing
Hardware
Device controller or
other system hardware
issues an interrupt
Processor finishes
execution of current
instruction
Software
Save remainder of
process state
information
cf. Fig. 1.11a
Process interrupt
Processor signals
acknowledgment
of interrupt
Restore process state
information
cf. Fig. 1.11b
Processor pushes PSW
and PC onto control
stack
Restore old PSW
and PC
Processor loads new
PC value based on
interrupt
Figure 1.10 Simple Interrupt Processing
12
1.4 Interrupts: processing
T–M
T–M
Y
Control
Stack
T
Control
Stack
N+1
T
Y
Start
Interrupt
Service
Y + L Return Routine
N+1
Y+L+1
Program
Counter
Program
Counter
General
Registers
T
Y
Start
Interrupt
Service
Y + L Return Routine
Stack
Pointer
Processor
User's
Program
T–M
Stack
Pointer
Processor
T–M
N
N+1
General
Registers
T
N
N+1
User's
Program
(a) Step 6 of Fig. 1.10
(b) Step 8 of Fig. 1.10
Main
Memory
(a) Interrupt occurs after instruction
at location N
Main
Memory
(b) Return from interrupt
Figure 1.11 Changes in Memory and Registers for an Interrupt
13
1.4 Interrupts: multiple interrupts
User Program
Interrupt
Handler X
Interrupt
Handler Y
(a) Sequential interrupt processing
User Program
Interrupt
Handler X
Interrupt
Handler Y
(b) Nested interrupt processing
Figure 1.12 Transfer of Control with Multiple Interrupts
14
1.4 Interrupts: multiple interrupts
Printer
interrupt service routine
User Program
Communication
interrupt service routine
t=0
t=
t=
10
15
t = 25
t=
t = 25
40
t=
Priority 2
Time arrival of the interrupts:
printer t=10, comm. t=15, disk t=20
Disk
interrupt service routine
35
Priority 5
Priority 4
Figure 1.13 Example Time Sequence of Multiple Interrupts
15
1.5 The Memory Hierarchy
Inb
Me oard
mo
ry
Ou
tb
Sto oard
rag
e
Off
Sto -line
rag
e
Figure 1.14
gRe rs
iste
che
Ca
in
Ma ory
m
Me
isk
ic D
t
e
gn OM
Ma D-R W
C -R W
CD -R
D
DV -RAM
D
V
D
tic
gne
a
M
pe
Ta
The Memory Hierarchy
16
1.5 The Memory Hierarchy: performance
T1 + T2
Average access time
T2
T1
0
1
Fraction of accesses involving only Level 1 (Hit ratio)
Figure 1.15 Performance of a Simple Two-Level Memory
Remark: hit rate are often around 90%, due to the “locality of references”,
see also fig. 1.24
17
1.6 Cache Memory
Byte or
word transfer
CPU
Block Transfer
Cache
Main Memory
Figure 1.16 Cache and Main Memory
18
1.6 Cache Memory: structure
Line
Number Tag
0
1
2
Block
Memory
address
0
1
2
3
Block
(K words)
C-1
Block Length
(K Words)
(a) Cache
Block
2n - 1
Word
Length
(b) Main memory
Figure 1.17 Cache/Main-Memory Structure
19
1.6 Cache Memory: operations
START
RA - read address
Receive address
RA from CPU
Is block
containing RA
in cache?
Access main
memory for block
containing RA
No
Yes
Allocate cache
slot for main
memory block
Fetch RA word
and deliver
to CPU
Load main
memory block
into cache slot
Deliver RA word
to CPU
DONE
Figure 1.18 Cache Read Operation
20
1.7 I/O Communication Techniques
Issue Read
command to
I/O module
CPU
Read status
of I/O
module
I/O
Issue Read
command to
I/O module
I/O
Read status
of I/O
module
CPU
CPU
I/O
I/O
Do something
else
CPU
Issue Read
block command
to I/O module
DMA
Do something
else
Interrupt
Read status
of DMA
module
Interrupt
CPU
Not
ready
Check
status
Ready
No
CPU
Next instruction
Check
status
Error
condition
DMA
Error
condition
(c) Direct memory access
Ready
Read word
from I/O
Module
I/O
Write word
into memory
CPU
CPU
memory
No
Done?
Yes
Read word
from I/O
Module
I/O
Write word
into memory
CPU
CPU
memory
Done?
Yes
Next instruction
(a) Programmed I/O
Next instruction
(b) Interrupt-driven I/O
Figure 1.19 Three Techniques for Input of a Block of Data
21
Appendix 1A: performance of 2 level memories
1.0
Hit Ratio
0.8
Strong
Locality
0.6
Moderate
Locality
0.4
No Locality
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Relative Memory Size (S1/S2)
Figure 1.24
Hit Ratio as a Function of Relative Memory Size
see also fig. 1.15
28
Appendix 1B: Procedure Control
29
Appendix 1B: Procedure Control
Addresses
4000
4100
4101
Main Memory
CALL Proc1
Main
Program
4500
4600
4601
CALL Proc2
4650
4651
CALL Proc2
Procedure
Proc1
RETURN
4800
Procedure
Proc2
RETURN
(a) Calls and returns
(b) Execution sequence
Figure 1.26 Nested Procedures
30
Appendix 1B: Procedure Control
31
Appendix 1B: Procedure Control
y2
top of
stack pointer
y1
Return address
Q:
x2
P:
top of
stack pointer
Previous frame
pointer
x2
x1
x1
Return address
Return address
Previous frame
pointer
(a) P is active
current
frame
pointer
P:
current
frame
pointer
Previous frame
pointer
(b) P has called Q
Figure 1.28 Stack Frame Growth Using Sample Procedures P and Q
32