Race Conditions in Operating Systems
Race Conditions
1
David Ferry
CSCI 3500 – Operating Systems
Saint Louis University
St. Louis, MO 63103
Definition
A
race condition
occurs whenever the output of a
computation changes depending on the timing of
execution.
Suppose x=0 initially:
Thread 1
Thread 2
u = x
v = x
u = u + 1
v = v * 2
x = u
x = v
What are the possible outcome values for x?
CSCI 3500 - Operating Systems
2
Linked List
push()
Example
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
CSCI 3500 - Operating Systems
3
push()
Race
Suppose two threads execute push() simultaneously
:
CSCI 3500 - Operating Systems
4
Thread 1:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
Thread 2:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
push()
Race
Suppose two threads execute push() simultaneously
:
CSCI 3500 - Operating Systems
5
Thread 1:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
Thread 2:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
current
push()
Race
Suppose two threads execute push() simultaneously
:
CSCI 3500 - Operating Systems
6
Thread 1:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
Thread 2:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
current
current
push()
Race
Suppose two threads execute push() simultaneously
:
CSCI 3500 - Operating Systems
7
Thread 1:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
Thread 2:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
HEAD
current
current
Data
Next
NULL
push()
Race
Suppose two threads execute push() simultaneously
:
CSCI 3500 - Operating Systems
8
Thread 1:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
Thread 2:
push( node* newNode ){node* current = HEAD;
while( current->next != NULL ){current = current->next;
}
current->next = newNode;
newNode->next = NULL;
}
HEAD
current
current
Data
Next
NULL
Data
Next
NULL
At least basic arithmetic is safe, right? What
could go wrong?
Thread 1:
Thread 2:
x++
x++
CSCI 3500 - Operating Systems
9
Not even increment is safe…
Suppose x=0 initially:
Thread 1:
Thread 2:
x++
x++
Becomes:
Thread 1:
Thread 2:
load x to register
load x to register
increment register
increment register
store reg. to memory
store reg. to memory
CSCI 3500 - Operating Systems
10
Race conditions in operating systems occur when the output of a computation changes based on the timing of execution, potentially leading to unexpected results. This phenomenon can be illustrated through examples involving concurrent threads and linked list operations. Learning about race conditions is crucial for ensuring the reliability and correctness of software systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Race Conditions David Ferry CSCI 3500 Operating Systems Saint Louis University St. Louis, MO 63103 1
Definition A race condition occurs whenever the output of a computation changes depending on the timing of execution. Suppose x=0 initially: Thread 1 u = x u = u + 1 x = u Thread 2 v = x v = v * 2 x = v What are the possible outcome values for x? CSCI 3500 - Operating Systems 2
Linked List push() Example Data Data Data HEAD Next Next Next NULL push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } CSCI 3500 - Operating Systems 3
push() Race Suppose two threads execute push() simultaneously: Data Data Data Next Next Next HEAD NULL Thread 1: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } Thread 2: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } CSCI 3500 - Operating Systems 4
push() Race Suppose two threads execute push() simultaneously: Data Data Data Next Next Next HEAD NULL current Thread 1: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } Thread 2: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } CSCI 3500 - Operating Systems 5
push() Race Suppose two threads execute push() simultaneously: Data Data Data Next Next Next HEAD NULL current current Thread 1: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } Thread 2: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } CSCI 3500 - Operating Systems 6
push() Race Suppose two threads execute push() simultaneously: Data Data Data Data Next Next Next Next HEAD NULL current current Thread 1: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } Thread 2: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } CSCI 3500 - Operating Systems 7
push() Race Suppose two threads execute push() simultaneously: Data Data Data Data Data Next Next Next Next Next NULL HEAD NULL current current Thread 1: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } Thread 2: push( node* newNode ){ node* current = HEAD; while( current->next != NULL ){ current = current->next; } current->next = newNode; newNode->next = NULL; } CSCI 3500 - Operating Systems 8
At least basic arithmetic is safe, right? What could go wrong? Thread 1: x++ Thread 2: x++ CSCI 3500 - Operating Systems 9
Not even increment is safe Suppose x=0 initially: Thread 1: x++ Thread 2: x++ Becomes: Thread 1: load x to register increment register store reg. to memory Thread 2: load x to register increment register store reg. to memory CSCI 3500 - Operating Systems 10
