Nguồn:
Bài học
giải ph
áp
hai lớp
t
waiting
I. GIảI
P
I.1.
C
I
.1.1.
S
Tiếp
này đư
ợ
trị của b
Nếu loc
k
giá trị 0
.
miền gă
n
while
while
lock
=
criti
c
lock

» và các gi
ả
P
HÁP « B
U
C
ác giải ph
á
S
ử dụng c
á
cân : các ti
ế
ợ
c khởi độn
g
iến lock.
N
k
đang nhậ
n
.
Như vậy
g
n
g, và lock
=
(TRUE)
(lock
=

ử dụng v
i
B
ÀI 5 :
C
i
thiệu các
g
h
iện việc tr
u
c
h tiếp cận
ả
i pháp «
s
U
SY WAI
T
á
p phần m
á
c biến cờ
h
ế
n t
r
ình ch
i
g

ư
ng trước
k
hoạt động.
Sau đó tiế
n
Như vậy t
ạ
i
ệc kiểm tr
a
C
ÁC GIẢ
I
g
iải pháp c
ụ
u
y xuất miề
n
trong xử l
ý
leep and w
a
T
ING »
ềm
h
iệu:
i

i
điểm. Giả
k
hi nó có th
ể
Tiến t
r
ình
n
t
r
ình thứ
n
ạ
i thời điể
m
a
luân ph
i
ê
n
I
PHÁP
Đ
ụ
thể để xử
n
găng, cá
c
ý

y
n
hất được t
á
m
đó cả hai
t
n
:
Đ
ỒNG B
Ộ
lý bài toán
c
giải pháp
ình bị khó
a
óng vai t
r
ò
m
iền găng t
r
t
rị cho loc
k
n
ngoài miề
n
không có t

đ
ồng bộ h
o
này được
p
a
:các giải
p
« chốt cửa
r
ước tiên p
h
k
= 1 và đi
v
n
găng cho
i
ến trình n
à
g
ăng.
g
bộ
: hai tiến t
r
ì
n
thấy lock
k là 1, nó

r
ì
nh có thể
c
= 0 và chu
ẩ
b
ị tạm dừng
ì
vào miền
g
c
k = 1 lần
n
m
iền găng.
ề
u
ành
y

b
iến
a
giá
ă
ng.
c
k có
r

criti
c
turn
=
Noncr
i
}
Hình 3.
6
Thảo
tiến trìn
h
trình cù
n
thể bị n
g
tiến trìn
h
và turn
=
là1, rồi
l
nhanh c
h
Tuy nhi
ê
mang gi
thực hiệ
n
I

0;
i
tical-
s
6
Cấu trúc
c
luận: Giải
h
nào được
n
g vào miề
n
g
ăn chặn v
à
h
B ra khỏi
=
0. Tiến tr
ì
l
ại xử lý đo
h
óng đoạn
l
ê
n lúc này
B
á t

