mutual-exclusion

Mutual Exclusion

This is the condition in which two or more process try to access a single shared resources at the same time. The sequence of accessing the resource matters. If the sequence changes, the result can vary and not wanted.

There are various proposed solutions to this problem. With each solution, there are sticking problem with them also.

1. Disabling interrupts

When the process goes into critical region, it stops responding to clock interrupts.

Problems

Giving the ability to enable/disable interrupts to user space is not a wise idea.
What if process disables the interrupts but never enables it?

It is better for kernel level operations instead of user space.

2. Lock variables

Process sets the lock variable to let other processes know that the sharing resource is in use.

If you notice, that variable is also a shared resource which is getting used to access another shared resource. How would this variable will be managed?

3. Strict turns

Processes takes turns for getting into their critical regions. Before going into critical region, it has to check if the turn has come. If not, process goes into loop until the turns comes.

turn = 0;

Process A

while (TRUE) {
    while (turn != 0)
    critical_region();
    turn = 1;
    normal_region();
}

Process B

while (TRUE) {
    while (turn != 1)
    critical_region();
    turn = 0;
    normal_region();
}

Initially, turn is 0, so process A executes critical region and changes turn to 1 . Process B starts executing critical region and changes turn to 0. This goes on like this.

It has a problem, one process executing non critical region can case another process to block executing its critical region.

4. Peterson’s solution

Solution proposed by Peterson in which he defines two functions in C, which are called before and after the execution of critial regions.

enter_region is called before going into critical region. exit_region is called after the critical region.

5. TSL instruction

The problem with lock variable was that a process can have old value of lock variable and can go into critical region at the same time.

enter_region:
    LOAD LOCK, REG
    MOVE LOCK, #1
    CMP REG, #0
    JNE enter_region
    RET

exit_region:
    MOVE LOCK, #0
    RET

It has a problem. Let’s say process A calls enter_region which executes first assembly instruction and gets suspended. Another process calls enter_region and sets LOCK to 1. Previous process again starts executing but has old value of LOCK.

So, we the reading and settings of LOCK variable should be atomic in nature. This can be accomplished using TSL (Test and Set Lock) instruction. It loads value and sets the value in one shot. It blocks the memory bus so that no other process access the LOCK variable.

enter_region:
    TSL REG, LOCK
    CMP REG, #0
    JNE enter_region
    RET

bitPhile

Explorer