Bài giảng Hệ điều hành nâng cao - Trần Hạnh Nhi - Bài giảng 4: Đồng bộ hóa tiến trình

phương
thức của monitor :
„ P1 : M.C() // i=5
„ P2: M.B() // printf(j)
MethodA
i=0
MethodB
prinf(j)
MethodC
i=5
Share variable: i,j;
Monitor M
10/28/2005 Trần Hạnh Nhi 56
Monitor : Ngữ nghĩa và tính chất(2)
„ Tự động bảo đảm Mutual Exclusion
„ Tại 1 thời điểm chỉ có 1 tiến trình được thực
hiện các phương thức của Monitor
„ Các tiến trình không thể vào Monitor sẽ
được đưa vào Entry queue của Monitor
„ Ví dụ
„ P1 : M.A();
„ P6 : M.B();
„ P7 : M.A();
„ P8 : M.C();
MethodA
i = 0
MethodB
printf(i)
MethodC
i=5
P1
P8P7P6
Entry
queue
Share variable: i,j;
10/28/2005 Trần Hạnh Nhi 57
Monitor : Ngữ nghĩa và tính chất(3)
„ Hỗ trợ Synchronization với các condition 
variables
„ Wait(c) : Tiến trình gọi hàm sẽ bị blocked
„ Signal(c): Giải phóng 1 tiến trình đang bị
blocked trên biến điều kiện c
„ C.queue : danh sách các tiến trình blocked 
trên c
„ Trạng thái tiến trình sau khi gọi Signal?
„ Blocked. Nhường quyền vào monitor cho tiến
trình được đánh thức
„ Tiếp tục xử lý hết chu kỳ, rồi blocked
MethodA
i=0;
signal(c1)
MethodB
MethodC
wait(C1);
i=5
signal(C2 );
C1:
C2: P5
P4
P1
P3
P2
P8P7P6
Entry
queue
Share variable: i,j;
Condition variable:
P1
10/28/2005 Trần Hạnh Nhi 58
Sử dụng Monitor
ƒ Tổ chức “độc quyền truy xuất”
Pi
M.AccessMutual(); //CS
ƒ Tổ chức “hò hẹn”
P1 : 
M.F1();
P2:
M.F2();
Monitor M
 RC;
