Bài giảng môn Hệ điều hành - Chương 3: Tương tranh giữa các Process

n
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 39
Chương 3 : Tương tranh giữa các process
3. Phương pháp gởi/nhận thông báo
//Code C hiện thực bài toán Sản xuất-Tiêu dùng
#define N 100
void Consumer(void) {
int item;
message m;
//gởi n yêu cầu sản xuất tới Producer
for (i = 0; i <N; i++)
send (producer, &m);
while (TRUE) {
receive(producer, &m); //chờ nhận sản phầm từ consumer
item = extract_item(&m); //rút trích sản phầm mới từ thông báo
send(producer, &m); //gởi yêu cầu mới đến producer
consume_item(&tiem); //tiêu dùng sản phẩm
}
}
3.5 Các phương pháp sleep/wakeup
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 40
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
1. Bài toán 5 SV ăn cơm :
1. bàn ăn có 5 chén cơm 
dành cho 5 SV, đánh số
thứ tự từ 0 - 4.
2. do thiếu đủa, chỉ có 5 chiếc 
được để xen kẻ giữa các 
chén cơm, đánh số thứ tự
từ 0 -4.
3. mỗi SV ăn cơm cần 1 đôi 
đủa. Vì lịch sự, mỗi SV chỉ 
được phép lấy 2 chiếc kề
chén cơm của mình (chiếc 
bên trái và chiếc bên phải).
21
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 41
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
1. Bài toán 5 SV ăn cơm :
4. hãy tìm qui trình ăn cơm 
cho mỗi SV sao cho các 
điều kiện sau được thỏa :
- các SV ăn cơm được 
càng đồng thời càng tốt 
(hiệu quả nhất).
- các SV không được 
tranh chấp nhau trong 
việc lấy đôi đủa.
- các SV không bị
deadlock trong quá
trình chờ lấy đủa.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 42
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
1. Bài toán 5 SV ăn cơm :
Phân tích hoạt động ăn cơm của SV :
- quá trình ăn cơm không đòi hỏi phải sở hữu liên tục đôi đủa.
- quá trình ăn cơm là hoạt động lặp, mỗi chu kỳ gồm 3 công đoạn :
1. đang nhai cơm hay nói chuyện. (THINKING)
2. cố gắng chiếm hữu đôi đủa. (HUNGRY)
3. và cơm và gắp thức ăn rồi để đủa xuống bàn. (EATING)
- trong đó công đoạn 1 tốn nhiều thời gian nhất nhưng may mắn là 
trong công đoạn này, SV không cần đủa (tài nguyên). Còn bước 
2 và 3 thì rất ngắn và cần loại trừ tương hỗ giữa các SV.
22
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 43
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
1. Bài toán 5 SV ăn cơm :
Phát họa qui trình ăn cơm cho mỗi SV :
#define N 5
void Sinhvien (int i) {
 while (còn cơm) {
 think(); //công đoạn 1
 take_fork(i); //công đoạn 2, có thể bị kẹt 1 thời gian
take_fork((i+1)%N);
 eat();
 put_fork(i); //công đoạn 3 thường rất nhanh
put_fork((i+1)%N);
}
}
Qui trình ăn ở trên dễ bị deadlock, thí dụ như 5 SV đều thực hiện lệnh 
take_fork(i); đồng thời và đều thành công. Bây giờ họ thực hiện tiếp lệnh kế
thì tất cả đều bị dừng chờ mãi mãi vì không còn đủa trên bàn.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 44
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
1. Bài toán 5 SV ăn cơm :
//thuật giải cải tiến để tránh deadlock :
#define N 5
void Sinhvien (int i) {
 while (còn cơm) {
 think(); //công đoạn 1
L1: take_fork(i);
if (!asyn_take_fork((i+1)%5)) { //thất bại
 put_fork(i); sleep(random()); goto L1; //công đoạn 2
 } 
 eat(); //công đoạn 3
...
}
}
Qui trình ăn ở trên tránh được deadlock, nhưng còn dựa vào yếu tố ngẫu 
nhiên nên chưa hiệu quả triệt để.
23
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 45
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
//thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ :
#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef unsigned int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];
void Sinhvien (int i) {
 while (còn cơm) {
 think(); //công đoạn 1
 take_forks(i); //công đoạn 2, có thể bị kẹt 1 thời gian
 eat(); put_forks(i); //công đoạn 3
}
}
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 46
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
//thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ :
void take_forks(int i) {
 down(&mutex); //đảm bảo 0 tranh chấp khi lấy đủa
state[i] = HUNGRY; //ghi nhận trạng thái đang cố gắng lấy đủa
test(i); //kiểm tra lấy được không ? nếu được s[i] → 1
 up(&mutex); //đánh thức các SV khác để họ truy xuất đủa
down(&s[i]); //cố gắng và cơm & gắp thức ăn, có thể bị kẹt
}
void test (int i) {
if (state[i] == HUNGRY //SV i muốn lấy đủa
&& state[LEFT] != EATING //SV bên trái chưa lấy
&& state[RIGHT] != EATING) { //SV bên phải chưa lấy
state[i] = EATING; //ghi nhận SV i đã lấy được đủa
 up(&s[i]); //tăng s[i] → 1
}
}
24
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 47
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
//thuật giải dùng semaphore để giải quyết tranh chấp và đồng bộ :
void put_forks (int i) {
 down(&mutex); //đảm bảo 0 tranh chấp khi lấy đủa
state[i] = THINKING; //ghi nhận trạng thái không dùng đủa
test(LEFT); //kiểm tra lấy được không ? nếu được đánh thức
//SV LEFT dậy để và cơm và gắp thức ăn
test(RIGHT); //kiểm tra lấy được không ? nếu được đánh thức
//SV RIGHT dậy để và cơm và gắp thức ăn
 up(&mutex); //đánh thức các SV khác để họ truy xuất đủa
}
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 48
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
2. Bài toán đọc/ghi database :
1. có nhiều process cần đọc/ghi database.
2. làm sao cho việc đọc/ghi database của các process thỏa các 
điều kiện sau :
ƒ không tranh chấp nhau và không làm hỏng dữ liệu.
ƒ việc truy xuất database hiệu quả cao nhất.
Cách giải quyết đơn giản nhất :
1. xem toàn bộ database như 1 tài nguyên dùng chung, dùng 1 
semaphore nhị phân db để bảo vệ nó.
2. bất kỳ process đọc/ghi database nào cũng phải down(db) trước 
khi truy xuất database và up(db) sau khi hoàn tất việc truy xuất 
database.
25
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 49
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
2. Bài toán đọc/ghi database :
semaphore db = 1;
void Reader (void) {
while (cần đọc datbase) {
 down(&db); //đảm bảo 0 tranh chấp
 read_database(); //đọc database
 up(&db); //đánh thức các process khác dậy
use_database((); //dùng kết quả đọc được
}
}
void Writer (void) {
while (cần ghi database) {
prepare_data(); //chuẩn bị dữ liệu để ghi
 down(&db); //đảm bảo 0 tranh chấp
write_database(); //ghi lên database
 up(&db); //đánh thức các process khác dậy
}
}
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 50
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
2. Bài toán đọc/ghi database :
Thuật giải cho Reader ở slide trước còn kém hiệu quả, vì các process 
Reader phải loại trừ tương hỗ trong việc đọc database. Thực tế, việc đọc 
đồng thời database không làm hư database nên cần cho phép các Reader 
cùng đọc. Giải thuật Reader có thể hiệu chỉnh thành :
semaphore db = 1, mutex = 1; int rc = 0;
void Reader (void) {
while (cần đọc datbase) {
 down(&mutex); //đảm bảo 0 tranh chấp
if (++rc == 1) down(&db); //nếu là reader đầu tiên thì loại trừ với WR 
up(&mutex); //cho phép các process khác truy xuất rc
 read_database(); //đọc database
 down(&mutex); //đảm bảo 0 tranh chấp
if (--rc == 0) up(&db); //nếu là reader cuối thì cho phép writer
up(&mutex); //cho phép các process khác truy xuất rc
use_database(); //dùng kết quả đọc được
}
}
26
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 51
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
3. Bài toán ở tiệm hớt tóc :
1. tiệm chỉ có 1 ghế hớt và 1 thợ cắt.
2. tiệm có hàng ghế chờ N ghế. Tìm qui trình làm việc của thợ và khách 
trong tiệm sao cho các điều kiện sau đây được thỏa :
ƒ không tranh chấp nhau về việc ngồi ghế chờ và ghế cắt.
ƒ ít tốn năng lượng (ít thao tác thừa) nhất.
Phân tích :
1. Tiệm có lúc vắng, lúc nhiều khách. Thợ nên ngủ khi không có khách. 
Nếu được đánh thức, thợ sẽ mời từng khách đến ghế cắt và cắt tóc cho 
khách cho đến khi hết khách, thợ lại tiếp tục ngủ.
2. khi đến tiệm, nếu thấy còn ghế chờ, khách sẽ ngồi vào 1 ghế, đánh 
thức thợ rồi ngủ ngay. Khi nào thợ đánh thức và mời đến ghế cắt thì
khách thức dậy và đến ngồi vào ghế cắt rồi ngủ chờ thợ cắt xong, trả
tiền và ra về.
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 52
Chương 3 : Tương tranh giữa các process
3.6 Các bài toán IPC kinh điển
3. Bài toán ở tiệm hớt tóc :
//thuật giải cho thợ dùng semaphore
semaphore customers = 0;
semaphore barbers = 0;
semaphore mutex = 1; int waiting = 0;
void Barber (void) {
while (còn làm việc) {
down(&customers); //nếu 0 có khách, ngủ chờ
 down(&mutex); //đảm bảo 0 tranh chấp
waiting--; //giảm số lượng khách chờ 1 đơn vị
 up(&barbers); //đánh thức 1 khách và mời họ cắt tóc
up(&mutex); //cho phép các process khác truy xuất waiting
cut_hair(); //cắt tóc cho khách
}
}
27
Khoa Công nghệ Thông tin
Trường ĐH Bách Khoa Tp.HCM
Môn : Hệ điều hành
Slide 53
Chương 3 : Tương tranh giữa các process
Các bài toán IPC kinh điển
3. Bài toán ở tiệm hớt tóc :
//thuật giải cho khách dùng semaphore
semaphore customers = 0;
semaphore barbers = 0;
semaphore mutex = 1; int waiting = 0;
void Customer (void) {
 down(&mutex); //đảm bảo 0 tranh chấp
if (waiting<CHAIRS) { //nếu còn ghế chờ
 waiting++; //tăng waiting 1 đơn vị
 up(&customers); //đánh thức thợ dậy
up(&mutex); //cho phép các process khác truy xuất waiting
down(&barbers); //ngủ chờ thợ
 get_haircut(); //đến ghế cắt cho thợ cắt tóc
} else up(&mutex);
}