/Race Conditions – I

Race Conditions – I

Operating systems, they’re fun and smart. That is why I prefer them and to some extent love them. However, computing revolution now involve larger processing power with the revolution of parallel processing and Heterogeneous Parallel Programming or Massively parallel processing. and even with micro-kernels coming up there’s still an old dilemma which is still fun to study and yet effective and still standing. which is race conditions.

This problem was first solved by Dekkar in late 1950s and was attributed to Edsger Dijkstra in 1965. Some of you might be asking what is that Race conditions thingy? the problem stands out when two cooperating processes try to use the same resource either sequentially or concurrently without causing malfunctioning or misreading a variable value. these conflicts occur due to random shared resource access whether it is read/write.

Race Conditions might not be any use for any of you, but I see that it is better to know the origins of Race conditions.

How can two processes sharing a resource misbehave?

from a sequential point of view, Two processes are writing a file. say each process is writing a sector and incrementing a shared sector seek variable which indicates where should a process write it’s next sector.

global SECTORSIZE = 512
Global SeekSectors
Process 1,2:
ReadFile file;
Seek SeekSectors X SECTORSIZE;
Write RandomData to file with SECTORSIZE;
SeekSectors ++;

this is a pseudo-code of both processes. Here the File and SeekSectors are shared data. the goal here is that each process write a sector in a file starting from where the other process ended.

Various conflicts can happen on several cases:

suppose Process 2 have just wrote a sector at index 7 in the file and incremented the SeekSectors variable to 8 and scheduler decides to put process 1 to execution. so process 1 starts to read file and seek number of sectors that has been written. at this point scheduler decides decides to put process 2 into execution, so process two starts and read sectors and seek the number of sectors which is 8. Here both processes 1 and 2 read the index of the next sector to write as 8. whoever executes or writes last will overwrite the data written by the earlier writer which is unacceptable. from this the idea of mutual exclusion came up which was to make the shared data exclusive for one process one it enters it’s critical region.

Critical region: Simply the place/code where process read/write a shared data.

There’s several solutions to this problem some are valid some are not: Locking Variables

The idea is to set a lock to a shared variable, lock is initialized to 0. If a process is entering a critical region. it sets the mutex to 1 so no other process can get into the critical region, However this scheme is also ineffcient, since a process can read the variable and get interrupted before it can set the variable to one, which will leave us with two processes in the critical region.

Strict alternation – taking turns

Here it’s done by taking turns, a variable which takes charge to process turns to enter a critical region is initalized to the 1st process number, say 0 and then every process checks the turn’s variable value, if it matches it’s index, i t’s allowed to enter critical region. This situation violates a rule, suppose process 0 finishes it’s critical region execution and sets the turn variable to 1 and process 1 enters and finishes quickly it’s critical region execution, and process 0 enter critical region again and sets variable to 1 <- Here turn =1 and both processes are not in the critical region. at this point process 0 will be blocked by process one which is busy in executing it’s non-critical region code. This is not allowed since a process in a non critical region is blocking a process from entering a critical region.

Peterson Solution

Here Peterson suggested to make an array of interested processes, and two calls, enter_region and leave_region. However, if process 0 is entering a critical region it calls enter_region which sets the turn variable to process index, and then check if the other process is interested, if not it executes region, if it is interested it spin locks until process 1 is not interested. suppose both processes call enter region together, both will set the turn variable to their index, whoever sets the turn variable last will be the actual turn value. now suppose that process 1 sets turn last, so now turn is set to 1, process 0 will execute it 0 times, and enter critical region and process 1 will hang.