CS/ECE 5780/6780:Embedded System DesignJohn RegehrLecture 12: SemaphoresTodayIThread synchronizationIWe already saw how to s ynchronize main() with interrupthandlersIToday we learn how to synchronize threads with each otherITable-driven thread schedulingSynchronization in Generalint Fifo_Put(char data){char *Ppt;// BEGIN CRITICALPpt=PutPt;*(Ppt++)=data;if (Ppt == &Fifo[FIFOSIZE]) Ppt = &Fifo[0];if (Ppt == GetPt ) {// END CRITICALreturn(0);} else {PutPt=Ppt;// END CRITICALreturn(1);}}Introduction to SemaphoresISemaphores used to implement synchronization, sharing, andcommunication between threads.IA semaphore is a counter with two operations:IP or waitIV or signalIA meaning is assigned to each c ounter value.IIn a binary semaph ore, 1 means free and 0 mean s busy.Spin-Lock SemaphoreSpin-Lock Counting Semaphore// decrement and spin if less than 0// input: pointer to a semaphore// output: nonevoid OS_Wait(short *semaPt) {unsigned char SaveSP = begin_critical();while(*semaPt <= 0) {end_critical (SaveSP);asm nopSaveSP = begin_critical();}(*semaPt)--;end_critical (SaveSP);}Spin-Lock Counting Semaphore (cont)// increment semaphore// input: pointer to a semaphore// output: nonevoid OS_Signal(short *semaPt) {unsigned char SaveSP = begin_critical();(*semaPt)++;end_critical (SaveSP);}Spin-Lock Binary Semaphorevoid bWait(char *semaphore) {asm clraasm loop: minm [2,x]asm bcc loop}void bSignal(char *semaphore) {(*semaphore) = 1; // compiler makes this atomic}Counting Semaphore from Binary Semaphoresstruct sema4{ short value; // semaphore valuechar s1; // binary semaphorechar s2; // binary semaphorechar s3; // binary semaphore};typedef struct sema4 sema4Type;typedef sema4Type * sema4Ptr;void Initialize(sema4Ptr semaphore, short initial) {semaphore->s1 = 1; // first one to bWait(s1) continuessemaphore->s2 = 0; // first one to bWait(s2) spinssemaphore->s3 = 1; // first one to bWait(s3) continuessemaphore->value=initial;}Counting Semaphore (cont)void Wait(sema4Ptr semaphore) {bWait(&semaphore->s3); // wait if other caller here firstbWait(&semaphore->s1); // mutual exclusive access to value(semaphore->value)--; // basic function of Waitif((semaphore->value)<0) {bSignal(&semaphore->s1); // end of exclusive accessbWait(&semaphore->s2); // wait for value to go above 0}elsebSignal(&semaphore->s1); // end of exclusive accessbSignal(&semaphore->s3); // let other callers in}Counting Semaphore (cont)void Signal(sema4Ptr semaphore) {bWait(&semaphore->s1); // exclusive access(semaphore->value)++; // basic function of Signalif((semaphore->value)<=0)bSignal(&semaphore->s2); // allow S2 spinner to continuebSignal(&semaphore->s1); // end of exclusive access}Blocking SemaphoreBlocking SemaphoreIInitialize:1. Set the counter to its initial value.2. Clear associated blocked tcb linked list.IWait:1. Disable interrupts to make atomic2. Decrement the semaphore counter, S=S-13. If semaphore counter < 0, then block this thread.4. Restore interrupt status.ISignal:1. Disable interrupts to make atomic2. Increment the semaphore counter, S=S+13. If counter ≤ 0, wakeup one thread.4. Restore interrupt statusAssembly to Initialize a Blocking SemaphoreS rmb 1 ;semaphore counterBlockPt rmb 2 ;Pointer to threads blocked on SInit tpapsha ;Save old value of Isei ;Make atomicldaa #1staa S ;Init semaphore valueldx #Nullstx BlockPt ;empty listpulatap ;Restore old value of IrtsAssembly to Block a Thread; To block a thread on semaphore S, execute SWISWIhan ldx RunPt ;running process "to be blocked"sts SP,x ;save Stack Pointer in its TCB; Unlink "to be blocked" thread from RunPt listldy Next,x ;find previous threadsty RunPt ;next one to runlook cpx Next,y ;search to find previousbeq foundldy Next,ybra lookfound ldd RunPt ;one after blockedstd Next,y ;link previous to next to runAssembly to Block a Thread (cont); Put "to be blocked" thread on block listldy BlockPtsty Next,x ;link "to be blocked"stx BlockPt; Launch next threadldx RunPtlds SP,x ;set SP for this new threadldd TCNT ;Next thread gets a full 10ms time sliceaddd #20000 ;interrupt after 10 msstd TC5ldaa #$20staa TFLG1 ;clear C5FrtiLinked ListsThread RendezvousISynchronize two threads at a rendezvous location.S1 S2 Meaning0 0 Neither thread at rendezvous location-1 +1 Thread 2 arrived first, waiting for thread 1+1 -1 Thread 1 arrived first, waiting for thread 2Thread 1 Thread 2signal(&S1); signal(&S2);wait(&S2); wait(&S1);Resource Sharing or Nonreentrant CodeIGuarantee mutual exclusive access to a critical section.Thread 1 Thread 2 Thread 3bwait(&S); bwait(&S); bwait(&S);printf("bye"); printf("tchau"); printf("ciao");bsignal(&S); bsignal(&S); bsignal(&S);Thread Communication Between Two ThreadsIThread 1 s end s mail to thread 2.Send Ack Meaning0 0 No mail available, consumer not waiting-1 0 No mail available, consumer is waiting+1 -1 Mail available and producer is waitingProducer thread Consumer threadMail=4; wait(&send);signal(&send); read(Mail);wait(&ack); signal(&ack);Thread Communication Between Many ThreadsIIn the bounded buffer problem, many threads put data intoand take out of a finite-size FIFO.PutFifo GetFifowait(&RoomLeft); wait(&CurrentSize);wait(&mutex); wait(&mutex);put data i n FIFO remove data from FIFOsignal(&mutex); signal(&mutex);signal(&CurrentSize); signal(&RoomLeft);ICould disable interrupts instead of using mutex, but wouldlock out threads that don’t affect the FIFO.Fixed SchedulingIThread sequence and allocated time-slices determined a priori.ITo create a fixed schedule, we need to:1. Assign a priority to each task.2. Define the resources required for each task.3. Determine how often each task must run.4. Estimate how long each task will require to complete.Fixed Scheduling ExampleFour User Threadsvoid FSM(void) {StatePtr Pt;Pt = SA; // Initial StateDDRT = 0x03; // PT1,PT0 outputs, PT3,PT2 inputsPTT = Pt->Out; // Outputfor(;;) {OS_Sleep(); // Runs every 2msPt = Pt->Next[PTT>>2]; // Next state depends on the inputPTT = Pt->Out;}} // Outputvoid PID(void) {unsigned char speed,power;PID_Init(); // Initializefor(;;) {OS_Sleep(); // Runs every 1msspeed = PID_In(); // read tachometerpower = PID_Calc(speed);PID_Out(power);}} // adjust power to motorFour User Threads (cont)void DAS(void) {unsigned char raw;DAS_Init(); // Initializefor(;;) {OS_Sleep(); // Runs every 1.5msraw = DAS_In(); // read ADCResult = DAS_Calc(raw); }}void PAN(void) {unsigned char input;PAN_Init(); // Initializefor(;;) {input = PAN_In(); // front panel inputif(input) {PAN_Out(input); //
View Full Document
Unlocking...