4003-440-02 Operating Systems I Module 4. Thread Coordination -- Lecture Notes Prof. Alan Kaminsky -- Winter Quarter 2012 Rochester Institute of Technology -- Department of Computer Science The Need For Thread Coordination Class UpDown1 is the main program for the Up-Down Demo Version 1. Two threads share an integer variable. One thread increases the variable N times, the other thread decreases the variable N times, and the program prints the final value. There is no synchronization between the threads.   Usage: java edu.rit.os1.UpDown1 N   Package edu.rit.os1 Class UpDown1 -- source code   Demonstration, running time   Why the program gives the wrong answer   Moral: If multiple threads use the same shared variable, the threads must coordinate (synchronize) with each other, otherwise the program won't work! Critical Sections The concept of a critical section   Mechanisms for performing a critical section Semaphores Locks Monitors   Java platform classes Class java.util.concurrent.Semaphore Interface java.util.concurrent.locks.Lock Class java.util.concurrent.locks.ReentrantLock Semaphores, Part 1 A semaphore is an integer counter Created with some initial value Acquire operation: Block until value > 0, then decrement value Release operation: Increment value and unblock one blocked thread (if any) The acquire and release operations are atomic Any thread can acquire a semaphore Any thread can release a sempahore, not necessarily the thread that acquired the semaphore   How to implement a critical section with a semaphore   Class UpDown2 is the main program for the Up-Down Demo Version 2. Two threads share an integer variable. One thread increases the variable N times, the other thread decreases the variable N times, and the program prints the final value. The threads use a semaphore for synchronization.   Usage: java edu.rit.os1.UpDown2 N   Package edu.rit.os1 Class UpDown2 -- source code   Demonstration, running time   Thread synchronization overhead   Semaphores were invented by Dutch computer scientist Edsger Dijkstra (1930-2002), first published in a paper on his THE operating system in 1968 Different authors use different names for the semaphore operations: Acquire/release -- Java platform Wait/signal -- Silberschatz's textbook Down/up P/V -- Dijkstra's original names Locks, Part 1 A lock is an object with two states Created in the "unlocked" state Lock operation: Block until lock is unlocked, then go into the "locked" state The thread which completed the lock operation is said to be "holding the lock" Unlock operation: Go into the "unlocked" state and unblock one blocked thread (if any) The lock and unlock operations are atomic Any thread can lock a lock Only the thread that locked a lock can unlock the lock (unlike a semaphore) A thread can lock a lock multiple times -- then the thread must unlock the lock the same number of times (nested locking)   How to implement a critical section with a lock   Class UpDown3 is the main program for the Up-Down Demo Version 3. Two threads share an integer variable. One thread increases the variable N times, the other thread decreases the variable N times, and the program prints the final value. The threads use a lock for synchronization.   Usage: java edu.rit.os1.UpDown3 N   Package edu.rit.os1 Class UpDown3 -- source code   Demonstration, running time   Thread synchronization overhead Monitors, Part 1 A monitor is an object with methods, where each method is a critical section If multiple threads call methods on the same monitor, only one thread at a time is allowed to execute a method In other words, if one thread is executing a method, other threads attempting to call a method will block until the first thread returns   Class UpDown4 is the main program for the Up-Down Demo Version 4. Two threads share an integer variable. One thread increases the variable N times, the other thread decreases the variable N times, and the program prints the final value. The threads use a monitor for synchronization.   Usage: java edu.rit.os1.UpDown4 N   Package edu.rit.os1 Class UpDown4 -- source code   Demonstration, running time   Thread synchronization overhead Atomic Compare-and-Set Atomic compare-and-set (CAS) is a hardware operation (CPU instruction) performed on a variable X X.compareAndSet (expectedValue, updatedValue)     If (X == expectedValue):         X = updatedValue         Return true     Else:         Return false The hardware does all of the above atomically   CAS is provided as a method in the multiple thread safe wrapper classes in package java.util.concurrent.atomic   CAS can be used to synchronize multiple threads updating a shared variable AtomicInteger x = new AtomicInteger(); int oldvalue, newvalue; do { oldvalue = x.get(); newvalue = /*some formula using oldvalue*/; } while (! x.compareAndSet (oldvalue, newvalue)); CAS achieves thread synchronization without blocking -- therefore, reduced running time   Class UpDown5 is the main program for the Up-Down Demo Version 5. Two threads share an integer variable. One thread increases the variable N times, the other thread decreases the variable N times, and the program prints the final value. The threads use an atomic compare-and-set operation for synchronization.   Usage: java edu.rit.os1.UpDown5 N   Package edu.rit.os1 Class UpDown5 -- source code   Demonstration, running time   Thread synchronization overhead   Pros and cons of semaphores, locks, monitors, and CAS Ease and correctness of programming Performance Mutual Exclusion The concept of mutual exclusion -- mutually exclusive access by multiple threads to a shared resource   Class Printer1 is the main program for the Printer Demo Version 1. There is one printer, a 30 character/second AncientPrinter, and there are multiple threads generating print jobs. Each job generator prints jobs directly on the printer. The job generators use a semaphore for mutually exclusive access to the printer. The program runs until killed externally.   Usage: java edu.rit.os1.Printer1 username [ username . . . ]   Package edu.rit.os1 Class AncientPrinter -- source code Class Printer1 -- source code   Demonstration The Producer-Consumer Pattern -- Shared Queue With Semaphores Problem: While one thread is using the printer, the other threads cannot make any progress   Solution: Put a queue in between the producers and the consumer   Producer threads produce items which are consumed by consumer threads   Class Printer2 is the main program for the Printer Demo Version 2. There is one printer, a 30 character/second AncientPrinter, and there are multiple threads generating print jobs. Each job generator puts jobs into a FIFO queue. A separate spooler thread takes jobs out of the queue one at a time and prints them on the printer. The job generators and spooler use semaphores to synchronize with each other. The program runs until killed externally.   Usage: java edu.rit.os1.Printer2 username [ username . . . ]   Package edu.rit.os1 Class AncientPrinter -- source code Class Printer2 -- source code   Demonstration The Producer-Consumer Pattern -- Shared Bounded Queue With Semaphores Problem: The threads generate print jobs so fast that the queue sucks up all the memory in the machine, and the threads crash   Solution: Make it a bounded queue (circular buffer)   Class Printer3 is the main program for the Printer Demo Version 3. There is one printer, a 30 character/second AncientPrinter, and there are multiple threads generating print jobs. Each job generator puts jobs into a bounded FIFO queue of size max, a circular buffer. A separate spooler thread takes jobs out of the queue one at a time and prints them on the printer. The job generators and spooler use semaphores to synchronize with each other. The program runs until killed externally.   Usage: java edu.rit.os1.Printer3 max username [ username . . . ]   Package edu.rit.os1 Class AncientPrinter -- source code Class Printer3 -- source code   Demonstration The Producer-Consumer Pattern -- Shared Bounded Queue With Monitor Problem: All those semaphores -- even hidden inside the job queue class -- are a hassle to program and are bug-prone   Solution: Use a monitor instead of semaphores   Class Printer4 is the main program for the Printer Demo Version 4. There is one printer, a 30 character/second AncientPrinter, and there are multiple threads generating print jobs. Each job generator puts jobs into a bounded FIFO queue of size max, a circular buffer. A separate spooler thread takes jobs out of the queue one at a time and prints them on the printer. The circular buffer acts as a monitor to synchronize the job generators and spooler. The program runs until killed externally.   Usage: java edu.rit.os1.Printer4 max username [ username . . . ]   Package edu.rit.os1 Class AncientPrinter -- source code Class CircularBuffer -- source code Class Printer4 -- source code   Pattern for using conditions with monitors A method must block until some condition is true before proceeding Mark the method synchronized (like any monitor method) while (condition is not true) wait(); Code for the method notifyAll();   Demonstration The Producer-Consumer Pattern -- Multiple Producers, Multiple Consumers Question: What code do we have to change to let multiple printers get jobs from the queue?   Answer: Nothing! Just run more spooler threads.   Class Printer5 is the main program for the Printer Demo Version 4. There are numprinters printers, each a 30 character/second AncientPrinter, and there are multiple threads generating print jobs. Each job generator puts jobs into a bounded FIFO queue of size max, a circular buffer. A separate spooler thread for each printer takes jobs out of the queue one at a time and prints them on the printer. The circular buffer acts as a monitor to synchronize the job generators and spoolers. The program runs until killed externally.   Usage: java edu.rit.os1.Printer5 numprinters max username [ username . . . ]   Package edu.rit.os1 Class AncientPrinter -- source code Class CircularBuffer -- source code Class Printer5 -- source code   Demonstration Java Platform Classes for the Producer-Consumer Pattern Package java.util.concurrent Interface BlockingQueue Class ArrayBlockingQueue Class DelayQueue Class LinkedBlockingQueue Class PriorityBlockingQueue Class SynchronousQueue Generalizing Mutual Exclusion: The Reader-Writer Pattern Regular mutual exclusion A shared data structure Multiple threads accessing the data structure At most one thread at a time allowed to access the data structure   Generalized mutual exclusion A shared data structure Multiple reader threads and multiple writer threads To "read" means to use the data structure's state without changing it To "write" means to change the data structure's state Any number of reader threads are allowed to read the data structure at the same time At most one writer thread at a time is allowed to write the data structure If any readers are reading, no writer is allowed to write If any writer is writing, no reader is allowed to read   Rationale and typical uses of reader-writer   Implementing reader-writer with semaphores   Implementing reader-writer with monitors Package edu.rit.os1 Class ReaderWriterMap1 -- source code   Implementing reader-writer with locks Package java.util.concurrent.locks Interface ReadWriteLock Class ReentrantReadWriteLock Package edu.rit.os1 Class ReaderWriterDemo1 -- source code Class ReaderWriterMap2 -- source code Barrier Synchronization A barrier is exactly like the starting gate at a horse race One stall for each horse (thread) Each horse (thread) waits at the gate (barrier) until all stalls are full (all threads are there waiting) Then all horses (threads) proceed past the gate (barrier) simultaneously   Barriers are often used in parallel programs to synchronize all the threads at the end of a block of parallel code   Class Tweakness simulates the starting gate at the Tweakness Stakes, a fictional horse racing event. It demonstrates thread synchronization with a barrier.   Usage: java edu.rit.os1.Tweakness horse . . .   Package edu.rit.os1 Class Tweakness -- source code   Demonstration Thread Programming With Parallel Java Parallel Java (PJ) is an API and middleware for parallel programming in 100% Java on shared memory multiprocessor (SMP) parallel computers, cluster parallel computers, and hybrid SMP cluster parallel computers. PJ was developed by Professor Alan Kaminsky and his student Luke McOmber in the Department of Computer Science at the Rochester Institute of Technology. Parallel Java Library Javadoc   Class UC is a main program that counts lines, words, and bytes in the URLs given on the command line. It is a multi-threaded program using Parallel Java.   Usage: java edu.rit.pj.test.UC url . . .   Package edu.rit.pj.test Class UC -- source code   Demonstration Operating Systems I • 4003-440-02 • Winter Quarter 2012 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2008 Alan Kaminsky. All rights reserved. Last updated 16-Sep-2008. Please send comments to ark­@­cs.rit.edu.