Deterministic Systems: Semaphore

Alex Egg,

This paper is part two in a study of deterministic RTOSs. We begin by studying behavior in non RTOS systems such as Linux and then contrast w/ a real RTOS system, tinyos. Finally, we will explore ways to improve the non-determinic limitations of Linux by tweaking the Scheduling system. The previous study focused processes while this study will focus on resource sharing with semaphores on a Linux based system. Click here to read part 1: http://www.eggie5.com/86-deterministic-systems-processes

Semaphores: The Linux primitaive semaphore is used to prevent race-conditoins on resources. Under certain circumstances obtaining a lock can have a non-consistant delay which show non-deterministic behavior.

Sharing a resources across multiple processes introduces the problem of deadlocks and race conditions. One method to avoid race conditions is the use of semaphores which lock a resources so it can only be used by one resource at a time. Although, the introduction of the semaphore may fix races it does not however come without side-effects. When we added a semaphore to our system it introduced timing overhead and removed an element of determinism: a catch-22.

Deadlocks & Race Conditions

In development of computer systems, or software development, the use of resources is often required. When multiple processes require the same resource multiple problems fundamental to computer operating systems arise: deadlocks and race conditions.

Deadlocks occur when there is present a circular dependency. For example, process A wants resource A while Process B wants process B while A currently has B and B currently has A – these systems are stuck w/o outside intervention – this is a deadlock.

A race condition is when a resources is read and written by two processes at the same time – which one wins? This results in inconsistent and non-deterministic results.

This project explores these issues and uses one tool to mitigate the issues: semaphores. This project uses a semaphore to effectively lock the shared resource – in this case a counter – so that races cannot occur. If another process tries to access the locked resource the semaphore will block it. However, there is overhead induced w/ the inclusion of semaphores which is also analyzed in this report.

Experiment

Using the provided simple test-bench, I added some simple times to the child process that mark the time before the semaphore lock and marks the time after the semaphore lock, then takes the delta – which is the lock time for the semaphore – and logs it.

The raw lock time values are shown below in figure 1:

Drawing
Figure 1: Raw data plot (microseconds)

From the raw lock-time scatter plot above in figure 1 it may seem like the lock-times are very distributed however, if one bins the results into discrete groups, the results are more clear, see the histogram in figure 2 below:

Drawing
Figure 2: Histogram of lock times (in microseconds)

From the histogram above in figure 2, it is clear that most of the results are grouped in the 0-500 microsecond bin.

From the statistical analysis in Figure 3 below, it shown that the average lock-time is 104 microseconds which a very large standard deviation of 193 microseconds – a very large variance. A lock time of 0 microseconds occurred 4 times and the longest lock time took 4.6 milliseconds

Drawing
Figure 3: Statistical analysis of lock times (microseconds)

Analysis

From figure 3, above, even though the average (mean) lock time is only 104 microseconds with such a large standard deviation of 193.7, the variation is too large to consider this a deterministic system by most standards. It seems like there might be an interesting trade-off between determinism and races. Similar to the Heisenberg Uncertainty Principle in DSP, we can’t have the best of both worlds.

Also, some interesting aberrations are the min. lock-times of 0 microseconds which happened a total of 4 times. I cannot explain this aberration except for glitches in the timing code which I can consider statistical outliers and safely ignore them as nose since my sample size is so large (659 222). The second aberration was the longest lock-time which was over 4 milliseconds.

Conclusion

In summary, we were able to mitigate race conditions and enforce mutual exclusion with the use of semaphores. The value-add of semaphores is the safe use of a shared resources across multiple processes, however, from the analysis above the benefits are not without tradeoffs. The introduction of the semaphore construct added time overhead to our system and removed an element of determinism in the timing.

Permalink: deterministic-systems-semaphore

Tags:

Last edited by Alex Egg, 2016-11-05 21:59:22
View Revision History