COT 4600 Operating Systems Fall 2009Lecture 21Evolution of ideas regarding communication among threads using a bounded bufferSlide 4Slide 5Primitives for thread sequence coordinationSlide 7This solution does not workAWAIT - ADVANCE solutionThread states and state transitionsSolution for a single sender and multiple receiversSupporting multiple senders: the sequencerMultiple sender solution; only the SEND must be modifiedSlide 14Slide 15Polling and interruptsEvolution of modularity for the Intel architecture x86Slide 18The increase in the number of lines of operating systems source code (millions)Virtual machinesSlide 21Slide 22Slide 23COT 4600 Operating Systems Fall 2009Dan C. MarinescuOffice: HEC 439 BOffice hours: Tu-Th 3:00-4:00 PM22222Lecture 21Last time: Preemptive schedulingThread primitives for sequence coordinationToday:Implementation of AWAIT, ADVANCE, TICKET, and READPolling and interruptsEvolution of the Intel x86 architectureVirtual MachinesNext Time: Performance Metrics (Chapter 5)Evolution of ideas regarding communication among threads using a bounded buffer 1. Use locks  did not address the busy waiting problem2. YIELD  based on voluntary release of the processor by individual threads3. Use WAIT (for an event ) and NOTIFY (when the event occurs) primitives .4. Use AWAIT (for an event) and ADVANCE (when the event occurs)Lecture 21 3Lecture 21 5Primitives for thread sequence coordinationYIELD requires the thread to periodically check if a condition has occurred.Basic idea  use events and construct two before-or-after actionsWAIT(event_name)  issued by the thread which can continue only after the occurrence of the event event_name.NOTIFY(event_name)  search the thread_table to find a thread waiting for the occurrence of the event event_name. Lecture 21 6This solution does not workLecture 21 8The NOTIFY should always be sent after the WAIT. If the sender and the receiver run on two different processor there could be a race condition for the notempty event. The NOTIFY could be sent before the WAIT.Tension between modularity and locksSeveral possible solutions: AWAIT/ADVANCE, semaphores, etcAWAIT - ADVANCE solutionA new state, WAITING and two before-or-after actions that take a RUNNING thread into the WAITING state and back to RUNNABLE state.eventcount  variables with an integer value shared between threads and the thread manager; they are like events but have a value. A thread in the WAITING state waits for a particular value of the eventcount AWAIT(eventcount,value)If eventcount >value  the control is returned to the thread calling AWAIT and this thread will continue executionIf eventcount ≤value  the state of the thread calling AWAIT is changed to WAITING and the thread is suspended.ADVANCE(eventcount) increments the eventcount by one then searches the thread_table for threads waiting for this eventcountif it finds a thread and the eventcount exceeds the value the thread is waiting for then the state of the thread is changed to RUNNABLELecture 21 9Thread states and state transitionsLecture 20 10Solution for a single sender and multiple receiversLecture 20 11Supporting multiple senders: the sequencerSequencer shared variable supporting thread sequence coordination -it allows threads to be ordered and is manipulated using two before-or-after actions.TICKET(sequencer)  returns a negative value which increases by one at each call. Two concurrent threads calling TICKET on the same sequencer will receive different values based upon the timing of the call, the one calling first will receive a smaller value.READ(sequencer)  returns the current value of the sequencer Lecture 20 12Multiple sender solution; only the SEND must be modifiedLecture 21 13Polling and interruptsPolling  periodically checking the status of a subsystem.How often should the polling be done? Too frequently  large overheadAfter a large time interval  the system will appear non-responsive Interrupts could be implemented in hardware as polling  before executing the next instruction the processor checks an “interrupt” bit implemented as a flip-flopIf the bit is ON invoke the interrupt handler instead of executing the next instructionMultiple types of interrupts  multiple “interrupts” bits checked based upon the priority of the interrupt. Some architectures allow the interrupts to occur durin the execution of an instructionThe interrupt handler should be short and very carefully written. Interrupts of lower priority could be masked.Evolution of modularity for the Intel architecture x86The address space size determined by the number of address bits: 24 for 80286 a 16 bit processor  modularity enforced through segmentation 32 for 80386 a 32 bit processor  each segment could have up to 232 byteswithin each segment support for virtual memoryBackward compatibility0102030405060The increase in the number of lines of operating systems source code (millions)Virtual machinesFirst commercial product IBM VM 370 originally developed as CP-67Advantages:One could run multiple guest operating systems on the same machineAn error in one guest operating system does not bring the machine downAn ideal environment for developing operating systemsLecture 21