Bài toán đồng bộ
Đối với các chương trình single-thread, ta không cần quan tâm đến việc đồng bộ, bởi chương trình sẽ thực thi theo thứ tự từ trên xuống dưới từng câu lệnh một, trạng thái của chương trình sẽ chỉ bị thay đổi bởi chính nó. Tuy nhiên với các chương trình multi-thread, sẽ xảy ra trường hợp có nhiều hơn một thread cố gắng truy cập vào cùng một biến và gây ra sai sót.
Xét ví dụ sau khi tráo đổi giá trị hai biến x và y (swap):
x = 10;
y = 20;
t = x;
x = y; (*)
y = t;
Tại vị trí (*), giá trị của x và y bằng nhau, và bằng 20. Đây có thể coi là một trạng thái sai, bởi chỉ có thể x = 10, y = 20 hoặc x = 20, y = 10 sau khi tráo đổi xong. Trước hay sau khi tráo lại thì x * y cũng phải bằng 200, tuy nhiên tại vị trí (*), x * y sẽ là 400.Nếu có một thread thứ hai đọc giá trị của x và y để xử lý công việc, sẽ có một lúc nào đó giá trị nó đọc được sẽ bị sai.Cũng với ví dụ trên, giả sử có 2 thread cùng thực thi, bởi các câu lệnh có thể ngắt quãng và thực thi xen kẽ bởi các thead khác nhau, nên có thể xảy ra trường hợp sau:(thread 1 ký hiệu t1, thread 2 ký hiệu t2)
[t1] t = x;
[t1] x = y; // ở đây t = 10, x = 20
[t2] t = x; // tới đây t = 20, x = 20
[t1] y = t; // t = 20, x = 20, y = 20
[t2] x = y;
[t2] y = t;
Sau khi 2 thread kết thúc, cả x và y đều bằng 20, giá trị cũ của x bị mất.
Để giải quyết vấn đề này, ta phải có cách nào đó để các thead khác biết được thao tác swap này không được phép ngắt ngang, hay nói cách khác, thao tác này là atomic, các thread khác phải coi nó là 1 lệnh duy nhất. Bất kỳ thread nào muốn đọc giá trị của x và y đều phải chờ cho đến khi kết thúc swap.Các đoạn lệnh như vậy được gọi là các critical section, là những vùng mà chỉ duy nhất 1 thead được thực thi tại một thời điểm.
Để hỗ trợ cho việc đồng bộ, các hệ điều hành sẽ cung cấp các hàm đặc biệt, ý tưởng cơ bản của các hàm này là dựa trên giá trị của 1 biến, mỗi khi một thread đi vào critical section, nó sẽ tăng giá trị biến đó lên, khi ra ngoài nó sẽ giảm giá trị biến đó xuống. Chỉ cần nhìn vào giá trị của của biến đó là ta biết được có bao nhiêu thread đang chạy bên trong critical section. Ta không thể đơn giản dùng câu lệnh if để kiểm tra, bởi bản thân phép kiểm tra đó cũng phải atomic. Như trong ví dụ
if (count == 0)
{
(*)
count++;
// làm việc
//count--;
}
Bạn sẽ thấy ngay tại vị trí (*), chương trình đã đi vào critical section nhưng count vẫn bằng 0, khi đó nếu một thread khác kiểm tra giá trị của count, nó sẽ tưởng rằng chỉ có một mình nó đang vào critical section.
Giới thiệu về các cơ chế hỗ trợ đồng bộ của hệ điều hành:
Có 2 cách hệ điều hành hỗ trợ đồng bộ: spin lock và semaphore.
– Spin lock thực chất là một vòng lặp để kiểm tra giá trị một biến, vòng lặp chỉ thoát ra khi biến đó mang giá trị 0.
– Semaphore: semaphore là một loại biến đặc biệt, có thể truy cập từ nhiều thread, thậm chí từ các process khác nhau. Thread sẽ chuyển về trạng thái sleep nếu có thread khác đang nắm giữ nó, và sẽ thức dậy khi ai đó giải phóng semaphore.
Điểm khác nhau quan trọng nhất giữa spin lock và semaphore là thread của bạn vẫn chạy khi dùng spin lock, còn với semaphore, chương trình của bạn sẽ thực sự “ngủ”, hoàn toàn không chiếm CPU.
Nếu semaphore tốt như vậy, tại sao người ta còn cần đến spin lock? Nên nhớ mỗi khi bạn gọi đến hàm chờ semaphore, hệ điều hành sẽ lấy lại quyền điều khiển, đặt trạng thái của thread là sleep, hoặc nếu semaphore đang sẵn sàng, hệ điều hành sẽ chuyển trở lại thread, quá trình chuyển từ một thread của ứng dụng sang hệ điều hành và chuyển trở lại là môt quá trình tiêu tốn tài nguyên, khá nhiều câu lệnh phải được thực thi: lưu lại các thanh ghi, chuyển từ user space sang kernel space, bản thân kernel chạy trong một vùng địa chỉ khác nên sẽ phát sinh thêm các quá trình ánh xạ bộ nhớ… Do vậy nếu đoạn critical section là đơn giản và kết thúc nhanh chóng (như ví dụ swap bên trên), người ta sẽ chọn spin lock, ngược lại, tức thời gian thực thi trong critical section lớn ta sẽ dùng đến semaphore.
Có thể các bạn còn nghe tới khái niệm Mutex:
Mutex chỉ là một loại semaphore đặc biệt trong đó chỉ có hai trạng thái 0 và 1. Tức nó chỉ có xác định đang có ai dùng tài nguyên hay không, thay vì với semaphore bạn vẫn có thể cho phép nhiều hơn 1 thread được nắm giữ. Hay nói một cách đơn giản, nếu bạn muốn một tài nguyên nào đó chỉ được phép truy cập tối đa bởi 1 thread, bạn sẽ dùng Mutex, nhưng nếu muốn dùng một số lớn hơn, ví dụ cho phép tối đa 10 thread thực thi đồng thời thì bạn sẽ dùng semaphore.
Với các ngôn ngữ như Java hay C#, VB.NET, người ta sẽ cung cấp các phương thức rất đơn giản để làm việc với critical section, với các từ khóa như synchronized hay lock.
Đào Hải Nam 