Real-time Operating Systems Homework Report

Real-Time Operating Systems Homework Report Vittorio Giovara 26/01/2009

Abstract In this document a solution will be described for implementing a concurrent programming scheme in a real-time operating system. The first part of the document will carry out the design planning, describing the main procedures and functions in pseudo-code and taking care of two possible issues, deadlock and starvation. Moreover an actual implementation of the problem will be discussed for the RTEMS Operating System. In the second part a complete working implementation of the solution will be presented for a general purpose operating system, providing profiling and time analysis.

Contents I

Preparation

2

1

The pseudo-code 1.1 Functions and Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Message Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 2 2 3

2

Dealing with deadlock and starvation issues 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Proof for deadlock free solution . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Starvation free condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 4

3

Initial RTEMS solution

4

II

Implementation

6

4

Development details 4.1 IPC Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6

5

Profiling 5.1 Testcases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Mean and Maximum Wait Time . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Execution Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 7 12 13

1

Part I

Preparation 1

The pseudo-code

1.1

Functions and Structures • void sync (int w) function for normal processes to put themselves in a passive wait; the argument w represent the weight of the wait; • void admit (int a) function for the master process to wake up some the waiting processes; the argument a determines which processes in the pool are actived; • send and recv functions for implementing message passing with fixed lenght format; the naming scheme is direct, asymmetric for the asynchronous send with infinite buffer. • information vector contains general data about every process: it stores the process identifier, its status (blocked or running), its weight and the age, which counts how many times a process eligible for activation has not been woken up after an admit; an additional field is required for the final solution to work, that is the fdlisten, need for communicating with the process; • vector order is a vector containing the ordered (by age) list of all the processes that are activated by an admit;

1.2

Proposed Solution

void sync (int w) 1. check if the argument w is greater or equal than 1 and less or equal than 10; 2. inform M of the status change with a send; 3. perform a blocking recv; 4. upon message receiving, check if the format is correct; 5. if the message is correct, return, else remain in wait. void admit (int a) 1. send a message asking the server to perfom the wake up of some processes; 2. return.

2

server process M 1. spawn a given number of P and Q processes and initilize the “information vector”; 2. enter endless loop 3. wait with a recv for an action to perfom; 4. if a sync has been called, update the status of the process in the information vector; 5. if an admit has been called perform the following: 6. initialize a list (vector of index) for storing the set of processes that are going to be activated (called “vector order”) ; 7. select the set of waiting processes with their weight and age from the information vector; 8. order the vector from highest age to the lowest and initialize pound equal to a ; 9. for every element in the vector, send a wake up if its weight is less than pound and if pound minus the weight is positive; 10. when a wake up is sent update the pound by subtracting the weight of the process; in this way both the conditions of the assignment are respected; 11. update the information vector with the new status for the selected processes and the incremented age for the unselected ones; 12. repeat loop.

1.3

Message Format

The format for the exchanged messages is to use 2 integers (8 bytes); the first integer is used for distinguishing whether a sync or an admit has been called, while the second integer contains the argument of the admit (sent from the process Q to the server M).

2 2.1

Dealing with deadlock and starvation issues Definitions

As with most of concurrent programming schemes, it is possible to incur in two important problems: deadlock and starvation. The former is situation whereby a set of processes cannot exit a from a given status because they are waiting for an event that can be generated only by a process inside the blocked set. This type of problem cannot be resolved (because deadlock detection algorithms are rarely implemented in the system), but only avoided beforehand, implementing secure states. The latter on the other hand is a condition in which a given process never manages to access a resource because other processes gain access before it, even if it is ready to execute. This is also called indefinite wait. Usually this kind of problem appears in priority scheduling systems with no aging techniques.

3

2.2

Proof for deadlock free solution

In order for deadlocks to appear, the following four conditions are must appear simultaneously (Coffman’s Conditions): • Mutual Exclusion: resource usable by one process at a time; • Hold and Wait: processes holding resources request for other resources; • No preempion: resources can be released only by explicit action of the holding process; • Circular Wait: circular loop chain for resource assignation. In this implementation there is no risk for deadlocks because the server M handles the processes only one at a time: in fact a single send can activate the server procedure because there is a single recv in the loop. Thanks to this implicit serialization, the necessary condition of the circular wait never occurs, thus neglecting the presence of possible deadlocks.

