Operating Systems

Implementation

Note that in this very simple problem, the data part is almost nonexistent. The philosophers and the forks are defined as active object, for they are imbedded in the functional model. The dynamic models are implemented as finite state machines located in the bodies of the active objects. It is a very simple way for controlling the order in which the operations can happen (called or accepted) within the philosophers (lines 102 - 110 below) and within the forks (lines 206 - 209 below). The resulting program can be compiled and executed (the initialization of available is not shown).

100 active class Philosopher {

101 int i ; // philosopher’s number

102 @Philosopher () { // body

103 for (;;) {

104 think: waituntil (now ()+random ());

105 forks[i].get();

106 forks[(i+1)%5].get();

107 eat: waituntil(now()+random());

108 forks[i].put();

109 forks[(i+1)%5].put();

110 }

111 }

112 };

113 Philosopher phil[5];

201 active class Fork {

202 int available;

203 public:

204 void get() {available = 0;}

205 void put() {available = 1;}

206 @Fork () { // body

207 for (;;) {

208 accept get;

209 accept put;

210 }

211 }

212 };

213 Fork forks[5] ;

We can look at the bodies of the forks under two angles. We can consider that the operations are the important thing and that the bodies just enable the operations when they are ready. We can also consider that the forks are made of automatons (the bodies) that are synchronized with the philosophers bodies, and that the methods get and put just describe the details of the transitions. The view to be considered depends on the characteristics the programmer is developing or checking. In applications where data are important, the methods must be developed first. In reactive systems (protocols...), the automaton aspects are more important.

The functional model, which includes the shape of the network of active objects, is implemented both explicitly with the instantiations (lines 113 and 212 above) and implicitly with the passing of the number attributed to each philosopher through its constructor (not shown here).

Behavior analysis

The graph shown on Figure 4 corresponds exactly to CCS processes [2]. The functional diagram of Figure 5 corresponds to a CCS combination of two philosophers and two forks. The potential deadlock can thus be found by just applying this theory (Fig. 6), or the tool that go with it (CWB: concurrency workbench).

Fig: Composition of one philosopher and one fork

A solution without deadlock is straightforward. It does not even need any semaphore nor any other special real time feature. It simply relies on two methods (please and thankYou) by which the philosophers politely borrow the forks from their neighbors, respectively return the forks to them.

Conclusion

A lot of work has still to be done along this way, but our goal was to show that it is possible to have a global approach, accessible to the average programmer, which offers an access to the libraries of the operating system, a support for the OOP approach, modeling as well as validation. This allows the merging of several domains that are essential to a professional development of reactive applications, but were until now very far apart.

As we have seen, the dynamic model describes the behavior of the objects. The functional model describes the synchronization’s or data flows (further studies should clarify the exact difference). Once the objects are placed in their proper environment (functional model), the real time kernel can automatically find the intersection of the behaviors of the active objects, as indicated in the automatons (dynamic model) The synchronization’s are fired according to the semantic of CCS, and the analysis realized on the models assure that the intersection of all elementary behaviors is not empty and in the contrary contains the effective traces that solve the problem of the application.

We have defined a extended version of C++, called sC++, that contains the features described above. A compiler, a debugger and different kinds of kernels are available. One of the kernel allows a random walk analysis, that is effective even in the case of state space explosion. Many examples (servers, a CORBA orb, user interfaces...) have been successfully developed with this approach.

2. Dekker’s Solution to Mutual Exclusion:

Mythical Mutex

Preventing race conditions requires the ability to protect critical regions of code - areas of code performing updates of a variable that is shared between threads must allow only one thread to enter one of these regions at a time. We need an operator that will allow only one thread to enter any one of regions at a time, suspending any others that try until the first has completed its task, and left the critical region.

A critical region is a code segment that, with respect to similar critical regions is (or should be) executed atomically. Variables that are shared amongst the processes are manipulated in the critical region, and no process must be allowed to change them while any other process is manipulating these variables.

