Transcript Document

Operating Systems Principles
Process Management and Coordination
Lecture 4:
The Operating System Kernel:
Implementing Processes and Threads
主講人：虞台文
Content




Kernel Definitions and Objects
Queue Structures
Threads
Implementing Processes and Threads
–
–

Implementing Sync/Comm Mechanisms
–
–
–
–

Process and Thread Descriptors
Implementing the Operations
Semaphores and Locks
Building Monitor Primitives
Clock and Time Management
Communications Kernel
Interrupt Handling
Operating Systems Principles
Process Management and Coordination
Lecture 4:
The Operating System Kernel:
Implementing Processes and Threads
Kernel Definitions
and Objects
Windows Kernel
Windows Kernel
Hardware dependent functions
are placed in the kernel.
OS Kernel


A basic set of objects, primitives, data structures,
processes from which the remainder of the
system may be built on its top.
In other words, the kernel transforms the
hardware into an OS’s machine.
OS’s Machine
I am staying on the
top of an OS machine.
Kernel Objects


Kernel defines/provides mechanisms to implement
various policies.
Four classes of possible functions and objects in a
kernel:
–
–
–
–
Process and thread management
Interrupt and trap handling
Resource management
Input/output
Process
Kernel Objects

and thread management
Interrupt and trap handling
Resource management
Input/output
Process and thread management
–
Process Creation
–
Process Destruction
–
Process Communication/Synchronization
Process
Kernel Objects

Interrupt and trap handling
–

and thread management
Interrupt and trap handling
Resource management
Input/output
Responding to signals triggered by various
system events.
Some system events:
–
–
–
–
–
Process termination
I/O completion
Time-out of clock
Error
Hardware malfunction
Process
Kernel Objects

and thread management
Interrupt and trap handling
Resource management
Input/output
Interrupt and trap handling
–
Responding to signals triggered by various
system events.
......
......
......
Do_I/O
......
......
CPU
Start I/O
Interrupt
I/O
Processor
Done
Process
Kernel Objects

Resource management
–

Primitives for maintaining, allocating, and
releasing system resources.
Some system resources:
–
–
–
–
–
–
and thread management
Interrupt and trap handling
Resource management
Input/output
CPUs
Timers
Main memory
Secondary storage
I/O devices
Files
Process
Kernel Objects

and thread management
Interrupt and trap handling
Resource management
Input/output
Input/output
–
Read, write, and control operations for
initiating and supervising the transfer of data
between I/O devices and main memory or
registers.
Main Topics in the Lecture

Process and thread management

Interrupt and trap handling

Resource management

Input/output
Main topics
Kernel
Interaction with kernel objects
Process Creation Hierarchy
ps
user 1 login
p1
...
q1
OS process
user j login
user n login
pj
...
...
qm
pn
user
processes
application
processes.
child
processes
Operating Systems Principles
Process Management and Coordination
Lecture 4:
The Operating System Kernel:
Implementing Processes and Threads
Queue Structures
Queues

OS needs many different queues
–

e.g., ready queues, wait queues.
Single-level queues
–
Implemented as array


–
Fixed size
Efficient for simple FIFO operations
Implemented as linked list


Unbounded size
More overhead, but more flexible operations
Single-Level Queues
Circular Array Implementation
Link List Implementation
Priority Queues
Array indexed
by priority
Priority Queues
Binary heap
of priority
Priority Queues
Binary heap
of priority
Array implementation
of binary heap
Operating Systems Principles
Process Management and Coordination
Lecture 4:
The Operating System Kernel:
Implementing Processes and Threads
Threads
Virtual Memory
Address Spaces
Lowest Address, e.g., 00000000
Memory
Highest Address, e.g., FFFFFFFF
Virtual Memory
Address Spaces
Lowest Address, e.g., 00000000
OS
Starting Address of all processes
Memory
User
Programs
Highest Address, e.g., FFFFFFFF
Only one process can be activated at a time.
Each process thinks that it owns all memory.
Processes
OS
User
Programs
OS
OS
OS
Process 1
Process 2
Process n
Their address spaces are different.
Only one process can be activated at a time.
Each process thinks that it owns all memory.
Context Switching
OS
User
Programs
OS
OS
OS
Process 1
Process 2
Process n
Context
Switching
Context
Switching
Only one process can be activated at a time.
Each process thinks that it owns all memory.
Context Switching
OS
OS
OS
OS
The context switching among processes, i.e., to
change address space, is very time consuming.
User
Programs
Process 1
Process 2
Process n