2.3

Starvation free condition

In order to prevent starvation an aging technique has been introduced in handling the processes: every activation creates different generations of processes. The oldest processes are always considered and awakened first, before any newer process may prevail over any of them. Since the number of possibile processes is finite, it always guaranteed that after a mean wait time (unknow, yet finite) a given process is awakened. It is possible to consider a case in which n processes are activated one at a time and no processes are blocked; if ta is the activation time for a process, then the total time (T ) for activating all the processes is exactly T = n ∗ ta As n and ta are finite values, also the T wait time is finite, thus neglecting the presence of starvation which requires an indefinite wait.

3

Initial RTEMS solution

In adapting the proposed solution to the RTEMS operating system, it is possible to find several issues. The most relevant problem is that the buffers of the send and recv function are not infnite, due to hardware and software intrinsic limitations. So one of the following solution must be adopted when performing a send to a full buffer: either assume that one process can send at most one message and so allocate a buffer as big as the number of processes generated (which is always finite), or block the send until the buffer is freed of at least one element. This latter approach heavily depends on the operating system implementation, but it is safe to assume that RTEMS manages blocked send buffers correctly, with no starvation or race conditions; for this reason this last solution is preferrable. As for the IPC mechanisms available on RTEMS, it is possible to choose between the native RTEMS functions or the POSIX implementation (rtems message queue send() and rtems message queue receive(), mq send() and mq receive() respectively). The POSIX mechanism allows to block the send functions when the buffer is full and do not require modifcation to the proposed solution (carefully handling differences in the naming scheme), so it should be selected over the native functions. 4

One final minor problem may be byte ordering that should be considered when dealing with message passing on different architectures; since it has been assumed that the processes run on a same machine it is possible to neglect this problem.

5

Part II

Implementation 4

Development details

The proposed solution has been implemented on Mac OS X 10.5.6, but as design choice only ANSI POSIX compliant directives have been used, resulting in highly portable code. As a matter of fact the program has been tested (and proved working) on Linux with kernel 2.6.24 and on Solaris (SunOS 5.19) over an UltraSPARC IIi. The solution heavily relies on wrappers for error checking and error analysis, as well as the errlib library by W. Richard Stevens for error reporting and general Input/Output management. Resource allocation is carefully considered (foreseeing a possible real-time port) and in fact when server and process are closed, socket descriptors are closed, pipes removed, memory deallocated and child processes killed. It is possible to select the level of verbosity for info and debug message by passing the TRACE and DEBUG symbols at compile time, while passing TIMETEST enables timing functions to be activated. Before starting the program asks the user to insert the number of processes of type P and to select the behiavior of the processes: actually the user can either choose to let the processes generate a random number or interact actively with an interface. In the first case the process sleeps for that random amount of time (only to prserve readability of the output; the program works even without the sleep() clauses) and then use that value to perform block or wake up. In the second case the user is prompted to an interface that allows process selection with PID and value insertion for the sync() and admit() (as well as a clean closing for the program); the interface process is generated only when interactive behavior is chosen.

4.1

IPC Mechanisms

In order to let the process exchange packets the underlying Inter Process Comunication chosen is the Unix socket: every child process generated is connected with the father through a connected socket with the socketpair() function. Then the server remains in listening mode on all of them with a select() and as soon as data arrives it selects the correct socket and proceeds unpacking the message. When the server needs to send a message to a child process (usually to activate it), it can obtain the process’ socket (which is included in the information vector) searching in the data structure using the PID as key. On the other hand in order to allow interaction, the processes are connected to the interface with a named pipe. Pipes have been chosen over a second set of sockets because they offer oneway message passing, instead of socket full-duplex channels; since the interface has only to send commands to the processes (and not receive any reply back), pipes offer resource-light facility for the task. The interface spawn a sub process to actually send data so to implement a timeout condition; in this way the user is informed when a process is already blocked and that it is not possible to block it again. Having both sockets and pipes as dedicated channels, integrity of the packets exchanged with send, recv, write and read is preserved; it is impossible to create conflicts because messages are sent one at a time.

6

5 5.1

Profiling Testcases

