![](indbul1a.gif) |
Mode: user & kernel mode |
![](indbul1a.gif) |
Space
![](indbul2a.gif) |
kernel space: system wide & shared
by all processes
![](indbul3a.gif) |
kernel segment (kernel code, data
structure, kernel address map) |
|
![](indbul2a.gif) |
user space: per process & private
![](indbul3a.gif) |
u area, text, data, stack, shared
memory region |
|
|
![](indbul1a.gif) |
Kernel accesses kernel space and u area |
![](indbul1a.gif) |
User process can only access its own user
space except the u area |
![](indbul1a.gif) |
Execution context
![](indbul2a.gif) |
process context: kernel executes on
behalf of a process, e.g., system call |
![](indbul2a.gif) |
system context: kernel executes
system-wide task, e.g., disk or network interrupt handling |
|
![](indbul1a.gif) |
Mode and context are orthogonal |
![](indbul1a.gif) |
User address space: text segment, data seg,
stack seg, shared memory regions |
![](indbul1a.gif) |
Control information: u area, proc structure,
kernel stack, address translation map(= page & segment table) |
![](indbul1a.gif) |
Credentials: UID, GID |
![](indbul1a.gif) |
Environment Variables: saved at the bottom of
user stack |
![](indbul1a.gif) |
Hardware context: saved in PCB, which is, in
turn, saved at the u area |
![](indbul1a.gif) |
User level library package such as C-thread of
Mach or POSIX pthread provides functions such as:
![](indbul2a.gif) |
creation, synchronization, scheduling,
and destruction of user threads |
|
![](indbul1a.gif) |
User thread can be implemented on top of
process or LWP |
![](indbul1a.gif) |
Kernel is unaware of user threads and only
schedules in terms of processes or LWP (Fig 3-5 (a) & (b)) |
![](indbul1a.gif) |
User thread becomes possible because
![](indbul2a.gif) |
a process can have multiple execution
contexts and switch among those contexts using setjmp, longjmp, and
signal |
![](indbul2a.gif) |
the execution context can be saved and
restored at the user level as Condor does |
|
![](indbul1a.gif) |
Resource
![](indbul2a.gif) |
Private user stack, user-level register
context, and other state info like signal mask |
|
![](indbul1a.gif) |
Synchronization at user level eliminates the
thread switch at kernel level
![](indbul2a.gif) |
When a thread needs to block on a lock,
thread library puts the thread into the corresponding queue and
schedules another user thread |
|
![](indbul1a.gif) |
Blocking system calls
![](indbul2a.gif) |
A user thread makes a blocking system
call -> |
![](indbul2a.gif) |
Replaced the call to non-blocking calls
-> |
![](indbul2a.gif) |
Another thread gets scheduled -> |
![](indbul2a.gif) |
The non-blocking system call completes
-> interrupts occurs -> |
![](indbul2a.gif) |
The blocked thread gets scheduled again |
|
![](indbul1a.gif) |
Pros
![](indbul2a.gif) |
Performance (Table 3-1) |
![](indbul2a.gif) |
Virtually unlimited number of threads
-> the number of threads = application's concurrency level ->
better programming model |
![](indbul2a.gif) |
A system can have several thread
libraries each of which can be used for different purposes |
|
![](indbul1a.gif) |
Cons
![](indbul2a.gif) |
No true parallelism without support from
kernel thread |
![](indbul2a.gif) |
No protection among threads within a
process or a LWP -> threads should be programmed as cooperative |
![](indbul2a.gif) |
Information barrier between library and
kernel
![](indbul3a.gif) |
A thread (on an LWP) holding lock
can be scheduled out by kernel to schedule in another thread
(on another LWP) waiting for the lock |
![](indbul3a.gif) |
A thread (on an LWP) of high
priority can be scheduled out by kernel to schedule in another
thread (on another LWP) of lower priority |
|
|
![](indbul1a.gif) |
Combines the advantages of kernel and user
thread |
![](indbul1a.gif) |
Basic principle: have close integration
between user threads and kernel |
![](indbul1a.gif) |
Clear mission allocation
![](indbul2a.gif) |
Kernel: processor allocation |
![](indbul2a.gif) |
Library: schedule threads by
multiplexing them on processors given from kernel |
|
![](indbul1a.gif) |
Library -> Kernel: information that affects
processor allocation
![](indbul2a.gif) |
request for processors |
![](indbul2a.gif) |
relinquish of processors |
|
![](indbul1a.gif) |
Kernel -> Library: information that affects
thread scheduling
![](indbul2a.gif) |
allocation and deallocation of
processors |
![](indbul2a.gif) |
status changes of threads, which affects
scheduling |
|
![](indbul1a.gif) |
upcall: call from kernel to library |
![](indbul1a.gif) |
scheduler activation: virtual processor given
to library by kernel
![](indbul2a.gif) |
Logically similar to LWP: has user &
kernel stack |
![](indbul2a.gif) |
Main difference from LWP: one-to-one
relationship to processors |
|
![](indbul1a.gif) |
Handling of blocking operation of threads
![](indbul2a.gif) |
Thread running in kernel blocks -> |
![](indbul2a.gif) |
Kernel preempts the
processor(=activation) -> |
![](indbul2a.gif) |
Kernel creates a new activation and make
an upcall to library -> |
![](indbul2a.gif) |
Library saves the context of the
deactivated thread from the old activation -> |
![](indbul2a.gif) |
Library schedules another thread on the
new activation -> |
![](indbul2a.gif) |
Blocking operation completes -> |
![](indbul2a.gif) |
Kernel makes a new activation (or
preempts an activation from the process) -> |
![](indbul2a.gif) |
Kernel notifies the library of the
blocking operation having been completed (and preemption of the
activation) -> |
![](indbul2a.gif) |
Library puts the thread having been
blocked (and the thread of preempted activation) into ready list
-> |
![](indbul2a.gif) |
Library select a thread from ready list
to run and attaches it to the new activation |
|
![](indbul1a.gif) |
Each LWP is bound to a kernel thread during
its life-time |
![](indbul1a.gif) |
Traditional proc and u area of process model
should be changed
![](indbul2a.gif) |
proc: hold all per-process data,
including the process-specific part of traditional u area |
![](indbul2a.gif) |
lwp data: per-LWP data
![](indbul3a.gif) |
user level register context:
meaningful only when the LWP is not running |
![](indbul3a.gif) |
system call arguments, results,
and error code |
![](indbul3a.gif) |
signal handling information |
![](indbul3a.gif) |
resource usage and profiling data,
virtual time alarms, user time and CPU usage |
![](indbul3a.gif) |
pointer to the kernel thread attached |
![](indbul3a.gif) |
pointer to the proc structure |
|
|
![](indbul1a.gif) |
All LWP share signal handlers but each may
have individual sigmask |
![](indbul1a.gif) |
Traps--synchronous signals like segfault--are
delivered to the causing LWP |
![](indbul1a.gif) |
Interrupt--asynchronous signals can be
delivered to any LWP that has not masked the signal |
![](indbul1a.gif) |
Semaphores
are rather low level and error prone: need careful program, otherwise race
condition or deadlock |
![](indbul1a.gif) |
Monitor
![](indbul2a.gif) |
Can
be thought as an object wrapped by mutex.down() & mutex.down() |
![](indbul2a.gif) |
Condition
variable instead of integer semaphore |
|
![](indbul1a.gif) |
Diff
between condition variable & (integer) semaphore
![](indbul2a.gif) |
up()
Vs. signal()
![](indbul3a.gif) |
up:
increase the semaphore value -> excess up operations get
remembered |
![](indbul3a.gif) |
signal:
wake up a process waiting for the condition variable, no
effect if no process is waiting |
|
![](indbul2a.gif) |
down()
Vs. wait()
![](indbul3a.gif) |
down:
block the caller only if value == 0 |
![](indbul3a.gif) |
wait:
always block the caller until next signal(), also release
mutex |
|
|
![](indbul1a.gif) |
Bounded
Buffer - in Java syntax
![](indbul2a.gif) |
synchronized
insert(object item) {
![](indbul3a.gif) |
if
(buffer is full)
![](indbul3a.gif) |
nonfull.wait(); |
|
![](indbul3a.gif) |
addElement(item); |
![](indbul3a.gif) |
nonempty.signal(); |
|
![](indbul2a.gif) |
} |
![](indbul2a.gif) |
synchronized
delete() {
![](indbul3a.gif) |
if
(buffer is empty)
![](indbul3a.gif) |
nonempty.wait(); |
|
![](indbul3a.gif) |
deleteElement(); |
![](indbul3a.gif) |
nonfull.signal(); |
|
![](indbul2a.gif) |
} |
|
![](indbul1a.gif) |
Notes
on signal
![](indbul2a.gif) |
When
a waiter is awaken, the condition it was waiting for is guaranteed
-> |
![](indbul2a.gif) |
No
process should sneak between signal() and return from wait() ->
![](indbul3a.gif) |
Signaling
mechanism should be absolutely reliable & Only one waiter
should be awaken & The signaler should block immediately
-> |
![](indbul3a.gif) |
Upon
waiter leaving the monitor, signaler should be awaken or be
able to contend to grab mutex released by the waiter |
|
![](indbul2a.gif) |
Inefficient:
unnecessary context switches signaler->waiter->signaler |
|
![](indbul1a.gif) |
Notify
![](indbul2a.gif) |
Wake
up a waiter, but signaler does NOT block -> |
![](indbul2a.gif) |
Other
processes can sneak into between signal and the return from wait
call -> |
![](indbul2a.gif) |
Waiter
should check whether the condition is still true after returning
from wait call
![](indbul3a.gif) |
'if'
block of the above code snippet should be replaced by 'while' |
|
|
![](indbul1a.gif) |
Monitor
in Java
![](indbul2a.gif) |
No
monitor modifier for the entire object. Instead each method can be
tagged with 'synchronized' |
![](indbul2a.gif) |
Only
one implicit condition variable per object -> notifyAll instead
of notify |
|
![](indbul1a.gif) |
Metrics
![](indbul2a.gif) |
Waiting time - the amount of time the
job is runnable and not running |
![](indbul2a.gif) |
Penalty ratio - elapsed-time /
ideal-time |
|
![](indbul1a.gif) |
FCFS
![](indbul2a.gif) |
Favors long burst, i.e., CPU-bound jobs
![](indbul3a.gif) |
Short job's penalty ratio is too
big |
|
![](indbul2a.gif) |
Favoring long job leads convoy effect |
![](indbul2a.gif) |
Convoy effect
![](indbul3a.gif) |
short jobs are waiting behind a
long job |
![](indbul3a.gif) |
CPU busy & I/O devices idle
<-> CPU idel & I/O busy |
|
|
![](indbul1a.gif) |
Shortest Job First
![](indbul2a.gif) |
Optimal with respect to average waiting
time |
![](indbul2a.gif) |
Don't know how long the job will run
-> Approx. algorithm needed |
![](indbul2a.gif) |
The length of burst is guessed from
history
![](indbul3a.gif) |
guess = ( guess + previousBurst )
/ 2 |
|
|
![](indbul1a.gif) |
Shortest Remaining Job First
![](indbul2a.gif) |
Preemptive version of SJF |
![](indbul2a.gif) |
Min ( shortest job in the ready queue,
remaining time for the job currently running to finish ) |
|
![](indbul1a.gif) |
Round-robin & Process Sharing
![](indbul2a.gif) |
Round-robin becomes process sharing when
quantum becomes zero |
|
![](indbul1a.gif) |
Priority scheduling
![](indbul2a.gif) |
Both preemptive and nonpreemptive
scheduling are possible |
![](indbul2a.gif) |
Priority can be given externally or
calculated internally |
![](indbul2a.gif) |
Multi-Level Feedback Queue
![](indbul3a.gif) |
Short jobs are favored |
![](indbul3a.gif) |
Long jobs get longer quantum and
run with less context switch |
|
|
![](indbul1a.gif) |
Analysis
![](indbul2a.gif) |
Queuing theory: arrival rate vs service
rate |
|