Tham khảo bài thuyết trình 'chương v-ii: đồng bộ và giải quyết tranh chấp', công nghệ thông tin, hệ điều hành phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
AMBIENT/
Chủ đề:
Nội dung Text: Chương V-II: Đồng Bộ và Giải Quyết Tranh Chấp
- Chöông VII
Ñoàng Boä vaø
Giaûi Quyeát Tranh Chaáp
(Process Synchronization)
-4.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 Vũ Đức Lung 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ûmsöï thöïc thi coù traät töï cuûa caùc process ñoàng thôøi.
Q
p L
R
Khoa KTMT Vũ Đức Lung 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
Gới hạn, không giới
hạn ???
P
Buffer (N)
Buffer (N)
C
Khoa KTMT Vũ Đức Lung 4
- Ñaët vaán ñeà
Xeùt baøi toaùn Producer-Consumer vôùi bounded
buffer
Bounded buffer (ch. 4), 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 Vũ Đức Lung 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
in = (in + 1) % BUFFER_SIZE; seû
} giöõa producer vaø
Quaù trình Consumer consumer
item nextConsumed;
while(1) {
while (count == 0); /* do nothing */
nextConsumed = buffer[out] ;
count--;
out = (out + 1) % BUFFER_SIZE;
} Vũ Đức Lung 6
Khoa KTMT
- 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++:
• register1 = count
• register1 = register1 + 1
• count = register1
• (Consumer) count--:
• register2 = count
• register2 = register2 - 1
• count = register2
Trong ñoù, caùc registeri laø caùc thanh ghi cuûa CPU.
Khoa KTMT Vũ Đức Lung 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: consumerregister2 := count {register2 = 5}
3: consumerregister2 := register2 1 {register2 = 4}
4: producer count := register1 {count = 6}
5: consumercount := 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 Vũ Đức Lung 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 Vũ Đức Lung 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 Vũ Đức Lung 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 Vũ Đức Lung 11
- Yeâu caàu cuûa lôøi giaûi cho Critical Section
Problem
• Lôøi giaûi phaûi thoûa ba 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) Moät tieán trình taïm döøng beân ngoaøi mieàn gaêng
khoâng ñöôïc ngaên caûn caùc tieán trình khaùc vaøo mieàn
gaêng
• (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 Vũ Đức Lung
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 Vũ Đức Lung 13
- Caùc giaûi phaùp “Busy waiting”
While (chưa có quyền) donothing() ;
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 Vũ Đức Lung 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 Vũ Đức Lung 15
- 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
Khoathuaät
KTMT Vũ Đức Lung 16
- Giaûi thuaät 1 (tt)
Process P0: Process P1:
do do
while (turn != 0); while (turn != 1);
critical section critical section
turn := 1; turn := 0;
remainder section remainder section
while (1); while (1);
Ví duï:
P0 coù RS (remainder section) raát lôùn coøn P1 coù RS
nhoû???
Khoa KTMT Vũ Đức Lung 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 Vũ Đức Lung 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 Vũ Đức Lung 19
- Giaûi thuaät Peterson2 process
Process P0 Process P1
do { do {
/* 0 wants in */ /* 1 wants in */
flag[0] = true; flag[1] = true;
/* 0 gives a chance to 1 */ /* 1 gives a chance to 0 */
turn = 1;
while (flag[1] && turn = 0;
turn == 1); while (flag[0] &&
critical section turn == 0);
/* 0 no longer wants in */ critical section
flag[0] = false; /* 1 no longer wants in */
remainder section flag[1] = false;
} while(1); remainder section
} while(1);
Khoa KTMT Vũ Đức Lung 20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