Threads
OS
User
Programs


Each process can have multiple threads.
They share the same address space.
The context switching among threads in
the process is efficient.
Lightweight process  Mesa
OS
OS
OS
Process 1
Process 2
Process n
Processes and Threads
Processes and Threads

Process has one or more threads

All threads in a process share:


–
Memory space
–
Other resources
Each thread has its own:
–
CPU state
(registers, program counter)
–
Stack
Threads are efficient, but lack
protection from each other
Microsoft
Windows
Process & Thread Functions
OS Support for Processes/Threads

Create a new Process/thread

Initiate or make a thread ready

Destroy or terminate a thread



Delay or put a thread to sleep for a given amount
of time
Synchronize threads through semaphore, events,
or condition variables
Perform lower-level operations, such as blocking,
suspending, or scheduling a thread.
Operating Systems Principles
Process Management and Coordination
Lecture 4:
The Operating System Kernel:
Implementing Processes and Threads
Implementing
Processes and Threads
Process and Thread Descriptors


System needs some data structures to keep track
the state and miscellaneous information, e.g.,
identification, resources used, accounting
information, of processes and treads.
In the following, we are dealing with a system
composed solely of processes, much of concept
will also apply to threads.
Process Control Block (PCB)
Process Identification
A system-wide unique
identifier.
State Vector
CPU’s State
Contain necessary data,
e.g., program counter, data
register, and flag register,
to restart the process at
the point of last interruption.
Processor ID
To identify the processor that is
executing the process. Make
sense only for multiprocessor
system.
Memory
Memory map information.
Physical Memory  Virtual Memory
Status
Status
Point to the list, e.g., ready
list or wait list, on which
the process may reside.
blocked
running
ready
More on Status

Basic process status
–

running, ready, and blocked
State transition diagram
running
Request
Scheduler
Create
ready
blocked
Release
Suspend
Thread
Resume
Thread
Process Activation and Suspension


Some applications require a process (or
thread) can be suspended by programs.
For examples
–
Suspension of a debugging program
–
Needed by the internal, e.g., to detect or
prevent a deadlock.
The Finer State Transition Diagram
The Finer State Transition Diagram
Active
Processes
Suspended
Processes
Interaction with kernel objects
Creation Tree
Kernel
Kernel
pps
s
user 1 login
pp1
1
...
qq1
1
OS process
user j login
ppj
j
...
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
Interaction with kernel objects
Creation Tree
Kernel
Kernel
pps
s
user 1 login
pp1
1
...
qq1
1
user j login
ppj
j
...
A link list of PCBs of
the child processes
Point to the PCB of the
parent process.
OS process
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
Priority
Two methods:
 Single-integer value
 Two-leveled valued
–
Base priority + Changeable part
Used by scheduler to
decide which process
should be running next.
Priority
Windows
NT priority
classes
Two methods:
 Single-integer value
 Two-leveled valued
–
Base priority + Changeable part
Others







CPU time used
Time remaining
Resource used
Resource claimed
Resource quotas
Number of I/O requests since creation
...
Processes and Threads
(Windows 2000)
Access Token
VAD
Process
Object
VAD
VAD
Virtual Address Space Descriptors
Handle Table
object
object
Thread
Thread
Thread
...
Access Token
Executive Process
Windows 2000 (EPROCESS)
Kernel Process Block
Processes and Threads
(Windows 2000)
EPROCESS
ETHREAD
Windows 2000 (ETHREAD)
Kernel Thread Block
Windows 2000 Thread States
Implement Operations on Processes

Create
–

Destroy
–

Remove one or more process
Suspend
–

Establish a new process
Change process status to suspended
Activate
–
Change process status to active
cobegin/coend
forall
fork/join/quit
......
Implement Operations on Processes

Create
–

Destroy
–

Remove one or more process
Suspend
–

