RTP
Real-Time Programming Project
Contents hide
Motivation
Real-Time Programming has become critical, as so-called real-time systems must give a "fast-enough" response to the input coming from their environment, within a given time frame. Real-Time Programming implies the use of synchronization tools, in order to make processes and threads aware of their surroundings, thus performing as quick as possible, in order to minimize the response time. [1]
The motivation for this project is based on the specification given by a teacher, where a multi-process system should be implemented. This multi-process system should demonstrate the use of a certain set of tools under Unix real-time programming, namely Inter-Process Communication (IPC). These tools are commonly referred as POSIX programming tools, since POSIX has been defining the standard way of implementing applications across different Unix operating systems.
The participants of this project (Todor, Michal Paszta and myself), have decided to implement a solution for the readers-writers problem. Furthermore, the main aim is to solve the third readers-writers problem, since it is the most challenging of all the readers-writers problem variants.
Background
The Dining Philosophers Problem
The readers-writers problem resembles the Dining philosophers problem, being, the latter, a general specification without the need of a computerized solution. At a glance, the Dining philosophers problem, states that there were N philosophers sitting at a round table, where each philosopher had one fork. In the middle of the table there is a bawl of spaghetti. In order to help oneself, a philosopher must use two forks, leading to the situation where a philosopher will always have to wait for another philosopher to be free, so that he or she can use the other philosopher's fork (to help him- or herself).
So far so good. However, this configuration immediately pops up the following question: what will then happen when all philosophers want to eat at the same time?. Obviously, that situation cannot be handled, and hence they must agree on a set of turns, in order to serve themselves from the table. Moreover, there is another problem that is not seen that soon. Imagine that one philosopher takes someone else's fork and starts eating, then another philosopher does the same (without the first philosopher being finished), etcetera. This behavior will result in a situation where, at some point, a philosopher has lost his or her fork, thus being unable to eat.
To sum up, in this problem there are three important elements:
- an user
- a common resource (wanted or needed by the users)
- a token (the shared fork, which is the element that enables an user to access the common resource)
The Readers-Writers Problem
Accordingly, the readers-writers problem deals with a computational problem where several processes need to access the same memory location. In order to be consistent (and following from the situation described by the Dining philosophers problem), the memory location is a shared resource (remember the diner's fork?), and hence it must be multiplexed, in order to allow every process to access the common memory location. Please notice the importance of the fact that every process must be allowed to access a common resource with the exact same access rights as every other process, thus making the sharing of the common resource fair.
There are three variants of the readers-writers problem. The simplest one is implemented by locking the memory location any time a process accesses it. This could be imagined as if the process (the one selected for accessing, right now, that memory location) had a token with itself, and any process needs to obtain this token before accessing the memory location. As soon as a process finishes using the memory location, it gives away the token, which is delivered to another process (the next in the queue for accessing the common resource). In addition to this, a process that only needs to read the memory location is always given the preference, since it will not modify the value of that location. This is called readers-preference, and it is done because, otherwise, a process would just finish reading and another process could come and update the data in the memory location, hence making the data read by the first process obsolete.
Analyzing the first readers-writers problem closely, we see that there is a preference problem. As long as there are readers waiting for accessing the shared memory location, writers will not be able to write, according to the readers-preference rule. Therefore, in the second readers-writers problem, the preference is given to the writers, namely writers-preference. In the latter case, writers will have proper access to the memory location, however there will be still starvation, this time for the readers.
Besides the first and second problem, there is another proposition, in which both readers and writers would have access to the memory location, without suffering from starvation (using a timeout or another type of control method), this is the third readers-writers problem.
Environment
Architecture
In order to implement an example of the third readers-writers problem, we must first come up with an idea of multi-process in which this architecture is feasible. Additionally, the development team was willing to implement the system using common and modern POSIX programming practices, due to the high demand of parallelization in current computer trends.
The architecture is based on a simulation program, where N clients try to read and write from and to a common memory area at the same time. These clients are created, they first try to write, then they try to read, and finally the die. The memory area is a shared memory area and it is multiplexed by M servers. Eventually, these servers must negotiate with each other in order to give the right access grants to each client, without leading the system into a deadlock nor to any other concurrency problem (from any possible mutual exclusions).
Figure 1 depicts the basic idea of multiplexing N clients through M servers, which become the actual readers and writers. The synchronization tool between clients and servers is, as shown in figure 1, some type of messaging protocol (typically, a message queue). Furthermore, the synchronization protocol used between servers is based on semaphores (mutex), which are set as one semaphore per memory location.
Process Communication
According to the software architecture described above, the communication process is simple and ordered. A client creates a message containing a type of operation (read or write), some data to write (or some pointer to a data variable, when reading) and the memory location where to perform the given operation. That message is then packed and sent through the message queue.
Subsequently, the messages arrive to the other end of the message queue, where M servers are constantly listening to. As soon as a server reads a message from the other end of the queue, it becomes a reader (if the operation type is to read) or a writer (if the operation type is to write). In fact, servers are the real readers and writers, and their task it then to synchronize with each other by using the mutex tool.
Finally, up on task completion, messages are notified back to the clients, probably through a different message queue, where only notifications are enqueued. Therefore, the architecture is better described in figure 2.
In figure 2, the difference with figure 1 is that, now, there are two message queues: one for sending operations and another one for receiving notifications. The double-queue technique is simple and separates the communication in one direction from the communication in another direction. As a reference, please notice that operation requests are marked with a normal arrow (flat line), whereas notifications back to clients are denoted by a dashed-line arrow.
Implementation Details
Solution to the Third Readers-Writers Problem
The main problem when specifying this project was not to design the architecture, but rather build a model where the third readers-writers problem could be solved without major trouble.
At first, I came up with several algorithms that were improving with respect their previous ones. However, soon I noticed that none of them would perfectly fit the third readers-writers problem, since there would always be a tiny possibility that some process was neglected, thus leading to a potential starvation.
Luckily enough, I found a source where this algorithm was presented in a clear manner. In fact, the main problem implementing the no process shall starve rule was to implement the timeout mechanism. In a scientific publication, by Jalal Kawash, this algorithm is reduced to use only two mutexes per memory location and two variables, one indicating the number of pending writers and the other one indicating the number of pending readers. The algorithm is shown in figure 3.
As it can be seen from the algorithms presented in figure 3, readers will access the memory location if there are no writers (conditioned by the if-statement). This means that the priority is always given to the writers. However, the first (and only the first) reader, is the one that tries to lock the resource, thus locking coming writers. This is the mechanism that allows a certain amount of readers to access the resource for a certain time. Afterwards, there will be again a frame where only writers can access the resource. [1]
This simple algorithm eliminates the necessity of implementing timeouts and watchdog processes. Furthermore, it allows to alternate turns between frames where writers are working, and frames where readers are working. And finally, writers have their own priority, since readers will always check if any writer is waiting or not, thus letting them to perform their work before reading from the shared resource. Just brilliant, Jalal Kawash! [1]
Please note that this algorithm is the one written inside the server processes, coming back to the purpose of this project. Remember that, to this project, the readers and writers are the servers, which take a read or write operation from the operations message queue.
Client Implementation
The code of each client is quite simple, and its task is just to generate random operations on random memory locations, make the request and wait for acknowledge. Please consider the flow of the client process in the following list:
- attach itself to the requests message queue
- attach itself to the notifications message queue
- perform N read or write operations (randomly):
- generate a random operation
- generate a random area location
- if operation is write: generate a random data
- pack both into a message
- send a message through the requests message queue
- wait for a notification (up on completion), on the notifications message queue
- print something on the screen (both read and write), and loop
- terminate
Main Program: Simulator
Last, the flow of the application is clear, and it follows a simple set of steps, in order to create this working simulation:
- create the shared memory area
- allocate two mutexes per memory location
- create the requests message queue
- create the notifications message queue
- launch M servers
- launch N clients
- wait for all clients to terminate
- send SIGTERM to all servers
- wait for all servers to terminate
- clean up all the resources
- print simulation statistics (if necessary)
- terminate
Development Model
In the beginning of the project the team had a couple of small meetings to identify the problem (functional description) and possible solutions. A milestone was the final design meeting during which the team decided upon a particular implementation. Additionally, at the end of this meeting, once the architecture of the application was specified to a great extent, the members discussed and established a rough breakdown structure (Table 1).
| Task | Responsibility |
|---|---|
| Project management | Claudio Camacho |
| Agent implementation | Michal Paszta |
| Server implementation | Claudio Camacho |
| Client implementation | Todor Vlaev |
As can be seen in Table 1, the areas of responsibility are quite general. This is why the members of the team committed to the idea of shared code ownership. This meant that if a member notices a bug or requires a functionality that is not yet implemented, he is free to fix or implement the code. Of course, if the missing functionality or present fault is of large complexity/size, the appropriate owner of the task is to be notified.
The arrangements made for the mentioned responsibilities is supported by an established git version control repository. This system makes it possible for the team members to collaborate easily and in an organized manner. Descriptive commit messages are given high priority. Apart from the git log the main communication channel was email and daily discussions made possible by the team members' common schedule.
Discussion
The following real-time programming tools were used to present and solve the problem:
Shared memory
- It is created by agent, servers and clients only have to attach to it. Shared memory by itself is not protected in any way from simultaneous read or write operations. There are two shared memory areas used in the project: in one of them the variables containing current number of readers or writers waiting are kept, and the other one is the area, being accessed by readers and writers to write data to or to read data from.
Semaphores
- A new POSIX semaphores API has been used for the project. There are two semaphores used: one of them locks the access to shared memory, and the other one locks access to variables keeping number of readers or writers.
Message queues
- Communication between client processes and server processes is implemented using message queues. One of them is used for passing requests from clients to servers, and another one is necessary to give response to those requests.
Apart from IPC tools, also other useful real-time programming features are present in the project, such as: double forking, awaiting child processes, signals. Much emphasis was put on writing the code in a neat, easy-to-read and parametric way. All the constants are kept in a separate file, the code is well-commented. Additionally, the team spent very productive sessions debugging the application. These meetings were examples of effective collaborative work. The results were rewarding in terms of work progress and especially personal experience and inter-team relations.
The proposed project organization and commitments were successfully implemented. A very strong factor was the active communication among the team members. Even though there was no official schedule for feature implementation the team managed to meet the goals before the project deadline. Milestone deadlines naturally emerged in the course of work. This approach in scheduling was chosen and successfully applied due to the following factors:
- team members were already familiar with each other's competences
- commitment and trust was on a very high level
- communication was on a very good level throughout the whole project
As can be deduced from the list above the flexible scheduling relied on the already established personal relationships. It is true, however, that a better structured plan would have been necessary if there were newcomers in the team. Nevertheless, in the current circumstances such arrangements would have added unnecessary overhead that would have degraded performance. The team members are confident that the project organization was the best one for the particular situation. The outcomes of the project justify the axiom of project management that every project is different and naturally requires appropriate leadership. This being said, the project management proved to be quite successful.
Conclusions
The readers-writers problem, seems to be optimally solved, using easily accessible and well documented tools. The participants of this project have learned to implement and test those tools. During their work they also acquired other useful skills, not directly connected with real-time programming, such as ability to use a git repository for version control or to write good comments in addition to the code. The participants have also proved (and improved) their ability to work in a team.