Phm Th Phi ©2004
5.1
H điu hành
Chng 5: ng b hóa tin trình
̈ C s
̈ Bài toán min tng trc
̈ ng b hóa bng phn cng
̈ Semaphores
̈ Các bài toán c đin v đng b hóa
̈ Monitors
̈ ng b hóa trong Solaris và Windows 2000
Phm Th Phi ©2004
5.2
H điu hành
C s
̈ Truy cp cnh tranh lên d liu đc chia s có th gây nên tình
trng không nht quán d liu.
̈ Vic duy trì s nht quán d liu yêu cu các c ch đ đm bo
s thc thi mt cách có th t ca các tin trình có hp tác vi
nhau.
̈ Ví d?
Phm Th Phi ©2004
5.3
H điu hành
Tình trng đua tranh
̈ Tình trng đua tranh:làtình trng mà vài tin trình cùng truy cp và
thay đi lên d liu đc chia s.Giátr cui cùng ca d liu chia s
ph thuc vào tin trình nào hoàn thành cui cùng.
̈  ngn chn tình trng đua tranh, các tin trình đua tranh phi đc
đng b hóa.
Phm Th Phi ©2004

̈ Ch có 2 tin trình, P
0
và P
1
̈ Cu trúc tng quát ca tin trình P
i
(tin trình kia là P
1-j
)
do {
entry section
critical section
exit section
reminder section
} while (1);
̈ Các tin trình có th chia s mt s bin chung đ đng b hóa hành
đng ca chúng.
Phm Th Phi ©2004
5.7
H điu hành
Gii thut1
̈ Các bin chung:
H int turn;
khi đu turn = 0
H turn = i ⇒ P
i
có th bc vào min tng trc ca nó
̈ Tin trình P
i
do {

Gii thut3
̈ Kt hp các bin chia s đc s dng trong các gii thut 1
và 2.
̈ Tin trình P
i
do {
flag [i]:= true;
turn = j;
while (flag [j] and turn = j) ;
critical section
flag [i] = false;
remainder section
} while (1);
̈ Thõa mãn c 3 điu kin
Phm Th Phi ©2004
5.10
H điu hành
Gii thut Bakery
̈ Trc khi bc vào min tng trc ca mình, tin trình nhn
đc mt con s. Tin trình nào nhn đc con s nh nht
s có quyn bc vào min tng trc.
̈ If tin trình P
i
và P
j
nhn đc cùng mt s, và nu i<j,thìP
i
đc phc v trc; ngc li P
j
đc phc v trc.

while (choosing[j]) ;
while ((number[j] != 0) && ((number[j],j) < (number[i],i)) ;
}
critical section
number[i] = 0;
remainder section
} while (1);
Phm Th Phi ©2004
5.13
H điu hành
ng b hóa vi s tr giúp ca phn cng
̈ c và sa đi ni dung ca mt word mt cách t đng
boolean TestAndSet(boolean &target) {
boolean rv = target;
target = true;
return rv;
}
Phm Th Phi ©2004
5.14
H điu hành
Loi tr tng h vi Test-and-Set
̈ D liu đc chia s:
boolean lock = false;
̈ Tin trình P
i
do {
while (TestAndSet(lock)) ;
critical section
lock = false;
remainder section

H điu hành
Semaphores
̈ Công c dùng đ đng b hóa không gây ra tình trng ch đi bn.
̈ Semaphore S –bin integer
̈ Ch có th đc truy cp thông qua hai thao tác nguyên t (không th
chia nh đc na):
wait (S):
while S≤
0 do no-op;
S ;
signal (S):
S++;
Phm Th Phi ©2004
5.18
H điu hành
Min tng trc ca n tin trình
̈ D liu chia s:
semaphore mutex; //khi đu mutex = 1
̈ Tin trình Pi:
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (1);
Phm Th Phi ©2004
5.19
H điu hành
Cài đt Semaphore
̈ nh ngha mt semaphore nh là mt record

ch sau khi A đã đc thc thi trong P
i
̈ S dng semaphore flag khi to vi giá tr 0
̈ Code:
P
i
P
j
MM
Await(flag)
signal(flag) B
Phm Th Phi ©2004
5.22
H điu hành
Deadlock và cht đói
̈ Deadlock – hai hoc nhiu tin trình đang ch đi vô hn mt s
kin nào đó, mà s kin đóch có th đc to ra bi mt trong các
tin trình đang ch đi kia.
̈ Xem S và Q là 2 semaphores đc khi to là 1
P
0
P
1
wait(S); wait(Q);
wait(Q); wait(S);
MM
signal(S); signal(Q);
signal(Q) signal(S);
̈ S cht đói – b nghn (block) không hn đnh. Mt tin trình có th
không bao gi đc xóa khi hàng đi trong semaphore.

do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);
Phm Th Phi ©2004
5.27
H điu hành
Bounded-Buffer – Tin trình Consumer
do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);
Phm Th Phi ©2004
5.28

signal(wrt);
signal(mutex):
Phm Th Phi ©2004
5.31
H điu hành
Bài toán nm nhà trit gia n ti
̈ D liu chia s
semaphore chopstick[5];
Khi đu, các giá tr là 1
Phm Th Phi ©2004
5.32
H điu hành
Bài toán nm nhà trit gia n ti
̈ Philosopher i:
do {
wait(chopstick[i])
wait(chopstick[(i+1) % 5])
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);
Phm Th Phi ©2004
5.33
H điu hành
Monitors

có ngha là tin trình đang gi thao tác này đang ng cho đn khi mt
tin trình khác gi
x.signal();
H Thao tác x.signal khi đng li chính xác mt tin trình đang ng đ
ch đi trên bin x. Nu không có tin trình nào đang ng trên x, thì
thao tác signal không gây nh hng gì c.
Phm Th Phi ©2004
5.35
H điu hành
Cái nhìn mt cách có s đ v Monitor
Phm Th Phi ©2004
5.36
H điu hành
Monitor vi các bin điu kin
Phm Th Phi ©2004
5.37
H điu hành
Ví d v cài đt bài toán 5 nhà trit gia n
ti trên monitor
monitor dp
{
enum {thinking, hungry, eating} state[5];
condition self[5];
void pickup(int i) // các slide k tip
void putdown(int i) // các slide k tip
void test(int i) // các slide k tip
void init() {
for (int i = 0; i < 5; i++)
state[i] = thinking;
}