Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Phần 2)

Chương 5: Đồng bộ - 2

01/2015

Câu hỏi ôn tập 5 - 1

 Khi nào thì xảy ra tranh chấp race condition?

 Vấn đề Critical Section là gì?

 Yêu cầu của lời giải cho CS problem?

 Có mấy loại giải pháp? Kể tên?

Đồng bộ

2

Mục tiêu

 Hiểu được nhóm giải pháp Busy waiting bao gồm:

 Các giải pháp phần mềm

 Các giải pháp phần cứng

Đồng bộ

3

Nội dung

 Các giải pháp phần mềm

 Sử dụng giải thuật kiểm tra luân phiên

 Sử dụng các biến cờ hiệu

 Giải pháp của Peterson

 Giải pháp Bakery

 Các giải pháp phần cứng

 Cấp ngắt

 Chỉ thị TSL

 Cấm ngắt

 Các lệnh đặc biệt

Đồng bộ

4

Giải thuật 1

 Biꢀn chia sꢁ

 int turn;

/* khꢂi đầu turn = 0 */

 nꢀu turn = i thꢃ Pi được phꢄp vꢅo critical section, vꢆi i = 0 hay 1

 Process Pi

do {

while (turn != i);

critical section

turn = j;

remainder section

} while (1);

 Thoả mꢇn mutual exclusion (1)

 Nhưng không thoả mꢇn yêu cầu về progress (2) vꢅ bounded

waiting (3)

Đồng bộ

5

Giải thuậ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í dụ:

P0 có RS (remainder section) rất lꢆn còn P1 có RS

nhỏ ???

Đồng bộ

6

Giải thuật 2

 Biꢀn chia sꢁ

 boolean flag[2]; /* khꢂi đầu flag[0] = flag[1] = false */

 Nꢀu flag[i] = true thꢃ Pi “sꢈn sꢅng” vꢅo critical section.

 Process Pi

do {

flag[ i ] = true;

/* Pi “sꢀn sꢁng” vꢁo CS */

while ( flag[ j ] ); /* Pi “nhưꢂng” Pj

critical section

*/

flag[ i ] = false;

remainder section

} while(1);

 Bảo đảm được mutual exclusion.

 Không thỏa mꢇn progress. Vꢃ sao?

Nếu flag[i] = flag[j] = true, cả 2 process đều lặp vòng vô tận tại while, không ai vào

được CS

Đồng bộ

7

Giải thuật 3 (Peterson)

 Biꢀn chia sꢁ

 Kꢀt hợp cả giải thuật 1 và 2.

 Process Pi, vꢆi i = 0 hay 1

do {

flag[ i ] = true;

turn = j;

/* Process i sꢀn sꢁng */

/* Nhưꢂng process j */

while (flag[ j ] and turn == j);

critical section

flag[ i ] = false;

remainder section

} while (1);

 Thoả mꢇn được cả 3 yêu cầu.

⇒ giải quyꢀt bꢅi toꢉn critical section cho 2 process

Đồng bộ

8

Giải thuật Peterson – 2 process

Process P₁

do {

Process P₀

do {

/* 1 wants in */

/* 0 wants in */

flag[1] = true;

flag[0] = true;

/* 1 gives a chance to 0 */

turn = 0;

/* 0 gives a chance to 1 */

turn = 1;

while (flag[0] && turn == 0);

critical section

/* 1 no longer wants in */

while (flag[1] &&turn == 1);

critical section

/* 0 no longer wants in */

flag[0] = false;

remainder section

} while(1);

flag[1] = false;

remainder section

} while(1);

Đồng bộ

9

Giải thuật 3: Tính đúng đắn

 Giải thuật 3 thỏa mutual exclusion, progress, và

bounded waiting

 Mutual exclusion được đảm bảo bꢂi vì

 P0 và P1 đều ꢂ trong CS nꢀu và chỉ nꢀu flag[0] =

flag[1] = true và turn = i cho mỗi Pi (không thể xảy

ra)

 Chứng minh thỏa yêu cầu về progress và bounded

