1
1
Nguyên lý hệđiềuhành
NguyễnHải Châu
Khoa Công nghệ thông tin
Trường Đạihọc Công nghệ
2
Đồng bộ hóa tiếntrình
3
Ví dụđồng bộ hóa (1)
TiếntrìnhghiP:
while (true) {
while (counter==SIZE) ;
buf[in] = nextItem;
in = (in+1) % SIZE;
counter++;
}
buf: Buffer
SIZE: cỡ của buffer
counter: Biến chung
Tiếntrìnhđọc Q:
while (true) {
while (counter==0) ;
nextItem = buf[out];
out = (out+1) % SIZE;
counter ;
}
z Đây là bài toán vùng
đệmcógiớihạn
4
Ví dụđồng bộ hóa (2)

z Giả sử P và Q thựchiện song song vớinhau
và giá trị của counter là 5:
register
1
= counter; // register
1
=5
register
1
= register
1
+ 1; // register
1
=6
register
2
= counter; // register
2
=5
register
2
= register
2
-1; // register
2
=4
counter = register
1
; // counter=6 !!
counter = register

-1; // register
2
=5
counter = register
2
; // counter=5
2
7
Tương tranh và đồng bộ
z Tình huống xuấthiệnkhinhiềutiếntrìnhcùng
thao tác trên dữ liệu chung và kếtquả các
thao tác đóphụ thuộcvàothứ tự thựchiện
củacáctiếntrìnhtrêndữ liệu chung gọilàtình
huống tương tranh (race condition)
z Để tránh các tình huống tương tranh, các tiến
trình cần được đồng bộ theo mộtphương
thứcnàođó ⇒ Vấn đề nghiên cứu: Đồng bộ
hóa các tiếntrình
8
Khái niệmvềđoạnmãgăng (1)
z Thuậtngữ: Critical section
z Thuậtngữ tiếng Việt: Đoạnmãgăng, đoạn
mã tớihạn.
z Xét mộthệ có n tiếntrìnhP
0
, P
1
, , P
n
, mỗi

10
Khái niệmvềđoạnmãgăng (3)
z Cấu trúc chung của P
i
để thựchiện đoạnmã
găng CS
i
.
do {
Xin phép (ENTRY
i
) thựchiện CS
i
; // Entry section
Thựchiện CS
i
;
Thông báo (EXIT
i
) đãthựchiệnxongCS
i
; // Exit section
Phầnmãlệnh khác (REMAIN
i
); // Remainder section
} while (TRUE);
11
Khái niệmvềđoạnmãgăng (4)
z Viếtlạicấutrúcchungcủa đoạnmãgăng:
do {

thựchiện CS
i
và có m tiếntrìnhP
j1
, P
j2
, , P
jm
muốn
thựchiện CS
j1
, CS
j2
, , CS
jm
thì chỉ có các tiếntrình
không thựchiện REMAIN
jk
(k=1, ,m) mới đượcxem
xét thựchiện CS
jk
.
z Chờ có giớihạn (bounded waiting): sau khi mộttiến
trình P
i
có yêu cầuvàoCS
i
và trướckhiyêu cầu đó
đượcchấpnhận, số lầncáctiếntrìnhP
j

Ví dụ: giảiphápcủa Peterson
z Mã lệnh của P
i
:
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j) ;
CS
i
;
flag[j] = FALSE;
REMAIN
i
;
} while (1);
15
Chứng minh giải pháp Peterson
z Xem chứng minh giảiphápcủa Peterson
thỏa mãn 3 điềukiệncủa đoạnmãgăng
trong giáo trình (trang 196)
z Giải pháp “kiểu Peterson”:
z Phứctạpkhisố lượng tiếntrìnhtăng lên
z Khó kiểm soát
16
Semaphore
17
Thông tin tham khảo
z Edsger Wybe Dijkstra
(người Hà Lan) phát

z Toán tử wait: Chờ khi
semaphore S âm và
giảmS đi1 nếuS>0
signal(S) // hoặcV(S)
{
S++;
}
z Toán tử signal: Tăng S
lên 1
20
Sử dụng semaphore (1)
z Với bài toán đoạnmãgăng:
do {
wait(mutex); // mutex là semaphore khởitạo1
CS
i
;
signal(mutex);
REMAIN
i
;
} while (1);
21
Sử dụng semaphore (2)
z P
1
:

