BÀI 1 TỔng quan về HỆ ĐIỀu hàNH

send(producer, &m); // gởi N thông điệp empty

receive(producer, &m); // chờ thông điệp dữ liệu

remove_item(&m,&item);// lấy dữ liệu từ thông điệp

send(producer, &m); // gởi thông điệp empty

consumer_item(item); // xử lý dữ liệu

}

}

Sử dụng một biến chung rc để ghi nhớ số lượng các tiến trình Reader muốn truy xuất cơ sở dữ liệu. Hai semaphore cũng được sử dụng : mutex, kiểm soát sự truy cập đến rc; và db, kiểm tra sự truy xuất độc quyền đến cơ sở dữ liệu.

Reader()

down(&mutex); // giành quyền truy xuất rc

rc = rc + 1; // thêm một tiến trình Reader

if (rc == 1) // nếu là Reader đầu tiên thì

down(&db); // cấm Writer truy xuất dữ liệu

up(&mutex); // chấm dứt truy xuất rc

read_database(); // đọc dữ liệu

down(&mutex); // giành quyền truy xuất rc

rc = rc - 1; // bớt một tiến trình Reader

if (rc == 0) // nếu là Reader cuối cùng thì

up(&db); // cho phép Writer truy xuất db

up(&mutex); // chấm dứt truy xuất rc

use_data_read();

}

}

{

while (TRUE) {

create_data();

down(&db); // giành quyền truy xuất db

write_database(); // cập nhật dữ liệu

up(&db); // chấm dứt truy xuất db

}

}

III.2.2. Monitor

{

if (busy) // nếu db đang bận, chờ

wait(OKRead);

rc++; // thêm một Reader

signal(OKRead);

}

procedure FinishRead()

{

rc--; // bớt một Reader

signal(OKWrite); // thì cho phép Writer

// truy xuất db

}

procedure BeginWrite()

{

if (busy || rc != 0) // nếu db đang bận, hay một

busy = true;

}

procedure FinishWrite()

{

busy = false;

signal(OKRead);

else

signal(OKWrite);

Reader()

{

ReaderWriter.BeginRead();

ReaderWriter.FinishRead();

}

}

Writer()

{

create_data(&info);

Write_database();

ReaderWriter.FinishWrite();

}

}

Cần có một tiến trình server điều khiển việc truy xuất cơ sở dữ liệu.

Các tiến trình Writer và Reader gởi các thông điệp yêu cầu truy xuất đến server và nhận từ server các thông điệp hồi đáp tương ứng .

Reader()

send (server, RequestRead);

receive (server, value);

print(value); }

}
Writer()

{

while (TRUE) {

create_data(&value);

send (server, RequestWrite,value);

receive (server,OKWrite); }

}

IV.1. Định nghĩa:

Một tập hợp các tiến trình được định nghĩa ở trong tình trạng tắc nghẽn khi mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh được.

Nói cách khác, mỗi tiến trình trong tập hợp đều chờ được cấp phát một tài nguyên hiện đang bị một tiến trình khác cũng ở trạng thái blocked chiếm giữ. Như vậy không có tiến trình nào có thể tiếp tục xử lý , cũng như giải phóng tài nguyên cho tiến trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn !

IV.2. Điều kiện xuất hiện tắc nghẽn

Coffman, Elphick và Shoshani đã đưa ra 4 điều kiện cần có thể làm xuất hiện tắc nghẽn:

Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình , khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.

Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số tài nguyên mới.

Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preemption): Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sủ dụng chúng xong.

Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên ( Circular wait): có ít nhất hai tiến trình chờ đợi lẫn nhau : tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại.

Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện trên thì không có tắc nghẽn.

IV.3. Đồ thị cấp phát tài nguyên

Có thể sử dụng một đồ thị để mô hình hóa việc cấp phát tài nguyên. Đồ thị này có 2 loại nút : các tiến trình được biễu diễn bằng hình tròn, và mỗi tài nguyên được hiển thị bằng hình vuông

Chủ yếu có ba hương tiếp cận để xử lý tắc nghẽn :

IV.5. Ngăn chặn tắc nghẽn

Để tắc nghẽn không xảy ra, cần bảo đảm tối thiểu một trong 4 điều kiện cần không xảy ra:

Tài nguyên không thể chia sẻ : nhìn chung gần như không thể tránh được điều kiện này vì bản chất tài nguyên gần như cố định. Tuy nhiên đối với một số tài nguyên về kết xuất, người ta có thể dùng các cơ chế spooling để biến đổi thành tài nguyên có thể chia sẻ.

Sự chiếm giữ và yêu cầu thêm tài nguyên: phải bảo đảm rằng mỗi khi tiến trình yêu cầu thêm một tài nguyên thì nó không chiếm giữ các tài nguyên khác. Có thể áp đặt một trong hai cơ chế truy xuất sau :

Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi bắt đầu xử lý .

=> phương pháp này có khó khăn là tiến trình khó có thể ước lượng chính xác tài nguyên cần sử dụng vì có thể nhu cầu phụ thuộc vào quá trình xử lý . Ngoài ra nếu tiến trình chiếm giữ sẵn các tài nguyên chưa cần sử dụng ngay thì việc sử dụng tài nguyên sẽ kém hiệu quả.

=> phương pháp này làm phát sinh các khó khăn trong việc bảo vệ tính toàn vẹn dữ liệu của hệ thống.

gọi R = {R₁, R₂,...,Rm} là tập các loại tài nguyên.

Các loại tài nguyên được phân cấp từ 1-N.

Ví dụ : F(đĩa) = 2, F(máy in) = 12

Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định : khi tiến trình đang chiếm giữ tài nguyên Ri thì chỉ có thể yêu cầu các tài nguyên Rj nếu F(Rj) > F(Ri).

IV.6. Tránh tắc nghẽn

Ngăn cản tắc nghẽn là một mối bận tâm lớn khi sử dụng tài nguyên. Tránh tắc nghẽn là loại bỏ tất cả các cơ hội có thể dẫn đến tắc nghẽn trong tương lai. Cần phải sử dụng những cơ chế phức tạp để thực hiện ý định này.