The following sets of trace of execution from the program are obtained with both random test cases and with interactive input test. These test aim to cover all the relevant part of code describing correct functionality of the algorithm, process interaction and concurrent behavior; thanks to the the fork() approach, no critical regions needed to be defined. Output may have been reduced with respect to the actual produced to preserve readability. Tests have been performed on Mac OS X, Linux and Solaris. Basic functionality In the following test case, the algorithm functionality will be taken in consideration. Five P processes are being generated and each of them performs a sync with a given value; Q sends an admit capable of activating only four of them and so only four are woken up, increasing the age of 8500. Then two of the activated processes perform other sync’s; at the next admit of 8 from Q, the first process to be awakened is the one that was left behind (8500) as it respects the given conditions and avoids starvation. Also process 8502 can be activated and it is awakened right away. Now processes 8501 and 8498 have their age increased and so are candidate to be activated at next sync; however Q sends a very low admit and so they have to be discarded in favour of 8500 which has just perfomed an equally low sync. They will be activated by the next admit of Q. (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2)

info info info info info info P:8498 server P:8499 server P:8500 server P:8501 server P:8502 server Q:8503 server server server server server P:8498 P:8499 P:8501 P:8502 P:8501 server

8497 spawned child 8498 (element 8497 spawned child 8499 (element 8497 spawned child 8500 (element 8497 spawned child 8501 (element 8497 spawned child 8502 (element 8497 spawned child 8503 (element sent a sync(2) received a sync(2) from P:8498 sent a sync(3) received a sync(3) from P:8499 sent a sync(7) received a sync(7) from P:8500 sent a sync(1) received a sync(1) from P:8501 sent a sync(1) received a sync(1) from P:8502 sent an admit(7) received a request for admit(7) sent WAKE UP to process 8498 sent WAKE UP to process 8499 sent WAKE UP to process 8501 sent WAKE UP to process 8502 has been woken up! has been woken up! has been woken up! has been woken up! sent a sync(4) received a sync(4) from P:8501 7

number number number number number number

0) 1) 2) 3) 4) 5)

(./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2)

P:8502 server P:8498 server Q:8503 server server server P:8500 P:8502 P:8500 server Q:8503 server server P:8500 server Q:8503 server server server P:8501 P:8500

sent a sync(1) received a sync(1) from P:8502 sent a sync(3) received a sync(3) from P:8498 sent an admit(8) received a request for admit(8) sent WAKE UP to process 8500 sent WAKE UP to process 8502 has been woken up! has been woken up! sent a sync(1) received a sync(1) from P:8500 sent an admit(1) received a request for admit(1) sent WAKE UP to process 8500 has been woken up! received a sync(1) from P:8500 sent an admit(5) received a request for admit(5) sent WAKE UP to process 8501 sent WAKE UP to process 8500 has been woken up! has been woken up!

Interesting interleaving In this trace there is an interesteing case of interleaving between P and Q an the server response; in fact between the final admit request sent by Q and the server acceptance there is the server reply that allowed process 8264 to be blocked. So as soon as the admit request is accepted, instead of issuing a warning for no blocked processes, 8264 is woken up right away. (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2)

P:8265 sent a sync(1) server received a sync(1) from P:8265 P:8266 sent a sync(2) server received a sync(2) from P:8266 P:8267 sent a sync(3) server received a sync(3) from P:8267 P:8264 sent a sync(5) server received a sync(5) from P:8264 Q:8268 sent an admit(10) server received a request for admit(5) sent WAKE UP to process 8264 sent WAKE UP to process 8265 sent WAKE UP to process 8266 P:8265 has been woken up! server received a sync(3) from P:8265 P:8264 has been woken up! server received a sync(3) from P:8264 P:8266 has been woken up! P:8266 sent a sync(1) server received a sync(1) from P:8266 8

(./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2)

P:8264 sent a sync(4) server received a sync(4) from P:8264 P:8265 sent a sync(5) server received a sync(5) from P:8265 Q:8268 sent an admit(9) server received a request for admit(9) P:8267 has been woken up! sent WAKE UP to process 8267 sent WAKE UP to process 8264 sent WAKE UP to process 8266 P:8264 has been woken up! P:8266 has been woken up! P:8264 sent a sync(1) server received a sync(1) from P:8264 Q:8268 sent an admit(1) process 8264 is set to BLOCKED with weight 1 server received a request for admit(1) sent WAKE UP to process 8264 P:8264 has been woken up!