Function AccessMutual
CS; // access RC
Monitor M
Condition c;
Function F1
Job1;
Signal(c);
Function F2
Wait(c);
Job2;
10/28/2005 Trần Hạnh Nhi 59
ƒĐược hỗ trợ bởi HĐH
ƒĐồng bộ hóa trên môi trường phân tán
ƒ 2 primitive Send & Receive
ƒ Cài đặt theo mode blocking
Server P
1. Send Request
2. Receive Accept
3. Send Finish
Giải pháp Sleep & Wakeup 3: Message
10/28/2005 Trần Hạnh Nhi 60
Nội dung bài giảng
„ Xử lý đồng hành và các vấn đề:
„ Vấn đề tranh đoạt điều khiển (Race Condition)
„ Vấn đề phối hợp xử lý
„ Bài toán đồng bộ hóa
„ Yêu cầu độc quyền truy xuất (Mutual Exclusion)
„ Yêu cầu phối hợp xử lý (Synchronization)
„ Các giải pháp đồng bộ hoá
„ Busy waiting
„ Sleep & Wakeup
„ Các bài toán đồng bộ hoá kinh điển
„ Producer – Consumer
„ Readers – Writers
„ Dinning Philosophers
10/28/2005 Trần Hạnh Nhi 61
Bài toán đồng bộ kinh điển 1: 
Producer - Consumer (Bounded-Buffer Problem)
P
C
Buffer (N) ( )
„ Mô tả : 2 tiến trình P và C hoạt động đồng hành
„ P sản xuất hàng và đặt vào Buffer
„ C lấy hàng từ Buffer đi tiêu thụ
„ Buffer có kích thước giới hạn
„ Tình huống
„ P và C đồng thời truy cập Buffer ?
„ P thêm hàng vào Buffer đầy ?
„ C lấy hàng từ Buffer trống ?
ƒ P không được ghi dữ liệu vào buffer đã đầy (Rendez-vous)
ƒ C không được đọc dữ liệu từ buffer đang trống (Rendez-vous)
ƒ P và C không được thao tác trên buffer cùng lúc (Mutual Exclusion)
10/28/2005 Trần Hạnh Nhi 62
Producer – Consummer : Giải pháp Semaphore
„ Các biến dùng chung giữa P và C
„ BufferSize = N; // số chỗ trong bộ đệm
„ semaphore mutex = 1 ; // kiểm soát truy xuất độc quyền
„ semaphore empty = BufferSize; // số chỗ trống 
„ semaphore full = 0; // số chỗ đầy
„ int Buffer[BufferSize]; // bộ đệm dùng chung
10/28/2005 Trần Hạnh Nhi 63
Producer – Consummer : Giải pháp Semaphore
Producer()
{
int item;
while (TRUE) 
{ 
produce_item(&item);
down(&empty);
down(&mutex)
enter_item(item,Buffer);
up(&mutex);
up(&full);
}
}
Consumer()
{
int item;
while (TRUE) 
{ 
down(&full); 
down(&mutex);
remove_item(&item,Buffer); 
up(&mutex); 
up(&empty);
consume_item(item); 
}
}
10/28/2005 Trần Hạnh Nhi 64
P&C - Giải pháp Semaphore: Thinking...
Producer()
{
int item;
while (TRUE) 
{ 
produce_item(&item);
down(&mutex)
down(&empty);
enter_item(item,Buffer);
up(&mutex);
up(&full);
}
}
Consumer()
{
int item;
while (TRUE) 
{ 
down(&mutex);
down(&full); 
remove_item(&item,Buffer); 
up(&mutex); 
up(&empty);
consume_item(item); 
}
}
10/28/2005 Trần Hạnh Nhi 65
Producer – Consummer : Giải pháp Monitor
monitor ProducerConsumer
condition full, empty;
int Buffer[N], count;
procedure enter();
{
if (count == N) 
wait(full);
enter_item(item,Buffer); 
count ++; 
if (count == 1) 
signal(empty);
}
procedure remove();
{
if (count == 0) 
wait(empty) 
remove_item(&item,Buffer);
count --; 
if (count == N-1) 
signal(full);
}
count = 0;
end monitor;
10/28/2005 Trần Hạnh Nhi 66
Producer – Consummer : Giải pháp Monitor
Producer()
{
int item;
while (TRUE)
{
produce_item(&item); 
ProducerConsumer.enter; 
}
}
Consumer();
{
int item;
while (TRUE)
{
ProducerConsumer.remove;
consume_item(item); 
}
}
10/28/2005 Trần Hạnh Nhi 67
Producer – Consummer : Giải pháp Message
Producer()
{
int item;
message m; 
while (TRUE) 
{
produce_item(&item);
receive(consumer, Request);
create_message(&m, item);
send(consumer,&m);
}
} 
Consumer();
{
int item;
message m;
for(0 to N)
send(producer, Request); 
while (TRUE)
{
receive(producer, &m);
remove_item(&m,&item); 
send(producer, Request);
consumer_item(item); 
}
}
Coi chừng
Deadlock
10/28/2005 Trần Hạnh Nhi 68
Bài toán đồng bộ hoá kinh điển 2:
Readers & Writers 
„ Mô tả : N tiến trình Ws và Rs hoạt động đồng hành
„ Rs và Ws chia sẻ CSDL
„ W cập nhật nội dung CSDL
„ Rs truy cập nội dung CSDL
„ Tình huống
„ Các Rs cùng truy cập CSDL ?
„ W đang cập nhật CSDL thì các Rs truy cập CSDL ?
„ Các Rs đang truy cập CSDL thì W muốn cập nhật CSDL ?
ƒ W không được cập nhật dữ liệu khi có ít nhất một R đang truy xuất CSDL (ME)
ƒ Rs không được truy cập CSDL khi một W đang cập nhật nội dung CSDL (ME)
ƒ Tại một thời điểm , chỉ cho phép một W được sửa đổi nội dung CSDL (ME)
Database
R1
R2 R3
W1 W2
10/28/2005 Trần Hạnh Nhi 69
Readers-Writers với “active readers”
10/28/2005 Trần Hạnh Nhi 70
Readers-writers với một “active writer”
10/28/2005 Trần Hạnh Nhi 71
Ưu tiên ai hơn đây ?
10/28/2005 Trần Hạnh Nhi 72
Readers & Writers 
„ W độc quyền truy xuất CSDL
„ W hiện tại kết thúc cập nhật CSDL : ai vào ?
„ Cho W khác vào, các Rs phải đợi
„ Ưu tiên Writer, Reader có thể starvation
„ Cho các Rs vào, Ws khác phải đợi
„ Ưu tiên Reader, Writer có thể starvation
10/28/2005 Trần Hạnh Nhi 73
Readers & Writers : Giải pháp Semaphore
„ Các biến dùng chung giữa Rs và Ws
„ semaphore db = 1; // Kiểm tra truy xuất CSDL
10/28/2005 Trần Hạnh Nhi 74
R&W : Giải pháp Semaphore (1)
Reader()
{
down(&db); 
read-db(Database); 
up(&db);
}
Writer()
{
down(&db); 
write-db(Database); 
up(&db);
}
ƒ Chuyện gì xảy ra ?
ƒ Chỉ có 1 Reader được đọc CSDL tại 1 thời điểm !
10/28/2005 Trần Hạnh Nhi 75
R&W : Giải pháp Semaphore (2)
Reader()
{
rc = rc +1;
if (rc ==1) 
down(&db); 
read-db(Database); 
rc = rc – 1;
if (rc == 0)
up(&db);
}
Writer()
{
down(&db); 
write-db(Database); 
up(&db);
}
ƒ Đúng chưa ?
ƒ rc là biến dùng chung giữa các
Reader...
ƒ CS đó/
10/28/2005 Trần Hạnh Nhi 76
Readers & Writers : Giải pháp Semaphore
„ Các biến dùng chung giữa Rs và Ws
„ semaphore db = 1; // Kiểm tra truy xuất CSDL
„ Các biến dùng chung giữa Rs 
„ int rc; // Số lượng tiến trình Reader
„ semaphore mutex = 1; // Kiểm tra truy xuất rc
10/28/2005 Trần Hạnh Nhi 77
R&W : Giải pháp Semaphore (3)
Reader()
{
down(&mutex);
rc = rc +1;
if (rc ==1) 
down(&db);
up(mutex); 
read-db(Database); 
down(mutex);
rc = rc – 1;
if (rc == 0)
up(&db);
up(mutex);
}
Writer()
{
down(&db); 
write-db(Database); 
up(&db);
}
Ai được ưu tiên ?
10/28/2005 Trần Hạnh Nhi 78
R&W : Giải pháp Semaphore (Thinking...)
Reader()
{
down(&mutex);
rc = rc +1;
up(mutex); 
if (rc ==1) 
down(&db);
read-db(Database); 
down(mutex);
rc = rc – 1;
up(mutex);
if (rc == 0)
up(&db);
}
Writer()
{
down(&db); 
write-db(Database); 
up(&db);
}
??? hê, hê, hê ☺
10/28/2005 Trần Hạnh Nhi 79
R&W: Giải pháp Monitor
monitor ReaderWriter
? Database;
procedure R1();
{
}
procedure R...();
{
}
procedure W1();
{
}
procedure W...();
{
}
monitor ReaderWriter
condition OKWrite, OKRead; 
int rc = 0;
Boolean busy = false;
procedure BeginRead()
{
if (busy)
wait(OKRead);
rc++; 
signal(OKRead);
}
procedure FinishRead()
{
rc--;
if (rc == 0) 
signal(OKWrite);
}
procedure BeginWrite()
{
if (busy || rc != 0) 
wait(OKWrite);
busy = true;
} 
procedure FinishWrite() 
{
busy = false;
if (OKRead.Queue)
signal(OKRead);
else
signal(OKWrite);
}
end monitor;
10/28/2005 Trần Hạnh Nhi 81
Reader&Writer : Giải pháp Monitor
Reader()
{
RW.BeginRead();
Read-db(Database);
RW.FinishRead();
}
Writer();
{
RW.BeginWrite();
Write-db(Database);
RW.FinishWrite();
}
10/28/2005 Trần Hạnh Nhi 82
Bài toán đồng bộ hoá kinh điển 3:
Bửa ăn của các Triết gia (Dining Philosophers)
„ Năm triết gia ngồi chung quanh bàn
ăn món spaghetti (yum..yum)
„ Trên bàn có 5 cái nĩa được đặt giữa 5 
cái đĩa (xem hình) 
„ Để ăn món spaghetti mỗi người cần có 2 
cái nĩa
„ Triết gia thứ i:
„ Thinking...
„ Eating...
Chuyện gì có thể xảy ra ?
10/28/2005 Trần Hạnh Nhi 83
Dining Philosophers : Tình huống nguy hiểm
ƒ 2 triết gia “giành giật” cùng 1 cái
nĩa
ƒ Tranh chấp
ƒ Cần đồng bộ hoá hoạt động
của các triết gia
10/28/2005 Trần Hạnh Nhi 84
Dining Philosophers : Giải pháp đồng bộ
semaphore fork[5] = 1;
Philosopher (i)
{
while(true)
{
down(fork[i]);
down(fork[i+1 mod 5])
eat;
up(fork[i]);
up(fork[i+1 mod 5]);
think;
}
Deadlock
10/28/2005 Trần Hạnh Nhi 85
Dining Philosophers : Thách thức
„ Cần đồng bộ sao cho:
„ Không có deadlock
„ Không có starvation