ECE/CS 5780/6780: Embedded System DesignScott R. LittleLecture 12: SemaphoresScott R. Little (Semaphores) ECE/CS 5780/6780 1 / 29Introduction to SemaphoresSemaphores used to implement synchronization, sharing, andcommunication between threads.A semaphore is a counter with two operations:P or waitV or signalA meaning is assigned to each counter value.In a binary semaphore, 1 means free and 0 means busy.Scott R. Little (Semaphores) ECE/CS 5780/6780 2 / 29Spin-Lock SemaphoreScott R. Little (Semaphores) ECE/CS 5780/6780 3 / 29Spin-Lock Counting Semaphore// decrement and spin if less than 0// input: pointer to a semaphore// output: nonevoid OS_Wait(short *semaPt){asm sei // Test and set is atomicwhile(*semaPt <= 0){ // disabledasm cli // disabledasm nop // enabledasm sei // enabled}(*semaPt)--; // disabledasm cli // disabled} // enabledScott R. Little (Semaphores) ECE/CS 5780/6780 4 / 29Spin-Lock Counting Semaphore (cont)// increment semaphore// input: pointer to a semaphore// output: nonevoid OS_Signal(short *semaPt){unsigned char SaveCCR;asm tpaasm staa SaveCCR // save previousasm sei // make atomic(*semaPt)++;asm ldaa SaveCCR // recall previousasm tap // end critical}Scott R. Little (Semaphores) ECE/CS 5780/6780 5 / 29Spin-Lock Binary Semaphorevoid bWait(char *semaphore){asm clra // new value for semaphoreasm loop: minm [2,x] // test and set (ICC12 version 5)asm bcc loop}void bSignal(char *semaphore){(*semaphore) = 1; // compiler makes this atomic}Scott R. Little (Semaphores) ECE/CS 5780/6780 6 / 29Counting Semaphorestruct 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;}Scott R. Little (Semaphores) ECE/CS 5780/6780 7 / 29Counting 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}Scott R. Little (Semaphores) ECE/CS 5780/6780 8 / 29Counting 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}Scott R. Little (Semaphores) ECE/CS 5780/6780 9 / 29Blocking SemaphoreScott R. Little (Semaphores) ECE/CS 5780/6780 10 / 29Blocking SemaphoreInitialize:1Set the counter to its initial value.2Clear associated blocked tcb linked list.Wait:1Disable interrupts to make atomic2Decrement the semaphore counter, S=S-13If semaphore counter < 0, then block this thread.4Restore interrupt status.Signal:1Disable interrupts to make atomic2Increment the semaphore counter, S=S+13If counter ≤ 0, wakeup one thread.4Restore interrupt statusScott R. Little (Semaphores) ECE/CS 5780/6780 11 / 29Assembly 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 IrtsScott R. Little (Semaphores) ECE/CS 5780/6780 12 / 29Assembly 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 runScott R. Little (Semaphores) ECE/CS 5780/6780 13 / 29Assembly 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 C5FrtiScott R. Little (Semaphores) ECE/CS 5780/6780 14 / 29Linked ListsScott R. Little (Semaphores) ECE/CS 5780/6780 15 / 29Thread Synchronization or RendezvousSynchronize 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);Scott R. Little (Semaphores) ECE/CS 5780/6780 16 / 29Resource Sharing or Nonreentrant Co deGuarantee mutual exclusive access to a critical section.Thead 1 Thread 2 Thread 3bwait(&S); bwait(&S); bwait(&S);printf("bye"); printf("tchau"); printf("ciao");bsignal(&S); bsignal(&S); bsignal(&S);Scott R. Little (Semaphores) ECE/CS 5780/6780 17 / 29Thread Communication Between Two ThreadsThread 1 sends 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 pro du cer is waitingProducer thread Consumer threadMail=4; wait(&send);signal(&send); read(Mail);wait(&ack); signal(&ack);Scott R. Little (Semaphores) ECE/CS 5780/6780 18 / 29Thread Communication Between Many ThreadsIn the bounded buffer problem, many threads put data into andtake out of a finite-size FIFO.PutFifo GetFifowait(&RoomLeft); wait(&CurrentSize);wait(&mutex); wait(&mutex);put data in FIFO remove data from FIFOsignal(&mutex); signal(&mutex);signal(&CurrentSize); signal(&RoomLeft);Could disable interrupts instead of using mutex, but would lockout threads that don’t affect the FIFO.Scott R. Little (Semaphores) ECE/CS 5780/6780 19 / 29Fixed SchedulingThread sequence and allocated time-slices determi ned a priori.To create a fixed schedule, we need to:1Assign a priority to each task.2Define the resources required for each task.3Determine how often each task must run.4Estimate how long each task will require to complete.Scott R. Little (Semaphores) ECE/CS 5780/6780 20 / 29Fixed Scheduling ExampleScott R. Little (Semaphores) ECE/CS
View Full Document
Unlocking...