O
1

đãhoànthành
z Giải pháp: Sử dụng semaphore synch = 0
22
Cài đặt semaphore cổđiển
z Định nghĩacổđiểncủawait chotathấytoán
tử này có chờ bận (busy waiting), tứclàtiến
trình phảichờ toán tử wait kết thúc nhưng
CPU vẫnphảilàmviệc: Lãng phí tài nguyên
z Liên hệ cơ chế polling trong kiến trúc máy tính
z Cài đặt semaphore theo định nghĩacổđiển:
z Lãng phí tài nguyên CPU với các máy tính 1 CPU
z Có lợinếuthờigianchờ wait ít hơnthờigianthực
hiện context switch
z Các semaphore loạinàygọilàspinlock
23
Cài đặt semaphore theo cấutrúc
z Khắcphụcchờ bận: Chuyểnvònglặpchờ
thành việcsử dụng toán tử block (tạmdừng)
z Để khôi phụcthựchiệntừ block, ta có toán tử
wakeup
z Khi đó để cài đặt, ta có cấutrúcdữ liệumới
cho semaphore:
typedef struct {
int value; // Giá trị của semaphore
struct process *L; // Danh sách tiếntrìnhchờ
} semaphore;
24
void wait(semaphore *S)
{
S->value ;

z Ta sử dụng 3 semaphore tên là full, empty và
mutex để giải quyết bài toán này
z Khởitạo:
z full: Số lượng phầntử buffer đãcódữ liệu(0)
z empty: Số lượng phầntử buffer chưacódữ liệu(n)
z mutex: 1 (Chưacótiến trình nào thựchiện đoạn
mã găng)
28
Bài toán vùng đệmcógiớihạn
TiếntrìnhghiP:
do {
wait(empty);
wait(mutex);
// Ghi mộtphầntử mới
// vào buffer
signal(mutex);
signal(full);
} while (TRUE);
Tiếntrìnhđọc Q:
do {
wait(full);
wait(mutex);
// Đọcmộtphầntử ra
// khỏi buffer
signal(mutex);
signal(empty);
} while (TRUE);
29
Bài toán tiếntrìnhđọc - ghi
z Thuậtngữ: the reader-writer problem

signal(wrt);
while (TRUE);
z Tiến trình reader P
r
:
do {
wait(mutex);
rcount++;
if (rcount==1) wait(wrt);
signal(mutex);
// Thựchiện phép đọc
wait(mutex);
rcount ;
if (rcount==0) signal(wrt);
signal(mutex);
} while (TRUE);
32
Bữa ăntốicủacáctriếtgia
z Thuậtngữ: the dining-
philosophers problem
z Có 5 triếtgia, 5 chiếc
đũa, 5 bát cơmvàmột
âu cơmbố trí như hình
vẽ
z Đây là bài toán cổđiển
và là ví dụ minh họa
cho mộtlớpnhiềubài
toán tương tranh
(concurrency): Nhiều
tiến trình khai thác

// Ăn
signal(chopstick[i]);
signal(chopstick[(i+1)%5];
// Suy nghĩ
} while (TRUE);
35
Mộtsố giảipháptránhbế tắc
z Chỉ cho phép nhiềunhất 4 triếtgiađồng thời
lấy đũa, dẫn đếncóítnhất1 triếtgialấy
được 2 chiếc đũa
z Chỉ cho phép lấy đũakhicả hai chiếc đũa
bên phải và bên trái đềunằmtrênbàn
z Sử dụng giảiphápbất đốixứng: Triếtgia
mang số lẻ lấychiếc đũa đầutiênở bên trái,
sau đóchiếc đũa ở bên phải; triếtgiamang
số chẵnlấychiếc đũa đầutiênở bên phải,
sau đólấychiếc đũabêntrái
36
Hạnchế của semaphore
z Mặc dù semaphore cho ta cơ chếđồng bộ
hóa tiệnlợi song sử dụng semaphore không
đúngcáchcóthể dẫn đếnbế tắchoặclỗido
trình tự thựchiệncủacáctiếntrình
z Trong mộtsố trường hợp: khó phát hiệnbế
tắchoặclỗi do trình tự thựchiệnkhisử dụng
semaphore không đúng cách
z Sử dụng không đúng cách gây ra bởi lỗilập
trình hoặc do ngườilập trình không cộng tác
7
37

wait(mutex);

z Đoạn mã sai này gây ra
bế tắc
39
Ví dụ hạnchế của semaphore (3)
z Nếungườilập trình quên các toán tử wait()
hoặc signal() trong trong các đoạnmãgăng,
hoặccả hai thì có thể gây ra:
z Bế tắc
z Vi phạm điềukiệnloạitrừ lẫnnhau
40
z Tiến trình P
1

wait(S);
wait(Q);

signal(S);
signal(Q);
z Tiến trình P
2

wait(Q);
wait(S);

signal(Q);
signal(S);
Ví dụ hạnchế của semaphore (4)
z Hai tiến trình P

44
Định nghĩa tổng quát
z Monitor là một cách tiếp cận để đồng bộ hóa
các tác vụ trên máy tính khi phải sử dụng các
tài nguyên chung. Monitor thường gồm có:
z Tập các procedure thao tác trên tài nguyên chung
z Khóa loại trừ lẫn nhau
z Các biến tương ứng với các tài nguyên chung
z Một số các giả định bất biến nhằm tránh các tình
huống tương tranh
z Trong bài này: Nghiên cứu một loại cấu trúc
monitor: Kiểu monitor (monitor type)
45
Monitor type
z Mộtkiểu(type) hoặckiểutrừutượng (abstract
type) gồmcócácdữ liệu private và các phương
thức public
z Monitor type được đặc trưng bởi tập các toán
tử củangườisử dụng định nghĩa
z Monitor type có các biếnxácđịnh các trạng
thái; mã lệnh của các procedure thao tác trên
các biến này
46
Cấutrúcmột monitor type
monitor tên_monitor {
// Khai báo các biến chung
procedure P1( ) {
}
procedure P2( ) {
}

phục việc thực hiện (wakeup) mộttiếntrìnhđãgọi
đến x.wait()
50
Monitor có kiểu condition
51
Đặc điểmcủa x.signal()
z x.signal() chỉđánh thức duy nhấtmộttiến
trình đang chờ
z Nếukhôngcótiếntrìnhchờ, x.signal() không
có tác dụng gì
z x.signal() khác với signal trong semaphore cổ
điển: signal cổđiển luôn làm thay đổitrạng
thái (giá trị) của semaphore
52
Signal wait/continue
z Giả sử có hai tiếntrìnhP vàQ:
z Q gọi đến x.wait(), sau đó P gọi đếnx.signal()
z Q đượcphéptiếptụcthựchiện (wakeup)
z Khi đó P phảivàotrạng thái wait vì nếungược
lạithìP và Q cùng thựchiện trong monitor
z Khả năng xảyra:
z Signal-and-wait: P chờđếnkhiQ rờimonitor hoặc
chờ một điềukiện khác (*)
z Signal-and-continue: Q chờđếnkhiP rời monitor
hoặcchờ một điềukiệnkhác
53
Bài toán Ăntối với monitor
z Giải quyết bài toán Ăntốicủacáctriếtgiavới
monitor để không xảyrabế tắckhihai triếtgiangồi
cạnh nhau cùng lấy đũa để ăn

Monitor củabàitoánĂntối
void test(int i) {
if ((state[(i+4)%5] != eating) &&
(state[i] == hungry) &&
(state[(i+1)%5] != eating)) {
state[i] = eating;
self[i].signal();
}
}
57
Đọcthêmở nhà
z Khái niệmvề miềngăng (critical region)
z Cơ chế monitor của Java:
public class XYZ {

public synchronized void safeMethod() {

}
}
z Toán tử wait() và notify() trong java.util.package
(tương tự toán tử wait() và signal())
z Cách cài đặt monitor bằng semaphore
58
Tóm tắt
z Khái niệm đồng bộ hóa
z Khái niệm đoạnmãgăng, ba điềukiệncủa
đoạnmãgăng
z Khái niệm semaphore, semaphore nhị phân
z Hiệntượng bế tắc do sử dụng sai semaphore
z Mộtsố bài toán cổđiểntrongđồng bộ hóa