waiting

 Pi không thể vào CS nꢀu và chỉ nꢀu bị kẹt tại vòng

lặp while() vꢆi điều kiện flag[j] =true và turn = j

 Nꢀu Pj không muốn vào CS thì flag[j] = false và do

đó Pi có thể vào CS

Đồng bộ

10

Giải thuật 3: Tính đúng đắn (tt)

Nếu Pj đã bật flag[j] = true và đang chờ tại while() thì

có chỉ hai trường hợp là turn = i hoặc turn = j

Nếu turn = i và Pi vào CS. Nếu turn = j thì Pj vào CS

nhưng sẽ bật flag[j] = false khi thoát ra  cho phép Pi

và CS

Nhưng nếu Pj có đủ thời gian bật flag[j] = true thì Pj

cũng phải gán turn = i

Vì Pi không thay đꢀi trꢁ của biến turn khi đang kꢂt

trong vꢃng lặp while(), Pi sẽ chờ đꢄ vꢅo CS nhiꢆu

nhꢇt lꢅ sau mꢈt lꢉn Pj vꢅo CS (bounded waiting)

Đồng bộ

11

Giải thuật bakery: n process

 Trưꢀc khi vꢁo CS, process Pi nhꢂn mꢃt con sꢄ. Process nꢁo

giꢅ con sꢄ nhꢆ nhꢇt thꢈ đưꢉc vꢁo CS

 Trưꢊng hꢉp Pi vꢁ Pj cꢋng nhꢂn đưꢉc mꢃt chꢌ sꢄ:

 Nꢍu i < j thꢈ Pi đưꢉc vꢁo trưꢀc

 Khi ra khꢆi CS, Pi đꢎt lꢏi sꢄ cꢐa mꢈnh bꢑng 0

 Cơ chꢍ cꢇp sꢄ cho cꢒc process thưꢊng tꢏo cꢒc sꢄ theo cơ chꢍ

tăng dꢓn, vꢔ dꢕ 1, 2, 3, 3, 3, 3, 4, 5,…

 Kꢔ hiꢖu

 (a,b) < (c,d) nꢍu a < c hoꢎc nꢍu a = c vꢁ b < d

 max(a0,…,ak) lꢁ con sꢄ b sao cho b ≥ ai vꢀi mꢗi i =

0,…, k

Đồng bộ

12

Giải thuật bakery: n process (tt)

/* shared variable */

boolean choosing[n]; /* initially, choosing[i] = false */

int

num[n];

/* initially, num[i] = 0

*/

do {

choosing[i] = true;

num[i] = max(num[0], num[1],…, num[n-1]) + 1;

choosing[i] = false;

for (j = 0; j < n; j++) {

while (choosing[j]);

while ((num[j] != 0) && (num[j], j) < (num[i], i));

}

critical section

num[i] = 0;

remainder section

} while(1);

Đồng bộ

13

Từ software đến hardware

 Khuyꢀt điểm của các giải pháp software:

 Cꢉc process khi yêu cầu được vꢅo vꢊng tranh

chấp đều phải liên tục kiểm tra điều kiện (busy

waiting), tốn nhiều thời gian xử lꢋ của CPU

 Nꢀu thời gian xử lꢋ trong vꢊng tranh chấp lꢆn,

mꢌt giải phꢉp hiệu quả nên có cơ chꢀ block cꢉc

process cần đợi.

 Các giải pháp phần cứng:

 Cấm ngắt (disable interrupts)

 Dꢊng cꢉc lệnh đặc biệt

Đồng bộ

14

Cấm ngắt

 Trong hệ thống uniprocessor:

Process Pi:

do {

mutual exclusion được đảm bảo

 Trong hệ thống multiprocessor:

mutual exclusion không được

đảm bảo

disable_interrupts();

critical section

enable_interrupts();

remainder section

} while (1);

 Chỉ cấm ngắt tại CPU thực thi

lệnh disable_interrupts, các

CPU khác vẫn có thể truy cập

bꢌ nhꢆ chia sꢁ

 Nꢀu cấm ngắt tất cả các CPU

