• Race condition: nhiều process truy xuất và thao tác đồng thời lên dữ liệu chia sẻ ( như biến count ); kết quả cuối cùng của việc truy xuất đồng thời này phụ thuộc thứ tự thực thi của các lệnh thao tác dữ liệu.
• Để dữ liệu chia sẻ được nhất quán, cần bảo đảm sao cho các process lần lượt thao tác lên dữ liệu chia sẻ. Do đó, cần có cơ chế đồng bộ hoạt động của các process này.

• Giả sử có n process đồng thời truy xuất dữ liệu chia sẻ.
• Không phải tất cả các đoạn code đều cần được giải quyết vấn đề race condition mà chỉ những đoạn code có chứa các thao tác lên dữ liệu chia sẻ. Đoạn code này được gọi là vùng tranh chấp (critical section, CS ).
• Bài toán loại trừ tương hỗ: phải bảo đảm sự loại trừ tương hỗ (mutual exclusion, mutex), tức là khi một process P đang thực thi trong CS của P, không có process Q nào khác đồng thời thực thi các lệnh trong CS của Q.

• 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 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 bakery

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

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.

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);

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 TestAndSet
Shared 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

Bài tập