The following program segment is used to manage a finite number of instances of
ID: 3703600 • Letter: T
Question
The following program segment is used to manage a finite number of instances of a resource such as a commercial software license. When a user starts the application, the license count is decremented. When it is terminated, the count is incremented. If all licenses are in use, requests to start the application are denied. There is no queuing of requests. Using a general solution, the maximum and available number of licenses is defined as follows
#define MAX_RESOURCES 5
int available_resources = MAX_RESOURCES;
When a process wishes to obtain a license, it invokes the decrease_count() function passing in 1:
// Decrease available_resources by count resources
// return 0 if no resources are available, 1 if successful
int decrease_count(int count) {
if (available_resources >= count) {
available_resources -= count;
return 1;
}
return 0;
}
When a process wants to return a number of resources, it calls increase_count() with the count.
// Increases available_resources by count
void increase_count(int count) {
available_resources += count;
}
The preceding code produces a race condition. Do the following:
Identify the location (or locations) in the code where the race condition occurs. (10 pts)
Identify the data involved in the race condition. (5 pts)
Using a semaphore, fix the race condition. It is OK to modify decrease_count so that the calling process is blocked until sufficient resources are available.
(Please type if possible, I find it hard to understand some of the handwriting on here)
Also explination is greatly appreciated
Explanation / Answer
Concurrent access to shared data may result in data inconsistency which leads to race condition.
In order to maintain data consistency certain mechanisms are required to ensure the orderly execution of cooperating processes
Cooperating process can affect or be affected by other processes, including sharing data.
Here processes increase_count and decrease_count are co-operating processes.
Here the variable available_resources is an integer count that keeps track of the number of licenses. Initially, available_resources is set to MAX_RESOURCES which is 5. It is decremented by the decrease_count function when a process wishes to obtain a license and is incremented by the increase_count function when a process wants to return a number of resources. The number of resources are indicated by variable count.
The functions decrease_count is given below
int decrease_count(int count)
{
if (available_resources >= count)
{
available_resources -= count;
return 1;
}
return 0;
}
The functions increase_count is given below
void increase_count(int count)
{
available_resources += count;
}
Race condition occurs when shared variable is modified. Here the shared variable is available_resources. This variable is decremented as available_resources -= count in decrease_count function. Also this variable is incremented as available_resources += count in increase_count function.
The data involved in race condition is the variable available_resources.
available_resources -= count could be implemented as
register1 = available_resources
register2=count
register1 = register1 - register2
available_resources = register1
available_resources += count could be implemented as
register1 = available_resources
register2=count
register1 = register1 + register2
available_resources = register1
Race condition is illustrated below. Consider this execution interleaving with available_resources =5 and “count = 1” initially:
S0: decrease_count execute register1 = available_resources {register1 = 5}
S1: decrease_count execute register2 = count {register2 = 1}
S2: decrease_count execute register1 = register1 - register2 {register1 = 4}
S3: increase_count execute register1 = available_resources {register1 = 5}
S4: increase_count execute register2 = count {register2 = 1}
S5: increase_count execute register1 = register1 + register2 {register1 = 6}
S6: decrease_count execute available_resources = register1 { available_resources = 4}
S7: decrease_count execute available_resources = register1 { available_resources = 6}
Here two processes access and manipulate the same data concurrently. And the outcome of the execution depends on the particular order in which access takes place. This situation is race condition.
Solution using semaphore
Proposed by Dijkstra, introducing a new type of variable
Atomic Action
¬ A single, indivisible action
Down (P)
¬ Check a semaphore to see whether it’s 0, if so, sleep; else, decrements the value and go on
Up (v)
¬ Increments the value of the semaphore.
Semaphore can only be accessed via two indivisible (atomic) operations
wait (S) {
while S <= 0
; // no-op
S--;
}
signal (S) {
S++;
}
To prevent race condition we use a semaphore variable, mutex. This mutex prevent access the variable available_resources at the same time. Its initial value 1 (binary semaphore)
Before accessing shared variable mutex is decremented using wait. Then shared variable is modified. After that mutex is incremented using signal. When one process is accessing shared variable and if other process request this shared variable, it has to do wait operation. Then the second process has to wait until the first process completes its execution and increment the value of semaphore variable mutex.
Here the semaphore is used in decrease_count function as follows
semaphore mutex = 1;
int decrease_count(int count)
{
if (available_resources >= count)
{
wait(&mutex);
available_resources -= count;
signal(&mutex);
return 1;
}
return 0;
}
Also the semaphore is used in increase_count function as follows
semaphore mutex = 1;
void increase_count(int count)
{
wait(&mutex);
available_resources += count;
signal(&mutex);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.