Desktop version

Home arrow Computer Science arrow Real-Time and Distributed Real-Time Systems: Theory and Applications

Implicit Synchronization

Implicit synchronization is always achieved using the RTOS, and the participating processes do not need to use each other's task IDs. Figure 1.10 represents the different types of implicit synchronization mechanisms for both single processor and multiprocessor systems.

Flag Semaphores

The use of semaphores for handling shared resources in a GPOS is well known. An RTOS uses semaphores in a similar way and implements several variants to take care of specific RT requirements. As in a GPOS, a set operation sets a flag semaphore and a reset resets it. To use a shared resource, a task has to first set the semaphore. A task that tries to set a semaphore in the set state or a task that tries to reset a semaphore in the reset state gets blocked.

To understand the use of a flag semaphore, the producer-consumer system represented in Figure 1.9 is revisited and this time a flag semaphore is used to synchronize the producer and the consumer. The necessity of synchronization becomes clear if one considers a case where the producer writes multiple data elements all pertaining to a time instant on a buffer, and the consumer reads them periodically. At the kth instant, the data belonging to the (k - 1)th instant remaining in the buffer is overwritten with fresh data by

FIGURE 1.10

Implicit synchronization.

FIGURE 1.11

Synchronization using a flag semaphore.

the producer. Now, if it so happens that the producer is preempted when it has written half the data elements and the consumer starts reading before the write operation is complete, then the temporal significance of the data will not be preserved and the system may behave erroneously. A flag semaphore can be used to synchronize the producer and the consumer as shown in Figure 1.11.

The difference between the case represented in Figure 1.9 and the one represented in Figure 1.11 is that in the former case task T2 succeeds task T1 and in the latter case task T2 is dependent on task T1. Thus, in this case, the tasks T1 and T2 may have asynchronous timelines with one task blocking the other only while accessing the buffer.

There are, however, some problems with flag semaphores, the first and foremost being the deadly embrace. Figure 1.12 illustrates this for a set of two tasks T1, T2 synchronized using two semaphores S1, S2.

It is clearly seen that in this case both the tasks will be perpetually in the blocked state resulting in a deadlock in the following scenario considering that the task T2 has a higher priority compared to T1; T1 sets the semaphore S1 and gets preempted by T2; T2 now sets the semaphore S2 and gets blocked while trying to set semaphore S1; and T1 is now scheduled and gets blocked while trying to set semaphore S2. One way of preventing this is the introduction of a critical section in the lower priority task such that it cannot be preempted within the critical section.

Next, extending this simple synchronization mechanism to a case involving multiple producers and a single consumer is attempted. It is first assumed that the m producers each write on a different buffer and the consumer reads these buffers. Since there are m shared resources, the synchronization between the producers and the consumer shall require m flag semaphores. Further, at the consumer end, the consumer can get blocked

FIGURE 1.12

Deadlock problem with flag semaphores.

m times within its request period to read data from m producers—in the worst case—sequentially, that is, and in that case if any of the producers get blocked after setting the corresponding semaphore, the consumer may get blocked perpetually. Figure 1.13 represents the pseudocode for the ith producer and the consumer.

At the consumer end, this causes a problem. The consumer tries to set the semaphores sequentially and it might so happen that one or more of the producers may get preempted after setting the corresponding semaphore, which will block the consumer perpetually.

FIGURE 1.13

Problem with multiple semaphores.

 
Source
< Prev   CONTENTS   Source   Next >

Related topics