Thảo luận Bài 7

Hai quá trình cùng chia sẻ 1 vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ tương hỗ để truy xuất vùng đệm và được khởi tạo giá trị bằng 1. Các biến semaphore empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo đến giá trị n, biến semaphore full được khởi tạo đến giá trị 0.
Dữ liệu chia sẻ:
SEMAPHORE full, empty, mutex;
Khởi tạo:
full=0;
mutex=1;
empty=BUFFER_SIZE;

Đèn hiệu nhị phân chỉ có 2 trạng thái (xanh và đỏ - 1 và 0).
VD: Giả sử có 1 cây cầu ở đầu cầu có 1 cái đèn, trên đoạn đường đến cầu có các oto (vd oto1, oto2...) và cầu chỉ có tải trọng 1 chiếc oto đi qua tại 1 thời điểm khi duy chuyển qua cầu, đèn báo có 2 trạng thái 0 và 1 (xanh và đỏ), đèn xanh xe oto được phép đi, đỏ oto còn lại phải chờ đến lượt, giống như trạng thái wait(s);, signal(s).
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):
typedef int semaphore; // Định nghĩa kiểu Đèn hiệu
wait (semaphore S) {
while ( S <= 0 ); // Chờ bận nếu S<=0
S --; // Giảm S đi 1
}

signal (semaphore S) {
S ++; // Tăng S lên 1
}
- Việc kiểm tra S <= 0 và giảm S (trong Wait) hoặc tăng S (trong Signal) phải được thực hiện trọn vẹn (không xảy ra ngắt trong thời gian thi hành), do đó Wait và Signal được gọi là các tác nguyên (Atomic Operations).

- Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).
Ví dụ:
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Ba
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 18 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Lê Văn Ba


