-4.1-
Chöông 5
Ñoàng Boä vaø
Giaûi Quyeát Tranh Chaáp
(Process Synchronization)
2
Khoa KTMT
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
3
Khoa KTMT
Ñ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
L
pR
4
Khoa KTMT
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
P
C
Buffe r (N)
Buffe r (N)
5
Khoa KTMT
Ñ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;