Interface testing This test demonstrates the capability of the interface process. It detectes all possible kind of inputs and correctly manages selected processes . This is possible because the interface is generated as last child when all the other P processes have been generated and so it has stored in memory all information of the other processes. In the following program trace it is verified in order: • blank input • wrong input (2 fields required) • non existing process • wrong weight value (check also performed by the sync function) • correct input towards a P process • correct input towards another P process • attempt to block a blocked process • correct input towards a Q process • program closing You chose 4 P processes and 1 Q process You chose to operate with the interface (./rtos-hw2) info - 8230 spawned child 8232 (element (./rtos-hw2) info - 8230 spawned child 8233 (element (./rtos-hw2) info - 8230 spawned child 8234 (element (./rtos-hw2) info - 8230 spawned child 8235 (element (./rtos-hw2) info - 8230 spawned child 8236 (element Enter ’<process pid> ’ to command the program > 9

number number number number number (’0 0’

0) 1) 2) 3) 4) to exit)

(./rtos-hw2) warning - command not correct Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 12345 (./rtos-hw2) warning - command not correct Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 12345 4 (./rtos-hw2) warning - no process 12345 found Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 8232 20 (./rtos-hw2) warning - command not correct (accepted values [1-10]) Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 8232 2 (./rtos-hw2) P:8232 sent a sync(2) (./rtos-hw2) server received a sync(2) from P:8232 Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 8233 5 (./rtos-hw2) P:8233 sent a sync(5) (./rtos-hw2) server received a sync(5) from P:8233 Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 8233 9 (./rtos-hw2) warning - could not send packet to 16689! Is it already blocked? Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 8236 7 (./rtos-hw2) Q:8236 sent an admit(7) (./rtos-hw2) server received a request for admit(7) (./rtos-hw2) server sent WAKE UP to process 8232 (./rtos-hw2) server sent WAKE UP to process 8233 (./rtos-hw2) P:8232 has been woken up! (./rtos-hw2) P:8233 has been woken up! Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 0 0 Closing interface and program. Goodbye! (./rtos-hw2) info - received signal number 15. Closing server and processes. Random generation While the previous example was generated through the interface, this test show a similar functionality but with random generation of values, as well as with a greater number of processes involved. From the point of view of functionality, there is not much differnce from the first test case, apart from the generation of a wrong sync value. This value is detected right away and discarded. Process Q can autonomously generate an higher value than allowed just to test this case. (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2)

info info info info info info info info P:8306

8300 8300 8300 8300 8300 8300 8300 8300 sent

spawned child spawned child spawned child spawned child spawned child spawned child spawned child spawned child a sync(1) 10

8303 8304 8305 8306 8307 8308 8309 8310

(element (element (element (element (element (element (element (element

number number number number number number number number

0) 1) 2) 3) 4) 5) 6) 7)

(./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2)

server received a sync(1) from P:8306 P:8307 sent a sync(2) server received a sync(2) from P:8307 P:8308 sent a sync(3) server received a sync(3) from P:8308 P:8309 sent a sync(4) server received a sync(4) from P:8309 P:8303 sent a sync(6) server received a sync(6) from P:8303 P:8304 sent a sync(7) server received a sync(7) from P:8304 P:8305 sent a sync(8) server received a sync(8) from P:8305 Q:8310 sent an admit(10) server received a request for admit(10) server sent WAKE UP to process 8303 server sent WAKE UP to process 8306 server sent WAKE UP to process 8307 P:8303 has been woken up! P:8306 has been woken up! P:8307 has been woken up! P:8303 sent a sync(11) warning - wrong weight value for 8303 (received: 11) P:8306 sent a sync(5) server received a sync(5) from P:8306 P:8307 sent a sync(6) server received a sync(6) from P:8307 P:8303 sent a sync(2) server received a sync(2) from P:8303 Q:8310 sent an admit(14) server received a request for admit(14) server sent WAKE UP to process 8304 server sent WAKE UP to process 8308 server sent WAKE UP to process 8309 P:8304 has been woken up! P:8308 has been woken up! P:8309 has been woken up! P:8304 sent a sync(3) server received a sync(3) from P:8304 P:8308 sent a sync(7) server received a sync(7) from P:8308 P:8309 sent a sync(8) server received a sync(8) from P:8309 Q:8310 sent an admit(9) server received a request for admit(9) server sent WAKE UP to process 8305 P:8305 has been woken up! P:8305 sent a sync(4) server received a sync(4) from P:8305