. Nội dung đơn này phải được đảm bảo tính toàn vẹn (Integrity), ví dụ: Phía trên là Lê Văn Ba thì phía dưới cũng phải là Lê Văn Ba.
. Nếu vài tiến trình (hơn 1) cùng sửa đơn trên một lúc (không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ, giả sử tiến trình P1 (nhà sản xuất) sửa Lê Văn Ba phía trên thành Lê Văn Bàng, trong khi P2 (nhà sản xuất khác) sửa Lê Văn Ba phía dưới thành Lê Văn Bá, mà có tiến trình P3 (nhà tiêu thụ) nào đó "lấy" đơn về dùng (để in ra) thì kết quả sẽ không nhất quán như sau:
Kính gửi: Giám đốc công ty x
Tôi tên là: Lê Văn Bàng
..........(nội dung đơn).............
TP Hồ Chí Minh, ngày 18 tháng 4 năm 2012
Người làm đơn
....(chữ ký)....
Lê Văn Bá[center]

HANDLE s;
s = CreateSemaphore(0, n, max, t); //t là tên đèn hiệu hoặc để giá trị 0.
WaitForSingleObject(s, timeout); //timeout = INFINITE hoặc số mili giây chờ.
RealeaseSemaphore(s, 1, NULL);

sem_t s;
sem_init(&s, 0, n);
sem_wait(&s);
sem_post(&s);

-Định nghĩa: Semaphore là một cờ hiệu trong thực thi đa tuyến, nếu một tuyến cần sử dụng tài nguyên nó sẽ thông báo với semaphore.
-Khởi đầu Semaphore mang giá trị dương. Tuyến yêu cầu sử dụng tài nguyên bằng cách gọi hàm sem_wait(), semaphore sẽ kiểm tra giá trị của mình xem có >0 hay không.
-Nếu Semaphore vẫn còn >0, nó sẽ tự động làm giảm giá trị đi 1 và cho phép tuyến sử dụng tài nguyên.
-Nếu giá trị Semaphore <=0 hệ thống sẽ tạm thời dừng tuyến.
-Khi một tuyến sử dụng xong tài nguyên nó gọi hàm sem_post() để trả quyền sử dụng tài nguyên lại cho Semaphore cấp phát cho lần sử dụng khác.
Ứng dụng Semaphore:
-Bài toán nổi tiếng về tranh chấp tài nguyên dễ hiểu nhất là bài toán “sản xuất – tiêu thụ”.
-Hai tuyến chạy song song nhau. Một tuyến chịu trách nhiệm sản xuất ra sản phẩm. Một tuyến lấy sản phẩm ra để tiêu thụ.

- Khắc phục chờ bận: Chuyển vòng lặp chờ
thành việc sử dụng toán tử block (tạm dừng)
- Để khôi phục thực hiện từ block, ta có toán tử
wakeup
- Khi đó để cài đặt, ta có cấu trúc dữ liệu mới
cho semaphore:
typedef struct {
int value; // Giá trị của semaphore
struct process *L; // Danh sách tiến trình chờ...
} semaphore;
*
void wait(semaphore *S)
{
S->value--;
if (S->value<0) {
Thêm tiến trình gọi
toán tử vào s->L;
block();
}
}
*
void signal(semaphore *S)
{
S->value++;
if (S->value<=0) {
Xóa một tiến trình P
ra khỏi s->L;
wakeup(P);
}
}

Mục đích đồng bộ hóa: để đảm bảo tính nhất quán của tài nguyên dùng chung, tránh hiện tượng Deadlock
VD: tính toàn vẹn của 1 lá đơn xin việc (phần họ tên và phần ký tên ghi họ tên phải giống nhau)
Đoạn tương tranh: là 1 đoạn mã của tiến trình mà khi thực hiện nó truy cập và tác động đến tài nguyên dùng chung
Tính loại trừ: mỗi thời điểm chỉ có 1 tiến trình được phục vụ (truy cập hay thay đổi tài nguyên dùng chung)

Ta dùng 2 đèn hiệu :
-SemFull : kiểm tra số Sản phẩm trong bộ đệm.
-SemEmpty: Kiểm tra số vùng trống trong bộ đệm.

Hai tác nguyên: Wait và Signal

Producer()

{ // Chờ khi bộ đệm đầy

WaitforSignal(SemFull,INITE)

//Sản xuất sản phẩm

Releave(SemEmpty)

//Bộ đệm đã có Sản phẩm

}

Consumer()

{ // Chờ đến khi có sản phẩm

WaitforSignal(SemEmpty ,INITE)

//tiêu thụ sản phẩm

Releave(SemFull)

//Bộ đệm đã có chổ trống

}

- Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

Đồng bộ hóa tiến trình là đồng bộ hóa các luồng ở bên trong của tiến trình, là biết cách điều khiển các luồng cho chúng ăn nhập với nhau có trước có sau để đảm bảo tính nhất quán và tính toàn vẹn của tài nguyên dùng chung,và đảm bảo theo yêu cầu của người dùng.
Tài nguyên dùng chung trong bài toán sản xuất tiêu thụ là Buffer, các biến In,Out
Ví dụ BUFFER_SIZE 10
Tài nguyên dùng chung là vùng nhớ để chúng trao đổi thông tin với nhau.
Tránh được hiện tượng Deadlock.
Trở lại vấn đề bài toán sản xuất – tiêu thụ với giải pháp mới dùng biến đếm Count.
Cấu trúc bộ nhớ đệm chung.
#define BUFFER_SIZE 10
typedef struct {
. . . // Mô tả các thành phần của 1 khoang chứa
} item;
item buffer [BUFFER_SIZE]; // Bộ nhớ đệm.
int in = 0; // Con trỏ tới vị trí trống kế kiếp.
int out = 0; // Con trỏ tới vị trí lấy tiếp theo.
int count= 0;// Đếm số sản phẩm có trong Buffer.

Producer:
Wait (SemEmpty);
Wait (Mutex);
Buffer [in] = sp mới; //xếp sản phẩm vào bộ đệm
in = (in + 1) % BUFFER_SIZE;
Signal (SemFull);
Signal(Mutex);
Consumer:
Wait (SemFull);
Wait (Mutex);
p = Buffer [out] //lấy sản phẩm ra khỏi bộ đệm
out = (out + 1) % BUFFER_SIZE;
Signal (SemEmpty);
Signal (Mutex);
Lưu ý:
Giá trị ban đầu của Mutex là 1.
Giá trị ban đầu của SemFull là 0.
Giá trị ban đầu của SemEmpty là BUFFER_SIZE.

Giả sử có hai tiến trình P1 và P2 thực hiện công việc của 1 kế toán, và cùng chia sẻ 1 vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút 1 khoản tiền tienrut từ tài khoản:
if (taikhoan - tienrut >= 0)
taikhoan = taikhoan - tienrut;
else
error( " không thể rút tiền !");

Giả sử trong tài khoản còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau:
-Sau khi đã kiểm tra điều kiện ( taikhoan - tienrut >=0 ) và nhận được kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.
-P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 ( do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400.
-Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện ( taikhoan - tienrut >= 0) vì đã được kiểm tra trong đợt xử lý trước, mà nó sẽ thực hiện rút tiền. Giá trị của taikhoan sẽ được cập nhật lại thành -100. Tình huống lỗi xảy ra !

Các tình huống tương tự như thế có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng 1 vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống, được gọi là các tình huống tranh đoạt điều khiển.

Các tiến trình p0,p1,pn-1 cùng làm việc song song, đồng hành lẫn nhau ( gọi là miền găng ).
Khi chúng hoạt động, chúng tác động, thay đổi tài nguyên dùng chung,những lệnh trong đoạn tương tranh ảnh hưởng đến các biến, tài nguyên dùng chung.
Các tiến trình tương tranh có đoạn đăng nhập, đăng xuất và đoạn còn lại

Để ngăn chặn các tình huống lỗi có thể xảy ra thì:
Mutual Exclusion: tính loại trừ lẫn nhau.

A: đang làm việc.
B: không được thực hiện.
A làm B nghỉ ( bắt buộc )

Nếu không sẽ có 2 người ghi lên bảng cùng lúc, phải bảo đảm có 1 người ghi, một người chụp nếu không 2 tiến trình cùng tác động, ảnh hưởng đến tài nguyên( theo ví dụ của Thầy)
Mỗi thời điểm chỉ có một mà thôi.

Một tiến trình bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng.

Không có tiến trình nào phải chờ vô hạn để được vào miền găng.

Đoạn tương tranh là đoạn mã của tiến trình, khi thực hiện thì ảnh hưởng đến vùng tranh chấp
VD: Vùng tranh chấp là bảng đen, mỗi thời điểm có một sinh viên thao tác trên đó, sau khi sinh viên đó xong thì sinh viên khác mới tiếp tục được thao tác trên bảng.

Xét 2 process: P1 và P2
Yêu cầu: lệnh S1 trong P1 được thực thi trước lệnh S2 trong P2
Định nghĩa semaphore "synch" dùng đồng bộ
Khởi động semaphore
synch.value = 0
Để đồng bộ họat động theo yêu cầu, P1 phải định nghĩa như sau:
S1;
signal (synch);
Và P2 định nghĩa như sau:
wait (synch);
S2;

Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung cấp kèm theo những cơ chế đồng bộ hóa để bảo đảm hoạt động của các tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đây:
Yêu cầu độc quyền truy xuất (Mutual exclusion)
Các tài nguyên trong hệ thống được phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một ( hay một số lượng hạn chế ) tiến trình sử dụng tại một thời điểm. Tính không thể chia sẻ của tài nguyên thường có nguồn gốc từ một trong hai nguyên nhân sau đây:
• Đặc tính cấu tạo phần cứng của tài nguyên không cho phép chia sẻ.
Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, có nguy cơ xảy ra các kết quả không dự đoán được do hoạt động của các tiến trình trên tài nguyên ảnh hưởng lẫn nhau.
Để giải quyết vấn đề, cần bảo đảm tiến trình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ có một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ.
Yêu cầu phối hợp (Synchronization)
Nhìn chung, mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước, vì điều này phụ thuộc vào nhiều yếu tố động như tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình được cấp phát bộ xử lý… Có thể nói rằng các tiến trình hoạt động không đồng bộ với nhau. Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đó cần phải đồng bộ hóa hoạt động của các tiến trình , ví dụ một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đó …

while (1) {
remainder section // Đoạn còn lại
entry section // Đoạn đăng nhập
critical section // Đoạn Tương Tranh
exit section // Đoạn Đăng Xuất.
remainder section // Đoạn còn lại.
}

-Bài toán nổi tiếng về tranh chấp tài nguyên dễ hiểu nhất là bài toán “sản xuất – tiêu thụ”.
-Hai tuyến chạy song song nhau. Một tuyến chịu trách nhiệm sản xuất ra sản phẩm. Một tuyến lấy sản phẩm ra để tiêu thụ.

Nội dung đơn này phải đảm bảo tính toàn vẹn( Integrity), ví dụ: Phía trên là Nguyễn Văn A thì phía dưới cũng phải là Nguyễn Văn A.
Nếu vài tiến trình(hơn 1) cùng sửa đơn trên một lúc( không đảm bảo được tính Loại trừ lẫn nhau) thì nội dung của nó có thể không đúng. Ví dụ: Giả sử tiến trình P1(nhà sản xuất) sửa Nguyễn Văn A phía trên thành Nguyễn Văn An, trong khi P2(nhà sản xuất khác) sửa Nguyễn Văn A phía dưới thành Nguyễn Văn Ân, mà có tiến trình P3( nhà tiêu thụ) nào đó "lấy" đơn về dùng( để in ra) thì kết quả sẽ không nhất quán.

HANDLE semEmpty, semFull; //hai đèn hiệu
CRITICAL_SECTION critSec;//Biến kiểu Mutex
void Producer(void * p)
{
while (1)
{
// ... Sản xuất (nextProduced)
// Chờ đến khi có chỗ trống
WaitForSingleObject(semEmpty, INFINITE);
EnterCriticalSection(&critSec);
//…Sắp sản phẩm vào Buffer
// Tăng (semFull) lên 1
ReleaseSemaphore(semFull, 1, NULL);
LeaveCriticalSection(&critSec);
SuspendThread(GetCurrentThread());
}
}
void Consumer()
{
int nextConsumed;
while (1)
{
// Chờ đến khi có sản phẩm
WaitForSingleObject(semFull, INFINITE);
EnterCriticalSection(&critSec);
nextConsumed=buffer[out];
out=(out+1)%BUFFER_SIZE;
// Tăng (semEmpty) lên 1
ReleaseSemaphore (semEmpty, 1, NULL);
LeaveCriticalSection(&critSec);
// ... Tiêu thụ (nextConsumed)
SuspendThread(GetCurrentThread());
}
}

Giả sử có hai tiến trình P1 và P2 thực hiện công việc của các kế toán, và cùng chia sẻ một vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút một khoản tiền tienrut từ tài khoản:

if (taikhoan - tienrut >=0)

taikhoan = taikhoan - tienrut;

else

error(" khong the rut tien ! ");

Giả sử trong tài khoản hiện còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau :

Sau khi đã kiểm tra điều kiện (taikhoan - tienrut >=0) và nhận kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.

P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 (do P1 vẫn chưa rút tiền) và rút 400. Giá trị của taikhoan được cập nhật lại là 400.

Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện (taikhoan - tienrut >=0).vì đã kiểm tra trong lượt xử lý trước mà thực hiện rút tiền. Giá trị của tai khoan sẽ lại được cập nhật thành -100. Tình huống lỗi xảy ra !

Các tình huống tương tự như thế - có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng một vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống.

Đoạn tương tranh :Xét một hệ có n tiến trình P0,P1, ...,Pn, mỗi tiến trình có một đoạn mã lệnh, nếu như trong đoạn mã này các tiến trình thao tác trên các biến chung,đọc ghi file... (tổng quát: thao tác trên dữ liệu chung) thì đoạn mã lệnh đó là đoạn tương tranh.
- Tính Loại trừ lẫn nhau hay Loại trừ tương hỗ (Mutual Exclusion) về phương diện thời gian: Khi có 1 tiến trình đang ở trong ĐTT của nó thì không có tiến trình nào khác trong nhóm cũng tại đoạn như vậy, nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được phép truy cập và/hoặc thay đổi tài nguyên chung.
- Các tiến trình tương tranh có cấu trúc mã bao gồm Entry Section (Đoạn Đăng nhập), Critical Section (Đoạn Tương tranh), Exit Section (Đoạn Đăng xuất) và các Remainder Section (Đoạn Còn lại).

Admin
- Đi thi mà trình bày như Giáo trình thế này thì không được điểm đâu !
- Phải trình bày theo cách hiểu của mình, với ví dụ minh hoạ nữa !

- Mục đích của đồng bộ hóa công việc các tiến trình là đảm bảo Tính nhất quán của tài nguyên chung và Tránh được hiện tượng Deadloack( Hiện tượng kẹt tiến trình )
+ Đảm bảo tính nhất quán của tài nguyên dùng chung.
+ Tránh được hiện tượng Deadlock (Hiện tượng kẹt tiến trình) .
VD1: một trường học chỉ có 1 phòng lab (tài nguyên dùng chung) , lớp có giờ học trước thì được vào phòng lab học, các lớp còn lại phải chờ đến khi lớp học trước đó hết giờ mới được vào phòng lab

-Đoạn tương tranh là doạn mã cho tiến trình mà khi thực hiện nó truy cập, tác động và thay đổi được tài nguyên dùng chung.
Còn đoạn mã ko truy cập, tác động và thay đổi được tài nguyên dùng chung là đoạn còn lại .
-Đồng bộ hóa tiến trình là đồng bộ hóa các luồng ở bên trong của tiến trình, là biết cách điều khiển các luồng cho chúng ăn nhập với nhau có trước có sau để đảm bảo tính nhất quán và tính toàn vẹn của tài nguyên dùng chung,và đảm bảo theo yêu cầu của người dùng.
Tài nguyên dùng chung trong bài toán sản xuất tiêu thụ là Buffer, các biến In,Out
- Đèn hiệu là phương tiện đồng bộ hoá được E.W. Dijkstra đề xuất năm 1965.
- Đèn hiệu được mô tả bằng một biến kiểu nguyên với 2 tác nguyên là Wait (Chờ) và Signal (Báo hiệu):
typedef int semaphore; // Định nghĩa kiểu Đèn hiệu