Smith 4/27/01 1Inter-task Communication04/27/01 Lecture # 29 16.070• Task state diagram (single processor)• Intertask Communication– Global variables– Buffering data– Critical regions• Synchronization– Semaphores– Mailboxes and Queues– Deadlock• Readings: Chapter 7 in LaplanteSmith 4/27/01 2Task state diagramA process goes through severalstates during its life in a multitaskingsystem.READYBlocked(waiting for I/Oor other resource)RunningReady QueueWait Queue(This is an interrupt, too. The CPU must stop what it’sdoing and mark the blocked task as “ready”)Tasks are movedfrom one state toanother inresponse to thestimuli marked onthe arrows.Smith 4/27/01 3State Diagram description• Any tasks that are ready to run sit on the ready queue.This queue may be prioritized so the most important taskruns next.• When the scheduler decides the current task has hadenough time on the CPU, either because it finished or itstime slice is up, the “Running” task is moved to the“Ready” queue. Then the first task on the “Ready” queueis selected for “Running”.• If the “Running” task needs I/O or needs a resource that iscurrently unavailable, it is put on the “Blocked” queue.When its resource becomes available, it goes back to“Ready”.Smith 4/27/01 4Tasks don’t work in isolation from each other. Theyoften need to share data or modify it in seriesGPStranslationInertial NavinterpreterInstrumentInterfacesPositionDataNavigationPackageDisplaySubsystemSmith 4/27/01 5Inter-task communication examples• Since only one task can be running at one time (rememberthe book analogy), there must be mechanisms for tasks tocommunicate with one another– A task is reading data from a sensor at 15 hz. It stores 1024 bytesof data and then needs to signal a processing task to take andprocess the data so it has room to write more.– A task is determining the state of a system- i.e. Normal Mode,Urgent Mode, Sleeping, Disabled. It needs to inform all othertasks in the system of a change in status.– A user is communicating to another user across a network. Thenetwork receive task has to deliver messages to the terminalprogram, and the terminal program has to deliver messages to thenetwork transmit task.Smith 4/27/01 6Inter-task Communication• Regular operating systems have many options for passingmessages between processes, but most involve significantoverhead and aren’t deterministic.– Pipes, message queues, semaphores, Remote Procedure Calls,Sockets, Datagrams, etc.• In a RTOS, tasks generally have direct access to a commonmemory space, and the fastest way to share data is bysharing memory.– In ordinary OS’s, tasks are usually prevented from accessinganother task’s memory, and for good reason.Smith 4/27/01 7Global Variables:an example in pseudocodeint finished = 0;main(){ spawn( task1 ); spawn( task2 ); spawn( task3 ); while( finished !=3) { ; } printf(“ done “);}void task1 (void){ compute_pi_to_a zillion_places(); finished++;}void task2 (void){ solve_world_hunger(); finished++;}void task3 (void){find_out_why_white_shirts_give_you_black_belly_button_lint(); finished++;}Smith 4/27/01 8Mailboxes• Post() - write operation- puts data in mailbox• Pend() - read operation- gets data from mailbox• Just like using a buffer or shared memory, except:– If no data is available, pend() task is suspended– Mutual exclusion built in: if somebody is posting, pend() has to wait.• No processor time is wasted on polling themailbox, to see if anything is there yet.• Pend might have a timeout, just in caseSmith 4/27/01 9Buffering Data• If you have a producer and a consumer that work atdifferent rates, a buffer can keep things running smoothly– As long as buffer isn’t full, producer can write– As long as buffer isn’t empty, consumer can readProducerConsumerSmith 4/27/01 10Shared Memory and Data CorruptionLet’s look at a navigation system:• We use a laser-based rangefinder to get altitude readings asavailable (approx. once every 5 seconds).• We add a redundant system, an inertial navigation system, toupdate the altitude once a second:Write()Write()•Shared memory can be as simple as a global variable in a Cprogram, or an OS-supplied block of common memory.•In a single-task program, you know only one function will tryto access the variable at a time.Smith 4/27/01 112 tasks sharing the same dataAltitudeLaser InputINS Input2890 m384860708090-10m-10m-10m-10m-10m-10m48 m23 mSmith 4/27/01 12Shared memory conflict:• The INS executesseveral instructionswhile updating thealtitude:– Get stored altitude– Subtract _ altitude– Replace altitude withresult• One task mayinterrupt another atan arbitrary (possiblyBad™) point.50m50m40m40m40m Laser Task Get alt. from sensor Store alt. in memory42m42m42mINS TaskRetrieve altitudeSubtract _ fromaltitude.Replace altitudeAltitude:Altitude:Altitude:Smith 4/27/01 13Timing Problem:AltitudeLaser InputINS Input0102030405060-10m-10m-10m-10m-10m-10m 26 m43 m9 m60 mSmith 4/27/01 14Avoiding Conflict We need to be careful inmulti-tasked systems,especially when modifyingshared data. We want to make sure that incertain critical sections of thecode, no two processes haveaccess to data at the sametime.Smith 4/27/01 15Mutual Exclusion• If we set a flag (memory is busy, please hold), wecan run into the same problem as the previousexample:Flag set?Flag set?Set flagFlag set?Set flagFlag set?Set flagWrite tomemoryUnset FlagWrite tomemorySmith 4/27/01 16Atomic Operations• An operating system that supports multiple taskswill also support atomic semaphores.• The names of the functions that implementsemaphores vary from system to system (test-set/release; lock/unlock; wait/signal; P()/V() )• The idea: You check a “lock” before entering acritical section. If it’s set, you wait. If it isn’t, yougo through the lock and unset it on your way out.• The word atomic means checking the lock andsetting it only takes one operation- it can’t beinterrupted.Smith 4/27/01 17Semaphore ExampleTelescopeImageUpdate(){ if( time_is_now() ) { lock( image_map ); … update( curr_image[] ); unlock( image_map ); …}ImageTransmit(){ … if( command == XMIT ) { lock( transmitter ); lock( image_map ); … broadcast( curr_image[] ); unlock( image_map ); unlock( transmitter ); } …}Smith 4/27/01 18Deadlock!ImageTransmit(){ … if( command == XMIT