thì có thể gây tốn thời gian mỗi

lần vào vùng tranh chấp

Đồng bộ

15

Lệnh TestAndSet

 Đọc và ghi mꢌt biꢀn trong mꢌt thao tác atomic

(không chia cắt được)

Shared data:

boolean lock = false;

boolean TestAndSet( boolean *target){

boolean rv = *target;

*target = true;

return rv;

Process P_i:

}

do {

while (TestAndSet(&lock));

critical section

lock = false;

remainder section

} while (1);

Đồng bộ

16

Lệnh TestAndSet (tt)

 Mutual exclusion được bảo đảm: nꢀu Pi vꢅo CS, cꢉc

process Pj khꢉc đều đang busy waiting

 Khi Pi ra khỏi CS, quꢉ trꢃnh chọn lựa process Pj vꢅo

CS kꢀ tiꢀp lꢅ tꢊy ꢋ ⇒ không bảo đảm điều kiện

bounded waiting. Do đó có thể xảy ra starvation (bị

bỏ đói)

 Cꢉc processor (vꢍ dụ Pentium) thông thường cung

cấp mꢌt lệnh đơn lꢅ Swap(a, b) có tꢉc dụng hoꢉn

chuyển nꢌi dung của a vꢅ b.

 Swap(a, b) cꢎng có ưu nhược điểm như

TestAndSet

Đồng bộ

17

Swap và mutual exclusion

 Biꢍn chia sꢘ (khꢙi tꢏo lꢁ false)

Biꢍn chia sꢘ lock đưꢉc khꢙi tꢏo

giꢒ trꢚ false

bool lock;

bool key;

Mꢛi process P_icꢜ biꢍn cꢕc bꢃ

key

 Process P_i

Process P_inꢁo thꢇy giꢒ trꢚ lock

= false thꢈ đưꢉc vꢁo CS.

do {

Process P_isꢝ loꢏi trꢞ cꢒc

process P_jkhꢒc khi thiꢍt lꢂp

lock = true

key = true;

while (key == true)

Swap(&lock, &key);

critical section

lock = false;

void Swap(boolean *a,

boolean *b) {

boolean temp = *a;

*a = *b;

remainder section

} while (1)

*b = temp;

Không thꢆa mꢟn bounded waiting

}

Đồng bộ

18

Giải thuật dꢃng TestAndSet thoả mꢄn 3 yêu cꢅu

 Cꢇu trꢠc dꢅ liꢖu dꢋng chung (khꢙi tꢏo lꢁ false)

bool waiting[n];

bool lock;

 Mutual exclusion: Pi chꢌ cꢜ thꢡ vꢁo CS nꢍu vꢁ chꢌ nꢍu hoꢎc waiting[i]

= false, hoꢎc key = false

 key = false chꢌ khi TestAndSet (hay Swap) đưꢉc thꢢc thi

Process đꢓu tiên thꢢc thi TestAndSet mꢀi cꢜ key == false; cꢒc

process khꢒc đꢣu phꢤi đꢉi

 waiting[i] = false chꢌ khi process khꢒc rꢊi khꢆi CS

Chꢌ cꢜ mꢃt waiting[i] cꢜ giꢒ trꢚ false

(Xem sách

tham khảo

 Progress: chꢥng minh tương tꢢ như mutual exclusion

 Bounded waiting: waiting in the cyclic order

trang 212)

Đồng bộ

19

Giải thuật dꢃng TestAndSet thoả mꢄn 3 yêu cꢅu (tt)

do {

waiting[ i ] = true;

key = true;

while (waiting[ i ] && key)

key = TestAndSet(&lock);

waiting[ i ] = false;

critical section

j = (i + 1) % n;

while ( (j != i) && !waiting[ j ] )

j = (j + 1) % n;

if (j == i)

lock = false;

else

waiting[ j ] = false;

remainder section

} while (1)

Đồng bộ

20

Bài giảng Hệ điều hành - Chương 5: Đồng bộ (Phần 2) - Trần Thị Như Nguyệt