(
{
= 1); /
/
t
ion ();
s
ection
(
c
ác tiến t
r
ì
n
pháp này
d
vào miền
g
n
găng, nh
ư
à
o miền gă
n
miền găng
ì
nh A vào
m
ạn lệnh ng
o

đ
/
wait
(
);
(a) Cấu
t
/
wait
(
);
(b) Cấu
n
h trong gi
ả
d
ựa trên việ
c
g
ăng. Do đ
ó
ư
ng lại có t
h
n
g bởi một
t
rất nhanh
c
m

rúc tiến t
r
ì
trúc tiến t
r
ì
ả
i pháp kiể
m
c
thực hiện
ó
nó có thể
h
ể vi phạm
t
iến t
r
ình k
h
c
hóng. Cả
h
v
à ra khỏi
n
ă
ng lần nữa
.
của nó và

p
sự kiểm tr
a
ngăn chặn
đ
điều kiện t
h
h
ác không
ở
h
ai tiến t
r
ìn
h
n
hanh chón
g
.
Sau đó, ti
ế
m
uốn vào
m
g
oài miền g
á
t
r
ị khi có

, đặt lại gi
á
ế
n t
r
ình A l
ạ
m
iền găng
m
ăng của mì
sự khác bi
ệ
h
này sử dụ
n
c
khởi độn
g
n
t
r
ình A đ
i
ề
n găng, nó
h
ặt đến lượ
t
r

n
ó
ả
sử
ă
ng,
r
n
.
lại
c
độ
Tiếp
Các tiế
n
int t
u
int i
n
Nếu int
e
interess
e
vào đư
ợ
rằng tiế
n
miền gă
n
(interes

.2.1.
Tiếp
ngắt khi
cận : Petso
n
n
t
r
ình chia
u
rn; //
n
teress
e
e
resse[i] =
T
e
[0]=inter
e
ợ
c miền găn
n
t
r
ình mu
ố
n
g). Nếu ti
ế

p
chỉ có thể
v
u
muốn và
o
có thể hoặ
c
C
ác giải ph
á
Cấm ngắt:
cân
: cho p
h
ra khỏi mi
ề
n
đưa ra m
ộ
sẻ hai biến
đến phi
ê
e
[2]; //
T
RUE có
n
e
sse[1]=F

= FALSE
;
s
ection
(
t
iến t
r
ình P
p
háp này n
g
v
ào miền g
ă
o
miền găn
g
c
là 0 hoặc
á
p phần c
ứ

h
ép tiến trì
n
ề
n găng. K
h

i
tr
ình còn lạ
i
i
nteres
s
;

(
);
i trong giải
g
ăn chặn đ
ư
ă
ng khi int
e
g
thì intere
s
là 1, do vậ
y
ứ
ng
n
h cấm tất
c
h
i đó, ngắt

i

s
e[j]==
T
pháp Pete
r
ư
ợc tình trạ
n
e
resse[j]=
F
s
se[i] = int
e
y
chỉ có m
ộ
c
ả các ngắt
t
đồng hồ c
ũ
t
ưởng của
c
F
ALSE
u

tr
ước khi v
à
ũ
ng không
x
c
ả hai giải
p
i
ền găng.
K
động là 0
h
e
[i]=TRU
E
h
ị thử tiến t
r
ề
n găng
Pi phải ch
ờ
ặt lại giá tr
ị
u
ẫn truy xu
ấ
c

t : mỗi tiế
n
N
ếu cả hai t
i
n
g giá t
r
ị c
ủ
m
iền găng.
n
g, và phụ
c
ậy hệ thốn
g
n
.
ó
thể
à
o
n

i
ến
ủ
a
c

}
Nếu có
h
tuần tự .
một biế
n
trước k
h
while
while
criti
c
lock
=
Noncr
i
}
Thảo
việc lập
h
ể tạm dừn
g
h
ờ đó tiến t
r
o
khác tran
h
luận: giải
p

T
Có thể cài
n
lock, đượ
c
h
i vào miền
(TRUE)
(Test-
a
c
al-sec
t
=
FALSE;
i
tical-
s
Hì
n
luận : cũn
g
t
r
ình để gi
ả
g
hoạt độn
g
r

:
l
ock(boo
l
l
ock = t
a
E
;
T
SL xử lý
đ
đặt giải p
h
c
khởi gán
l
găng, nếu
l
{
a
nd-Setl
o
t
ion ();

s
ection
(
n

iệt cho ph
é
p
hân chia,
g
l
ean ta
r
a
rget;
đ
ồng thời (t
r
h
áp truy xu
ấ
l
à FALSE.
l
ock = FA
L
o
ck(loc
k
(
);
u
trúc một c
h
ư

h
r
get)
r
ên hai bộ
x
ấ
t độc quyề
n
Tiến trình
p
L
SE, tiến t
r
ì
k
));
h
ương trìn
h
h
áp phần c
ứ
g
lại không
ử
lý để cấp
r
ên miền g
ă

trong giải
ứ
ng khác, c
dễ dàng để
phát CPU
c
ă
ng mà khô
n
thận trọng
nữa, nếu h
ệ
n
g xử lý tiế
n
đến miền
g
ế
phần cứn
g
ậ
t nội dung
m
Set Lock (
T
n
hau), chú
n
b
ằng cách

á
m
ột vùng
n
T
SL) và đư
ợ
n
g sẽ được
x
s
ử dụng thê
m
ủ
a biến loc
k
ă
ng.

giảm nhẹ c
ô
thị TSL sa
o
n
h
n

é
p
các

hướng cho một tiến trình chưa đủ điều kiện vào miền găng chuyển sang trạng thái
blocked, từ bỏ quyền sử dụng CPU. Để thực hiện điều này, cần phải sử dụng các thủ tục
do hệ điều hành cung cấp để thay đổi trạng thái tiến trình. Hai thủ tục cơ bản SLEEP và
WAKEUP thường đượ
c sử dụng để phục vụ mục đích này.
SLEEP là một lời gọi hệ thống có tác dụng tạm dừng hoạt động của tiến trình (blocked)
gọi nó và chờ đến khi được một tiến trình khác « đánh thức ». Lời gọi hệ thống WAKEUP
nhận một tham số duy nhất : tiến trình sẽ được tái kích hoạt (đặt về trạng thái ready).
Ý tưởng sử dụng SLEEP và WAKEUP như sau : khi mộ
t tiến trình chưa đủ điều kiện vào
miền găng, nó gọi SLEEP để tự khóa đến khi có một tiến trình khác gọi WAKEUP để giải
phóng cho nó. Một tiến trình gọi WAKEUP khi ra khỏi miền găng để đánh thức một tiến
trình đang chờ, tạo cơ hội cho tiến trình này vào miền găng :
int busy; // 1 nếu miền găng đang bị chiếm, nếu không là
0
int blocked; // đếm s
ố lượng tiến trình đang bị khóa

while (TRUE) {
if (busy){
blocked = blocked + 1;
sleep();
}
else busy = 1;
critical-section ();

busy = 0;
if(blocked){
wakeup(process);
blocked = blocked - 1;

Chỉ có hai thao tác được định nghĩa trên semaphore
Down(s): giảm giá trị của semaphore s đi 1 đơn vị nếu semaphore có trị e(s) > 0, và tiếp
tục xử lý. Ngược lại, nếu e(s) ≤ 0, tiến trình phải chờ đến khi e(s) >0.
Up(s): tăng giá trị của semaphore s lên 1 đơn vị. Nếu có một hoặc nhiều tiến trình đang
chờ trên semaphore s, bị khóa bởi thao tác Down, thì hệ thống sẽ chọn một trong các tiến
trình này để kết thúc thao tác Down và cho tiế
p tục xử lý.

Hình 3.10 Semaphore s
Cài đặt: Gọi p là tiến trình thực hiện thao tác Down(s) hay Up(s).
Down(s):
e(s) = e(s) - 1;
if e(s) < 0 {
status(P)= blocked;
enter(P,f(s));
}
Up(s):
e(s) = e(s) + 1;
if s ≤ 0 {
exit(Q,f(s)); //Q là tiến trình đang chờ trên s
status (Q) = ready;
enter(Q,ready-list);
}
Lưu ý cài đặt này có thể đưa đến một giá trị âm cho semaphore, khi đó trị tuyệt đối của
semaphore cho biết số tiến trình đang chờ trên semaphore.
Điều quan trọng là các thao tác này cần thực hiện một cách không bị phân chia, không bị
ngắt nữa chừng, có nghĩa là không một tiến trình nào được phép truy xuất đến semaphore
nếu tiến trình đang thao tác trên semaphore này chưa kết thúc xử lý hay chuyển sang
trạng thái blocked.
Sử dụng:


Thảo luận :
Nhờ có thực hiện một các không thể phân chia, semaphore đã giải quyết
được vấn đề tín hiệu "đánh thức" bị thất lạc. Tuy nhiên, nếu lập trình viên vô tình đặt các
primitive Down và Up sai vị trí, thứ tự trong chương trình, thì tiến trình có thể bị khóa
vĩnh viễn.
Ví dụ
: while (TRUE) {
Down(s)
critical-section ();
Noncritical-section ();
}
tiến trình trên đây quên gọi Up(s), và kết quả là khi ra khỏi miền găng nó sẽ không cho
tiến trình khác vào miền găng !
Vì thế việc sử dụng đúng cách semaphore để đồng bộ hóa phụ thuộc hoàn toàn vào lập
trình viên và đòi hỏi lập trình viên phải hết sức thận trọng.
II.2. Monitors
Tiếp cận:
Để có thể dễ viết đúng các chương trình đồng bộ hóa hơn, Hoare(1974) và
Brinch & Hansen (1975) đã đề nghị một cơ chế cao hơn được cung cấp bởi ngôn ngữ lập
trình , là monitor. Monitor là một cấu trúc đặc biệt bao gồm các thủ tục, các biến và cấu
trúc dữ liệu có các thuộc tính sau :
Các biến và cấu trúc dữ liệu bên trong monitor chỉ có thể được thao tác bởi các thủ tục
định nghĩa bên trong monitor đó. (encapsulation).
Tại một thời điểm, chỉ có một tiến trình duy nhất được hoạt động bên trong một monitor
(mutual exclusive).
Trong một monitor, có thể định nghĩa các biến điều kiện và hai thao tác kèm theo là
Wait và Signal như sau : gọi c là biến điều kiện được định nghĩa trong monitor:
Wait(c): chuyển trạng thái tiến trình gọi sang blocked , và đặt tiến trình này vào hàng
đợi trên biến điều kiện c.

();
{

}
procedure Action
n
();
{

}
end monitor;
Hình 3.14 Cấu trúc một monitor
Các tiến trình muốn sử dụng tài nguyên chung này chỉ có thể thao tác thông qua các thủ
tục bên trong monitor được gắn kết với tài nguyên:
while (TRUE) {
Noncritical-section ();
<monitor>.Actioni; //critical-section();
Noncritical-section ();
}
Hình 3.15 Cấu trúc tiến trình Pi

trong giải

pháp monitor
Thảo luận:
Với monitor, việc truy xuất độc quyền được bảo đảm bởi trình biên dịch
mà không do lập trình viên, do vậy nguy cơ thực hiện đồng bộ hóa sai giảm rất nhiều.

Các primitive semaphore và monitor có thể giải quyết được vấn đề truy
xuất độc quyền trên các máy tính có một hoặc nhiều bộ xử lý chia sẻ một vùng nhớ
chung. Nhưng các primitive không hữu dụng trong các hệ thống phân tán, khi mà mỗi bộ
xử lý sỡ hữu một bộ nhớ riêng biệt và liên lạc thông qua mạng. Trong những hệ thống
phân tán như thế, cơ chế trao đổi thông điệp tỏ ra hữu hiệu và được dùng để gi
ải quyết
bài toán đồng bộ hóa.
