04-The OS Kernel

1 .Operating Systems 1 4. The OS Kernel 4.1 Kernel Definitions and Objects 4.2 Queue Structures 4.3 Threads 4.4 Implementing Processes and Threads Process and Thread Descriptors Implementing the Operations 4.5 Implementing Synchronization and Communication Mechanisms Requesting and Releasing Resources Semaphores and Locks Building Monitor Primitives Clock and Time Management Communications Kernel 4.6 Interrupt Handling

2 .CompSci 143A 2 The OS Kernel OS Kernel : basic set of objects, processes, primitives Rest of OS is built on top of kernel Kernel provides mechanisms to implement different policies

3 .Operating Systems 3 Processes and threads Process has one or more threads Each thread has its own : CPU state (registers, PC) Stack All threads in a process share : Memory space Other resources Threads are efficient , but lack protection from each other Processes/threads run concurrently

4 .Operating Systems 4 The Ready List (RL ) Each process is represented by a PCB PCBs reside on different lists : waiting list, ready list Example: priority queue:

5 .Operating Systems 5 Process S tatus Process is a “living” entity: Alternates between states: Running / Ready / Blocked Running : process is currently running on a CPU Ready : process is ready to run, waiting for a CPU Blocked : process is waiting for some resource (lock, file, semaphore, message, …) Each state can be Active or Suspended (sub-state) Suspended : process cannot run (similar to blocked) but: Not waiting for any resource Suspended explicitly by another process (e.g. to examine or modify its state, prevent deadlock, detect runaway process, swap process out of memory, …)

6 .Operating Systems 6 The State Transition Diagram

7 .Operating Systems 7 The Process Control Block (PCB ) ID CPU_State : registers, flags Proc_ID : for multiprocessors Memory: addresses, page table Open_Files Other_Resources Stat type: running, ready, blocked (suspended) Stat list: pointer to RL or wait list Parent/Child: creation hierarchy Priority

8 .Operating Systems 8 Process Operations: Create Create(s0, m0, pi) { 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); Scheduler(); }

9 .Operating Systems 9 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(); } }

10 .Operating Systems 10 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 ’; }

11 .Operating Systems 11 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); }

12 .Operating Systems 12 Resource Management Request(res) { if (Free(res)) Allocate(res, self) else { Block(self, res); Scheduler(); } } Release(res) { Deallocate (res, self); if ( Proc_Blocked_on ( res,pr )) { Allocate(res, pr ); Unblock( pr , res); Scheduler(); } } Resources : semaphores, monitors, messages, time, files, devices, etc. Generic code to request/release resource Instantiated for each type of resource Example: if resource is a semaphore t hen request/release is P/V

13 .Operating Systems 13 Implementing semaphores Each semaphore operation, P/V, must be atomic (CS) Use special hardware instruction: test_and_set First implementing binary semaphores using test_and_set Then implement general semaphores using binary semaphores and busy waiting Finally, avoid busy wait using process blocking

14 .Operating Systems 14 Test_and_Set Instruction Special hardware instruction: TS(R,X) R is a register (private) , X is a variable (shared) S emantics: R = X; X = 0; Explanation: Always set variable X = 0 Register R indicates whether X changed: R=1 if X changed ( 1 0 ) R=0 if X did not change ( 0 0 ) TS is a machine instruction, i.e. indivisible (atomic) If multiple processes execute TS and X=1 , only one will reset it , the other sees no change

15 .Operating Systems 15 Binary Semaphores t est_and_set can implement binary semaphores, sb : Has only two values, 0 or 1 Two atomic operations: Pb ( sb ): if ( sb ==1) sb =0; else wait until sb becomes 1 Vb ( sb ): sb =1; Implementation using TS instruction: Pb ( sb ): do (TS( R,sb )) while (!R); /*wait loop*/ Vb ( sb ): sb =1; Also known as a spin lock (“Spinning” = “Busy Waiting”)

16 .Operating Systems 16 Binary Semaphores test_and_set is crucial for the implementation Compare : Pb ( sb ): do (TS( R,sb )) while (!R); /*wait loop*/ Pb ( sb ): while ( sb ==0) ; /*do nothing -- wait loop*/ sb = 0; Both are testing sb for 0 Why is second implementation NOT sufficient?

17 .Operating Systems 17 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 ; } Pb ( delay_s ) implements the actual waiting (busy wait!) mutex_s protects access to s (critical section) Inhibit_interrupt prevents deadlock Assume a process is in P or V Context switch wakes up higher-priority process that tries to execute P or V mutex_s is still needed on multiprocessor Note : s can become negative Serves as a counter of waiting processes

18 .Operating Systems 18 General Semaphores w/out 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 ; } } Ls is a blocked list for semaphore s V(s) { Inhibit_Interrupts ; Pb ( mutex_s ); s = s+1; if (s <= 0) { Unblock( q,Ls ); Vb ( mutes_s ); Enable_Interrupts ; Scheduler(); } else { Vb ( mutex_s ); Enable_Interrupts ; } } Block/Unblock only change data structures Scheduler performs context switch

19 .Operating Systems 19 Implementing Monitors Compiler need to insert code to: Guarantee mutual exclusion of procedures (entering/leaving) Implement c.wait Implement c.signal Use 3 types of semaphores: mutex : for mutual exclusion condsem_c : for blocking on each condition c urgent : for blocking process after signal , to implement special high-priority queue

20 .Operating Systems 20 Implementing Monitor Primitives Code for each procedure : P( mutex ); [ procedure_body ;] if ( urgentcnt > 0) V(urgent); else V( mutex ); Code for c.wait : condcnt_c = condcnt_c + 1; if ( urgentcnt > 0) V(urgent); else V( mutex ); P( condsem_c ); condcnt_c = condcnt_c - 1; Code for c.signal : if ( condcnt_c ) { urgentcnt = urgentcnt +1; V( condsem_c ); P(urgent); urgentcnt = urgentcnt –1; }