Requirements of Synchronization Mechanism

We have two types of requirement: primary and secondary. As the name says primary requirements should be met first and then we check the secondary.
However if the secondary are not met then also the solution is disqualified.

Primary Requirements:

We have following requirements under this category:
1. Mutual Exclusion: This condition says that the resource/critical section must be accessed by one process at a time. Example: Suppose you went to shopping mall and there we have dressing rooms, so this above condition says that one person should use it at a time.
2. Progress: Let’s say there are two processes and one process does not want to go into critical section then it should not prevent other process to go into critical section. So when we see this case happening we say that progress is not there and solution is not qualified. Example: Taking the dressing room example, suppose if someone is not using it then he/she should let others use it.

Secondary Requirements:

We have following requirements under this category:
1. Bounded Waiting: When the critical section is occupied by some process then the other process’s waiting time should be definite. So we will say bounded waiting is good. As the term is clear by its name that waiting should be bounded. Example: If someone is waiting for the dressing room then his number should come in definite period of time. It should not be like he is waiting all the time. 2. Portability or Architectural Neutrality: Means the solution should be working irrespective of the system architecture.

Synchronization Mechanisms:

We have two types of synchronization mechanism, 1. With Busy Waiting and 2. Without Busy Waiting

1. With Busy Waiting: This solution says when someone is inside the critical section then it should continuously wait outside. Example: Suppose you went to someone’s house and you knocked on the door and that person is not inside the house. So you are continuously knocking the door will termed as busy waiting.
2. Without Busy Waiting: This solution says when someone is inside the critical section then it should not continuously wait outside. It should take small breaks and then come back because that will consume CPU time which is useless. Example: Suppose you went to someone’s house and you knocked on the door and that person is not inside the house. And you are not continuously knocking the door, you are taking small breaks/nap and then again tried, this scenario will be termed as “a solution without busy waiting”.

Lock Variables

It is busy waiting solution to handle critical section. The following points will make the approach more clear:
  1. It is implemented in user mode of the operating system. For user mode click here.
  2. This solution can used for more than 2 processes
  3. It is busy waiting solution.
Note: Nowadays solution without busy waiting is preferred. It has three section as:
Here
Lock = 0 means process can enter the dressing room 
Lock = 1 means critical section is occupied with some other process.
We will understand this Lock mechanism with dressing room augmentation. Suppose nine minions are opting for dressing room. [Here idea of a queue is not implemented till now, we will come to that point in later approaches].
We are having a tag on the dressing room’s door to show occupied or vacant, which is the function of Lock variable. Let’s 1 minion got the chance and made Lock =1 and went into the dressing room/critical section. And rest of the minions will not get the chance as the dressing room is occupied. This will be made sure by the Line number 1 in the code above. So rest of the minions just wait which some of them do not like as it clear from the picture.

The Problem:

Suppose every minions came and saw that tag is vacant i. e. Lock =1 and then got preempted/indulge in some other activity, and when they come back then they will not again see the Lock =1 or the tag is Vacant or not. So every minion will go into the dressing all at once which is very bad right?
I mean this should not happen. This is violation of the primary requirement “Mutual Exclusion”.




Quantitative Aptitude
Reasoning
Programming
Interview