Transcript powerpoint

Lecture Topics: 11/6
• More on threads
• Synchronization problem
– Too much milk
• Locks
Processes and Threads
• A full process includes numerous things:
– an address space (defining all the code and data pages)
– OS resources and accounting information
– a “thread of control”, which defines where the process is
currently executing (basically, the PC and registers)
• Creating a new process is costly, because of all of the
structures (e.g., PCB, page tables) that must be
allocated
• Communicating between processes is costly, because
most communication goes through the OS
Threads and Processes
• Some newer operating systems (Mach,
Chorus, NT) therefore support two entities:
– the process, which defines the address space
and general process attributes
– the thread, which defines a sequential execution
stream within a process
• A thread is bound to a single process. For
each process, however, there may be many
threads.
• Threads are much cheaper than processes,
but they are not free
How different OS’s support threads
= address space
= thread
example: MS/DOS
example: Xerox Pilot
example: Unix
example: Mach, OSF, Chorus, NT
Creating Threads
• What does the following print?
Thread1( void * voidPair ) {
cout << "Thread1 " << endl;
cout << "Thread1 " << endl;
}
Thread2( void * voidPair ) {
cout << "Thread2 " << endl;
cout << "Thread2 " << endl;
}
main() {
CreateThread(Thread1);
CreateThread(Thread2);
Sleep( 5000 );
}
Creating Threads (2)
• Sleep(0) yields the CPU to another thread
• What does this print?
Thread1( void * voidPair ) {
cout << "Thread1 " << endl;
cout << "Thread1 " << endl;
}
Sleep(0);
Sleep(0);
Thread2( void * voidPair ) {
cout << "Thread2 " << endl;
cout << "Thread2 " << endl;
}
Sleep(0);
Sleep(0);
main() {
CreateThread(Thread1);
CreateThread(Thread2);
Sleep( 5000 );
}
Synchronization Problem: Too
Much Milk
3:00
3:05
3:10
3:15
3:20
3:25
3:30
You
Look in fridge; no milk
Leave for store
Arrive at store
Buy milk
Arrive home; put milk away
Your Roommate
Look in fridge; no milk
Leave for store
Arrive at store
Buy milk
Arrive home; put milk away
Oh no!
Synchronization Definitions
• Atomic Operation—an operation that
cannot be interrupted (in MIPS read-modifywrite is not atomic)
• Synchronization—using atomic operations
to ensure cooperation among threads
• Mutual Exclusion—ensuring that only one
thread does a particular thing at a time. One
thread doing it excludes the other and vice
versa.
• Critical Section—piece of code that only
one thread can execute at once.
• Lock—prevents someone from doing
something
Modeling the Problem
• Model you and your roommate as
threads
• “Looking in the fridge” and “putting
away milk” are reading/writing a
variable in memory
• Current implementation
YOU:
YOUR ROOMMATE:
// look in fridge
if( milkAmount == 0 ) {
// buy milk
milkAmount++;
}
// look in fridge
if( milkAmount == 0 ) {
// buy milk
milkAmount++;
}
Correctness Properties
• What are the correctness properties of
the “Too Much Milk” problem
• Decomposed into safety and liveness
– safety—the program never does anything
bad
– liveness—the program eventually does
something good
Too Much Milk: Solution #1
• Basic idea
– Leave a note when you are buying milk
– Remove the note when you are done buying milk
if( milkAmount == 0 ){
if( !isNote ){
isNote = true;
milkAmount++;
isNote = false;
}
}
if( milkAmount == 0 ){
if( !isNote ){
isNote = true;
milkAmount++;
isNote = false;
}
}
• Why doesn’t this work?
• This solution is even worse because it only fails
occassionally
• very hard to debug
Too Much Milk: Solution #2
• Use labeled notes so we can leave a
note before checking the milk
Thread A:
Thread B:
isNoteA = true;
if( !isNoteB ) {
if( milkAmount == 0 ){
milkAmount++;
}
}
isNoteA = false;
isNoteB = true;
if( !isNoteA ) {
if( milkAmount == 0 ){
milkAmount++;
}
}
isNoteB = false;
• Does this work?
Locks
• A lock provides mutual exclusion
• A thread must acquire the lock before
entering a critical section of code
• A thread releases the lock after it leaves
the critical section
• Only one thread holds the lock at a time
• A lock is also called a mutex (for mutual
exclusion)
Lock::Acquire() {
Lock::Release() {
while( lockInUse ) {
lockInUse = false;
// wait
}
}
Naïve implementation
lockInUse = true;
that doesn’t work
}
Too Much Milk: Solution #3
• Here’s a working solution that uses a
Lock
MilkLock->Acquire();
if( milkAmount == 0 ){
milkAmount++;
}
}
MilkLock->Release();
MilkLock->Acquire();
if( milkAmount == 0 ){
milkAmount++;
}
}
MilkLock->Release();
• Implementing Acquire and Release
requires help from the CPU
Implementing Locks #1
• A flawed, but simple solution: disable
interrupts to prevent a context switch
Lock::Acquire() {
disable interrupts;
}
Lock::Release() {
enable interrupts;
}
• What about a multiprocessor?
• Kernel can’t get control back when interrupts
disabled
• Critical sections may be long, turning off
interrupts for a long time is bad
• This approach doesn’t work for more complex
synchronization primitives
Implementing Locks #2
• Better solution: only disable interrupts when
updating a flag
Lock::Lock() {
value = FREE;
}
Lock::Release() {
disable interrupts;
value = FREE;
enable interrupts;
}
Lock::Acquire() {
disable interrupts;
while(value != FREE){
enable interrupts;
disable interrupts;
}
value = BUSY;
enable interrupts
}
• Why do we need to disable interrupts at all?
• Why do we enable interrupts inside of the
while loop?
Atomic Memory Operations
• On a multiprocessor disabling interrupts
doesn’t work
• All modern processors provide an
atomic read-modify-write instruction
• These instructions allow locks to be
implemented on a multiprocessor
Examples of Atomic Operations
• Test and set (most architectures)—sets a
value to 1 and returns the previous value
• Exchange (x86)—swaps value between
register and memory
• Compare & swap (68000)—read value, if
value matches register, do exchange
• Load linked and store conditional (Alpha
& MIPS)—designed for load/store
architectures
– read value in one instruction (LL—load linked)
– do some operation
– when store occurs, check if value has been
modified in the meantime (SC—store conditional)
Locks with Test and Set
Lock::Acquire() {
Lock::Release() {
// while busy
value = FREE;
while( TestAndSet(value) == 1 ) {} }
}
• This works, but what is the problem?
Busy Waiting
• CPU cycles are consumed while the
thread is waiting for value to become 0
• This is very inefficient
• Big problem if the thread that is waiting
has a higher priority than the thread
that holds the lock
Locks with Minimal Busy Waiting
• Use a queue for threads waiting on the lock
• A guard variable provides mutual exclusion to
the queue
Lock::Acquire() {
while( TestAndSet(guard)
== 1 );
if( value != FREE ) {
Put self on wait queue;
go to sleep,
set guard = 0;
} else {
value = BUSY;
guard = 0;
}
}
Lock::Release() {
while( TestAndSet(guard)
== 1 );
if(anyone on wait queue){
move thread from wait
queue to ready queue;
} else {
value = FREE;
}
guard = 0;
}
Synchronization Summary
• Threads often work independently
• But sometimes threads need to access shared
data
• Access to shared data must be mutually
exclusive to ensure safety and liveness
• Locks are a good way to provide mutual
exclusion
• Next time we’ll see other synchronization
primitives—semaphores and condition
variables