Establish a new process
Change process status to suspended
Activate
–
Change process status to active
Operating on PCBs
CSs must be cared
Create
Create
Create(s0, m0, pi, pid) {
p = Get_New_PCB(); pid = Get_New_PID();
pid = Get_New_PID();
p->ID
= pid;
p->CPU_State
= s0;
Get_New_PCB();
s0
p->Memory = m0;
p->Priority
= pi;
p->Status.Type = ’ready_s’;
m0
p->Status.List = RL;
p->Creation_Tree.Parent
=RL self;
ready_s
p->Creation_Tree.Child
= NULL
NULL;
self
pi
insert(self-> Creation_Tree.Child,
p);
insert(RL, p);
Activate(); Scheduler();
}
pid = Get_New_PID();
s0
Get_New_PCB();
m0
Create
ready_s
self
RL
NULL
pi
Create(s0, m0, pi, pid) {
p = Get_New_PCB(); pid = Get_New_PID();
p->ID = pid;
p->CPU_State = s0;
p->Memory = m0;
p->Priority = pi;
p->Status.Type = ’ready_s’;
The calling
process
p->Status.List = RL;
p->Creation_Tree.Parent = self;
p->Creation_Tree.Child = NULL;
insert(self-> Creation_Tree.Child, p);
insert(RL, p);
Activate(); Scheduler();
}
pid = Get_New_PID();
s0
Get_New_PCB();
m0
Create
ready_s
self
RL
NULL
pi
Create(s0, m0, pi, pid) {
p = Get_New_PCB(); pid = Get_New_PID();
p->ID = pid;
p->CPU_State = s0;
p->Memory = m0;
p->Priority = pi;
p->Status.Type = ’ready_s’;
p->Status.List = RL;
p->Creation_Tree.Parent = self;
p->Creation_Tree.Child = NULL;
insert(self-> Creation_Tree.Child, p);
insert(RL, p);
Activate(); Scheduler();
}
Suspend
Interaction with kernel objects
Suspend
Kernel
Kernel
pps
s
user 1 login
pp1
1
user j login
...
Suspend (
qq1
1
OS process
ppj
j
)
...
Suspend?
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
We choose not.
Suspend
Suspend(pid) {
p = Get_PCB(pid);
s = p->Status.Type;
if ((s==’blocked_a’)||(s==’blocked_s’))
p->Status.Type = ’blocked_s’;
else
p->Status.Type = ’ready_s’;
if (s==’running’) {
cpu = p->Processor_ID;
p->CPU_State = Interrupt(cpu);
Scheduler();
returns all registers’ values
}
of the cpu and frees the
}
cpu.
Activate
Interaction with kernel objects
Activate
Kernel
Kernel
pps
s
user 1 login
pp1
1
user j login
...
Activate (
qq1
1
OS process
ppj
j
)
...
Activate?
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
We choose not.
An option
to do this.
Activate
Activate(pid) {
p = Get_PCB(pid);
if (p->Status.Type == ’ready_s’) {
p->Status.Type = ’ready_a’;
Scheduler();
}
else
p->Status.Type = ’blocked_a’;
}
We need to release all resources
associated with the process.
Destroy
What special action needs to be
taken if the process is running?
Interaction with kernel objects
Destroy
Kernel
Kernel
pps
s
user 1 login
pp1
1
user j login
...
Destroy (
qq1
1
OS process
ppj
j
)
Killed?
...
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
We choose to kill
child processes.
Interaction with kernel objects
Destroy
Kernel
Kernel
pps
s
user 1 login
pp1
1
user j login
...
subroutine
Kill_Tree (
qq1
1
ppj
j
)
...
killed
Kill_Tree(p) {
for (each q in p->Creation_Tree.Child)
Kill_Tree(q);
if (p->Status.Type == ’running’) {
cpu = p->Processor_ID;
Marked the corresponding cpu free.
Interrupt(cpu);
}
Remove(p->Status.List, p);
Release_all(p->Memory);
Release_all(p->Other_Resources);
Close_all(p->Open_Files);
Delete_PCB(p);
}
OS process
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
Interaction with kernel objects
Destroy
Kernel
Kernel
pps
s
user 1 login
pp1
1
user j login
...
subroutine
Kill_Tree (
qq1
1
ppj
j
)
...
killed
Kill_Tree(p) {
for (each q in p->Creation_Tree.Child)
Kill_Tree(q);
if (p->Status.Type == ’running’) {
cpu = p->Processor_ID;
Interrupt(cpu);
}
Remove(p->Status.List, p);
Release_all(p->Memory);
Release_all(p->Other_Resources);
Close_all(p->Open_Files);
Delete_PCB(p);
}
OS process
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
Interaction with kernel objects
Destroy
Kernel
Kernel
pps
s
user 1 login
pp1
1
user j login
...
Destroy (
qq1
1
OS process
ppj
j
)
...
user n login
...
qqm
m
ppn
n
user
processes
application
processes.
child
processes
Destroy(pid) {
p = Get_PCB(pid);
Kill_Tree(p);
Scheduler();
}
Kill_Tree(p)
Kill_Tree(p) {{
for
for (each
(each qq in
in p->Creation_Tree.Child)
p->Creation_Tree.Child)
Kill_Tree(q);
Kill_Tree(q);
if
if (p->Status.Type
(p->Status.Type ==
== ’running’)
’running’) {{
cpu
cpu == p->Processor_ID;
p->Processor_ID;
Interrupt(cpu);
Interrupt(cpu);
}}
Remove(p->Status.List,
Remove(p->Status.List, p);
p);
Release_all(p->Memory);
Release_all(p->Memory);
Release_all(p->Other_Resources);
Release_all(p->Other_Resources);
Close_all(p->Open_Files);
Close_all(p->Open_Files);
Delete_PCB(p);
Delete_PCB(p);
}}
Operating Systems Principles
Process Management and Coordination
Lecture 4:
The Operating System Kernel:
Implementing Processes and Threads
Implementing
Sync/Comm Mechanisms
Semaphores, locks, monitors, messages, time, and
other hardware and software objects are
considered resources.
General Resource Access Scheme
Request(res) {
if (Free(res))
Allocate(res, self)
else {
Block(self, res);
Scheduler();
}
}
Release(res) {
Deallocate(res, self);
if (Process_Blocked_in(res,pr)) {
Allocate(res, pr);
Unblock(pr, res);
Scheduler();
}
}
Implementing Semaphores/Locks



