Mô tả:
Chöông V - Phaàn II
Ñoàng Boä vaø Giaûi Quyeát Tranh Chaáp
(Process Synchronization)
1
Noäi dung
Ñaët vaán ñeà (taïi sao phaûi ñoàng boä vaø giaûi
quyeát tranh chaáp ?)
Vaán ñeà Critical section
Caùc giaûi phaùp phaàn meàm
– Giaûi thuaät Peterson, vaø giaûi thuaät bakery
Ñoàng boä baèng hardware
Semaphore
Caùc baøi toaùn ñoàng boä
Critical region
Monitor
Khoa KTMT
2
Ñaët vaán ñeà
Khaûo saùt caùc process/thread thöïc thi ñoàng thôøi vaø chia
seû döõ lieäu (qua shared memory, file).
Neáu khoâng coù söï kieåm soaùt khi truy caäp caùc döõ lieäu chia
seû thì coù theå ñöa ñeán ra tröôøng hôïp khoâng nhaát quaùn döõ
lieäu (data inconsistency).
Ñeå duy trì söï nhaát quaùn döõ lieäu, heä thoáng caàn coù cô cheá
baûo ñaûm söï thöïc thi coù traät töï cuûa caùc process ñoàng thôøi.
Q
p
Khoa KTMT
R
L
3
Baøi toaùn Producer-Consumer
Producer-Consumer
P không được ghi dữ liệu vào buffer đã đầy
C không được đọc dữ liệu từ buffer đang trống
P và C không được thao tác trên buffer cùng lúc
Giôùi haïn, khoâng giôùi
haïn ???
P
Khoa KTMT
Buffer (N)
C
4
Ñaët vaán ñeà
Xeùt baøi toaùn Producer-Consumer vôùi bounded buffer
Bounded buffer, theâm bieán ñeám count
#define BUFFER_SIZE 10 /* 10 buffers */
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0, out = 0, count = 0;
Khoa KTMT
5
Bounded buffer (tt)
Quaù trình Producer
item nextProduced;
while(1) {
while (count == BUFFER_SIZE); /* do nothing */
buffer[in] = nextProduced;
count++;
bieán count ñöôïc chia seû
in = (in + 1) % BUFFER_SIZE;
giöõa producer vaø consumer
}
Quaù trình Consumer
item nextConsumed;
while(1) {
while (count == 0); /* do nothing */
nextConsumed = buffer[out] ;
count--;
out = (out + 1) % BUFFER_SIZE;
}
Khoa KTMT
6
Bounded buffer (tt)
Caùc leänh taêng, giaûm bieán count töông ñöông trong ngoân
ngöõ maùy laø:
(Producer)
count++:
(Consumer)
count--:
register1 = count
register1 = register1 + 1
count
= register1
register2 = count
register2 = register2 - 1
count
= register2
Trong ñoù, caùc registeri laø caùc thanh ghi cuûa CPU.
Khoa KTMT
7
Bounded buffer (tt)
Maõ maùy cuûa caùc leänh taêng vaø giaûm bieán count coù theå bò thöïc thi xen
keõ
Giaû söû count ñang baèng 5. Chuoãi thöïc thi sau coù theå xaûy ra:
0:
producer
register1 := count
{register1 = 5}
1:
producer
register1 := register1 + 1
{register1 = 6}
2:
consumer
register2 := count
{register2 = 5}
3:
consumer
register2 := register2 - 1
{register2 = 4}
4:
producer
count := register1
{count = 6}
5:
consumer
count := register2
{count = 4}
Caùc leänh count++, count-- phaûi laø ñôn nguyeân
(atomic), nghóa laø thöïc hieän nhö moät leänh ñôn, khoâng
bò ngaét nöûa chöøng.
Khoa KTMT
8
Bounded buffer (tt)
Race condition: nhieàu process truy xuaát vaø thao taùc
ñoàng thôøi leân döõ lieäu chia seû (nhö bieán count)
– Keát quaû cuoái cuøng cuûa vieäc truy xuaát ñoàng thôøi naøy phuï thuoäc
thöù töï thöïc thi cuûa caùc leänh thao taùc döõ lieäu.
Ñeå döõ lieäu chia seû ñöôïc nhaát quaùn, caàn baûo ñaûm
sao cho taïi moãi thôøi ñieåm chæ coù moät process ñöôïc
thao taùc leân döõ lieäu chia seû. Do ñoù, caàn coù cô cheá
ñoàng boä hoaït ñoäng cuûa caùc process naøy.
Khoa KTMT
9
Vaán ñeà Critical Section
Giaû söû coù n process cuøng truy xuaát ñoàng thôøi döõ lieäu
chia seû
Caáu truùc cuûa moãi process Pi - Moãi process coù ñoaïn
code nhö sau :
Do {
entry section
/* vaøo critical section */
critical section /* truy xuaát döõ lieäu chia xeû */
exit section
/* rôøi critical section */
remainder section /* laøm nhöõng vieäc khaùc */
} While (1)
Trong moãi process coù nhöõng ñoaïn code coù chöùa caùc
thao taùc leân döõ lieäu chia seû. Ñoaïn code naøy ñöôïc
goïi laø vuøng tranh chaáp (critical section, CS).
Khoa KTMT
10
Vaán ñeà Critical Section
Vaán ñeà Critical Section: phaûi baûo ñaûm söï loaïi tröø
töông hoã (MUTual EXclusion, mutex), töùc laø khi moät
process ñang thöïc thi trong vuøng tranh chaáp, khoâng
coù process naøo khaùc ñoàng thôøi thöïc thi caùc leänh
trong vuøng tranh chaáp.
Khoa KTMT
11
Yeâu caàu cuûa lôøi giaûi cho Critical Section Problem
Lôøi giaûi phaûi thoûa boán tính chaát:
(1) Ñoäc quyeàn truy xuaát (Mutual exclusion): Khi moät process P ñang
thöïc thi trong vuøng tranh chaáp (CS) cuûa noù thì khoâng coù process Q
naøo khaùc ñang thöïc thi trong CS cuûa Q.
(2) Progress: Moät tieán trình taïm döøng beân ngoaøi mieàn gaêng (CS)
khoâng ñöôïc ngaên caûn caùc tieán trình khaùc vaøo mieàn gaêng (CS) vaø
vieäc löïa choïn P naøo vaøo CS phaûi coù haïn ñònh
(3) Chôø ñôïi giôùi haïn (Bounded waiting): Moãi process chæ phaûi chôø
ñeå ñöôïc vaøo vuøng tranh chaáp trong moät khoaûng thôøi gian coù haïn
ñònh naøo ñoù. Khoâng xaûy ra tình traïng ñoùi taøi nguyeân (starvation).
(4)Khoâng coù giaû thieát naøo ñaët ra cho söï lieân heä veà toác ñoä cuûa caùc
tieán trình, cuõng nhö veà soá löôïng boä xöû lyù trong heä thoáng
Khoa KTMT
12
Phaân loaïi giaûi phaùp
Nhóm giải pháp Busy Waiting
– Sử dụng các biến cờ hiệu
– Sử dụng việc kiểm tra luân phiên
– Giải pháp của Peterson
– Cấm ngắt
– Chỉ thị TSL
Nhóm giải pháp Sleep & Wakeup
– Semaphore
– Monitor
– Message
Khoa KTMT
13
Caùc giaûi phaùp “Busy waiting”
While (chưa có quyền) do nothing() ;
CS;
Từ bỏ quyền sử dụng CS
Tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng
Không đòi hỏi sự trợ giúp của Hệ điều hành
Khoa KTMT
14
Caùc giaûi phaùp “Sleep & Wake up”
if (chưa có quyền) Sleep() ;
CS;
Wakeup( somebody);
Từ bỏ CPU khi chưa được vào miền găng
Cần được Hệ điều hành hỗ trợ
Khoa KTMT
15
Caùc giaûi phaùp “Busy waiting”
Giaûi thuaät 1
Bieán chia seû
Int turn;
/* khôûi ñaàu turn = 0 */
neáu turn = i thì Pi ñöôïc pheùp vaøo critical section, vôùi i = 0 hay 1
Process Pi
do {
while (turn != i);
critical section
turn = j;
remainder section
} while (1);
Thoaû maõn mutual exclusion (1)
Nhöng khoâng thoaû maõn yeâu caàu veà progress (2) vaø bounded
waiting (3) vì tính chaát strict alternation cuûa giaûi thuaät
Khoa KTMT
16
Giaûi thuaät 1 (tt)
Process P1:
do
while (turn != 1);
critical section
turn := 0;
remainder section
while (1);
Process P0:
do
while (turn != 0);
critical section
turn := 1;
remainder section
while (1);
Ví duï:
P0 coù RS (remainder section) raát lôùn coøn P1 coù RS nhoû???
P0 (I/O)
P1
P0
?
Hệ Thống bị treo
Khoa KTMT
17
Giaûi thuaät 2
Bieán chia seû
boolean flag[ 2 ]; /* khôûi ñaàu flag[ 0 ] = flag[ 1 ] = false */
Neáu flag[ i ] = true thì Pi “saün saøng” vaøo critical section.
Process Pi
do {
flag[ i ] = true;
/* Pi “saün saøng” vaøo CS */
while ( flag[ j ] ); /* Pi “nhöôøng” Pj
*/
critical section
flag[ i ] = false;
remainder section
} while (1);
Baûo ñaûm ñöôïc mutual exclusion. Chöùng minh?
Khoâng thoûa maõn progress. Vì sao?
Khoa KTMT
18
Giaûi thuaät 3 (Peterson)
Bieán chia seû: keát hôïp caû giaûi thuaät 1 vaø 2
Process Pi , vôùi i = 0 hay 1
do {
flag[ i ] = true;
/* Process i saün saøng */
turn = j;
/* Nhöôøng process j */
while (flag[ j ] and turn == j);
critical section
flag[ i ] = false;
remainder section
} while (1);
Thoaû maõn ñöôïc caû 3 yeâu caàu (chöùng minh?)
giaûi quyeát baøi toaùn critical section cho 2 process.
Khoa KTMT
19
Giaûi thuaät Peterson-2 process
Process P0
do {
/* 0 wants in */
flag[0] = true;
/* 0 gives a chance to 1 */
turn = 1;
while (flag[1] && turn == 1);
critical section;
/* 0 no longer wants in */
flag[0] = false;
remainder section;
} while(1);
Khoa KTMT
Process P1
do {
/* 1 wants in */
flag[1] = true;
/* 1 gives a chance to 0 */
turn = 0;
while (flag[0] && turn == 0);
critical section;
/* 1 no longer wants in */
flag[1] = false;
remainder section;
} while(1);
20
- Xem thêm -