Transcript Processes

Processes
Week 2 – CS 502
CS502 Spring 2006
Processes 1
Last week
• Abstractions — simplified idealization of a very
complex, real phenomenon or action
• Atomic reads from and writes to memory
• Most machine opcodes behave as if they are atomic
• Critical section — a discipline to keep different
computations from tripping over each other on
common data
• Peterson’s solution – busy waiting, depends only on atomic
loads and stores of data
• Semaphores – a possible abstraction for controlling access to
shared data, blocking and unblocking as needed.
CS502 Spring 2006
Processes 2
Today’s outline
• Process – an abstraction representing the
execution of a program
• Background:– interrupts and machine architecture
• Implementation of processes and semaphores
• Process creation
• Scheduling
• Unix/Windows processes
CS502 Spring 2006
Processes 3
Brief Class Discussion
• Can Peterson’s solution be generalized to
more than two concurrent activities?
• See Dijkstra’s earlier solution:–
– “Solution of a Problem in Concurrent
Programming Control,” Communications of the
ACM, v. 8, #9, Sept. 1965, p. 569
CS502 Spring 2006
Processes 4
Background – Interrupts
• A mechanism in (nearly) all computers by which a
running program can be suspended in order to
cause processor to do something else
• Two kinds:–
• Interrupts – asynchronous, spawned by concurrent activity of
devices.
• Traps – synchronous, caused by running program
– Deliberate: e.g., system call
– Error: divide by zero
• Essential to the usefulness of computing systems
CS502 Spring 2006
Processes 5
Interrupt mechanism (hardware)
• Upon receipt of a signal, the processor
• Saves current PSW to fixed location
• Loads new PSW from fixed location
• PSW — Program Status Word
•
•
•
•
Program counter
Condition code bits (comparison results)
Interrupt enable/disable bits
Other control and mode information
– E.g., privilege level, access to special instructions, etc.
• Occurs between machine instructions
• An abstraction in modern processors (see Tannenbaum, §5.1.5)
CS502 Spring 2006
Processes 6
Interrupt Handler
/* Enter with interrupts disabled */
Save registers of interrupted computation
Load registers needed by handler
Examine cause of interrupt
Take appropriate action (brief)
Reload registers of interrupted computation
Reload interrupted PSW and re-enable interrupts
or
Load registers of another computation
Load its PSW and re-enable interrupts
CS502 Spring 2006
Processes 7
Requirements of interrupt handlers
• Fast
• Avoid possibilities of interminable waits
• Must not count on correctness of interrupted
computation
• …
• More challenging on multiprocessor
systems
CS502 Spring 2006
Processes 8
“process” (with a small “p”)
• Definition: A particular execution of a program.
• Requires time, space, and (perhaps) other resources
• Can be
•
•
•
•
•
Interrupted
Suspended
Blocked
Unblocked
Started or continued
• A fundamental abstraction in all operating systems
• Note: a Unix/Windows “Process” is a heavyweight concept
with more implications than this simple definition
CS502 Spring 2006
Processes 9
State of a process
• PSW (program status word)
• Program counter
• Condition codes
• Registers, stack pointer, etc.
• Whatever hardware resources needed to compute
• Control information for OS
• Owner, privilege level, priority, restrictions, etc.
• Other stuff …
CS502 Spring 2006
Processes 10
Process and semaphore data structures
Class State {
long int PSW;
long int regs[R];
/*other stuff*/
}
class PCB {
PCB *next, prev, queue;
State s;
Class Semaphore {
int count;
PCB *queue;
friend DecrOrBlock
(Semaphore &s);
friend IncrAndUnblock
(Semaphore &s);
Semaphore(int initial);
/*constructor*/
~Semaphore();
/*destructor*/
PCB (…); /*constructor*/
~PCB(); /*destructor*/
}
}
CS502 Spring 2006
Processes 11
Implementation
Ready queue
PCB
PCB
Semaphore A
PCB
PCB
count = 0
Semaphore B
count = 2
CS502 Spring 2006
Processes 12
PCB
PCB
Implementation
Ready queue
PCB
PCB
PCB
PCB
• Action – dispatch a process to CPU
• Remove first PCB from ready queue
• Load registers and PSW
• Return from interrupt or trap
• Action – interrupt a process
•
•
•
•
Save PSW and registers in PCB
If not blocked, insert PCB into ReadyQueue (in some order)
Take appropriate action
Dispatch another process from ReadyQueue
CS502 Spring 2006
Processes 13
Implementation
Ready queue
PCB
PCB
• Action – DecrOrBlock(Semaphore
PCB
&s)
• Implement as a Trap (with interrupts disabled)
• If s.count == 0
– Save registers and PSW in PCB
– Queue PCB on s.queue
– Dispatch next process on ReadyQueue
• else
– s.count = s.count – 1;
– Re-dispatch current process
CS502 Spring 2006
Processes 14
PCB
Implementation
Ready queue
PCB
PCB
Semaphore A
PCB
PCB
count = 0
• Action – IncrAndUnblock(Semaphore
PCB
&s)
• Implement as a Trap (with interrupts disabled)
• If s.count != null
– Save current process in ReadyQueue
– Move first process on s.queue to ReadyQueue
– Dispatch another process on ReadyQueue
• else
– s.count = s.count + 1;
– Re-dispatch current process
CS502 Spring 2006
Processes 15
PCB
Device Interrupts
• Implement as IncrAndUnblock to special
semaphores
• Device-specific handling entrusted to device
manager processes
• Very high priority
• Requests from application processes
• Implemented in device-specific routines
• Critical sections
• Buffers and variables shared with device managers
CS502 Spring 2006
Processes 16
Timer interrupts
• Can be used to enforce “fair sharing”
• Current process goes back to ReadyQueue
• After other processes of equal or higher priority
• Simulates concurrent execution of multiple
processes on same processor
CS502 Spring 2006
Processes 17
Definition
• Context Switch — the act of switching from
one process to another
• E.g., upon interrupt or block
• Not a big deal in simple systems and
processors
• Very big deal in large systems such
• Unix and Windows
• Pentium 4
CS502 Spring 2006
Processes 18
Complications for Multiple Processors
• Disabling interrupts not sufficient for
atomic operations
• Semaphore operations must be in critical sections
• Queuing and dequeuing PCB’s must be in critical
sections
• Other control operations need protection
• These problems all have solutions but need
deeper thought!
CS502 Spring 2006
Processes 19
Summary
• Interrupts transparent to processes
• DecrOrBlock() and IncrAndUnblock()
behave as if they are atomic
• Device handlers and all other OS services
can be embedded in processes
• All processes behave as if concurrently
executing
• Fundamental underpinning of all modern
operations systems
CS502 Spring 2006
Processes 20