Simply put, a critical region is one in which shared variables can be changed.

If two threads try to write different values to the same memory word at the same time, the net result will be one of the two values, not some combination of the values. Similarly, if one CPU tries to read a memory word at the same time another modifies it, the read will return either the old or new value--it will not see a ``half-changed'' memory location.

We assume the existence of Mutex class than contains two methods:

Lock:

which consists of all the steps required before the critical region is safe to enter.

UnLock:

which consists of the actions require after the critical region, to allow other processes to gain their own lock on the region.

Mutual exclusion then becomes associated with critical regions. Each critical region needs to be surrounded by a lock-unlock pair, and one common mutex operator must be used by all processes desiring to enter the critical region. The specifics of the lock and unlock operators are unimportant in terms of the abstract functionality provided by the mutex.

Mutex operator may exist as part of the library of functions provided by the operating system, or can be created using atomic primitives supported by the microprocessor. Mutexes can also be created by careful manipulation of shared variables, or by using other synchronization operators provided by the operating system. Mutexes can also be built into more complex synchronization operators that offer additional functionality or ease of use in some situations.

Dekker’s Solution to Mutual Exclusion:

This is the first correct solution proposed for the two-process case. Originally developed by Dekker in a different context, it was applied to the critical section problem by Dijkstra.

Both the turn variable and the status flags are combined in a careful way. The entry protocol begins as in Solution 3; we (the requesting process) set our flag and then check our neighbor's flag. If that flag is also set, the turn variable is used. There is no progress problem now because we know the other process is in, or before its critical region. If the turn is ours we wait for the flag of the other process to clear. No process will wait indefinitely with its flag set. If the turn belongs to the other process we wait, but we clear our flag before waiting to avoid blocking the other process. When the turn is given to us we reset our flag and proceed.

Global boolean array variable flag with two components both initialized to false;

Global integer turn = 0;
Process Pi , where i is 0 or 1

integer variable i with value 0 for P0 and 1 for P1 ;

flag[i] = true;

while (flags[1-i] == true)

if (turn != i)

flags[i] = false;

while (turn != i);

flags[i] = true;

critical region

turn = 1 - i;

flags[i] = false;

ANALYSIS: The mutual exclusion requirement is assured. No process will enter its critical region without setting its flag. Every process checks the other flag after setting its own. If both are set, the turn variable is used to allow only one process to proceed. .

The turn variable is only considered when both processes are using, or trying to use, the resource. Deadlock is not possible. No process waits with its flag continuously set, and one process always has the turn. The process with the turn will (eventually) discover the other flag free and will proceed.

Finally, bounded waiting is assured. Suppose Pj exits its critical region and re-enters immediately while Pi is waiting. Then the turn has been given to Pi , and the flag of Pi is set. Pj will clear its flag and wait, and Pi will proceed.

The mutex class constructed from this successful solution would look like:

class Mutex
{
boolean flag[2]
int turn;

Mutex ()
{
flag[0] = false;
flag[1] = false;
turn = 0;
}

void Lock (int i) // supply id of process as parameter.
{
flag[i] = true;
while (flags[1-i] == true)
{
if (turn != i)
{
flags[i] = false;
while (turn != i);
flags[i] = true;
}
}
}

void UnLock (int i) // supply id of process as parameter.
{
turn = 1 - i;
flags[i] = false;
}
}

RSA ALGORITHM
RSA MD5Source Code(rsa algorithm in Visual C++ source code)
RSA Algorithm program in JAVA (RSA Signature and Calculations) by Orlin from his java cryptography page
RSA Algorithm Implementation in C language
The Cigarette-Smokers Problem.

The Cigarette-smokers problem: Consider a system with three smoker processes and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper and matches. One of the smoker processes has an infinite supply of all the three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes the smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a program to synchronize the agent and the smokers.