What is progress and bounded waiting in critical section?

I was reading Critical Section Problem from Operating System Concepts by Peter B. Galvin. According to it

1) Progress is : If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.

And

2) Bounded waiting is : There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

I am not understanding what the author wants to say in both the cases.

Could you please make me understand by giving a proper example related to this definition.

Thank You.

First, let me introduce some terminology. A critical section (CS) is a sequence of instructions that can be executed by at most one process at the same time. When using critical sections, the code can be broken down into the following sections:

// Some arbitrary code (such as initialization).

EnterCriticalSection(cs);

// The code that constitutes the CS.
// Only one process can be executing this code at the same time. 

LeaveCriticalSection(cs);

// Some arbitrary code. This is called the remainder section.

The first section contains some code such as initialization code. We don't have a name for that section. The second section is the code that tries to enter the CS. The third section is the CS itself. The fourth section is the code that leaves the critical section. The fifth and last section is called the remainder section which can contain any code. Note that the CS itself can be different between processes (consider for example a process that that receives requests from a client and insert them in a queue and another process that processes these requests).

To make sure that an implementation of critical sections works properly, there are three conditions that must be satisfied. You mentioned two of them (which I will explain next). The third is mutual exclusion which is obviously vital. It's worth noting that mutual exclusion applies only to the CS and the leave section. However, the other three sections are not exclusive.

The first condition is progress. The purpose of this condition is to make sure that either some process is currently in the CS and doing some work or, if there was at least one process that wants to enter the CS, it will and then do some work. In both cases, some work is getting done and therefore all processes are making progress overall.

> Progress: If no process is executing in its critical section and > some processes wish to enter their critical sections, then only those > processes that are not executing in their remainder section can > participate in deciding which will enter its critical section next, > and this selection cannot be postponed indefinitely.

Let's understand this definition sentence by sentence.

> If no process is executing in its critical section

If there is a process executing in its critical section (even though not stated explicitly, this includes the leave section as well), then this means that some work is getting done. So we are making progress. Otherwise, if this was not the case...

> and some processes wish to enter their critical sections

If no process wants to enter their critical sections, then there is no more work to do. Otherwise, if there is at least one process that wishes to enter its critical section...

> then only those processes that are not executing in their remainder section

This means we are talking about those processes that are executing in either of the first two sections (remember, no process is executing in its critical section or the leave section)...

> can participate in deciding which will enter its critical section next,

Since there is at least one process that wishes to enter its CS, somehow we must choose one of them to enter its CS. But who's going to make this decision? Those process who already requested permission to enter their critical sections have the right to participate in making this decision. In addition, those processes that may wish to enter their CSs but have not yet requested the permission to do so (this means that they are in executing in the first section) also have the right to participate in making this decision.

> and this selection cannot be postponed indefinitely.

This states that it will take a limited amount of time to select a process to enter its CS. In particular, no deadlock or livelock will occur. So after this limited amount of time, a process will enter its CS and do some work, thereby making progress.

Now I will explain the last condition, namely bounded waiting. The purpose of this condition is to make sure that every process gets the chance to actually enter its critical section so that no process starves forever. However, please note that neither this condition nor progress guarantees fairness. An implementation of a CS doesn't have to be fair.

> Bounded waiting: There exists a bound, or limit, on the number of > times other processes are allowed to enter their critical sections > after a process has made request to enter its critical section and > before that request is granted.

Let's understand this definition sentence by sentence, starting from the last one.

> after a process has made request to enter its critical section and > before that request is granted.

In other words, if there is a process that has requested to enter its CS but has not yet entered it. Let's call this process P.

> There exists a bound, or limit, on the number of > times other processes are allowed to enter their critical sections

While P is waiting to enter its CS, other processes may be waiting as well and some process is executing in its CS. When it leaves its CS, some other process has to be selected to enter the CS which may or may not be P. Suppose a process other than P was selected. This situation might happen again and again. That is, other processes are getting the chance to enter their CSs but never P. Note that progress is being made, but by other processes, not by P. The problem is that P is not getting the chance to do any work. To prevent starvation, there must be a guarantee that P will eventually enter its CS. For this to happen, the number of times other processes enter their CSs must be limited. In this case, P will definitely get the chance to enter its CS.

I would like to mention that the definition of a CS can be generalized so that at most N processes are executing in their critical sections where N is any positive integer. There are also variants of reader-writer critical sections.

Mutual exclusion

No two process can be simultaneously present inside critical section at any point in time, only one process can enter into a critical section at any point in time.

Image for Progress:

Progress

No process running outside the critical section should block the other interesting process from entering into a critical section when in fact the critical section is free. In this image, P1 (which is running outside of critical section )is blocking P2 from entering into the critical section where in fact critical section is free.

Bounded waiting

No process should have to wait forever to enter into the critical section. there should be a boundary on getting chances to enter into the critical section. If bounded waiting is not satisfied then there is a possibility of starvation.

Note
No assumption is related to H/W or processing speed.

Overall, a solution to the critical section problem must satisfy three conditions:

1. Mutual Exclusion: Exclusive access of each process to the shared memory. Only one process can be in it's critical section at any given time.

2. Progress: If no process is in its critical section, and if one or more threads want to execute their critical section then any one of these threads must be allowed to get into its critical section.

3. Bounded Waiting: After a process makes a request for getting into its critical section, there is a limit for how many other processes can get into their critical section, before this process's request is granted. So after the limit is reached, system must grant the process permission to get into its critical section. The purpose of this condition is to make sure that every process gets the chance to actually enter its critical section so that no process starves forever.

Requirements to tell synchronisation solution is correct or not

1). Mutual exclusion:-at any point of time only one process should be present inside critical section.

2). Progress:-the process which is outside critical section and who do not want to enter critical section then such process should not stop the other interested process to enter into its critical section. If a process is getting success to stop other interested process then the progress is not guaranteed or else it is guaranteed. Critical section should be free.

3). Bounded waiting:-the waiting time of a process outside a critical section should be Limited.

4). Architectural neutral:-there is no assumption regarding hardware

(Definition in simple words)

Bounded Waiting :- when only single process gets the turn to enter into critical section every time indeed other process are also interested to enter into critical section.