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đọcQ:
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)
zcounter++
register1= counter;
register1= register1+ 1;
counter = register1;
zcounter--
register2= counter;
register2= register2-1;
counter = register2;
zCác toán tử++ và -- có thểđượccàiđặtnhưsau:
P và Q có thểnhậnđược các giá trịkhác nhau của
counter tại cùng 1 thờiđiểmnếunhưđoạnmãxanh
và đỏ thựchiệnxenkẽnhau.
5
Ví dụđồng bộhóa (3)
zGiảsửP và Q thựchiện song song vớinhau
và giá trịcủa counter là 5:
register1= counter; // register1=5
register1= register1+ 1; // register1=6
register2= counter; // register2=5
register2= register2-1; // register2=4
counter = register1;// counter=6 !!
counter = register2;// counter=4 !!
6
Ví dụđồng bộhóa (4)
zLỗi: Cho phép Pvà Qđồng thờithao táctrên
biếnchungcounter. Sửalỗi:
register1= counter; // register1=5
register1= register1+ 1; // register1=6
counter = register1;// counter=6
register2= counter; // register2=6
register2= register2-1; // register2=5
counter = register2;// counter=5
2
7
Tương tranh và đồng bộ
zTì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)
zThuậtngữ: Critical section
zThuậtngữtiếng Việt: Đoạnmãgăng, đoạn
mã tớihạn.
zXét mộthệcó ntiếntrìnhP0, P1, ..., Pn, mỗi
tiến trình có mộtđoạnmãlệnh gọilàđoạn
mã găng, ký hiệulàCSi, nếunhưtrong đoạn
mã này, các tiến trình thao tác trên các biến
chung, đọc ghi file... (tổng quát: thao tác trên
dữliệu chung)
9
Khái niệmvềđoạnmãgăng (2)
zĐặcđiểm quan trọng mà hệntiến trình này
cầncólà: KhimộttiếntrìnhPithựchiệnđoạn
mã CSithì không có tiếntrìnhPjnào khác
đượcphépthựchiệnCSj
zMỗitiếntrìnhPiphải “xin phép” (entry
section) trướckhithựchiệnCSivà thông báo
(exit section) cho các tiến trình khác sau khi
thựchiện xong CSi.
10
Khái niệmvềđoạnmãgăng (3)
zCấu trúc chung củaPiđể thựchiệnđoạnmã
găng CSi.
do {
Xin phép (ENTRYi) thựchiệnCSi; // Entry section
ThựchiệnCSi;
Thông báo (EXITi) đãthựchiệnxongCSi; // Exit section
Phầnmãlệnh khác (REMAINi); // Remainder section
} while (TRUE);
11
Khái niệmvềđoạnmãgăng (4)
zViếtlạicấutrúcchungcủađoạnmãgăng:
do {
ENTRYi; // Entry section
ThựchiệnCSi; // Critical section
EXITi; // Exit section
REMAINi; // Remainder section
} while (TRUE);
12
Giải pháp cho đoạnmãgăng
zGiải pháp cho đoạnmãgăng cầnthỏa mãn 3
điềukiện:
zLoạitrừlẫn nhau (mutual exclusion): NếuPiđang
thựchiệnCSithì Pjkhông thểthựchiệnCSj∀j≠i.
zTiếntriển (progress): Nếu không có tiếntrìnhPinào
thựchiệnCSivà có mtiếntrìnhPj1, Pj2, ..., Pjm muốn
thựchiệnCSj1, CSj2, ..., CSjm thì chỉcó các tiếntrình
không thựchiệnREMAINjk (k=1,...,m) mớiđượcxem
xét thựchiệnCSjk.
zChờcó giớihạn (bounded waiting): sau khi mộttiến
trình Picó yêu cầuvàoCSivà trướckhiyêu cầuđó
đượcchấpnhận, sốlầncáctiếntrìnhPj(vớij≠i) được
phép thựchiệnCSjphảibịgiớihạn.
3
13
Ví dụ: giảiphápcủa Peterson
zGiảsửcó 2 tiếntrìnhP0và P1với hai đoạn
mã găng tương ứng CS0và CS1
zSửdụng mộtbiến nguyên turn vớigiátrịkhởi
tạo0 hoặc1 vàmảng boolean flag[2]
zturn có giá trịicó nghĩalàPiđượcphépthực
hiệnCSi(i=0,1)
znếu flag[i] là TRUE thì tiếntrìnhPiđãsẵn
sàng để thựchiệnCSi
14
Ví dụ: giảiphápcủa Peterson
zMã lệnh củaPi:
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j) ;
CSi;
flag[j] = FALSE;
REMAINi;
} while (1);
15
Chứng minh giải pháp Peterson
zXem 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)
zGiải pháp “kiểu Peterson”:
zPhứctạpkhisốlượng tiếntrìnhtăng lên
zKhó kiểm soát
16
Semaphore
17
Thông tin tham khảo
zEdsger Wybe Dijkstra
(người Hà Lan) phát
minh ra khái niệm
semaphore trong khoa
học máy tính vào năm
1972
zSemaphore được sử
dụng lầnđầutiêntrong
cuốnsách“The
operating system” của
ông Edsger Wybe Dijkstra
(1930-2002) 18
Định nghĩa
zSemaphore là mộtbiến nguyên, nếu không tính
đếntoántửkhởitạo, chỉcó thểtruy cập thông
qua hai toán tửnguyên tốlà wait (hoặcP) và
signal (hoặcV).
zP: proberen – kiểmtra(tiếng Hà Lan)
zV: verhogen–tăng lên (tiếng Hà Lan)
zCác tiếntrìnhcóthểsửdụng chung semaphore
zCác toán tửlà nguyên tốđểđảmbảo không xảy
ra trường hợpnhưví dụđồng bộhóa đãnêu
4
19
Toán tửwait và signal
wait(S) // hoặcP(S)
{
while (S<=0);
S--;
}
zToán tửwait: Chờkhi
semaphore S âm và
giảmS đi1 nếuS>0
signal(S) // hoặcV(S)
{
S++;
}
zToán tửsignal: Tăng S
lên 1
20
Sửdụng semaphore (1)
zVới bài toán đoạnmãgăng:
do {
wait(mutex); // mutex là semaphore khởitạo1
CSi;
signal(mutex);
REMAINi;
} while (1);
21
Sửdụng semaphore (2)
zP1:
...
O1;
signal(synch);
...
zP2:
...
wait(synch);
O2;
...
zXét hai tiếntrìnhP1và P2, P1cầnthựchiện
toán tửO1, P2cầnthựchiệnO2và O2chỉ
đượcthựchiện sau khi O1đãhoànthành
zGiả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
zLiên hệcơchếpolling trong kiến trúc máy tính
zCài đặt semaphore theo định nghĩacổđiển:
zLãng phí tài nguyên CPU với các máy tính 1 CPU
zCó lợinếuthờigianchờwait ít hơnthờigianthực
hiện context switch
zCác semaphore loạinàygọilàspinlock
23
Cài đặt semaphore theo cấutrúc
zKhắ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
zKhi đóđể 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--;
if (S->value<0) {
Thêm tiếntrìnhgọi
toán tửvào s->L;
block();
}
}
void signal(semaphore *S)
{
S->value++;
if (S->value<=0) {
Xóa mộttiếntrìnhP
ra khỏis->L;
wakeup(P);
}
}
Cài đặt semaphore theo cấutrúc
5
25
Semaphore nhịphân
zLà semaphore chỉnhậngiátrị0 hoặc1
zCài đặt semaphore nhịphân đơngiảnhơn
semaphore không nhịphân (thuậtngữ:
counting semaphore)
26
Mộtsốbài toán
đồng bộhóa cơbản
27
Bài toán vùng đệmcógiớihạn
zĐãxétởví dụđầu tiên (the bounded-buffer
problem)
zTa sửdụng 3 semaphore tên là full, empty và
mutex để giải quyết bài toán này
zKhởitạo:
zfull: Sốlượng phầntửbuffer đãcódữliệu(0)
zempty: Sốlượng phầntửbuffer chưacódữliệu(n)
zmutex: 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đọcQ:
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
zThuậtngữ: the reader-writer problem
zTình huống: Nhiềutiến trình cùng thao tác trên mộtcơ
sởdữliệutrongđó
zMộtvàitiếntrìnhchỉđọcdữliệu(kýhiệu: reader)
zMộtsốtiếntrìnhvừađọcvừa ghi (ký hiệu: writer)
zKhi có đọc/ghi đồng thờicủanhiềutiến trình trên cùng
mộtcơsởdữliệu, có 2 bài toán:
zBài toán 1: reader không phảichờ,trừkhi writer đãđượcphép
ghi vào CSDL (hay các reader không loạitrừlẫn nhau khi đọc)
zBài toán 2: Khi writer đãsẵn sàng ghi, nó sẽ được ghi trong
thời gian sớm nhất (nói cách khác khi writer đã sẵn sàng,
không cho phép các reader đọcdữliệu) 30
Bài toán tiếntrìnhđọc-ghi số1
zSửdụng các semaphore vớigiátrịkhởitạo:
wrt (1), mutex (1)
zSửdụng biếnrcount (khởitạo0) để đếmsố
lượng reader đang đọcdữliệu
zwrt: Đảmbảoloạitrừlẫn nhau khi writer ghi
zmutex: Đảmbảoloạitrữlẫnnhaukhicập
nhậtbiếnrcount