Deterministic Systems: Scheduling

Alex Egg,

This paper is fourth and final part in a study of deterministic operating systems. The previous study focused on a a real RTOS called Tinyos. This final part will explores scheduling tweaks to improve the deterministic flaws we observed in parts 1 & 2. Click here to read part 3: http://www.eggie5.com/86-deterministic-systems-scheduling
Source code for this project is available here: https://github.com/eggie5/SDSU-COMPE571-FALL13/tree/master/hmwk4

Using the default posix scheduler, processes are not real time constant and only achieve a degree of determinism when timers come into play. Using a FIFO scheduling policy and the highest priority available it is possible to achieve near real-time performance with a high level of determinism.

Introduction

When developing a real-time system, it is apparent that some tasks are more important than others. Some must be run on-time, every time, while others can run whenever the processor has a few cycles to spare. Scheduling is the term given to the method by which processes are run on a UNIX system. In this experiment, the methods by which processes can be scheduled are examined including how to change the scheduler and the priority of a process.

There are many circumstances where the designer of a real-time system will wish to have one process be “more important” than another. In other words, if process A is able to run, it should run in place of any other process. In this case, process A would have a high priority. The operating system decides when a process should or should not get to run based on a set of rules it has. Scheduling is the functionality of the operating system deciding what should run and when. POSIX.1b gives a set of calls through which the programmer can modify how and when a set of processes will run.

In labs 1 and 2 we measured the time it took to complete the gettimeofday() call and measured the time it took to get a semaphore lock. However, due to system load, the results were not always consistent. Now that scheduling has been introduced, it is possible to have a process run to completion (FIFO scheduler) and alter its priority such that it is higher than any other process and thus, will not be interrupted. In this way, the performance measurement that is taken will be more accurate since the scheduler guarantees that the process will not be interrupted while it is calculating.

Semaphore Experiment

In lab 2 we measured the time it takes to get a semaphore lock on a resource and determined that while it added the benefit of mutual exclusion it came with the side-effect of removing a degree of determinism from the timing of our code. One way to mitigate this issue is to use a FIFO scheduler with the max priority which should allow the most resources possible available to our program.

##Default Scheduler

To establish a baseline for testing we first ran the semaphore program with the default system scheduler and process. FIgure 1 shows the locks times for 1029 trial runs.

alt text
Figure 1: Timing results (microseconds) of default scheduler. The above results are for 1029 calls for a semaphore lock w/ the time recorded on the y axis. Observe that the times are widely scattered.

Although the scatter plot in Figure 1 is full of data, no clear patterns are obvious. In Figure 2 below, we create a histogram to see any patterns.

alt text
Figure 2: Histogram of timing data. The near uniform distribution indicates a low-level of determinism.

After observing the near uniform distribution in Figure 2 it can be inferred that there is no strong pattern in response times with the default scheduler, or in other words: the process has a low degree of determinism.

alt text
Figure 3: Statistical analysis of default scheduler.

Now that we have our baseline results we can replace the system default scheduler with a FIFO policy.

FIFO Scheduler

We now set the scheduler to a FIFO policy with the maximum priority which should mitigate the issues we saw with loss of determinism with the default scheduler.

The results of the trial runs can be seen in Figure 4: no clear changes can be made.

alt text
Figure 4: Scatter Plot of timing samples. They look similar to the default scheduler, however the difference is apparent when the histogram is observed.

However, the results are very interesting when viewed as a histogram:

alt text
Figure 5: Histogram of timing data from figure 4. It is clear from contract to the histogram in Figure 2, that this test has a much more distinct timing distribution. The majority of the samples are grouped in the 500-800 and 800-900 bins which implies a higher degree of determinism compared to default scheduler in Figure 2.

There is a clear pattern in the data with over 60% of the timing results landing within 500-900 us. This is in stark contrast to the uniform distribution in Figure 2. Assuming no other variables have changed between tests (background noise, load, etc) we can infer that the FIFO policy has helped us achieve a higher degree of determinism.

alt text
Figure 6: Statistical analysis of FIFO test

The mean for FIFO policy is 737 which is 129 us faster, the median is faster by 171 us also. It is clear from this analysis that the FIFO policy is giving our program faster results and higher levels of determinism.

#Timer Experiment

In Project 1 we measured the system timer determinism on unix. We found that it is hard to get full real-time performance due to competing resources on the system. Below is the baseline test results for the system scheduler.

##Default Scheduler

alt text
Figure 7: Histogram of timing values

alt text
Figure 8: Statistical Analysis of data

##FIFO Scheduler

alt text
Figure 9: Histogram of FIFO values

alt text
Figure 10: Statistical Analysis of FIFO policy test

It is clear that the mean time of test sample is faster by an order of magnitude. Also the Std. Deviation is smaller so we have more consistent timing which can be attributed to increased determinism due to the FIFO scheduler and max priority.

#Analysis

It is clear, especially from the comparison of comparison of the histograms in Figures 2 and 5 that the addition of a FIFO policy and a max priority, that the program gained a large degree of determinism. The default scheduler test produces a largely uniform distribution which implies a low degree of determinism in the time needed to acquire the semaphore lock. While the FIFO policy test produces a rough gaussian distribution which implies a higher degree in determinism. Also the overall timing of the program decreased with the FIFO policy; the program ran faster because it had a lock on the CPU with the highest priority and a FIFO policy.

#Conclusion

Unix is a non-real-time operating system and accordingly timing precision is not guaranteed. The non-determinism of a unix system was demonstrated in labs 1 and 2. In this lab we were able to demonstrate that with certain modifications we are able to achieve a higher level of determinism in a non-real time system. With the addition of a FIFO scheduling policy combined with a high process priority causes our programs to gain a higher degree of determinism and faster execution times.

Permalink: deterministic-systems-scheduling

Tags:

Last edited by Alex Egg, 2016-11-05 22:44:03
View Revision History