CS162Operating Systems andSystems ProgrammingLecture 5Cooperating ThreadsSeptember 15, 2008Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 5.29/15/07 Kubiatowicz CS162 ©UCB Fall 2008Review: Per Thread State• Each Thread has a Thread Control Block (TCB)– Execution State: CPU registers, program counter, pointer to stack– Scheduling info: State (more later), priority, CPU time– Accounting Info– Various Pointers (for implementing scheduling queues)– Pointer to enclosing process? (PCB)?– Etc (add stuff as you find a need)• OS Keeps track of TCBs in protected memory– In Arrays, or Linked Lists, or …OtherStateTCB9LinkRegistersOtherStateTCB6LinkRegistersOtherStateTCB16LinkRegistersHeadTailReadyQueueLec 5.39/15/07 Kubiatowicz CS162 ©UCB Fall 2008Review: Yielding through Internal Events• Blocking on I/O– The act of requesting I/O implicitly yields the CPU• Waiting on a “signal” from other thread– Thread asks to wait and thus yields the CPU• Thread executes a yield()– Thread volunteers to give up CPUcomputePI() {while(TRUE) {ComputeNextDigit();yield();}}– Note that yield() must be called by programmer frequently enough!Lec 5.49/15/07 Kubiatowicz CS162 ©UCB Fall 2008Review: Stack for Yielding Thread• How do we run a new thread?run_new_thread() {newThread = PickNewThread();switch(curThread, newThread);ThreadHouseKeeping(); /* Later in lecture */}• How does dispatcher switch to a new thread?– Save anything next thread may trash: PC, regs, stack– Maintain isolation for each threadyieldComputePIStack growthrun_new_threadkernel_yieldTrap to OSswitchLec 5.59/15/07 Kubiatowicz CS162 ©UCB Fall 2008Review: Two Thread Yield Example• Consider the following code blocks:proc A() {B();}proc B() {while(TRUE) {yield();}}• Suppose we have 2 threads:– Threads S and TThread SStack growthAB(while)yieldrun_new_threadswitchThread TAB(while)yieldrun_new_threadswitchLec 5.69/15/07 Kubiatowicz CS162 ©UCB Fall 2008Goals for Today• More on Interrupts• Thread Creation/Destruction• Cooperating ThreadsNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne Note: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and Gagne. Many slides generated from my lecture notes by Kubiatowicz.Lec 5.79/15/07 Kubiatowicz CS162 ©UCB Fall 2008Interrupt Controller• Interrupts invoked with interrupt lines from devices• Interrupt controller chooses interrupt request to honor– Mask enables/disables interrupts– Priority encoder picks highest enabled interrupt – Software Interrupt Set/Cleared by Software– Interrupt identity specified with ID line• CPU can disable all interrupts with internal flag• Non-maskable interrupt line (NMI) can’t be disabledNetworkIntIDInterruptInterrupt MaskControlSoftwareInterruptNMICPUPriority EncoderTimerInt DisableLec 5.89/15/07 Kubiatowicz CS162 ©UCB Fall 2008Example: Network Interrupt• Disable/Enable All Ints ⇒ Internal CPU disable bit– RTI reenables interrupts, returns to user mode• Raise/lower priority: change interrupt mask • Software interrupts can be provided entirely in software at priority switching boundaries…add $r1,$r2,$r3subi $r4,$r1,#4slli $r4,$r4,#2PC savedDisable All IntsSupervisor ModeRestore PCUser ModeRaise priorityReenable All IntsSave registersDispatch to Handler…Transfer Network Packet from hardwareto Kernel Buffers…Restore registersClear current IntDisable All IntsRestore priorityRTI“Interrupt Handler”lw $r2,0($r4)lw $r3,4($r4)add $r2,$r2,$r3sw 8($r4),$r2…External InterruptPipeline FlushLec 5.99/15/07 Kubiatowicz CS162 ©UCB Fall 2008Review: Preemptive Multithreading• Use the timer interrupt to force scheduling decisions• Timer Interrupt routine:TimerInterrupt() {DoPeriodicHouseKeeping();run_new_thread();}• This is often called preemptive multithreading, since threads are preempted for better scheduling– Solves problem of user who doesn’t insert yield();Some Routinerun_new_threadTimerInterruptInterruptswitchStack growthLec 5.109/15/07 Kubiatowicz CS162 ©UCB Fall 2008Review: Lifecycle of a Thread (or Process)• As a thread executes, it changes state:– new: The thread is being created– ready: The thread is waiting to run– running: Instructions are being executed– waiting: Thread waiting for some event to occur– terminated: The thread has finished execution• “Active” threads are represented by their TCBs– TCBs organized into queues based on their stateLec 5.119/15/07 Kubiatowicz CS162 ©UCB Fall 2008ThreadFork(): Create a New Thread• ThreadFork() is a user-level procedure that creates a new thread and places it on ready queue– We called this CreateThread() earlier• Arguments to ThreadFork()– Pointer to application routine (fcnPtr)– Pointer to array of arguments (fcnArgPtr)– Size of stack to allocate• Implementation– Sanity Check arguments– Enter Kernel-mode and Sanity Check arguments again– Allocate new Stack and TCB– Initialize TCB and place on ready list (Runnable).Lec 5.129/15/07 Kubiatowicz CS162 ©UCB Fall 2008Group assignments are complete!• Go to “Group/Section Assignments”– Everyone should be up there.– Let Andrey (cs162-tc) know if there are problems.• Sections:Tony Huang 320 SodaW 1:00P-2:00p101Jon Whiteaker3 Evans(Big Section!)W 2:00P-3:00P 10587 Evans87 Evans320 SodaLocationAndreyErmolinskiyW 11:00P-12:00P 104AndreyErmolinskiyTu 2:00P-3:00P 103Jon WhiteakerTu 1:00P-2:00P 102TATimeSectionLec 5.139/15/07 Kubiatowicz CS162 ©UCB Fall 2008Administrivia• Information about Subversion on Handouts page– Make sure to take a look• Other things on Handouts page– Synchronization examples/Interesting papers – Previous finals/solutions• Sections in this class are mandatory– Make sure that you go to the section that you have been assigned!• Reader will be available at Copy Central on Hearst• Should be reading Nachos code by now!– Start working on the first project– Set up regular meeting times with your group– Try figure out group interaction problems early onLec 5.149/15/07 Kubiatowicz CS162 ©UCB Fall 2008How do we initialize TCB and Stack?• Initialize Register fields of TCB– Stack pointer made to point at stack– PC return address ⇒ OS (asm) routine ThreadRoot()– Two arg registers initialized to fcnPtr and fcnArgPtr• Initialize stack data?– No. Important part of stack
View Full Document
Unlocking...