Silberschatz,Galvin,and Gagne?19997.1Applied Operating System Concepts
Module 7,Process Synchronization
Background（背景）
The Critical-Section Problem （临界区问题）
Synchronization Hardware （同步的硬件实现）
Semaphores （信号量）
Classical Problems of Synchronization（ 经典同步问题）
Monitors （管程）
Java Synchronization （ Java中的同步机制）
Synchronization in Solaris 2 （ Solaris 2的同步机制）
Synchronization in Windows NT （ Windows NT的同步机制）
Silberschatz,Galvin,and Gagne?19997.2Applied Operating System Concepts
Background
Concurrent access to shared data may result in data
inconsistency（对共享数据的并发访问可能导致数据的不一致性）,
Maintaining data consistency requires mechanisms to ensure
the orderly execution of cooperating processes（要保持数据的一致性，就需要一种保证并发进程的正确执行顺序的机制）,
Shared-memory solution to bounded-butter problem (Chapter
4) has a race condition on the class data count （ [第 4章中 ]解决有界缓冲区问题的共享内存方法在类数据 count 上将一起竞争条件）
Silberschatz,Galvin,and Gagne?19997.3Applied Operating System Concepts
Bounded Buffer
public class BoundedBuffer {
public void enter(Object item) {
// producer calls this method
}
public Object remove() {
// consumer calls this method
}
// potential race condition on count
private volatile int count;
}
Silberschatz,Galvin,and Gagne?19997.4Applied Operating System Concepts
enter() Method
// producer calls this method
public void enter(Object item) {
while (count == BUFFER_SIZE); // do nothing
// add an item to the buffer
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
}
Silberschatz,Galvin,and Gagne?19997.5Applied Operating System Concepts
remove() Method
// consumer calls this method
public Object remove() {
Object item;
while (count == 0); // do nothing
// remove an item from the buffer
--count;
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
return item;
}
Silberschatz,Galvin,and Gagne?19997.6Applied Operating System Concepts
Solution to Critical-Section Problem
1,Mutual Exclusion,If process Pi is executing in its critical section,then
no other processes can be executing in their critical sections（互斥。假定进程 Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外）,
2,Progress,If no process is executing in its critical section and there exist
some processes that wish to enter their critical section,then the selection
of the processes that will enter the critical section next cannot be
postponed indefinitely（有空让进。临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间
）,
3,Bounded Waiting,A bound must exist on the number of times that other
processes are allowed to enter their critical sections after a process has
made a request to enter its critical section and before that request is
granted（有限等待。在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区前的等待时间必须是有限的）,
Assume that each process executes at a nonzero speed （假定每个进程都以非零的的速率执行）,
No assumption concerning relative speed of the n processes（没有任何关于这 n个进程相对执行速率的假定 ）,
Silberschatz,Galvin,and Gagne?19997.7Applied Operating System Concepts
Worker Thread
public class Worker extends Thread {
public Worker(String n,int i,MutualExclusion s) {
name = n;
id = i;
shared = s;
}
public void run() { /* see next slide */ }
private String name;
private int id;
private MutualExclusion shared;
}
Silberschatz,Galvin,and Gagne?19997.8Applied Operating System Concepts
run() Method of Worker Thread
public void run() {
while (true) {
shared.enteringCriticalSection(id);
// in critical section code
shared.leavingCriticalSection(id);
// out of critical section code
}
}
Silberschatz,Galvin,and Gagne?19997.9Applied Operating System Concepts
MutualExclusion Abstract Class
public abstract class MutualExclusion {
public static void criticalSection() {
// simulate the critical section
}
public static void nonCriticalSection() {
// simulate the non-critical section
}
public abstract void enteringCriticalSection(int t);
public abstract void leavingCriticalSection(int t);
public static final int TURN_0 = 0;
public static final int TURN_1 = 1;
}
Silberschatz,Galvin,and Gagne?19997.10Applied Operating System Concepts
Testing Each Algorithm
public class TestAlgorithm
{
public static void main(String args[]) {
MutualExclusion alg = new Algorithm_1();
Worker first = new Worker("Runner 0",0,alg);
Worker second = new Worker("Runner 1",1,alg);
first.start();
second.start();
}
}
Silberschatz,Galvin,and Gagne?19997.11Applied Operating System Concepts
Algorithm 1
public class Algorithm_1 extends MutualExclusion {
public Algorithm_1() {
turn = TURN_0;
}
public void enteringCriticalSection(int t) {
while (turn != t)
Thread.yield();
}
public void leavingCriticalSection(int t) {
turn = 1 - t;
}
private volatile int turn;
}
Silberschatz,Galvin,and Gagne?19997.12Applied Operating System Concepts
Algorithm 2
public class Algorithm_2 extends MutualExclusion {
public Algorithm_2() {
flag[0] = false;
flag[1] = false;
}
public void enteringCriticalSection(int t) {
// see next slide
}
public void leavingCriticalSection(int t) {
flag[t] = false;
}
private volatile boolean[] flag = new boolean[2];
}
Silberschatz,Galvin,and Gagne?19997.13Applied Operating System Concepts
Algorithm 2 – enteringCriticalSection()
public void enteringCriticalSection(int t) {
int other = 1 - t;
flag[t] = true;
while (flag[other] == true)
Thread.yield();
}
Silberschatz,Galvin,and Gagne?19997.14Applied Operating System Concepts
Algorithm 3
public class Algorithm_3 extends MutualExclusion {
public Algorithm_3() {
flag[0] = false;
flag[1] = false;
turn = TURN_0;
}
public void enteringCriticalSection(int t) {/* see next slides */ }
public void leavingCriticalSection(int t) {{/* see next slides */ }
private volatile int turn;
private volatile boolean[] flag = new boolean[2];
}
Silberschatz,Galvin,and Gagne?19997.15Applied Operating System Concepts
Algorithm 3 – enteringCriticalSection()
public void enteringCriticalSection(int t) {
int other = 1 - t;
flag[t] = true;
turn = other;
while ( (flag[other] == true) && (turn == other) )
Thread.yield();
}
Silberschatz,Galvin,and Gagne?19997.16Applied Operating System Concepts
Algo,3 – leavingingCriticalSection()
public void leavingCriticalSection(int t) {
flag[t] = false;
}
Silberschatz,Galvin,and Gagne?19997.17Applied Operating System Concepts
Synchronization Hardware
public class HardwareData {
public HardwareData(boolean v) {
data = v;
}
public boolean get() {
return data;
}
public void set(boolean v) {
data = v;
}
private boolean data;
}
Silberschatz,Galvin,and Gagne?19997.18Applied Operating System Concepts
Test-and-Set Instruction (in Java)
public class HardwareSolution
{
public static boolean testAndSet(HardwareData target) {
HardwareData temp = new HardwareData(target.get());
target.set(true);
return temp.get();
}
}
Silberschatz,Galvin,and Gagne?19997.19Applied Operating System Concepts
Thread using Test-and-Set
HardwareData lock = new HardwareData(false);
while (true) {
while (HardwareSolution.testAndSet(lock))
Thread.yield(); // do nothing
// now in critical section code
lock.set(false);
// out of critical section
}
Silberschatz,Galvin,and Gagne?19997.20Applied Operating System Concepts
Swap instruction
public static void swap(HardwareData a,HardwareData b) {
HardwareData temp = new HardwareData(a.get());
a.set(b.get());
b.set(temp.get());
}
Silberschatz,Galvin,and Gagne?19997.21Applied Operating System Concepts
Thread using Swap
HardwareData lock = new HardwareData(false);
HardwareData key = new HardwareData(true);
while (true) {
key.set(true);
do {
HardwareSolution.swap(lock,key);
} while (key.get() == true);
// now in critical section code
lock.set(false);
// out of critical section
}
Silberschatz,Galvin,and Gagne?19997.22Applied Operating System Concepts
Semaphore
Synchronization tool that does not require busy waiting（一种不需要忙等待的同步工具）,
Semaphore S – integer variable（信号量 S– 整型变量）
can only be accessed via two indivisible (atomic) operations
（仅能通过两个不可分割的 [原子 ]操作访问）
P (S),while S? 0 do no-op;
S--;
V(S),S++;
Silberschatz,Galvin,and Gagne?19997.23Applied Operating System Concepts
Semaphore as General Synchronization Tool
Semaphore S; // initialized to 1
P(S);
CriticalSection()
V(S);
Silberschatz,Galvin,and Gagne?19997.24Applied Operating System Concepts
Semaphore Eliminating Busy-Waiting
P(S) {
value--;
if (value < 0) {
add this process to list
block
}
}
V(S) {
value++;
if (value <= 0) {
remove a process P from list
wakeup(P);
}
}
Silberschatz,Galvin,and Gagne?19997.25Applied Operating System Concepts
Synchronization Using Semaphores
public class FirstSemaphore {
public static void main(String args[]) {
Semaphore sem = new Semaphore(1);
Worker[] bees = new Worker[5];
for (int i = 0; i < 5; i++)
bees[i] = new Worker(sem,"Worker " + (new Integer(i)).toString()
);
for (int i = 0; i < 5; i++)
bees[i].start();
}
}
Silberschatz,Galvin,and Gagne?19997.26Applied Operating System Concepts
Worker Thread
public class Worker extends Thread {
public Worker(Semaphore) { sem = s;}
public void run() {
while (true) {
sem.P();
// in critical section
sem.V();
// out of critical section
}
}
private Semaphore sem;
}
Silberschatz,Galvin,and Gagne?19997.27Applied Operating System Concepts
Deadlock and Starvation
Deadlock – two or more processes are waiting indefinitely for
an event that can be caused by only one of the waiting
processes（死锁 – 两个或多个进程无限期地等待一个事件的发生，
而该事件正是由其中的一个等待进程引起的）,
Let S and Q be two semaphores initialized to 1（ S和 Q是两个初值为 1的信号量）
P0 P1
P(S); P(Q);
P(Q); P(S);
V(S); V(Q);
V(Q) V(S);
Starvation – indefinite blocking,A process may never be
removed from the semaphore queue in which it is suspended（
饥饿 – 无限期地阻塞。进程可能永远无法从它等待的信号量队列中移去）,
Silberschatz,Galvin,and Gagne?19997.28Applied Operating System Concepts
Two Types of Semaphores
Counting semaphore – integer value can range over an
unrestricted domain（计数信号量 –变化范围没有限制的整型值）,
Binary semaphore – integer value can range only
between 0
and 1; can be simpler to implement（二值信号量 – 变化范围仅限于 0和 1的信号量；容易实现）,
Can implement a counting semaphore S as a binary
semaphore（可以将计数信号量 S用作二值信号量）,
Silberschatz,Galvin,and Gagne?19997.29Applied Operating System Concepts
Classical Problems of Synchronization
Bounded-Buffer Problem
（有限缓冲区问题）
Readers and Writers Problem
（读者写者问题）
Dining-Philosophers Problem
（哲学家就餐问题）
Silberschatz,Galvin,and Gagne?19997.30Applied Operating System Concepts
Bounded-Buffer Problem
public class BoundedBuffer {
public BoundedBuffer() { /* see next slides */ }
public void enter() { /* see next slides */ }
public Object remove() { /* see next slides */ }
private static final int BUFFER_SIZE = 2;
private Semaphore mutex;
private Semaphore empty;
private Semaphore full;
private int in,out;
private Object[] buffer;
}
Silberschatz,Galvin,and Gagne?19997.31Applied Operating System Concepts
Bounded Buffer Constructor
public BoundedBuffer() {
// buffer is initially empty
count = 0;
in = 0;
out = 0;
buffer = new Object[BUFFER_SIZE];
mutex = new Semaphore(1);
empty = new Semaphore(BUFFER_SIZE);
full = new Semaphore(0);
}
Silberschatz,Galvin,and Gagne?19997.32Applied Operating System Concepts
enter() Method
public void enter(Object item) {
empty.P();
mutex.P();
// add an item to the buffer
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
mutex.V();
full.V();
}
Silberschatz,Galvin,and Gagne?19997.33Applied Operating System Concepts
remove() Method
public Object remove() {
full.P();
mutex.P();
// remove an item from the buffer
Object item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
mutex.V();
empty.V();
return item;
}
Silberschatz,Galvin,and Gagne?19997.34Applied Operating System Concepts
Readers-Writers Problem,Reader
public class Reader extends Thread {
public Reader(Database db) {
server = db;
}
public void run() {
int c;
while (true) {
c = server.startRead();
// now reading the database
c = server.endRead();
}
}
private Database server;
}
Silberschatz,Galvin,and Gagne?19997.35Applied Operating System Concepts
Readers-Writers Problem,Writer
public class Writer extends Thread {
public Writer(Database db) {
server = db;
}
public void run() {
while (true) {
server.startWrite();
// now writing the database
server.endWrite();
}
}
private Database server;
}
Silberschatz,Galvin,and Gagne?19997.36Applied Operating System Concepts
Readers-Writers Problem (cont)
public class Database
{
public Database() {
readerCount = 0;
mutex = new Semaphore(1);
db = new Semaphore(1);
}
public int startRead() { /* see next slides */ }
public int endRead() { /* see next slides */ }
public void startWrite() { /* see next slides */ }
public void endWrite() { /* see next slides */ }
private int readerCount; // number of active readers
Semaphore mutex; // controls access to readerCount
Semaphore db; // controls access to the database
}
Silberschatz,Galvin,and Gagne?19997.37Applied Operating System Concepts
startRead() Method
public int startRead() {
mutex.P();
++readerCount;
// if I am the first reader tell all others
// that the database is being read
if (readerCount == 1)
db.P();
mutex.V();
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.38Applied Operating System Concepts
endRead() Method
public int endRead() {
mutex.P();
--readerCount;
// if I am the last reader tell all others
// that the database is no longer being read
if (readerCount == 0)
db.V();
mutex.V();
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.39Applied Operating System Concepts
Writer Methods
public void startWrite() {
db.P();
}
public void endWrite() {
db.V();
}
Silberschatz,Galvin,and Gagne?19997.40Applied Operating System Concepts
Dining-Philosophers Problem
Shared data
Semaphore chopStick[] = new Semaphore[5];
Silberschatz,Galvin,and Gagne?19997.41Applied Operating System Concepts
Dining-Philosophers Problem (Cont.)
Philosopher i:
while (true) {
// get left chopstick
chopStick[i].P();
// get right chopstick
chopStick[(i + 1) % 5].P();
// eat for awhile
//return left chopstick
chopStick[i].V();
// return right chopstick
chopStick[(i + 1) % 5].V();
// think for awhile
}
Silberschatz,Galvin,and Gagne?19997.42Applied Operating System Concepts
Monitors
A monitor is a high-level abstraction that provides thread
safety（管程是对提供线程安全机制的高度抽象）,
Only one thread may be active within the monitor at a time（
任一时刻在管程中只有一个线程是能运行的）,
monitor monitor-name
{
// variable declarations
public entry p1(…) {
…
}
public entry p2(…) {
…
}
}
Silberschatz,Galvin,and Gagne?19997.43Applied Operating System Concepts
Condition Variables
condition x,y;
A thread that invokes x.wait is suspended until another thread
invokes x.signal（调用 x.wait的线程将一直等待到有另一个线程调用 x.signal）
Silberschatz,Galvin,and Gagne?19997.44Applied Operating System Concepts
Monitor with condition variables
Silberschatz,Galvin,and Gagne?19997.45Applied Operating System Concepts
Solution to Dining Philosophers
monitor diningPhilosophers {
int[] state = new int[5];
static final int THINKING = 0;
static final int HUNGRY = 1;
static final int EATING = 2;
condition[] self = new condition[5];
public diningPhilosophers {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
public entry pickUp(int i) { /* see next slides */ }
public entry putDown(int i) { /* see next slides */ }
private test(int i) {/* see next slides */ }
}
Silberschatz,Galvin,and Gagne?19997.46Applied Operating System Concepts
pickUp() Procedure
public entry pickUp(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self[i].wait;
}
Silberschatz,Galvin,and Gagne?19997.47Applied Operating System Concepts
putDown() Procedure
public entry putDown(int i) {
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
Silberschatz,Galvin,and Gagne?19997.48Applied Operating System Concepts
test() Procedure
private test(int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING;
self[i].signal;
}
}
Silberschatz,Galvin,and Gagne?19997.49Applied Operating System Concepts
Java Synchronization
Synchronized,wait(),notify() statements（同步化,wait(),
notify()语句）
Multiple Notifications（多重声明）
Block Synchronization（大块程序的同步化）
Java Semaphores（ Java信号量）
Java Monitors（ Java管程）
Silberschatz,Galvin,and Gagne?19997.50Applied Operating System Concepts
synchronized Statement
Every object has a lock associated with it（每个对象都有与之相关联的锁）,
Calling a synchronized method requires,owning” the lock（只有拥有这把锁的方法才能称为同步化进程）,
If a calling thread does not own the lock (another thread already
owns it),the calling thread is placed in the wait set for the object’s
lock（如果主调线程没有这把锁,[而其他线程有了 ]，主调线程就会进入该物体的等待集）
The lock is released when a thread exits the synchronized method（
当线程退出了同步化方法时锁就会释放）,
Silberschatz,Galvin,and Gagne?19997.51Applied Operating System Concepts
Entry Set
Silberschatz,Galvin,and Gagne?19997.52Applied Operating System Concepts
synchronized enter() Method
public synchronized void enter(Object item) {
while (count == BUFFER_SIZE)
Thread.yield();
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
}
Silberschatz,Galvin,and Gagne?19997.53Applied Operating System Concepts
synchronized remove() Method
public synchronized Object remove() {
Object item;
while (count == 0)
Thread.yield();
--count;
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
return item;
}
Silberschatz,Galvin,and Gagne?19997.54Applied Operating System Concepts
The wait() Method
When a thread calls wait(),the following occurs（当线程调用
wait()时，会产生以下动作）,
- the thread releases the object lock（该线程释放对象锁）,
- thread state is set to blocked（线程状态置为阻塞）,
- thread is placed in the wait set（线程进入等待集）,
Silberschatz,Galvin,and Gagne?19997.55Applied Operating System Concepts
Entry and Wait Sets
Silberschatz,Galvin,and Gagne?19997.56Applied Operating System Concepts
The notify() Method
When a thread calls notify(),the following occurs（当线程调用 notify()时，会产生以下动作）,
- selects an arbitrary thread T from the wait set（任意从等待集中选出一个线程 T.
- moves T to the entry set(将 T置入入口集）,
- sets T to Runnable（设置 T为可运行状态）,
T can now compete for the object’s lock again（此时,T又能竞争使用对象锁了）,
Silberschatz,Galvin,and Gagne?19997.57Applied Operating System Concepts
enter() with wait/notify Methods
public synchronized void enter(Object item) {
while (count == BUFFER_SIZE)
try {
wait();
}
catch (InterruptedException e) { }
}
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
notify();
}
Silberschatz,Galvin,and Gagne?19997.58Applied Operating System Concepts
remove() with wait/notify Methods
public synchronized Object remove() {
Object item;
while (count == 0)
try {
wait();
}
catch (InterruptedException e) { }
--count;
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
notify();
return item;
}
Silberschatz,Galvin,and Gagne?19997.59Applied Operating System Concepts
Multiple Notifications
notify() selects an arbitrary thread from the wait set,*This
may not be the thread that you want to be selected（ notify()
从等待集中任意选取一个线程。这可能导致所选的线程并不是你想要的）,
Java does not allow you to specify the thread to be selected
（ Java不容许你指定想要选取的线程）,
notifyAll() removes ALL threads from the wait set and places
them in the entry set,This allows the threads to decide
among themselves who should proceed next（ notifyAll()将等待集中所有的线程移至入口集。这就可以由他们自己决定让谁接着运行）,
notifyAll() is a conservative strategy that works best when
multiple threads may be in the wait set（ notifyAll()是较保守的策略，只有在多线程可能在等待集的时候最有效）,
Silberschatz,Galvin,and Gagne?19997.60Applied Operating System Concepts
Reader Methods with Java
Synchronization
public class Database {
public Database() {
readerCount = 0;
dbReading = false;
dbWriting = false;
}
public synchronized int startRead() { /* see next slides */ }
public synchronized int endRead() { /* see next slides */ }
public synchronized void startWrite() { /* see next slides */ }
public synchronized void endWrite() { /* see next slides */ }
private int readerCount;
private boolean dbReading;
private boolean dbWriting;
}
Silberschatz,Galvin,and Gagne?19997.61Applied Operating System Concepts
startRead() Method
public synchronized int startRead() {
while (dbWriting == true) {
try {
wait();
}
catch (InterruptedException e) { }
++readerCount;
if (readerCount == 1)
dbReading = true;
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.62Applied Operating System Concepts
endRead() Method
public synchronized int endRead() {
--readerCount
if (readerCount == 0)
db.notifyAll();
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.63Applied Operating System Concepts
Writer Methods
public void startWrite() {
while (dbReading == true || dbWriting == true)
try {
wait();
}
catch (InterruptedException e) { }
dbWriting = true;
}
public void endWrite() {
dbWriting = false;
notifyAll();
}
Silberschatz,Galvin,and Gagne?19997.64Applied Operating System Concepts
Block Synchronization
Blocks of code – rather than entire methods – may be
declared as synchronized（宣称同步化的往往是成块的程序代码而不是全部的方法）
This yields a lock scope that is typically smaller than a
synchronized method（这将产生出典型的比同步化方法小的锁定范围）,
Silberschatz,Galvin,and Gagne?19997.65Applied Operating System Concepts
Block Synchronization (cont)
Object mutexLock = new Object();
.,,
public void someMethod() {
// non-critical section
synchronized(mutexLock) {
// critical section
}
// non-critical section
}
Silberschatz,Galvin,and Gagne?19997.66Applied Operating System Concepts
Java Semaphores
Java does not provide a semaphore,but a basic semaphore
can be constructed using Java synchronization mechanism
（ Java不提供信号量，但是可以用 Java同步机制来建构基本信号量）,
Silberschatz,Galvin,and Gagne?19997.67Applied Operating System Concepts
Semaphore Class
public class Semaphore {
public Semaphore() {
value = 0;
}
public Semaphore(int v) {
value = v;
}
public synchronized void P() { /* see next slide */ }
public synchronized void V() { /* see next slide */ }
private int value;
}
Silberschatz,Galvin,and Gagne?19997.68Applied Operating System Concepts
P() Operation
public synchronized void P() {
while (value <= 0) {
try {
wait();
}
catch (InterruptedException e) { }
}
value --;
}
Silberschatz,Galvin,and Gagne?19997.69Applied Operating System Concepts
V() Operation
public synchronized void V() {
++value;
notify();
}
Silberschatz,Galvin,and Gagne?19997.70Applied Operating System Concepts
Solaris 2 Synchronization
Solaris 2 Provides（ Solaris 2提供）,
- adaptive mutex（可变互斥量）
- condition variables（环境变量）
- semaphores（信号量）
- reader-writer locks（读 –写锁）
Silberschatz,Galvin,and Gagne?19997.71Applied Operating System Concepts
Windows NT Synchronization
Windows NT Provides（ Windows NT提供）,
- mutex（互斥量）
- critical sections（临界区）
- semaphores（信号量）
- event objects（事件对象）
Module 7,Process Synchronization
Background（背景）
The Critical-Section Problem （临界区问题）
Synchronization Hardware （同步的硬件实现）
Semaphores （信号量）
Classical Problems of Synchronization（ 经典同步问题）
Monitors （管程）
Java Synchronization （ Java中的同步机制）
Synchronization in Solaris 2 （ Solaris 2的同步机制）
Synchronization in Windows NT （ Windows NT的同步机制）
Silberschatz,Galvin,and Gagne?19997.2Applied Operating System Concepts
Background
Concurrent access to shared data may result in data
inconsistency（对共享数据的并发访问可能导致数据的不一致性）,
Maintaining data consistency requires mechanisms to ensure
the orderly execution of cooperating processes（要保持数据的一致性，就需要一种保证并发进程的正确执行顺序的机制）,
Shared-memory solution to bounded-butter problem (Chapter
4) has a race condition on the class data count （ [第 4章中 ]解决有界缓冲区问题的共享内存方法在类数据 count 上将一起竞争条件）
Silberschatz,Galvin,and Gagne?19997.3Applied Operating System Concepts
Bounded Buffer
public class BoundedBuffer {
public void enter(Object item) {
// producer calls this method
}
public Object remove() {
// consumer calls this method
}
// potential race condition on count
private volatile int count;
}
Silberschatz,Galvin,and Gagne?19997.4Applied Operating System Concepts
enter() Method
// producer calls this method
public void enter(Object item) {
while (count == BUFFER_SIZE); // do nothing
// add an item to the buffer
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
}
Silberschatz,Galvin,and Gagne?19997.5Applied Operating System Concepts
remove() Method
// consumer calls this method
public Object remove() {
Object item;
while (count == 0); // do nothing
// remove an item from the buffer
--count;
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
return item;
}
Silberschatz,Galvin,and Gagne?19997.6Applied Operating System Concepts
Solution to Critical-Section Problem
1,Mutual Exclusion,If process Pi is executing in its critical section,then
no other processes can be executing in their critical sections（互斥。假定进程 Pi在其临界区内执行，其他任何进程将被排斥在自己的临界区之外）,
2,Progress,If no process is executing in its critical section and there exist
some processes that wish to enter their critical section,then the selection
of the processes that will enter the critical section next cannot be
postponed indefinitely（有空让进。临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间
）,
3,Bounded Waiting,A bound must exist on the number of times that other
processes are allowed to enter their critical sections after a process has
made a request to enter its critical section and before that request is
granted（有限等待。在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区前的等待时间必须是有限的）,
Assume that each process executes at a nonzero speed （假定每个进程都以非零的的速率执行）,
No assumption concerning relative speed of the n processes（没有任何关于这 n个进程相对执行速率的假定 ）,
Silberschatz,Galvin,and Gagne?19997.7Applied Operating System Concepts
Worker Thread
public class Worker extends Thread {
public Worker(String n,int i,MutualExclusion s) {
name = n;
id = i;
shared = s;
}
public void run() { /* see next slide */ }
private String name;
private int id;
private MutualExclusion shared;
}
Silberschatz,Galvin,and Gagne?19997.8Applied Operating System Concepts
run() Method of Worker Thread
public void run() {
while (true) {
shared.enteringCriticalSection(id);
// in critical section code
shared.leavingCriticalSection(id);
// out of critical section code
}
}
Silberschatz,Galvin,and Gagne?19997.9Applied Operating System Concepts
MutualExclusion Abstract Class
public abstract class MutualExclusion {
public static void criticalSection() {
// simulate the critical section
}
public static void nonCriticalSection() {
// simulate the non-critical section
}
public abstract void enteringCriticalSection(int t);
public abstract void leavingCriticalSection(int t);
public static final int TURN_0 = 0;
public static final int TURN_1 = 1;
}
Silberschatz,Galvin,and Gagne?19997.10Applied Operating System Concepts
Testing Each Algorithm
public class TestAlgorithm
{
public static void main(String args[]) {
MutualExclusion alg = new Algorithm_1();
Worker first = new Worker("Runner 0",0,alg);
Worker second = new Worker("Runner 1",1,alg);
first.start();
second.start();
}
}
Silberschatz,Galvin,and Gagne?19997.11Applied Operating System Concepts
Algorithm 1
public class Algorithm_1 extends MutualExclusion {
public Algorithm_1() {
turn = TURN_0;
}
public void enteringCriticalSection(int t) {
while (turn != t)
Thread.yield();
}
public void leavingCriticalSection(int t) {
turn = 1 - t;
}
private volatile int turn;
}
Silberschatz,Galvin,and Gagne?19997.12Applied Operating System Concepts
Algorithm 2
public class Algorithm_2 extends MutualExclusion {
public Algorithm_2() {
flag[0] = false;
flag[1] = false;
}
public void enteringCriticalSection(int t) {
// see next slide
}
public void leavingCriticalSection(int t) {
flag[t] = false;
}
private volatile boolean[] flag = new boolean[2];
}
Silberschatz,Galvin,and Gagne?19997.13Applied Operating System Concepts
Algorithm 2 – enteringCriticalSection()
public void enteringCriticalSection(int t) {
int other = 1 - t;
flag[t] = true;
while (flag[other] == true)
Thread.yield();
}
Silberschatz,Galvin,and Gagne?19997.14Applied Operating System Concepts
Algorithm 3
public class Algorithm_3 extends MutualExclusion {
public Algorithm_3() {
flag[0] = false;
flag[1] = false;
turn = TURN_0;
}
public void enteringCriticalSection(int t) {/* see next slides */ }
public void leavingCriticalSection(int t) {{/* see next slides */ }
private volatile int turn;
private volatile boolean[] flag = new boolean[2];
}
Silberschatz,Galvin,and Gagne?19997.15Applied Operating System Concepts
Algorithm 3 – enteringCriticalSection()
public void enteringCriticalSection(int t) {
int other = 1 - t;
flag[t] = true;
turn = other;
while ( (flag[other] == true) && (turn == other) )
Thread.yield();
}
Silberschatz,Galvin,and Gagne?19997.16Applied Operating System Concepts
Algo,3 – leavingingCriticalSection()
public void leavingCriticalSection(int t) {
flag[t] = false;
}
Silberschatz,Galvin,and Gagne?19997.17Applied Operating System Concepts
Synchronization Hardware
public class HardwareData {
public HardwareData(boolean v) {
data = v;
}
public boolean get() {
return data;
}
public void set(boolean v) {
data = v;
}
private boolean data;
}
Silberschatz,Galvin,and Gagne?19997.18Applied Operating System Concepts
Test-and-Set Instruction (in Java)
public class HardwareSolution
{
public static boolean testAndSet(HardwareData target) {
HardwareData temp = new HardwareData(target.get());
target.set(true);
return temp.get();
}
}
Silberschatz,Galvin,and Gagne?19997.19Applied Operating System Concepts
Thread using Test-and-Set
HardwareData lock = new HardwareData(false);
while (true) {
while (HardwareSolution.testAndSet(lock))
Thread.yield(); // do nothing
// now in critical section code
lock.set(false);
// out of critical section
}
Silberschatz,Galvin,and Gagne?19997.20Applied Operating System Concepts
Swap instruction
public static void swap(HardwareData a,HardwareData b) {
HardwareData temp = new HardwareData(a.get());
a.set(b.get());
b.set(temp.get());
}
Silberschatz,Galvin,and Gagne?19997.21Applied Operating System Concepts
Thread using Swap
HardwareData lock = new HardwareData(false);
HardwareData key = new HardwareData(true);
while (true) {
key.set(true);
do {
HardwareSolution.swap(lock,key);
} while (key.get() == true);
// now in critical section code
lock.set(false);
// out of critical section
}
Silberschatz,Galvin,and Gagne?19997.22Applied Operating System Concepts
Semaphore
Synchronization tool that does not require busy waiting（一种不需要忙等待的同步工具）,
Semaphore S – integer variable（信号量 S– 整型变量）
can only be accessed via two indivisible (atomic) operations
（仅能通过两个不可分割的 [原子 ]操作访问）
P (S),while S? 0 do no-op;
S--;
V(S),S++;
Silberschatz,Galvin,and Gagne?19997.23Applied Operating System Concepts
Semaphore as General Synchronization Tool
Semaphore S; // initialized to 1
P(S);
CriticalSection()
V(S);
Silberschatz,Galvin,and Gagne?19997.24Applied Operating System Concepts
Semaphore Eliminating Busy-Waiting
P(S) {
value--;
if (value < 0) {
add this process to list
block
}
}
V(S) {
value++;
if (value <= 0) {
remove a process P from list
wakeup(P);
}
}
Silberschatz,Galvin,and Gagne?19997.25Applied Operating System Concepts
Synchronization Using Semaphores
public class FirstSemaphore {
public static void main(String args[]) {
Semaphore sem = new Semaphore(1);
Worker[] bees = new Worker[5];
for (int i = 0; i < 5; i++)
bees[i] = new Worker(sem,"Worker " + (new Integer(i)).toString()
);
for (int i = 0; i < 5; i++)
bees[i].start();
}
}
Silberschatz,Galvin,and Gagne?19997.26Applied Operating System Concepts
Worker Thread
public class Worker extends Thread {
public Worker(Semaphore) { sem = s;}
public void run() {
while (true) {
sem.P();
// in critical section
sem.V();
// out of critical section
}
}
private Semaphore sem;
}
Silberschatz,Galvin,and Gagne?19997.27Applied Operating System Concepts
Deadlock and Starvation
Deadlock – two or more processes are waiting indefinitely for
an event that can be caused by only one of the waiting
processes（死锁 – 两个或多个进程无限期地等待一个事件的发生，
而该事件正是由其中的一个等待进程引起的）,
Let S and Q be two semaphores initialized to 1（ S和 Q是两个初值为 1的信号量）
P0 P1
P(S); P(Q);
P(Q); P(S);
V(S); V(Q);
V(Q) V(S);
Starvation – indefinite blocking,A process may never be
removed from the semaphore queue in which it is suspended（
饥饿 – 无限期地阻塞。进程可能永远无法从它等待的信号量队列中移去）,
Silberschatz,Galvin,and Gagne?19997.28Applied Operating System Concepts
Two Types of Semaphores
Counting semaphore – integer value can range over an
unrestricted domain（计数信号量 –变化范围没有限制的整型值）,
Binary semaphore – integer value can range only
between 0
and 1; can be simpler to implement（二值信号量 – 变化范围仅限于 0和 1的信号量；容易实现）,
Can implement a counting semaphore S as a binary
semaphore（可以将计数信号量 S用作二值信号量）,
Silberschatz,Galvin,and Gagne?19997.29Applied Operating System Concepts
Classical Problems of Synchronization
Bounded-Buffer Problem
（有限缓冲区问题）
Readers and Writers Problem
（读者写者问题）
Dining-Philosophers Problem
（哲学家就餐问题）
Silberschatz,Galvin,and Gagne?19997.30Applied Operating System Concepts
Bounded-Buffer Problem
public class BoundedBuffer {
public BoundedBuffer() { /* see next slides */ }
public void enter() { /* see next slides */ }
public Object remove() { /* see next slides */ }
private static final int BUFFER_SIZE = 2;
private Semaphore mutex;
private Semaphore empty;
private Semaphore full;
private int in,out;
private Object[] buffer;
}
Silberschatz,Galvin,and Gagne?19997.31Applied Operating System Concepts
Bounded Buffer Constructor
public BoundedBuffer() {
// buffer is initially empty
count = 0;
in = 0;
out = 0;
buffer = new Object[BUFFER_SIZE];
mutex = new Semaphore(1);
empty = new Semaphore(BUFFER_SIZE);
full = new Semaphore(0);
}
Silberschatz,Galvin,and Gagne?19997.32Applied Operating System Concepts
enter() Method
public void enter(Object item) {
empty.P();
mutex.P();
// add an item to the buffer
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
mutex.V();
full.V();
}
Silberschatz,Galvin,and Gagne?19997.33Applied Operating System Concepts
remove() Method
public Object remove() {
full.P();
mutex.P();
// remove an item from the buffer
Object item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
mutex.V();
empty.V();
return item;
}
Silberschatz,Galvin,and Gagne?19997.34Applied Operating System Concepts
Readers-Writers Problem,Reader
public class Reader extends Thread {
public Reader(Database db) {
server = db;
}
public void run() {
int c;
while (true) {
c = server.startRead();
// now reading the database
c = server.endRead();
}
}
private Database server;
}
Silberschatz,Galvin,and Gagne?19997.35Applied Operating System Concepts
Readers-Writers Problem,Writer
public class Writer extends Thread {
public Writer(Database db) {
server = db;
}
public void run() {
while (true) {
server.startWrite();
// now writing the database
server.endWrite();
}
}
private Database server;
}
Silberschatz,Galvin,and Gagne?19997.36Applied Operating System Concepts
Readers-Writers Problem (cont)
public class Database
{
public Database() {
readerCount = 0;
mutex = new Semaphore(1);
db = new Semaphore(1);
}
public int startRead() { /* see next slides */ }
public int endRead() { /* see next slides */ }
public void startWrite() { /* see next slides */ }
public void endWrite() { /* see next slides */ }
private int readerCount; // number of active readers
Semaphore mutex; // controls access to readerCount
Semaphore db; // controls access to the database
}
Silberschatz,Galvin,and Gagne?19997.37Applied Operating System Concepts
startRead() Method
public int startRead() {
mutex.P();
++readerCount;
// if I am the first reader tell all others
// that the database is being read
if (readerCount == 1)
db.P();
mutex.V();
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.38Applied Operating System Concepts
endRead() Method
public int endRead() {
mutex.P();
--readerCount;
// if I am the last reader tell all others
// that the database is no longer being read
if (readerCount == 0)
db.V();
mutex.V();
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.39Applied Operating System Concepts
Writer Methods
public void startWrite() {
db.P();
}
public void endWrite() {
db.V();
}
Silberschatz,Galvin,and Gagne?19997.40Applied Operating System Concepts
Dining-Philosophers Problem
Shared data
Semaphore chopStick[] = new Semaphore[5];
Silberschatz,Galvin,and Gagne?19997.41Applied Operating System Concepts
Dining-Philosophers Problem (Cont.)
Philosopher i:
while (true) {
// get left chopstick
chopStick[i].P();
// get right chopstick
chopStick[(i + 1) % 5].P();
// eat for awhile
//return left chopstick
chopStick[i].V();
// return right chopstick
chopStick[(i + 1) % 5].V();
// think for awhile
}
Silberschatz,Galvin,and Gagne?19997.42Applied Operating System Concepts
Monitors
A monitor is a high-level abstraction that provides thread
safety（管程是对提供线程安全机制的高度抽象）,
Only one thread may be active within the monitor at a time（
任一时刻在管程中只有一个线程是能运行的）,
monitor monitor-name
{
// variable declarations
public entry p1(…) {
…
}
public entry p2(…) {
…
}
}
Silberschatz,Galvin,and Gagne?19997.43Applied Operating System Concepts
Condition Variables
condition x,y;
A thread that invokes x.wait is suspended until another thread
invokes x.signal（调用 x.wait的线程将一直等待到有另一个线程调用 x.signal）
Silberschatz,Galvin,and Gagne?19997.44Applied Operating System Concepts
Monitor with condition variables
Silberschatz,Galvin,and Gagne?19997.45Applied Operating System Concepts
Solution to Dining Philosophers
monitor diningPhilosophers {
int[] state = new int[5];
static final int THINKING = 0;
static final int HUNGRY = 1;
static final int EATING = 2;
condition[] self = new condition[5];
public diningPhilosophers {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
public entry pickUp(int i) { /* see next slides */ }
public entry putDown(int i) { /* see next slides */ }
private test(int i) {/* see next slides */ }
}
Silberschatz,Galvin,and Gagne?19997.46Applied Operating System Concepts
pickUp() Procedure
public entry pickUp(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self[i].wait;
}
Silberschatz,Galvin,and Gagne?19997.47Applied Operating System Concepts
putDown() Procedure
public entry putDown(int i) {
state[i] = THINKING;
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
}
Silberschatz,Galvin,and Gagne?19997.48Applied Operating System Concepts
test() Procedure
private test(int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING;
self[i].signal;
}
}
Silberschatz,Galvin,and Gagne?19997.49Applied Operating System Concepts
Java Synchronization
Synchronized,wait(),notify() statements（同步化,wait(),
notify()语句）
Multiple Notifications（多重声明）
Block Synchronization（大块程序的同步化）
Java Semaphores（ Java信号量）
Java Monitors（ Java管程）
Silberschatz,Galvin,and Gagne?19997.50Applied Operating System Concepts
synchronized Statement
Every object has a lock associated with it（每个对象都有与之相关联的锁）,
Calling a synchronized method requires,owning” the lock（只有拥有这把锁的方法才能称为同步化进程）,
If a calling thread does not own the lock (another thread already
owns it),the calling thread is placed in the wait set for the object’s
lock（如果主调线程没有这把锁,[而其他线程有了 ]，主调线程就会进入该物体的等待集）
The lock is released when a thread exits the synchronized method（
当线程退出了同步化方法时锁就会释放）,
Silberschatz,Galvin,and Gagne?19997.51Applied Operating System Concepts
Entry Set
Silberschatz,Galvin,and Gagne?19997.52Applied Operating System Concepts
synchronized enter() Method
public synchronized void enter(Object item) {
while (count == BUFFER_SIZE)
Thread.yield();
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
}
Silberschatz,Galvin,and Gagne?19997.53Applied Operating System Concepts
synchronized remove() Method
public synchronized Object remove() {
Object item;
while (count == 0)
Thread.yield();
--count;
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
return item;
}
Silberschatz,Galvin,and Gagne?19997.54Applied Operating System Concepts
The wait() Method
When a thread calls wait(),the following occurs（当线程调用
wait()时，会产生以下动作）,
- the thread releases the object lock（该线程释放对象锁）,
- thread state is set to blocked（线程状态置为阻塞）,
- thread is placed in the wait set（线程进入等待集）,
Silberschatz,Galvin,and Gagne?19997.55Applied Operating System Concepts
Entry and Wait Sets
Silberschatz,Galvin,and Gagne?19997.56Applied Operating System Concepts
The notify() Method
When a thread calls notify(),the following occurs（当线程调用 notify()时，会产生以下动作）,
- selects an arbitrary thread T from the wait set（任意从等待集中选出一个线程 T.
- moves T to the entry set(将 T置入入口集）,
- sets T to Runnable（设置 T为可运行状态）,
T can now compete for the object’s lock again（此时,T又能竞争使用对象锁了）,
Silberschatz,Galvin,and Gagne?19997.57Applied Operating System Concepts
enter() with wait/notify Methods
public synchronized void enter(Object item) {
while (count == BUFFER_SIZE)
try {
wait();
}
catch (InterruptedException e) { }
}
++count;
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
notify();
}
Silberschatz,Galvin,and Gagne?19997.58Applied Operating System Concepts
remove() with wait/notify Methods
public synchronized Object remove() {
Object item;
while (count == 0)
try {
wait();
}
catch (InterruptedException e) { }
--count;
item = buffer[out];
out = (out + 1) % BUFFER_SIZE;
notify();
return item;
}
Silberschatz,Galvin,and Gagne?19997.59Applied Operating System Concepts
Multiple Notifications
notify() selects an arbitrary thread from the wait set,*This
may not be the thread that you want to be selected（ notify()
从等待集中任意选取一个线程。这可能导致所选的线程并不是你想要的）,
Java does not allow you to specify the thread to be selected
（ Java不容许你指定想要选取的线程）,
notifyAll() removes ALL threads from the wait set and places
them in the entry set,This allows the threads to decide
among themselves who should proceed next（ notifyAll()将等待集中所有的线程移至入口集。这就可以由他们自己决定让谁接着运行）,
notifyAll() is a conservative strategy that works best when
multiple threads may be in the wait set（ notifyAll()是较保守的策略，只有在多线程可能在等待集的时候最有效）,
Silberschatz,Galvin,and Gagne?19997.60Applied Operating System Concepts
Reader Methods with Java
Synchronization
public class Database {
public Database() {
readerCount = 0;
dbReading = false;
dbWriting = false;
}
public synchronized int startRead() { /* see next slides */ }
public synchronized int endRead() { /* see next slides */ }
public synchronized void startWrite() { /* see next slides */ }
public synchronized void endWrite() { /* see next slides */ }
private int readerCount;
private boolean dbReading;
private boolean dbWriting;
}
Silberschatz,Galvin,and Gagne?19997.61Applied Operating System Concepts
startRead() Method
public synchronized int startRead() {
while (dbWriting == true) {
try {
wait();
}
catch (InterruptedException e) { }
++readerCount;
if (readerCount == 1)
dbReading = true;
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.62Applied Operating System Concepts
endRead() Method
public synchronized int endRead() {
--readerCount
if (readerCount == 0)
db.notifyAll();
return readerCount;
}
Silberschatz,Galvin,and Gagne?19997.63Applied Operating System Concepts
Writer Methods
public void startWrite() {
while (dbReading == true || dbWriting == true)
try {
wait();
}
catch (InterruptedException e) { }
dbWriting = true;
}
public void endWrite() {
dbWriting = false;
notifyAll();
}
Silberschatz,Galvin,and Gagne?19997.64Applied Operating System Concepts
Block Synchronization
Blocks of code – rather than entire methods – may be
declared as synchronized（宣称同步化的往往是成块的程序代码而不是全部的方法）
This yields a lock scope that is typically smaller than a
synchronized method（这将产生出典型的比同步化方法小的锁定范围）,
Silberschatz,Galvin,and Gagne?19997.65Applied Operating System Concepts
Block Synchronization (cont)
Object mutexLock = new Object();
.,,
public void someMethod() {
// non-critical section
synchronized(mutexLock) {
// critical section
}
// non-critical section
}
Silberschatz,Galvin,and Gagne?19997.66Applied Operating System Concepts
Java Semaphores
Java does not provide a semaphore,but a basic semaphore
can be constructed using Java synchronization mechanism
（ Java不提供信号量，但是可以用 Java同步机制来建构基本信号量）,
Silberschatz,Galvin,and Gagne?19997.67Applied Operating System Concepts
Semaphore Class
public class Semaphore {
public Semaphore() {
value = 0;
}
public Semaphore(int v) {
value = v;
}
public synchronized void P() { /* see next slide */ }
public synchronized void V() { /* see next slide */ }
private int value;
}
Silberschatz,Galvin,and Gagne?19997.68Applied Operating System Concepts
P() Operation
public synchronized void P() {
while (value <= 0) {
try {
wait();
}
catch (InterruptedException e) { }
}
value --;
}
Silberschatz,Galvin,and Gagne?19997.69Applied Operating System Concepts
V() Operation
public synchronized void V() {
++value;
notify();
}
Silberschatz,Galvin,and Gagne?19997.70Applied Operating System Concepts
Solaris 2 Synchronization
Solaris 2 Provides（ Solaris 2提供）,
- adaptive mutex（可变互斥量）
- condition variables（环境变量）
- semaphores（信号量）
- reader-writer locks（读 –写锁）
Silberschatz,Galvin,and Gagne?19997.71Applied Operating System Concepts
Windows NT Synchronization
Windows NT Provides（ Windows NT提供）,
- mutex（互斥量）
- critical sections（临界区）
- semaphores（信号量）
- event objects（事件对象）