11

No blocked processes This test show that after every process has been activated, it may happen that Q asks for another admit; the server is capable of handling this situation warning that no blocked processes are present. (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2) (./rtos-hw2)

P:5440 sent a sync(1) server received a sync(1) from P:5440 P:5441 sent a sync(2) server received a sync(2) from P:5441 P:5442 sent a sync(3) server received a sync(3) from P:5442 P:5443 sent a sync(4) server received a sync(4) from P:5443 Q:5444 sent an admit(11) server received a request for admit(11) server sent WAKE UP to process 5440 server sent WAKE UP to process 5441 server sent WAKE UP to process 5442 server sent WAKE UP to process 5443 server P:5441 has been woken up! server P:5443 has been woken up! server P:5440 has been woken up! server P:5442 has been woken up! server Q:5444 sent an admit(2) server received a request for admit(2) warning - there are no BLOCKED processes

Blocked processes, admit value too little In this test a P process (8063) is stopped with an high weight; then Q asks for low value admit. The server detects the blocked process but can’t correctly acativate it. (./rtos-hw2) info - Interface 8065 is born from 8059 Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 8063 10 (./rtos-hw2) P:8063 sent a sync(10) (./rtos-hw2) server received a sync(10) from P:8063 Enter ’<process pid> ’ to command the program (’0 0’ to exit) > 8064 2 (./rtos-hw2) interface - writing packet on /tmp/rtos-pipe-8064 (./rtos-hw2) ingo - Q:8064 received a packet containg 2 (./rtos-hw2) Q:8064 sent an admit(2) (./rtos-hw2) server received a request for admit(2) (./rtos-hw2) admit value too little to wake up any process

5.2

Mean and Maximum Wait Time

As hinted in 2.3 it is possible to compute the maximum wait time given the number of processes and the period for admitting. For this purpose the wrost case scenario must be considered:if Pi performs a sync(5), at wrost there will be higher priority (that is with greater age) processe. Supposing that every admit manages to wake up only one of them at a time, Pi will be awakened only at the last period of execution. 12

Since by hypothesis an admit is executed every 50 ns and there are 4 process, the maximum wait time for any process PI is given by: Tmaxwait = 50ms ∗ 4 = 200ms As for the mean time it has been computed with the following reasoning. Since there are only 4 P processes it may happen that Pi is in one of four possible cases: 1. Pi has the highest priority; 2. Pi has the highest priority but there is another process with same priority (Pj ); 3. Pi has the highest priority but there are other two processes with same priority (Pj , Pk ); 4. Pi has the highest priority but there are other three processes with same priority (Pj , Pk , Pl ). For every case Pi will have to wait for an amount of time if 1. no wait; 2. wait if the sync value of Pj is > 5; 3. wait if the sum of the sync values of Pj and Pk is > 5; 4. wait if the sum of the sync values of Pj , Pk and Pl is > 5; It has been computed that the probability for the last three to happen is 50%, 69% and 96% respectively. Since it has been supposed that the processes are independent between each other, it is possible to compute a mean probability of 71,6%. Finally, to compute the mean time waiting it is sufficient to compute Tmeanwait = 50ms ∗ 71, 6% = 35, 83ms

5.3

Execution Time

In order to compute the execution time for sync() and admit() the function gettimeofday() has been used. At function start the time is recorded in a timeval structure and substracted to the time sampled at function end; then data is converted in µs which is the maximum resolurion of the clock. Since blocking time doesn’t have to be computed, time in sync() is sampled twice leaving out the blocking recv(). The test program has been embedded in the final solution and it is accessible by passing the symbol TIMETEST at compile time; this symbol removes also any I/O function that may negatively influence the computation. There is a certain amount of uncertainty regarding the computed time. As a matter of fact resolution of µs is not guaranteed by ANSI C and the POSIX function gettimeofday() relies on internal constants (such as CLOCKS PER SEC) that might differ in many implementations. Moreover the hardware ticker present in computers may have a different resolution and uncertainty, so results can be heavily hardware dependent. A statistical approach has been used by sampling the amount of time in different situations (like different number of P processes); usually the first time the function is executed has an higher value, most likely due to loading in cache operations.

13

Function sync() admit()

Execution Time 28.2 µs 15.4 µs

14