Vì sao phải đồng bộ hóa giữa các tiến trình

Khái niệm “Critical Section”

Cấu trúc tổng quát của quá trình trong bài toán loại trừ tương hỗ

Giả sử mỗi process thực thi bình thường (i.e., nonzero speed) và không có sự tương quan giữa tốc độ thực thi của các process

Cấu trúc tổng quát của một process:

Một số giả định

• Có thể có nhiều CPU nhưng phần cứng không cho phép nhiều tác vụ truy cập một vị trí trong bộ nhớ cùng lúc (simultaneous)
• Không ràng buộc về thứ tự thực thi của các process
• Các process có thể chia sẻ một số biến chung nhằm đồng bộ hoạt động của chúng
• Giải pháp cần phải đặc tả entry section và exit section

Giải bài toán loại trừ tương hỗ

Lời giải phải thỏa 3 tính chất:1. Mutual exclusion : Khi một process P đang thực thi trong vùng tranh chấp (CS) thì không có process Q nào khác đang thực thi trong CS.2. Progress: Nếu không có quá trình nào đang thực thi trong vùng tranh chấp (CS) và có ít nhất một quá trình muốn vào vùng tranh chấp, thì chỉ có những quá trình đangkhông thực thi trong vùng remainder (RS) mới có quyền quyết định lựa chọn quá trình kế tiếp vào vùng tranh chấp và quyết định đó không được phép trì hoãn vô hạn định

3. Bounded waiting ( lockout-freedom ): Khi một quá trình muốn vào vùng tranh chấp (CS), thì từ khi yêu cầu đến khi được đáp ứng là khoảng thời gian có hạn (bounded or limit)

Phân loại giải pháp cho loại trừ tương hỗ

• Giải pháp dùng lệnh máy thông thường
• Giải pháp dùng lệnh cấm ngắt hay lệnh máy đặc biệt
  
  • Lệnh Disable interrupt
  • Lệnh máy đặc biệt như TestAndSet

Giải pháp dùng lệnh máy thông thường

• Giải pháp cho 2 process đồng thời
  
  • Giải thuật 1 và 2 (Dekker1 &2)
  • Giải thuật Peterson cho 2 process
• Giải pháp cho n process
  

Giải thuật 1 (Dekker1)

Biến chia sẻ

int turn; /* khởi đầu turn = 0 */ if turn = i then ( P i được phép vào critical section, với i = 0 hay 1)

Process P i

do { while (turn != i); critical section turn = j; remainder section } while (1);

Giải thuật thoả mãn mutual exclusion (1), nhưng không thoả mãn tính chất progress (2) vì tính chất strict alternation của giải thuật

Giải thuật không thỏa mãn tính chất progress (2):Nếu turn = 0, P0 được vào CS và sau đó thực thi turn = 1 và vào vùng RS; giả sử P0 “ở lâu” trong đó.

Lúc đó P1 vào CS và sau đó gán turn = 0, kế đó P1 vào và xong RS, vào entry section, đợi vào CS một lần nữa; nhưng vì turn = 0 nên P1 phải chờ P0.

Giải thuật 2 (Dekker2)

Biến chia sẻ boolean flag[ 2 ]; /* khởi đầu flag[ 0 ] = flag[ 1 ] = false */ if flag[ i ] = true then P i “sẵn sàng” vào critical section.

Process P i

do { flag[i] = true; /* P i “sẵn sàng” vào CS */ while (flag[j]); /* P i “nhường” P j */ critical section flag[i] = false; remainder section } while (1); Không thỏa mãn bounded wait(3). Vì sao? Trường hợp sau có thể xảy ra:P0 gán flag[ 0 ] = trueP1 gán flag[ 1 ] = true

P0 và P1 loop mãi mãi trong vòng lặp while

Giải thuật Peterson (1981)

Biến chia sẻ: kết hợp cả giải thuật 1 và 2
Process P i , với i = 0 hay 1 do { flag[i] = true; /* Process i sẵn sàng */ favor = j; /* Nhường process j */ while (flag[j] and favor == j); critical section flag[i] = false; remainder section } while (1);

Giải thuật Peterson cho 2 process: Tính đúng đắn

Giải thuật Peterson cho 2 process thỏa mutual exclusion, progress, và lockout-freedom

• Mutual exclusion được bảo đảm 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(2) và bounded wait(3): Xem tài liệu

Giải thuật bakery

• 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ố 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 if a = c và b < d
  • max(a 0 ,…,a k ) là con số b sao cho b ≥ a i với mọi i = 0,…, k

/* shared variable */ boolean choosing[n]; int num[n]; do { /* initially, choosing[ i ] = false */ /* initially, num[ i ] = 0 */ 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);

Đánh giá

• Các giải pháp dùng lệnh máy thông thường
  
  • 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 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 dùng lệnh cấm ngắt hay dùng các lệnh máy đặc biệt ⇒ slide tiếp theo

Dùng lệnh cấm ngắt

• 
  Trong hệ thống uniprocessor: mutual exclusion được bảo đảm.
• Trên hệ thống multiprocessor: mutual exclusion không được đảm bảo vì
  
  • 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ẻ

Dùng các lệnh máy đặc biệt

• Ý tưởng
  • Việc truy xuất vào vào một địa chỉ của bộ nhớ vốn đã có tính loại trừ tương hỗ (chỉ có một thao tác truy xuất tại một thời điểm)
• Mở rộng
  • Thiết kế một lệnh máy đơn nguyên có thể thực hiện hai thao tác trên cùng một ô nhớ (vd: read và write)
  • Việc thực thi các lệnh máy như trên luôn bảo đảm mutual exclusion (ngay cả với multiprocessor)
• Các lệnh máy đặc biệt có thể đảm bảo mutual exclusion nhưng cần kết hợp với một số cơ chế khác để thoả mãn progress, tránh starvation và deadlock.

Lệnh TestAndSet

Đọc và ghi một biến chia sẻ bằng một lệnh đơn nguyên boolean TestAndSet(boolean & target) { boolean rv = target; target = true; return rv; } Áp dụng TestAndSetShared data:boolean lock = false;
Process P i : do { while (TestAndSet(lock)); critical section lock = false; remainder section } while (1);

• Mutual exclusion được bảo đảm: nếu P i vào CS, các process P j khác đều đang busy waiting
• Khi P i ra khỏi CS, sự chọn lựa process P j vào CS kế tiếp là tùy ý  starvation (bounded wait)
• Các processor (ví dụ Pentium) thông thường cung cấp một lệnh máy đơn nguyê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

Lệnh Swap void Swap(boolean & a, boolean & b) { boolean temp = a; a = b; b = temp; }

Biến chia sẻ (khởi tạo là false)

bool lock;

Process P i :

do { key = true; while (key == true) Swap(lock, key); critical section lock = false; remainder section } while (1);

Không thỏa mãn starvation freedom

Giải thuật dùng TestAndSet: thoả mãn 3 yêu cầu

• 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
• Progress
• Lockout-freedom: waiting in the cyclic order