Transcript Midterm_Review_Spring_2005_Operating_Systems

Chapters 1-10
Midterm Review
CSCI 3753
Operating Systems, Spring 2005
Professor Rick Han
Announcements
• Solutions to HW#1 - HW #3 already online, HW #4
by 3 pm
• Midterm Review slides online by tomorrow a.m.
•
All previous lectures online, except last Thursday's (by
tonight)
• Extended office hours Wednesday 5-6 pm
•
Normal OH: Tues & Wed 2-3 pm
• Extended TA office hours Tuesday
• Programming Assignment #2 due Thursday March
17, before Spring Break
Prof. Rick Han, University of
Colorado at Boulder
Midterm
• Midterm March 10
•
•
•
•
•
•
•
Chapter 1 Through Chapter 10 Deadlock
Excluding...
75 minutes
In class
Closed book, I'll give you what's needed, e.g. algorithms
Calculator OK
3-4 multipart questions (multiple sections a, b, c, d)
•
•
likely all short-answer questions
Look over first, then spend about 20 minutes for each long
question
Prof. Rick Han, University of
Colorado at Boulder
Potential Topics for Midterm
• List is not all-inclusive; some topics may appear on
midterm not listed here
• How does ___ work? Why is it used? Under what
conditions does it apply/not apply?
• Work backwards
• Start with the slides, then supplement with the book
•
•
•
Chapters 8-10 Synchronization and Deadlock
• probably 2 problems
Chapters 6-7 Processes, Threads, and Scheduling
• probably 1 problem
Chapters 3-5 Hardware, Device Management
• probably 1 problem
Prof. Rick Han, University of
Colorado at Boulder
Potential Topics for Midterm
• Synchronization
–
–
–
–
–
–
–
Critical sections
Race conditions
Atomic operations
Mutual exclusion
Spinlocks
disabling interrupts
TestandSet()
Prof. Rick Han, University of
Colorado at Boulder
Semaphores
• Pseudo-code for classic semaphore
P(S) {
while(S<=0)
{wait or no op;}
S--;
}
atomic
“atomic”
– its value can’t go below zero, i.e. classic semaphore
is non-negative
V(S) {
S++;
}
P() is “atomic” in the sense that it tests S atomically, and if S<=0, then the
Prof. Rick Han,
UniversityOtherwise,
of
process calling P() will relinquish
control.
the process continues
at Boulder
forward and decrements SColorado
atomically.
See Next Slide for implementation.
Semaphores
• Synchronization
– Binary semaphores as mutex locks
– Counting semaphores
– Deadlock examples with semaphores
Prof. Rick Han, University of
Colorado at Boulder
Classic Synchronization Problems
• Bounded Buffer Producer-Consumer Problem
• Readers-Writers Problem
– First Readers Problem
• Dining Philosophers Problem
• These are not just abstract problems
– They are representative of several classes of
synchronization problems commonly encountered when
trying to synchronize access to shared resources among
multiple processes
Prof. Rick Han, University of
Colorado at Boulder
Bounded Buffer Producer/Consumer
Problem
• Pool of n buffers, each capable of holding 1 item
• producer takes an empty buffer and produces a full buffer
• consumer takes a full buffer and produces an empty buffer
Empty Pool
Producer
Consumer
Full Pool
Prof. Rick Han, University of
Colorado at Boulder
Graphic © Pearson textbook slides
The Readers/Writers Problem
• There are several writer processes that want to
write to a shared object, e.g. a file, and also
several reader processes that want to read from the
same shared object
• Want to synchronize access
Writers
a writer must have
exclusive access
Shared
object,
e.g. file
Readers
W1
R1
W2
R2
Readers can share
with any other reader
but not a writer
The “First Readers/Writers Problem”: no reader is kept waiting unless a writer
already has seized the shared
object.
We willofimplement this in the next slides.
Prof. Rick
Han, University
Colorado at Boulder
Dining Philosophers Problem
• N philosophers seated around a
circular table
– There is one chopstick between each
philosopher
– A philosopher must pick up its two
nearest chopsticks in order to eat
– A philosopher must pick up first one
chopstick, then the second one, not both at P1
once
• Devise an algorithm for allocating
these limited resources (chopsticks)
among several processes
(philosophers) in a manner that is
– deadlock-free, and
– starvation-free
Prof. Rick Han, University of
Colorado at Boulder
P2
P3
P4
P5
Monitors and Condition Variables
•
•
Declare a monitor as follows (looks somewhat
like a C++ class):
monitor monitor_name {
// shared local variables
function f1(...) {
...
}
...
function fN(...) {
...
}
init_code(...) {
...
}
}
A monitor ensures that only 1
process/thread at a time can be active
within a monitor
–
•
simplifies programming, no need to
explicitly synchronize
Implicitly, the monitor defines a mutex
lock
semaphore mutex = 1;
•
Implicitly, the monitor also defines
essentially mutual exclusion around
each function
–
Each function’s critical code is
surrounded as follows:
function fj(...) {
P(mutex)
// critical code
V(mutex)
}
•
•
Prof. Rick Han, University of
Colorado at Boulder
The monitor’s local variables can only
be accessed by local monitor functions
Each function in the monitor can only
access variables declared locally
within the monitor and its parameters
Necessary Conditions for Deadlock
•
Deadlock can arise if the following 4 conditions hold
simultaneously:
1. Mutual exclusion
•
at least 1 resource is held in a non-sharable mode. Other requesting
processes must wait until the resource is released
2. Hold and wait
•
a process may hold a resource while request (and waiting for)
another one
3. No preemption
•
resources cannot be preempted and can only be released by the
process holding it, after the process is finished. No OS intervention
is allowed. A process cannot withdraw its request.
4. Circular wait
•
A set of waiting processes {P0, ..., Pn-1} must exist such that Pi waits
for a resource held by P(i+1)%n
Prof. Rick Han, University of
Colorado at Boulder
Deadlock Prevention
• Prevent the circular wait condition from
coming true
– Solution I: a process can only hold 1 resource at
a time
• disadvantage: in some cases, a process needs to hold
multiple resources to accomplish a task
– Solution II: impose a total ordering of all
resource types and require each process to
request resources in increasing order
• this prevents a circular wait - see next slide
Prof. Rick Han, University of
Colorado at Boulder
Deadlock Avoidance
• A state is safe if there exists a safe sequence
of processes <P1, ..., Pn> for the current
resource allocation state
– A sequence of processes is safe if for each Pi in
the sequence, the resource requests that Pi can
still make can be satisfied by:
• currently available resources + all resources held by
all previous processes in the sequence Pj, j<i
– If resources needed by Pi are not available, Pi
waits for all Pj to release their resources
Prof. Rick Han, University of
Colorado at Boulder
Deadlock Avoidance
•
Banker’s (Safety) Algorithm: find a safe sequence, i.e.
is the system in a safe state?
1.
2.
Let Work and Finish be vectors length m and n respectively.
Initialize Work = Available, and Finish[i]=false for i=0,...,n-1
Find a process i such that both
• Finish[i]==false, and
• Needi ≤ Work
If no such i exists, go to step 4.
3.
Intuition: if all prior processes
give up all their resources,
is there enough to meet the
max needs of next process
in the sequence?
Work = Work + Alloci
Finish[i] = true
Go to step 2.
4. If Finish[i]==true for all i, then the system is in a safe state
Prof. Rick Han, University of
Colorado at Boulder
What is a Process?
• A process is a
program actively
Main
executing from main
Memory
memory
– has a Program
Counter (PC) and
execution state
associated with it
• CPU registers keep
state
• OS keeps process
state in memory
• it’s alive!
– has an address space
associated with it
• a limited set of
(virtual) addresses
that can be
accessed by the
executing code
Program
P1
binary
Process
Fetch Code
and Data
Code
CPU
Execution
Program
Counter (PC)
Registers
ALU
Data
Write Data
Prof. Rick Han, University of
Colorado at Boulder
Multiple Processes
Main Memory
Process
P1
Process
P2
Code
Code
Data
Heap
Data
Stack
Heap
Stack
• Each process is in
memory
• Only one process at a
time executes on the
CPU
• OS provides the
mechanisms to switch
between processes
– this is called a context
switch
Prof. Rick Han, University of
Colorado at Boulder
Context Switching
Executable Memory
Initialization
Interrupt
1
Process
Manager
7
8
Interrupt
Handler
2
4
3
P1
9
5
P2
6
Pn
Prof. Rick Han, University of
Colorado at Boulder
• Each time a
process is
switched out, its
context must be
saved, e.g. in the
PCB
• Each time a
process is
switched in, its
context is restored
• This usually
requires copying
of registers
Main Memory
Threads
Process P1’s Address Space
Code
Data
Heap
Thread 1 Thread 2 Thread 3
PC1
PC2
Process
P2
•
Code
•
Data
•
Heap
•
PC3
Stack
Reg.
State
Reg.
State
Reg.
State
Stack
Stack
Stack
Prof. Rick Han, University of
Colorado at Boulder
Process P1 is
multithreaded
Process P2 is
single
threaded
The OS is
multiprogram
med
If there is
preemptive
timeslicing,
the system is
multitasked
Scheduler
Preemption or voluntary yield
New
Process
Ready
List
Scheduler
CPU
job
job
job
“Running”
“Ready”
Allocate
Done
Resource
Manager
job
job
Request
“Blocked”
Resources
Prof. Rick Han, University of
Colorado at Boulder
Scheduling Policies
•
•
•
•
•
•
•
FCFS
SJF
Round Robin
Deadline
Priority
Multi-level feedback queues
Preemptive vs. non-preemptive
Prof. Rick Han, University of
Colorado at Boulder
Signals
• Kernel sends a signal to a destination process by
updating some state in the context of the
destination process
• A destination process receives a signal when it is
forced by the kernel to react in some way to the
delivery of the signal:
– can ignore the signal
– terminate / exit (this is the usual default)
– catch the signal by executing a user-defined function
called the signal handler
Prof. Rick Han, University of
Colorado at Boulder
Stacks and Frames: Entering a Function
%ebp
max memory
PC
PC
foo1(int v1, v2) {
local var’s
assembly code:
• foo1 first saves the old
...
frame pointer by
pushing it onto the
}
stack: pushl %ebp
•
•
main’s
frame
Stack
unallocated
main()’s
local
variables are
allocated here,
e.g. int a1
%esp
arg 2
top of the stack unallocated
arg 1
%esp
%esp
top of the stack return address
foo1 resets frame ptr
top of the stack saved fr ptr %ebp
to new base (current
%ebp and %ebp
%esp
stack ptr): movl
top of the stack
local var’s
unallocated
%esp
%esp, %ebp
foo1’s
foo1 saves any callee CPU registers on frame
stack (not shown)
• foo1 allocates local
by
Prof.variables
Rick Han, University
of
Colorado at Boulder
decrementing stack ptr
Stacks and Frames: Exiting a Function
max memory
%ebp
PC
foo1(int v1, v2) {
local var’s
assembly code:
...
• foo1 restores callee
save registers (not
}
shown)
main’s
frame
%esp
• deallocate local variables off of the
%esp
stack, which resets stack ptr equal
to current base/frame ptr
%esp and %ebp
• pop saved frame pointer off the stack
%esp
and into the base/frame register
foo1’s
frame
• pop the saved return address off the
Prof.(PC
Rick Han, University of
stack and jump to this location
Colorado at Boulder
changes)
Stack
unallocated
main()’s
local
variables are
allocated here,
e.g. int a1
arg 2
unallocated
arg 1
return address
saved fr ptr %ebp
local var’s
unallocated
The von Neumann Architecture
Central Processing Unit (CPU)
Arithmetical Logical Unit
(ALU)
Control Unit
(CU)
Address Bus
Data Bus
Primary
Memory Unit
(Executable
Memory)
Device
Prof. Rick Han, University of
Colorado at Boulder
Processor Modes
• Mode bit: Supervisor or User mode
• Supervisor mode
– Can execute all machine instructions
– Can reference all memory locations
• User mode
– Can only execute a subset of instructions
– Can only reference a subset of memory
locations
Prof. Rick Han, University of
Colorado at Boulder
System Call Using the trap Instruction
…
fork();
…
Trap Table
fork() {
…
trap
N_SYS_FORK()
…
}
Kernel
sys_fork()
sys_fork() {
/* system function */
…
return;
}
Prof. Rick Han, University of
Colorado at Boulder
Interrupt-driven I/O Operation
read(device, …);
1
9
8b
Data
System Interface
Device Status Table
read driver
2
4
7
Device
Handler
write driver
6
3
Interrupt
Handler
5
Hardware Interface
Command
Status
Device
Controller
Prof. Rick
Han, University of
Colorado at Boulder
Data
8a
Operating System Architecture
App2
App1
Posix, Win32,
Java, C library API
System call API
App3
System Libraries and Tools
(Compilers, Shells, GUIs)
OS
“Kernel” Scheduler
VM
File
System
Device
Manager
CPU Memory Disk Display Mouse I/O
Prof. Rick Han, University of
Colorado at Boulder
Linking Multiple Object Files Into
P1 or P1.exe
an Executable
file P1.c
Code
foo2.o
Source
Code
Compiler P1.s
cc1
Assembler
as
P1.o
Linker
ld
Data
foo3.o
• in combining multiple object files, the linker must
– resolve references to variables and functions defined in other object
files - this is called symbol resolution
– relocate each object’s internal addresses so that the executable’s
combination of objects is consistent in its memory references
• an object’s code and data are compiled in its own private world to start at
address zero
Prof. Rick Han, University of
Colorado at Boulder
Linker Resolves Unknown Symbols
P1.c
foo2.c
extern void f1(...);
extern int globalvar1;
int globalvar1=0;
void f1(...) {
---}
main(...) {
----f1(...)
----}
void f2(...) {
---globalvar1 = 4;
---}
P1.o
foo2.o
the P1.o object file will contain a list of
foo2.o’s symbol table lists
unknown symbols, e.g. f1, in aProf.
symbol
table
symbols, e.g. globalvar1
Rick Han,
Universityunknown
of
Colorado at Boulder
Linker Relocates Addresses
• After resolving symbols, the linker relocates addresses
when combining the different object modules
–
–
–
–
merges separate code .text sections into a single .text section
merges separate .data sections into a single .data section
each section is assigned a memory address
then each symbol reference in the code and data sections is
reassigned to the correct memory address
• looks at .relo.text and .relo.data to find relocation entries of references
that needed address translation
– these are virtual memory addresses that are translated at load time
into real run-time memory addresses
Prof. Rick Han, University of
Colorado at Boulder
Sample Types of Problems
• Variations on the sleepy barber
– given fragments of code, add your own
code to synchronize properly
• Consider the traffic situation at right
– Show that the four necessary conditions
for deadlock indeed hold
– State a simple rule for avoiding
deadlocks in this system
Prof. Rick Han, University of
Colorado at Boulder
Sample Types of Problems
• Given a snapshot of the system, is it in a
safe state?
– Given Alloc[i,j] matrix, Max[i,j], and
Available[j]
– Employ Banker’s Algorithm to find a safe
sequence, if any
• Suppose I modify the Banker’s Algorithm in
some way, will it still produce a safe
sequence - why or why not?
Prof. Rick Han, University of
Colorado at Boulder
Sample Types of Problems
• Use monitors to implement solutions to
– Producer/Consumer problem
– First Readers/Writers problem
– explain how condition variables work - do they have
state?
• Apply semaphores to solve synchronization
problems
– given a fragment of code, improve it to provide mutual
exclusion
Prof. Rick Han, University of
Colorado at Boulder
Sample Types of Problems
• How are wait() and signal() implemented?
• Given N processes, M resources, Q instances, D
demands, is the system in deadlock?
• Scheduling
–
–
–
–
–
Given some process arrival times
I/O overlap
Draw a Gantt chart for deadline-based scheduling
What is the total waiting time?
In general, does scheduling policy X produce less
average waiting time than scheduling policy Y?
Prof. Rick Han, University of
Colorado at Boulder