COT 4600 Operating Systems Fall 2009Lecture 21Evolution of ideas regarding communication among threads using a bounded buffer Primitives for thread sequence coordinationThis 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 modifiedPolling and interruptsEvolution of modularity for the Intel architecture x86The increase in the number of lines of operating systems source code (millions)Virtual machinesCOT 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 213shared structure processor_table(2)integer thread_idshared structure thread_table(7)integer topstack integer stateshared lock instance thread_table_lockprocedure GET_THREAD_ID() return processor_table(CPUID).thread_idprocedure YIELD() ACQUIRE (thread_table_lock) ENTER_PROCESSOR_LAYER(GET_THREAD_ID()) RELEASE(thread_table_lock)returnprocedure ENTER_PROCESSOR_LAYER(this_thread) thread_table(this_thread).state RUNNABLE thread_table(this_thread).topstack SP SCHEDULER()returnprocedure SCHEDULER() j _GET_THREAD_ID()do j j+1 (mod 7)while thread_table(j).state¬= RUNNABLE thread_table(j).state RUNNING processor_table(CPUID).thread_idj EXIT_PROCESSOR_LAYER(j)returnprocedure EXIT_PROCESSOR_LAYER(new) SP,-- thread_table(new).topstackreturnLecture 215Primitives 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 216This solution does not workLecture 218 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 219Thread states and state transitionsLecture 2010Solution for a single sender and multiple receiversLecture 2011Supporting multiple senders: the sequencer SequencerÆ shared variable supporting thread sequence coordination -it allows threads to be ordered and is manipulated using two before-or-afteractions. 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 2012Multiple sender solution; only the SEND must be modifiedLecture 2113structure sequencerlong integer ticketprocedure TICKET(sequence reference s) ACQUIRE (thread_table_lock) t s.ticket s.ticket s.ticket + 1 RELEASE(thread_table_lock)return tprocedure READ(eventcount reference event)ACQUIRE (thread_table_lock) e event.count RELEASE(thread_table_lock)returnPolling 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 232bytes within each segment support for virtual memoryBackward compatibility0102030405060Windows 3.1 (1992)Windows NT (1992)Solaris (1998)Windows 95Windows 98Windows NT 5.0 (1998)RedHat Linux 6.2 (2000)RedHat Linux 7.1 (2001)Windows XPVistaThe 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