Kernel Implementations of Processes and Synchronizing Primitives

Andrews Chapter 6

· Kernel: It’s role is to provide a virtual processor to each process. Each process should have the illusion that it has its own real processor.

· Need the following mechanisms in the kernel to implement parallelism

o Create process

o Start process

o Stop process

o Destroy process

o Join process

· All the runnable software on a computer, including the OS, is organized into a number of sequential processes (or processes in short)

o Process: a unit of work scheduled by OS, consisting of

o program's data and stack (and the memory areas)

o program counter, stack pointer, and other CPU registers

o all other information necessary to run the program:

§ process id, priority, accounting information,
memory information, open files, process state, etc.

o executable code (and the memory area)

· Kernel contains

o Data structures to represent processes

§ Process Control Blocks (PCBs)

o Routines for handling interrupts, the primitives for handling processes, and a dispatcher

· Process states (from Dr. Singh’s slides)

o New – process is being created.

o Running – instructions are being executed.

o Waiting – blocked waiting for an external event to occur; e.g., message arrival.

o Ready – ready to run on a processor.

o Terminated – finished, awaiting garbage collection.

· Process switches resulting from interrupt or primitive kernel call (from Dr. Singh’s slides)

· A Monolithic Single Processor Kernel Architecture

o Each primitive executes as an atomic region

o PCB holds information for idle processes

o Kernel starts executing when an interrupt arrives

§ each interrupt has a unique interrupt handler

§ internal interrupt is called SVC (supervisor call)

§ context switching

· on interrupt, the processor saves executing process state in its PCB

· then it calls dispatcher to find a “ready” PCB and then loads its state onto the processor

· Representing Processes

o processType processDescriptor[maxProcs];

o Lists for holding PCBs

§ Free list of empty PCBs

§ Ready list of PCBs

Outline of a Single Processor Kernel

processType PCB[maxProcs];

int executing = 0; /*index of the executing process*/

declaration of variables for free, ready, and waiting lists ;

SVC_Handler; { /* entered with interrupts inhibited*/

save state of executing process in PCB;

determine which primitive was invoked, and call it;

}

Timer_Handler: { /*entered with disabled interrupts*/

Insert PCB of executing process at the end of the ready list;

Set executing =0;

dispatcher();

}

procedure fork(initial process state){

remove a PCB from the free list and initialize it;

insert the PCB on the end of the ready list;

dispatcher();

}

procedure quit() {

record that executing has quit;

insert PCB of executing process at end of free list;

executing = 0;

if (parent process is waiting for this child) {

remove parent PCB from the waiting list;

put parent PCB on ready list; }

dispatcher();

procedure join(name of child process) {

if (child has not yet quit) {

put the PCB of the executing process on the waiting list;

executing = 0;

}

dispatcher();

}

Procedure dispatcher() {

If (executing==0) {/*current process blocked or quit*/

remove PCB from front of ready list;

set executing to point to it;

}

start the interval timer;

load state of executing; /*with interrupts enabled*/

}

Outline of a multiprocessor kernel

· Extending the single processor kernel

o Store kernel procedures and data structures in shared memory

o Provide mutual exclusive access to these data structures to avoid interference between the multiple processes operating within the kernel

o Change the dispatcher routine to exploit multiple processors

· On interrupt, the interrupts (on the processor that is interrupted) must be disabled

· Critical data structures that need “mutex” access

o Free, ready, and waiting lists

· Traps are handled by the processor on which they occur

o Interrupt handlers work as in the single processor but

o executing needs to be an array and

o timer-handler needs to lock and unlock the ready list

· Changes to the dispatcher()

o Some processors may be idle and we can handle this in a couple of ways:

§ Execute an idle process which periodically checks ready list (most efficient)

§ each processor can have its own dispatcher and continuously attempts to assign ready processors to the idle processes

· Idle process

process Idle {

while (executing[i] == the Idle process){

while(ready list empty) delay;

lock ready list;

if (ready list not empty) {

remove PCB from front of ready list;

set executing[i] to ready PCB;

}

unlock ready list;

}

Start the interval timer on processor i;

Load state of executing[i]; /* with interrupts enabled*/

}

· Outline of a kernel for a shared-memory multiprocessor

processType PCB[maxProcs];

int executing[maxProcs]; /*one entry per processor*/

declarations of free, ready, and waiting lists and their locks;

SVC_Handler: {

/*entered with interrupts disabled on processor i*/

Save state of executing[i];

Determine which primitive was invoked and call it;

}

Timer_Handler: {

/*entered with interrupts disabled on processor i*/

Lock ready list; insert executing[i] at end; unlock ready list;

executing[i] = 0;

dispatcher();

}

procedure fork(initial process state) {

lock free list; remove a PCB; unlock free list;

initialize the PCB;

lock ready list; insert PCB at end of ready list; unlock ready list;

dispatcher();

}

procedure quit() {

lock free list; insert executing[i] at end; unlock free list;

record that executing[i] has quite; executing[i]=0;

if (parent process is waiting) {

lock waiting list; remove parent from that list; unlock waiting list;

lock ready list; put parent on ready list; unlock ready list;

}

dispatcher();

}

procedure join(name of child process) {

if (child has already quit) return;

lock waiting list; put executing[i] on the waiting list; unlock waiting list;

}

dispatcher();

}

procedure dispatcher() {

if (executing[i]=0){

lock ready list;

if (ready list not empty) {

remove PCB from ready list;

set executing[i] to point to PCB;

}

else /* ready list is empty*/

set executing[i] to point to the IDLE process;

unlock ready list;

}

if (executing[i] is not the IDLE process) {

start timer on processor i;

load state of executing[i]; /*interrupts enabled*/

}