4.

The OS Kernel

Fundamentals of Modern Operating Systems

Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes and weigh only 1.5 tons. Popular Mechanics, 1949

Fundamentals of Modern Operating Systems

Overview
4.1 Kernel Denitions and Objects 4.2 Queue Structures 4.3 Threads 4.4 Implementing Processes and Threads
Process and Thread Descriptors Implementing the Operations

Fundamentals of Modern Operating Systems

Overview
4.5 Implementing Synchronization and Communication Mechanisms
Semaphores and Locks Building Monitor Primitives Clock and Time Management Communications Kernel

4.6 Interrupt Handling

Fundamentals of Modern Operating Systems 4

Kernel Definitions and Objects

Basic set of objects, primitives, data structures, processes Rest of OS is built on top of kernel Kernel denes/provides mechanisms to implement various policies
process and thread management interrupt and trap handling resource management input/output
5

Fundamentals of Modern Operating Systems

Queues
OS needs many different queues Single-level queues
implemented as array
xed size efcient for simple FIFO operations unbounded size more overhead, but more exible operations

implemented as linked list

Priority queues
implemented as array of linked lists
Fundamentals of Modern Operating Systems 6

FIFO Queues

Figure 4-2
Fundamentals of Modern Operating Systems 7

Priority Queues

Figure 4-3(a)
Fundamentals of Modern Operating Systems 8

Priority Queues

Figure 4-3(b)
Fundamentals of Modern Operating Systems 9

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

Implemented in user space or kernel space Threads are efcient, but lack protection from each other
Fundamentals of Modern Operating Systems

Figure 4-4
10

Implementing Processes/Threads
Process Control Block (PCB)
State Vector = Information necessary to run process p Status
basic types:
Running, Ready, Blocked

additional types:

Ready_active, Ready_suspended Blocked_active, Blocked_suspended

Fundamentals of Modern Operating Systems

Figure 4-5

11

Process and Thread States

State Transition Diagram

Figure 4-6
Fundamentals of Modern Operating Systems 12

Process Operations: Create

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; PCB p->Creation_Tree.Child = NULL; insert(self-> Creation_Tree.Child, p); insert(RL, p); Scheduler(); }
Fundamentals of Modern Operating Systems 13

Process Operations: 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(); } }
Fundamentals of Modern Operating Systems 14

Process Operations: 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; }

Fundamentals of Modern Operating Systems

15

Process Operations: Destroy

Destroy(pid) { p = Get_PCB(pid); Kill_Tree(p); Scheduler(); } 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); }
Fundamentals of Modern Operating Systems 16

Synchronization/Communication
Semaphores, locks, monitors, etc. are resources
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(); } }
Fundamentals of Modern Operating Systems 17

Semaphores/Locks
Need special test_and_set instruction: TS(R,X) Behavior: R = X; X = 0;

always set variable X=0 register R indicates change:

R=1 if X changed (10) R=0 if X did not change (00) TS is indivisible (atomic) operation
Fundamentals of Modern Operating Systems 18

Spin/Spinning Locks
Binary semaphore sb (only 0 or 1) Behavior of Pb/Vb:
if (sb==1) sb=0; else wait sb=1; Indivisible implementation of Pb/Vb: Pb(sb): do (TS(R,sb)) while (!R);/*wait loop*/ Vb(sb): sb=1; Pb(sb): Vb(sb):

Note: sb is shared, but each process has its own

R

Spinning = Busy Waiting

Fundamentals of Modern Operating Systems 19

GeneralSemaphoresw/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; }

Inhibiting interrupts prevents deadlock due to context switching mutex_s needed to implement critical section with multiple
CPUs
Fundamentals of Modern Operating Systems 20

Avoiding the Busy-Wait

P(s) { Inhibit_Interrupts; Pb(mutex_s); s = s-1; if (s < 0) { /*Context Switch*/ Block(self, Ls); Vb(mutex_s); Enable_Interrupts; Scheduler(); } else { Vb(mutex_s); Enable_Interrupts; } }
Fundamentals of Modern Operating Systems

V(s) { Inhibit_Interrupts; Pb(mutex_s); s = s+1; if (s <= 0) { Unblock(q, Ls); Vb(mutex_s); Scheduler(); } else { Vb(mutex_s); Enable_Interrupts; } }

21

Implementing Monitors
Need to insert code to:
guarantee mutual exclusion of procedures (entering/ leaving) implement c.wait implement c.signal

Implement 3 types of semaphores:

1. mutex: 2. 3.

for mutual exclusion condsem_c: for blocking on each condition c urgent: for blocking process after signal
22

Fundamentals of Modern Operating Systems

Monitor Primitives

Each procedure guarded by mutex Semaphore

P(mutex); procedure_body; if (urgentcnt) V(urgent); else V(mutex);

Fundamentals of Modern Operating Systems

23

Monitor Primitives
c.wait:
condcnt_c = condcnt_c + 1; if (urgentcnt) V(urgent); else V(mutex); P(condsem_c); condcnt_c = condcnt_c - 1;

c.signal:
if (condcnt_c) { urgentcnt = urgentcnt + 1; V(condsem_c); P(urgent); urgentcnt = urgentcnt - 1; }
Fundamentals of Modern Operating Systems 24

Clock and Time Management 1

Most systems provide hardware
ticker: issues periodic interrupt countdown timer: issues interrupt after a set number of ticks

Build higher-level services with this hardware Wall clock timers

typical functions:
Update_Clock : increment tnow Get_Time : return current time Set_Time(tnew) : set time to tnew

must maintain monotonicity

Fundamentals of Modern Operating Systems 25

Clock and Time Management 2

