Transcript 02_01_05_threads

Slide 6-1
6
Processes and
Threads
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Announcements
• Homework Set #2 due Thursday at 11 am
• Program Assignment #1 due Thursday Feb.
10 at 11 am
– TA will introduce in recitation Wednesday
• Read chapters 6 and 7
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-2
Slide 6-3
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
Copyright © 2004 Pearson Education, Inc.
Program
P1
binary
Process
Fetch Code
and Data
Code
CPU
Execution
Program
Counter (PC)
Registers
Data
ALU
Heap
Stack
Write Data
Operating Systems: A Modern Perspective, Chapter 6
How is a Process Structured in
Memory? Run-time memory
max address
User stack
• Run-time memory
image
• Essentially code,
data, stack, and
heap
• Code and data
loaded from
executable file
• Stack grows
downward, heap
grows upward
Unallocated
Heap
Read/write .data, .bss
Read-only .init, .text, .rodata
address 0
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-4
Slide 6-5
Multiple Processes
Main Memory
Process
P1
•
Process
P2
OS
Code
Code
Code
•
•
•
•
Data
PCB for P1
Heap
•
Data
Stack
PCB for P2
Heap
Stack
Copyright © 2004 Pearson Education, Inc.
•
More Data,
Heap, Stack
Operating Systems: A Modern Perspective, Chapter 6
Process state,
e.g. ready,
running, or
waiting
accounting
info, e.g.
process ID
Program
Counter
CPU registers
CPUscheduling
info, e.g.
priority
Memory
management
info, e.g. base
and limit
registers,
page tables
I/O status
info, e.g. list
of open files
Multiple Processes
Slide 6-6
Main Memory
Process
P1
Process
P2
OS
Code
Code
Code
Data
PCB for P1
CPU
Execution
Program
Counter (PC)
Heap
Data
Stack
PCB for P2
ALU
Heap
Stack
Copyright © 2004 Pearson Education, Inc.
More Data,
Heap, Stack
Operating Systems: A Modern Perspective, Chapter 6
Context Switching
Slide 6-7
Executable Memory
Initialization
Interrupt
1
Process
Manager
7
8
Interrupt
Handler
2
4
3
P1
9
5
P2
6
Pn
Copyright © 2004 Pearson Education, Inc.
• 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
Operating Systems: A Modern Perspective, Chapter 6
Threads
• A thread is a logical flow of execution that
runs within the context of a process
– has its own program counter (PC), register
state, and stack
– shares the memory address space with other
threads in the same process,
• share the same code and data and resources (e.g.
open files)
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-8
Threads
Slide 6-9
• Why would you want multithreaded processes?
– reduced context switch overhead
• In Solaris, context switching between processes is 5x slower
than switching between threads
– shared resources => less memory consumption => more
threads can be supported, especially for a scalable
system, e.g. Web server must handle thousands of
connections
– inter-thread communication is easier and faster than
inter-process communication
– thread also called a lightweight process
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-10
Threads
Main Memory
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
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Process P1 is
multithreaded
Process P2 is
single
threaded
The OS is
multiprogram
med
If there is
preemptive
timeslicing,
the system is
multitasked
Slide 6-11
Processes &Threads
Stack
State
Copyright © 2004 Pearson Education, Inc.
Static data
Map
Operating Systems: A Modern Perspective, Chapter 6
Program
Map
Resources
Address Space
Stack
State
Thread-Safe/Reentrant Code
• If two threads share and execute the same code,
then the code needs to be thread-safe
– the use of global variables is not thread safe
– the use of static variables is not thread safe
– the use of local variables is thread safe
• need to govern access to persistent data like
global/static variables with locking and
synchronization mechanisms
• reentrant is a special case of thread-safe:
– reentrant code does not have any references to global
variables
– thread-safe code protects and synchronizes access to
global variables
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-12
User-Space and Kernel Threads
• pthreads is a POSIX user space threading API
–
–
–
–
provides interface to create, delete threads in the same process
threads will synchronize with each other via this package
no need to involve the OS
implementations of pthreads API differ underneath the API
• Kernel threads are supported by the OS
– kernel must be involved in switching threads
– mapping of user-level threads to kernel threads is usually one-toone
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-13
Model of Process Execution
Slide 6-14
Preemption or voluntary yield
New
Process
Ready
List
Scheduler
CPU
job
job
Resource
Manager
job
job
Request
“Blocked”
Resources
Copyright © 2004 Pearson Education, Inc.
job
“Running”
“Ready”
Allocate
Done
Operating Systems: A Modern Perspective, Chapter 6
The Scheduler
Slide 6-15
From
Other
States
Process
Descriptor
Ready Process
Enqueuer
Ready
List
Dispatcher
Context
Switcher
CPU
Running Process
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Invoking the Scheduler
• Need a mechanism to call the scheduler
• Voluntary call
– Process blocks itself
– Calls the scheduler
• Involuntary call
– External force (interrupt) blocks the process
– Calls the scheduler
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-16
Voluntary CPU Sharing
yield(pi.pc, pj.pc) {
memory[pi.pc] = PC;
PC = memory[pj.pc];
}
• pi can be “automatically” determined from
the processor status registers
yield(*, pj.pc) {
memory[pi.pc] = PC;
PC = memory[pj.pc];
}
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-17
More on Yield
Slide 6-18
• pi and pj can resume one another’s execution
yield(*, pj.pc);
. . .
yield(*, pi.pc);
. . .
yield(*, pj.pc);
. . .
• Suppose pj is the scheduler:
// p_i yields to scheduler
yield(*, pj.pc);
// scheduler chooses pk
yield(*, pk.pc);
// pk yields to scheduler
yield(*, pj.pc);
// scheduler chooses ...
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Voluntary Sharing
• Every process periodically yields to the scheduler
• Relies on correct process behavior
– process can fail to yield: infinite loop either intentionally
(while(1)) or due to logical error (while(!DONE))
• Malicious
• Accidental
– process can yield to soon: unfairness for the “nice” processes who
give up the CPU, while others do not
– process can fail to yield in time:
• another process urgently needs the CPU to read incoming data
flowing into a bounded buffer, but doesn’t get the CPU in time to
prevent the buffer from overflowing and dropping information
• Need a mechanism to override running process
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-19
Involuntary CPU Sharing
Slide 6-20
• Interval timer
– Device to produce a periodic interrupt
– Programmable period
IntervalTimer() {
InterruptCount--;
if(InterruptCount <= 0) {
InterruptRequest = TRUE;
InterruptCount = K;
}
SetInterval(programmableValue) {
}
K = programmableValue:
InterruptCount = K;
}
}
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Involuntary CPU Sharing (cont)
• Interval timer device handler
– Keeps an in-memory clock up-to-date (see Chap 4 lab
exercise)
– Invokes the scheduler
IntervalTimerHandler() {
Time++; // update the clock
TimeToSchedule--;
if(TimeToSchedule <= 0) {
<invoke scheduler>;
TimeToSchedule = TimeSlice;
}
}
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-21
Contemporary Scheduling
• Involuntary CPU sharing – timer interrupts
– Time quantum determined by interval timer –
usually fixed size for every process using the
system
– Sometimes called the time slice length
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-22
Choosing a Process to Run
Process
Descriptor
Ready Process
Enqueue
Ready
List
Dispatch
Context
Switch
CPU
Running Process
• Mechanism never changes
• Strategy = policy the dispatcher uses to
select a process from the ready list
• Different policies for different requirements
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-23
Policy Considerations
• Policy can control/influence:
– CPU utilization
– Average time a process waits for service
– Average amount of time to complete a job
• Could strive for any of:
–
–
–
–
Equitability
Favor very short or long jobs
Meet priority requirements
Meet deadlines
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-24
Slide 6-25
Optimal Scheduling
• Suppose the scheduler knows each process
pi’s service time, t(pi) -- or it can estimate
each t(pi) :
• Policy can optimize on any criteria, e.g.,
– CPU utilization
– Waiting time
– Deadline
• To find an optimal schedule:
– Have a finite, fixed # of pi
– Know t(pi) for each pi
– Enumerate all schedules, then choose the best
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
However ...
Slide 6-26
• The t(pi) are almost certainly just estimates
• General algorithm to choose optimal
schedule is O(n2)
• Other processes may arrive while these
processes are being serviced
• Usually, optimal schedule is only a
theoretical benchmark – scheduling policies
try to approximate an optimal schedule
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Talking About Scheduling ...
• Let P = {pi | 0  i < n} = set of processes
• Let S(pi)  {running, ready, blocked}
• Let t(pi) = Time process needs to be in
running state (the service time)
• Let W(pi) = Time pi is in ready state before
first transition to running (wait time)
• Let TTRnd(pi) = Time from pi first enter ready
to last exit ready (turnaround time)
• Batch Throughput rate = inverse of avg TTRnd
• Timesharing response time = W(pi)
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-27
Slide 6-28
Simplified Model
Preemption or voluntary yield
New
Process
Ready
List
Scheduler
CPU
job
job
Done
job
“Running”
“Ready”
Allocate
Resource
Manager
job
job
Request
“Blocked”
Resources
• Simplified, but still provide analysis result
• Easy to analyze performance
• No issue of voluntary/involuntary sharing
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Estimating CPU Utilization
New
Process
Ready
List
Let l = the average rate
at which processes are
placed in the Ready List,
arrival rate
l pi per second
Scheduler
CPU
Slide 6-29
Done
Let m = the average service rate
 1/ m = the average t(pi)
System
Each pi uses 1/ m units of
the CPU
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6
Slide 6-30
Estimating CPU Utilization
New
Process
Ready
List
Let l = the average rate
at which processes are
placed in the Ready List,
arrival rate
Scheduler
CPU
Done
Let m = the average service rate
 1/ m = the average t(pi)
Let r = the fraction of the time that the CPU is expected to be busy
r = # pi that arrive per unit time * avg time each spends on CPU
r = l * 1/ m = l/m
Copyright © 2004 Pearson Education, Inc.
• Notice must have l < m (i.e., r < 1)
• What if r approaches 1?
Operating Systems: A Modern Perspective, Chapter 6
Nonpreemptive Schedulers
Slide 6-31
Blocked or preempted processes
New
Process
Ready
List
Scheduler
CPU
Done
• Try to use the simplified scheduling model
• Only consider running and ready states
• Ignores time in blocked state:
– “New process created when it enters ready state”
– “Process is destroyed when it enters blocked state”
– Really just looking at “small phases” of a process
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 6