Monday, May 2, 2011

Process Synchronization

The dining philosophers problem:

This example will illustrate the correspondance between the OOP paradigm, the formal description techniques and validation.

The goal of the problem is to create a program that simulates the behavior of 5 philosophers gathered around a table to think and eat. Each philosopher thinks for a while, then eats then thinks again, and so on, independently of the others. Each philosopher has one fork, but needs two forks to eat. Thus the philosophers decide to share their forks. When a philosopher wants to eat, he takes the fork on his left, when it is available, then the fork on his right, eats, and then puts both forks back.

After the philosophers have thought and eaten several times, it may happen that all philosophers simultaneously decide to eat. They take their left fork, and find the right fork already taken by their right neighbor. In this case, if nothing has been foreseen, the philosophers will stay in that situation (deadlock) indefinitely. The program should avoid that situation.

The descriptions below are based on a free interpretation of the OMT models. This example puts the emphasis on the dynamic, and the functional models, which are less well understood than the object model.

Object model:

Object model:
The philosophers have no data, only a behavior, described below.
The forks have only one piece of data, the boolean indicating when the 
fork is available, and two operations that act upon it.
201 class Fork {
202 int available;
203 public:
204 void get() { }
205 void put() { }
206 };

Dynamic model:
The graphs of Figure 4 model the behavior of a fork and the one of a philosopher. The first delay in the philosopher's graph represents the time during which the philosopher thinks. The second the delay during which he eats. Fi.get represents the action of taking the fork number i .

Functional model (data flow, sources and sinks of signals):
Usually, one would rather embed these objects within a entity-relationship schema. However, as the philosophers and the forks are not a passive database on which one simply execute operations, the functional diagram is closer to reality. Moreover, this specification can be coded and compiled in a straight manner. The arrows represent signal or message passing, and they can be implemented as calls to (active object) methods.

Fig: Data flow of the dining philosophers

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.


Study and implementation of RSA Algorithm using C programming language.

In a classic cryptosystem in order to make sure that nobody, except the intended recipient, deciphers the message, the people involved had to strive to keep the key secret. In a public-key cryptosystem. The public key cryptography solves one of the most vexing problems of all prior cryptography: the necessity of establishing a secure channel for the exchange of the key.

RSA algorithm is a public-key cryptosystem defined by Rivest, Shamir, and Adleman. The scheme is as follows:
Let p and q be distinct large primes and let n be their product. Assume that we also computed two integers, d (for decryption) and e (for encryption) such that d * e 1 (mod ø(n)) where ø(n) is the number of positive integers smaller than n that have no factor except 1 in common with n the integers n and e are made public, while p, q, and d are kept secret.

Let m be the message to be sent, where m is a positive integer less than and relatively prime to n. A plaintext message is easily converted to a number by using either the alphabet position of each letter (a=01, b=02, ..., z=26) or using the standard ASCII table. If necessary (so that m<n), the message can be broken into several blocks.

The encoder computes and sends the number
m' = m^e mod n
To decode, we simply compute
e^d mod n
Now, since both n and e are public, the question arises: can we compute from them d? The answer: it is possible, if n is factored into prime numbers.
The security of RSA depends on the fact that it takes an impractical amount of time to factor large numbers.

No comments:

Post a Comment