Countdown timers
main use: as alarm clocks typical function:
Delay(tdel) block process for tdel time units
Delay(tdel) { Set_Timer(tdel); P(delsem); } Timeout() { V(delsem); }
Fundamentals of Modern Operating Systems

implementation using hardware countdown:

/*set hardware timer*/ /*wait for interrupt*/ /*called at interrupt*/

26

Clock and Time Management 3

Implement multiple logical countdown timers using a single hardware timer Functions
tn = Create_LTimer() create new timer Destroy_LTimer(tn) Set_LTimer(tn,tdel) block process and call Timeout() at interrupt

Fundamentals of Modern Operating Systems

27

Clock and Time Management 4

Implement Set_LTimer() using Absolute Wakeup Times
priority queue TQ records wakeup times function of Set_LTimer(tn,tdel)
compute absolute time of tdel (using wall-clock) insert new request into TQ (according to time) if new request is earlier than previous head of queue, set hardware countdown to tdel
28

Fundamentals of Modern Operating Systems

Clock and Time Management 5

Absolute Wakeup Times Example: Set_LTimer(tn,35)

Figure 4-8
Fundamentals of Modern Operating Systems 29

Clock and Time Management 6

Implement Set_LTimer() using Time Differences
priority queue TQ records only time increments, no wall-clock is needed function of Set_LTimer(tn,tdel)
nd the two elements L and R between which tdel is to be inserted (add differences until tdel is reached) split the current difference between L and R into difference between L and new element and difference between new element and R
Fundamentals of Modern Operating Systems 30

Clock and Time Management 7

Time Differences Example: Set_LTimer(tn,35)

X
Figure 4-9
Fundamentals of Modern Operating Systems 31

Communication Primitives
Message Passing as basic form of communication between processes/threads
most natural with processes executing in separate address spaces or machines heavily used in distributed, cluster computing environment (MPI library)

Two generic basic operations:

send(p, m) send message m to process p receive(q, m) receive a message m from process q either can be blocking or non-blocking or (non-)selective (specify process explicitly)
32

Fundamentals of Modern Operating Systems

SM-Message Passing

1
Figure 4-10a

In a shared-memory system:
send and receive each use a buffer to hold message
in the user-space of sender/receiver
33 Fundamentals of Modern Operating Systems

SM-Message Passing
System copies message from sbuf to rbuf upon a send call Important issues:

1. How does sender know that sbuf may be reused (overwritten)? 2. How does system know that rbuf may be reused (overwritten)?

Possible solutions include blocking the sender/receiver

completely synchronous if both
Fundamentals of Modern Operating Systems 34

SM-Message Passing
Reusing sbuf:
use blocking send:
reuse as soon as send returns sender blocked even if sbuf not reused! sender needs to poll ag!

provide a ag (or interrupt) to indicate release of sbuf

Reusing rbuf:
provide a ag to system to indicate release of rbuf
receiver must explicitly set ag and system must test repeatedly!
35

Solutions are awkward

Fundamentals of Modern Operating Systems

SB-Message Passing

1
Figure 4-10b

Better solution: use pool of system buffers

send and receive each use intermediate system buffer(s) to hold message(s)
system simply copies messages from/to user buffers sbuf/rbuf to/from system buffers
36

Fundamentals of Modern Operating Systems

SB-Message Passing
Send copies sbuf to a system buffer
sender is free immediately after copy is mode
non-blocking with large pool of buffers

sender may continue generating messages

until no more system buffers are available (block!)

selective sends include send/recv process IDs

System copies (or reallocates) full buffers to receiver

asynchronous
Fundamentals of Modern Operating Systems 37

SB-Message Passing
Receive copies a system buffer to rbuf
frees consumed system buffer receiver decides when to reuse rbuf for next message

Blocking if no more system buffers with messages are available

non-blocking: returns corresponding error condition
Fundamentals of Modern Operating Systems 38

Networked Message Passing

Figure 4-10c

Use of system buffers important in distributed systems

no shared memory between CPUs large delays in message transmissions extra processing:
packeting, routing, error handling etc.
39 Fundamentals of Modern Operating Systems

Interrupts
Unpredictable event that forces transfer of control from running process
abstraction and handling of asynchronous events external: generated by hardware (asynchronous) I/O completion or GUI handling internal: consequence of current computation (synchronous)
exceptional (error) conditions (also called exceptions or traps)
40

Fundamentals of Modern Operating Systems

Interrupt Handling

Example: external hardware device accessed by process p via procedure Fn

Fn initiates device and returns results to caller
blocks itself to await completion of device

OS schedules other processes while device busy upon termination of device an interrupt is generated
Fn has to be unblocked and completed

Fundamentals of Modern Operating Systems

41

Interrupt Handling
Figure 4-11a

Standard interrupt-handling sequence:

1. 2. 3. 4.

save state of interrupted process/thread (q) identify interrupt type and invoke IH IH services interrupt restore state of interrupted process (q or of another one p waiting for that interrupt)
42

Fundamentals of Modern Operating Systems

Interrupt Handling
Main challenges:
Fn must be able to block itself on a given event

lowest-level device functions Fn generally provided by OS

IH must be able to unblock p and to return from interrupt

unblock and make process ready to run which was waiting for the device IH is generally provided by OS

Abstract Fn and IH more from application

Fundamentals of Modern Operating Systems 43

Interrupt Handling
View hardware device as a process:
implement Fn and IH as monitor functions
Fn waits on c
after initializing device

IH invoked by hardware process

IH signals c

condition c is associated with device

Figure 4-11b
44

Fundamentals of Modern Operating Systems

Fundamentals of Modern Operating Systems

45