CPU usually doesn’t support P and V operations
directly.
Test-and-Set instruction  supported mostly
–
It atomically tests and modifies the contents of a
memory location.
–
It can be used to implement general semaphores in
multiprocessor systems.
In uniprocessor systems, it is sufficient to
disable interrupts before accessing a semaphore.
The Story (80x86)
Memory
Memory
Access
resource
The Story (80x86)
Lock XCHG
Memory
Access
resource
The Story (80x86)
Access
resource
The Story (80x86)
Memory
The spin locks
Access
resource
The Story (80x86)
Lock XCHG
Memory
The spin locks
Lock XCHG
Memory
Job Done
Access
resource
The Story (80x86)
The spin locks
Memory
Job Done
Access
resource
The Story (80x86)
The spin locks
Lock XCHG
Memory
Job Done
Access
resource
The Story (80x86)
Test-and-Set CPU Instruction
TS(R, X)
A CPU Register
Returns the
value in R.
The lock is always
locked after
being called.
A Memory Location
(Lock Value)
R = X;
X = 0;
Read (test) lock value
0: locked is locked
Indivisible
1: locked is unlocked
Atomic
Lock (set) the lock
sb  {0, 1}
Spin Locks on Binary Semaphore
Request( res ) {
if (Free(res))
Allocate(res, self)
else {
Block(self, res);
Scheduler();
}
}
Release( res ) {
Deallocate(res, self);
if (Process_Blocked_in(res,pr)) {
Allocate(res, pr);
Unblock(pr, res);
Scheduler();
}
}
sb  {0, 1}
Spin Locks on Binary Semaphore
Pb
Sb ) {
Request(
res
Sb==1
if (Free(res))
Sb=0;
Allocate(res, self)
else {
Block(self, res);
wait until Sb==1
Scheduler();
}
}
Sb ) {
Vb
Release(
res
Sb=1;
Deallocate(res, self);
if (Process_Blocked_in(res,pr)) {
Allocate(res, pr);
Unblock(pr, res);
Scheduler();
}
}
sb  {0, 1}
Spin Locks on Binary Semaphore
Pb(Sb) {
do
TS(R, Sb)
while(!R);
}
/* wait loop */
Vb(Sb) {
Sb=1;
}
sb  {0, 1}
Spin Locks on Binary Semaphore
Pb(Sb) {
do
TS(R, Sb)
while(!R);
}
/* wait loop */
Vb(Sb) {
Sb=1;
}
General Semaphores w/ Busy Wait
P(s) {
Inhibit_Interrupts;
Pb(mutex_s);
s = s-1;
if (s < 0) {
Vb(mutex_s);
Enable_Interrupts;
Pb(delay_s);
}
Vb(mutex_s);
Enable_Interrupts;
}
V(s) {
Inhibit_Interrupts;
Pb(mutex_s);
s = s+1;
if (s <= 0) Vb(delay_s);
else Vb(mutex_s);
Enable_Interrupts;
}
Disallowing Preemption
P(s) {
Inhibit_Interrupts;
Pb(mutex_s);
s = s-1;
if (s < 0) {
Vb(mutex_s);
Disallowed
to be preempted
by aEnable_Interrupts;
higher-priority process.
Pb(delay_s);
}
Vb(mutex_s);
Enable_Interrupts;
}
V(s) {
Inhibit_Interrupts;
Pb(mutex_s);
sDisallowed
= s+1; to be preempted
by a(s
higher-priority
process.
if
<= 0) Vb(delay_s);
else Vb(mutex_s);
Enable_Interrupts;
}
Interrupt Inhibition
P(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s-1;
if (s < 0) {
Vb(mutex_s);
Enable_Interrupts;;
Pb(delay_s);
}
Vb(mutex_s);
Enable_Interrupts;;
}
V(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s+1;
if (s <= 0) Vb(delay_s);
else Vb(mutex_s);
Enable_Interrupts;;
}
Uniprocessor
P(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s-1;
if (s < 0) {
Vb(mutex_s);
Enable_Interrupts;;
Pb(delay_s);
}
Vb(mutex_s);
Enable_Interrupts;;
}
V(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s+1;
if (s <= 0) Vb(delay_s);
else Vb(mutex_s);
Enable_Interrupts;;
}
Busy Wait
P(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s-1;
if (s < 0) {
Vb(mutex_s);
Enable_Interrupts;;
Pb(delay_s);
}
Vb(mutex_s);
Enable_Interrupts;;
}
V(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s+1;
if (s <= 0) Vb(delay_s);
else Vb(mutex_s);
Enable_Interrupts;;
}
Avoiding Busy Wait
P(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s-1;
if (s < 0) {
Block(self, Ls);
Vb(mutex_s);
Enable_Interrupts;;
Scheduler();
}
else {
Vb(mutex_s);
Enable_Interrupts;
}
}
V(s) {
Inhibit_Interrupts;;
Pb(mutex_s);
s = s+1;
if (s <= 0) {
Unblock(q, Ls);
Vb(mutex_s);
Enable_Interrupts;
Scheduler();
}
else{
Vb(mutex_s);
Enable_Interrupts;
};
}
Initial values: mutex = 1;
condsem_c = 0; condcnt_c = 0;
urgentcnt = 0;
urgent = 0;
Implementing Monitors (Hoare)
condcnt_c: #processes wait on c
Internal Data
Condition Variables
Procedure 1
Procedure 2
Procedure 3
c.wait
c.signal
Need a semaphore for
processes blocked on
c, say condsem_c.
Need a semaphore for
signaling processes,
say urgent.
urgentcnt: #signalers
mutually exclusive access
for processes
Need a mutex, say mutex.
Initial values: mutex = 1;
condsem_c = 0; condcnt_c = 0;
urgentcnt = 0;
urgent = 0;
Mutual Access of Processes
monitor QueueHandler{
struct Queue queue;
condition itemAvail, freenodeAvail;
void AddToQueue( int val ) {
if ( queue is full ) {
freenodeAvail.wait;
}
. . . add val to the end of the queue . . .
itemAvail.signal;
} /* AddToQueue */
int RemoveFromQueue() {
if ( queue is empty ) {
itemAvail.wait;
}
. . . remove value from queue . . .
freenodeAvail.signal;
return value;
} /* RemoveFromQueue */
};
Initial values: mutex = 1;
condsem_c = 0; condcnt_c = 0;
urgentcnt = 0;
urgent = 0;
Mutual Access of Processes
monitor QueueHandler{
struct Queue queue;
condition itemAvail, freenodeAvail;
void AddToQueue( int val ) {
P(mutex)
if ( queue is full ) {
freenodeAvail.wait;
}
. . . add val to the endif(urgentcnt)
of the queue . . . V(urgent);
itemAvail.signal;
else V(mutex);
} /* AddToQueue */
int RemoveFromQueue() {
if ( queue is empty ) { P(mutex)
itemAvail.wait;
}
. . . remove value from queue . . .
freenodeAvail.signal;
if(urgentcnt) V(urgent);
return value;
else V(mutex);
} /* RemoveFromQueue */
};
Initial values: mutex = 1;
condsem_c = 0; condcnt_c = 0;
urgentcnt = 0;
urgent = 0;
Mutual Access of Processes
P(mutex)
Procedure_body
if(urgentcnt) V(urgent);
else V(mutex);
Initial values: mutex = 1;
condsem_c = 0; condcnt_c = 0;
urgentcnt = 0;
urgent = 0;
wait/signal
c.wait:
condcnt_c = condcnt_c + 1;
c.signal:
if (condcnt_c) {
urgentcnt = urgentcnt + 1;
if (urgentcnt) V(urgent);
V(condsem_c);
else V(mutex);
P(urgent); /* wait */
P(condsem_c); /* wait */
condcnt_c = condcnt_c - 1;
urgentcnt = urgentcnt - 1;
}
Clock and Time Management

Why OS needs time?
–
Performance measurement
–
Processor Scheduling
–
Time-Stamping Events

e.g., I/O and file system call
–
Deadlock and other fault detection
–
........
Clock and Time Management

Most systems provide hardware
–
ticker: issues periodic interrupt
–
countdown timer: issues interrupt after a set number of ticks

Build higher-level services with this h/w

Wall clock timers
–
–
Typical functions:

Update_Clock : increment tnow (invoked each time tick)

Get_Time : return current time

Set_Time(tnew) : set time to tnew
Must maintain monotonicity
Countdown Timer (Alarm Clocks)



Processes or threads may need timeout
signal at some specified time in the future.
Examples:
–
Delay an amount of time to wait I/O completion
–
Sleep to hand over CPU time
–
Block until awakened by timer signal events
Typical Function:
–
Delay(tdel) block process for tdel time units
To block process for tdel time units.
Implementation of Delay(tdel)

Implementation using hardware countdown:
semaphore delsem;
Delay(tdel) {
Set_Timer(tdel);
P(delsem);
}
/*set hardware timer*/
/*wait for interrupt*/
Timeout() { /*called at interrupt*/
V(delsem);
}
How to implement multiple logical timers?
Logical Countdown Timers


Implement multiple logical countdown
timers using a single hardware timer
Functions:
–
tn = Create_LTimer()  create new timer
–
Destroy_LTimer(tn)
–
Set_LTimer(tn, tdel)  logically equivalent
to Set_Timer(tdel)
Set_LTimer(tn, tdel)
Priority Queue with
Absolute Wakeup Times
Hardware
Timers
Wall-clock
Countdown
103
12
Timer
Queue
TQ
p1 115
p2 135
p3 140
p4 150
Set_LTimer(??, 35)
+103
with
+138
Priority Queue
Absolute Wakeup Times
Hardware
Timers
Wall-clock
Countdown
103
12
Timer
Queue
TQ
p1 115
p2 135
p3 140
p4 150
TQ
p1 115
p2 135
p5 138
p3 140
p4 150
Priority Queue with
Absolute Wakeup Times
Hardware
Timers
TQ
p1 115
p2 135
Wall-clock
Countdown
104
105
106
107
108
109
110
112
113
114
115
111
103
10
12
11
9
8
7
6
5
4
3
2
0
1
p5 138
p3 140
p4 150
Priority Queue with
Absolute Wakeup Times
Hardware
Timers
Wall-clock
Countdown
115
20
0
135
-115
20
TQ
p2 135
p5 138
p3 140
p4 150
Set_LTimer(tn, tdel)
Priority Queue with Time Differences
Countdown
Hardware
Timer
12
Timer
Queue
TQ
p1 15
p2 20
p3 5
p4 10
Set_LTimer(??, 35)
Priority Queue with Time Differences
Countdown
Hardware
Timer
Timer
Queue
TQ
p1 15
12
12
32
37
p2 20
p3 5
p4 10
37
47
p5 3
p3 2
35
32
3
TQ
p1 15
p2 20
2
p4 10
Priority Queue with Time Differences
Countdown
Hardware
Timers
TQ
p1 15
p2 20
12
10
11
2
3
4
5
6
7
8
9
0
1
p5 3
p3 2
p4 10
Priority Queue with Time Differences
Countdown
Hardware
Timers
TQ
p2 20
20
0
p5 3
p3 2
p4 10
Assume that the communication
processes are in the same machine.
Communication Primitives
OS
System Space
Process
Memory
q
Address space for
process q
User Space
The same physical
memory used.
Different physical
memory used.
OS
Process
Memory
p
Address space for
process p
send/receive can be blocked or nonblocked.
Communication Primitives
OS
OS
Process
Communication
Process
q
send/receive
p
Address space for
process q
Address space for
process p
send/receive can be blocked or nonblocked.
Communication Primitives
OS
Process
OS
send(p,m)
receive(q,m)
q
Process
p
sbuf
rbuf
Address space for
process q
Address space for
process p
send/receive can be blocked or nonblocked.
Communication Primitives
OS
Process
OS
Different address mappings
for p and q.
send(p,m)
receive(q,m)
q
Process
p
sbuf
rbuf
Address space for
process q
How?
Address space for
process p
send/receive can be blocked or nonblocked.
Communication Primitives
OS
OS
sbuf’
Process
send(p,m)
q
sbuf’
Process
p
sbuf
Address space for
process q
Address space for
process p
send/receive can be blocked or nonblocked.
Communication Primitives
OS
Process
rbuf’
rbuf’
sbuf’
sbuf’
send(p,m)
receive(q,m)
q
OS
Process
p
sbuf
rbuf
Address space for
process q
Address space for
process p
send/receive can be blocked or nonblocked.
Communication Primitives
OS
Process
rbuf’
rbuf’
sbuf’
sbuf’
send(p,m)
receive(q,m)
q
OS
Process
p
sbuf
rbuf
Address space for
process q
Address space for
process p
send/receive can be blocked or nonblocked.
Communication Primitives
OS
Process
rbuf’
rbuf’
sbuf’
sbuf’
send(p,m)
receive(q,m)
q
OS
Process
p
sbuf
rbuf
Address space for
process q
Address space for
process p
Use pool of system buffers
Communication Primitives
Copying through
system buffers
(Processes in the
same machine)
Use pool of system buffers
Communication Primitives
Copying accross network
(Processes in the
different machines)
Operating Systems Principles
Process Management and Coordination
Lecture 4:
The Operating System Kernel:
Implementing Processes and Threads
Interrupt Handling
The program to serve interrupt is called interrupt
handler (IH) or interrupt service routine (ISR).
Why Interrupt Handling?


Many events occur at an unpredictable time, i.e.,
asynchronously
–
Polling is impractical
–
Transfer of control out of normal process temporarily
upon coming of an event and, then, back.
To remove the notion of asynchronous events from
higher levels of kernel, the OS, and applications
–
Process abstraction: processes are almost to have
independent activities and operating in parallel.
–
For example, OS and applications don’t deal with I/O
completion event directly.
We deal with hardware interrupt in the following.
Types of Interrupt

External Interrupts
–
–
–

Generated by hardware
Asynchronous
E.g., I/O completion, time-out, the arrival of
message (network card), …
Internal Interrupts
–
–
–
Generated by software
Synchronous
E.g., Exceptions (instruction errors), SVC
Interrupt Controller (82C59A)
80x86 uses STI and CLI to temporarily
enable and disable all interrupts, respectively.
Interrupt Controller (82C59A)
Interrupt requests are
priority-leveled.
to CPU
IH’s of high-priority
events can preempt
those of lower priority.
Interrupt
requests are
maskable.
Signaled
By I/O
Devices
Each interrupt has an interrupt
service routine (ISR).
Interrupt Handling
ISR7:
ISR6:
..........
ISR5:
..........
IRET
ISR4:
..........
IRET
ISR3:
..........
IRET
ISR2:
..........
IRET
ISR1:
..........
IRET
ISR0:
..........
IRET
..........
IRET
IRET
Normal Job
CPU
INT
Interrupt
Controller
(e.g., 8259)
stack
IRQ0
IRQ1
IRQ2
IRQ3
IRQ4
IRQ5
IRQ6
IRQ7
Each interrupt has an interrupt
service routine (ISR).
Interrupt Handling
ISR7:
ISR6:
..........
ISR5:
..........
IRET
ISR4:
..........
IRET
ISR3:
..........
IRET
ISR2:
..........
IRET
ISR1:
..........
IRET
ISR0:
..........
IRET
..........
IRET
IRET
Normal Job
PC (*)
Put the value of flag register,
and program counter (PC) into
the stack.
CPU
INT
Interrupt
Controller
(e.g., 8259)
*
flag
stack
IRQ0
IRQ1
IRQ2
IRQ3
IRQ4
IRQ5
IRQ6
IRQ7
ISR3:
Each interrupt has an interrupt
service routine (ISR).
Push used registers (PUSHA)
Interrupt
. . . . Handling
...................
ISR7:
ISR6:
..........
ISR5:
..........
IRET
(IRET)
ISR4:
..........
IRET
ISR3:
..........
IRET
ISR2:
..........
IRET
ISR1:
..........
IRET
ISR0:
..........
IRET
..........
IRET
IRET
Pop used registers (POPA)
Normal Job
Return from interrupt
PC (*)
CPU
Read
Interrupt
Vector
*
flag
stack
INT
Interrupt
Controller
(e.g., 8259)
IRQ0
IRQ1
IRQ2
IRQ3
IRQ4
IRQ5
IRQ6
IRQ7
ISR3:
Each interrupt has an interrupt
service routine (ISR).
Push used registers (PUSHA)
Interrupt
. . . . Handling
...................
ISR7:
ISR6:
..........
ISR5:
..........
IRET
(IRET)
ISR4:
..........
IRET
ISR3:
..........
IRET
ISR2:
..........
IRET
ISR1:
..........
IRET
ISR0:
..........
IRET
..........
IRET
IRET
Pop used registers (POPA)
Normal Job
Return from interrupt
PC (*)
CPU
INT
Interrupt
Controller
(e.g., 8259)
*
flag
stack
IRQ0
IRQ1
IRQ2
IRQ3
IRQ4
IRQ5
IRQ6
IRQ7
Each interrupt has an interrupt
service routine (ISR).
Interrupt Handling
ISR7:
ISR6:
..........
ISR5:
..........
IRET
ISR4:
..........
IRET
ISR3:
..........
IRET
ISR2:
..........
IRET
ISR1:
..........
IRET
ISR0:
..........
IRET
..........
IRET
IRET
Normal Job
PC (*)
CPU
INT
Interrupt
Controller
(e.g., 8259)
stack
IRQ0
IRQ1
IRQ2
IRQ3
IRQ4
IRQ5
IRQ6
IRQ7
Standard Interrupt Handing Sequence
1.
Save state of interrupted process/thread
2.
Identify interrupt type and invoke IH
3.
IH services interrupt
4.
Restore state of interrupted process (or of
another one if the interrupt for awakening a
waiting process)
The Typical Sequence for
Using a Hardware Device
......
......
......
Do_I/O
......
......
CPU
Start I/O
Interrupt
I/O
Processor
Done
The Typical Sequence for
Using a Hardware Device
The Typical Sequence for
Using a Hardware Device









P/V
wait/signal
Synchronization Primitives Needed
Monitor: Object-Oriented Approach
Called while I/O
completion.
Device
Driver
Implemented
Using monitor
Called by the
processes need
to do I/O.
Implementing Using Monitor
Example: Monitor Clock Server
Example: Monitor Clock Server
monitor Clock_Server {
int tnow;
Update_Clock() {
. . .
tnow = tnow + 1;
/* Perhapes update time structure also */
}
int Get_Time() {
. . .
return(tnow);
/* Perhaps return some more complex structure instead */
}
Set_Clock(int tnew) {
. . .
tnow = tnew;
}
}