Bài giảng Hệ điều hành: Tương tranh và đồng bộ - Nguyễn Thị Hải Bình

TƯƠNG TRANH VÀ
ĐỒNG BỘ
ThS. Nguyễn Thị Hải Bình
Khoa CNTT, ĐH Giao thông vận tải
Email: calmseahn@gmail.com
Website: calmseahn.weebly.com
VÍ DỤ VỀ TƯƠNG TRANH
2
TƯƠNG TRANH VÀ ĐỒNG BỘ
• Race condition
• Thuật ngữ
• Tranh đoạt điều khiển
• Tình huống tương tranh
• Xảy ra khi
• Nhiều tiến trình cùng thao tác trên dữ liệu chung và kết quả các
thao tác đó phụ thuộc vào thứ tự thực hiện của các tiến trình
• Process synchronization
• Thuật ngữ: đồng bộ hoá các tiến trình
• Để tránh các tình huống tương tranh, các tiến trình cần 
được đồng bộ theo một phương thức nào đó
3
BÀI TOÁN SẢN XUẤT – TIÊU THỤ
• Thuật ngữ
• The producer – consumer problem
• Yêu cầu của bài toán
• Tiến trình sản xuất (producer process) tạo ra thông tin
• Còn tiến trình tiêu thụ (consumer process) sử dụng thông tin 
được tạo ra
• Bộ đệm: 
• Chứa thông tin tạo ra bởi tiến trình sản xuất
• Tiến trình tiêu thụ lấy thông tin từ bộ đệm để sử dụng
• Bộ đệm cho phép 2 tiến trình thực thi đồng thời
• Vấn đề
• Tiến trình tiêu thụ không sử dụng thông tin chưa được tạo ra
• Nếu bộ đệm rỗng thì tiến trình tiêu thụ phải chờ
• Nếu bộ đệm đầy thì tiến trình sản xuất phải chờ
4
KHAI BÁO BIẾN
5
TIẾN TRÌNH SẢN XUẤT
6
item newItem;
while( true ) {
/* Produce an item and store it in newItem */
newItem = makeNewItem( . . . );
/* Wait for space to become available */
while( counter == BUFFER_SIZE)
; /* Do nothing */
/* And then store the item and repeat the loop. */
buffer[in] = newItem;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
TIẾN TRÌNH TIÊU THỤ
7
item usedItem;
while( true ) {
/* Wait for an item to become available */
while( counter == 0)
; /* Do nothing */
/* Get the next available item */
usedItem = buffer[out];
out = (out+1) % BUFFER_SIZE;
counter--;
/* Consume the item in usedItem (do something 
with it) */
}
TƯƠNG TRANH?
• Lệnh “counter++” và “counter--” có thể được cài
đặt trên ngôn ngữ máy (typical machine language) 
như sau
8
counter++
register1 = counter;
register1= register1 + 1;
counter = register1;
counter--
register2 = counter;
register2= register2 - 1;
counter = register2;
TƯƠNG TRANH?
9
10
XỬ LÝ TƯƠNG 
TRANH
Giải pháp phần mềm –
Độc quyền truy xuất
Giải pháp phần cứng –
Đồng bộ hoá
Giải pháp đồng bộ cơ
bản
11
XỬ LÝ TƯƠNG 
TRANH
Giải pháp phần mềm –
Độc quyền truy xuất
MIỀN GĂNG (CRITICAL SECTION)
• Còn được gọi là đoạn mã găng hay đoạn tới hạn
• Khái niệm miền găng
• Xét hệ thống gồm n tiến trình {P0, P1, , Pn-1}
• Mỗi tiến trình có một đoạn mã gọi là miền găng chứa
các lệnh có thể thay đổi các biến dùng chung
• Vấn đề
• Đảm bảo tại một thời điểm chỉ có một tiến trình được
phép thi hành đoạn mã trong miền găng (gọi là bước
vào miền găng)
• Để các tiến trình có thể hợp tác với nhau, mỗi tiến trình
cần phải xin phép trước khi bước vào miền găng và
thông báo thoát khỏi miền găng
12
MIỀN GĂNG (CRITICAL SECTION)
13
GIẢI PHÁP CHO MIỀN GĂNG
• Cần thoả mãn các yêu cầu sau
• Độc quyền truy xuất (hay loại trừ lẫn nhau - Mutual 
Exclusion)
• Nếu tiến trình Pi đang ở trong miền găng, thì không tiến trình
nào được bước vào miền găng
• Tiến triển (Progress)
• Nếu không có tiến trình nào ở trong miền găng và có một số
tiến trình muốn vào miền găng thì một tiến trình nào đó phải
được vào miền găng
• Chờ có giới hạn (Bounded waiting)
• Thời gian từ khi tiến trình yêu cầu cho đến khi bước vào miền
găng phải bị chặn bởi giới hạn nào đó
14
GIẢI PHÁP THỨ NHẤT CHO HAI TIẾN
TRÌNH
• Giả sử có 2 tiến trình P0 và P1 muốn phối hợp với
nhau vào miền găng
• Biến chung
• int turn;
• Khởi tạo: turn = 0 hoặc 1
• turn = i Pi được vào miền găng
15
GIẢI PHÁP THỨ NHẤT CHO HAI TIẾN
TRÌNH
• Tiến trình Pi
• Vấn đề
• Không thoả mãn yêu cầu tiến triển (progress)
16
do{
while (turn != i) ;
critical section
turn = j;
reminder section
}while(true);
GIẢI PHÁP THỨ HAI CHO HAI TIẾN
TRÌNH
• Biến chung
• boolean flag[2];
• Khởi tạo: flag[0] = flag[1] = false
• flag[i] = true Pi sẵn sàng vào miền găng
• Tiến trình Pi
17
do{
flag[i] = true;
while (flag[j]) ;
critical section
flag[i] = false;
reminder section
}while(true);
PHƯƠNG PHÁP KIỂM TRA VÀ XÁC LẬP
• Thuật toán Peterson
• Thuật toán Dekker
• Thuật toán tiệm bánh mỳ
18
THUẬT TOÁN PETERSON
• Thuật ngữ
• Peterson’s solution
• Peterson’s algorithm
• Biến chung
• int turn;
• Khởi tạo: turn = 0 hoặc 1
• boolean flag[2];
• Khởi tạo: flag[0] = flag[1] = false
19
THUẬT TOÁN PETERSON
• Tiến trình Pi
20
do{
flag[i] = true;
turn = j;
while (flag[j] && turn == j) ;
critical section
flag[i] = false;
reminder section
}while(true);
THUẬT TOÁN DEKKER
• Biến chung: Giống thuật toán Peterson
• Tiến trình Pi
21
do{
flag[i] = true;
while (flag[j]){
if (turn=j){
flag[i] = false;
while (turn=j);
}
flag[i] = true;
}
critical section
turn = j;
flag[i] = false;
reminder section
}while(true);
THUẬT TOÁN TIỆM BÁNH MỲ
• Thuật ngữ
• Bakery algorithm
• Trước khi vào miền găng, mỗi tiến trình được cấp
một số thứ tự
• Tiến trình có số thứ tự nhỏ nhất sẽ được vào miền
găng trước
• Nếu Pi và Pj có cùng số thứ tự, nếu I < j thì Pi được
vào miền găng trước
22
23
24
XỬ LÝ TƯƠNG 
TRANH
Giải pháp phần mềm –
Độc quyền truy xuất
Giải pháp phần cứng –
Đồng bộ hoá
Giải pháp đồng bộ cơ
bản
25
XỬ LÝ TƯƠNG 
TRANH
Giải pháp phần cứng –
Đồng bộ hoá
CHE NGẮT
• Không cho ngắt xảy ra khi chỉnh sửa biến chung
• Chuỗi chỉ thị thao tác trên biến chung không bị
gián đoạn bởi tiến trình khác
• Che ngắt trên hệ thống nhiều CPU tốn thời gian 
hiệu suất hệ thống bị suy giảm
26
do {
Prevent interrupts
Critical section
Allow interrupts
Remainder section
} while(true);
CÁC CHỈ THỊ ĐẶC BIỆT
• Một số hệ thống cung cấp các chỉ thị phần cứng
đặc biệt cho phép kiểm tra và chỉnh sửa nội dung 
của một từ hoặc tráo đổi nội dung hai từ trong bộ
nhớ một cách đơn nhất (atomically)
• Các chỉ thị này là các đơn vị không thể bị ngắt
(uninterruptible unit)
27
CHỈ THỊ TEST_AND_SET
28
CHỈ THỊ TEST_AND_SET
• Biến chung
• Boolean lock = false;
29
CHỈ THỊ COMPARE_AND_SWAP
30
CHỈ THỊ COMPARE_AND_SWAP
31
• Biến chung:
• int lock = 0;
THUẬT TOÁN CHO MIỀN GĂNG
32
33
XỬ LÝ TƯƠNG 
TRANH
Giải pháp phần mềm –
Độc quyền truy xuất
Giải pháp phần cứng –
Đồng bộ hoá
Giải pháp đồng bộ cơ
bản
34
XỬ LÝ TƯƠNG 
TRANH
Giải pháp đồng bộ cơ
bản
KHOÁ TRONG (MUTEX LOCK)
35
KHOÁ TRONG (MUTEX LOCK)
• acquire() và release() phải thực thi một cách đơn nhất
(atomically)
• Mutex lock thường được cài đặt bằng các cơ chế đồng
bộ hoá (giải pháp phần cứng)
• Tình trạng chờ bận (busy waiting)
• Khi có một tiến trình trong miền găng, tiến trình khác muốn
vào miền găng phải thực hiện vòng lặp để gọi hàm acquire()
• Lãng phí thời gian CPU
• Dạng khoá này còn gọi là khoá xoay (spinlock) vì các
tiến trình “spin” khi chờ khoá
• Ưu điểm của spinlock trong hệ thống đa xử lý là không
cần chuyển ngữ cảnh khi một tiến trình đợi khoá
36
SEMAPHORE 
(PHƯƠNG PHÁP ĐÈN HIỆU)
• Semaphore S là một biến nguyên
• Ngoài toán tử khởi tạo, S chỉ được truy cập thông
qua hai toán tử nguyên tố (standard atomic 
operation) wait() và signal()
• wait() còn được gọi là P (proberen – kiểm tra)
• signal() còn được gọi là V (verhogen – tăng)
37
SỬ DỤNG SEMAPHORE
• Binary semaphore (Semaphore nhị phân)
• Có thể sử dụng để giải quyết vấn đề miền găng
• Biến chung: 
• semaphore mutex;
• Khởi tạo mutex = 1
• Tiến trình Pi:
38
do{
waiting(mutex);
critical section
signal(mutex);
reminder section
}while(true);
SỬ DỤNG SEMAPHORE
• Counting semaphores
• Nhận giá trị là một số nguyên bất kỳ
• Thường dùng để đếm số lượng tài nguyên rảnh rỗi của
hệ thống
• Biến chung
• semaphore S;
• Khởi tạo: S = số lượng tài nguyên (resources) của hệ thống
• Tiến trình Pi
39
do{
waiting(S);
using resource
signal(S);
reminder section
}while(true);
SỬ DỤNG SEMAPHORE
• Semaphore có thể dùng để giải quyết một số vấn
đề đồng bộ hoá giữa các tiến trình
• Ví dụ
• Tiến trình P1 có lệnh S1 
• Tiến trình P2 có lệnh S2
• S1 phải được hoàn thành trước khi S2 thực thi
• Biến chung: semaphore synch;
• Khởi tạo synch = 0;
40
/* Tiến trình P1 */
S1;
signal(synch);
/* Tiến trình P2 */
wait(synch);
S2;
CÀI ĐẶT SEMAPHORE
• Ý tưởng
• Khi một tiến trình phải chờ vì semaphore âm, thay vì
thực hiện lặp (vào tình trạng chờ bận – busy waiting), 
tiến trình phong toả (block) chính nó (tiến trình chuyển
từ trạng thái tích cực sang trạng thái không tích cực)
• Quá trình phong toả diễn ra như sau
• Tiến trình được đặt vào hàng chờ semaphore
• Tiến trình chuyển sang trạng thái chờ (waiting)
• Khi semaphore sẵn sàng
• Một trong số các tiến trình bị phong toả sẽ được đánh thức
• Tiến trình đó sẽ được đưa vào hàng đợi ready hoặc được
chuyển sang trạng thái running (tuỳ thuộc vào thuật toán điều
phối CPU)
41
42
CÀI ĐẶT SEMAPHORE
• Toán tử wait() và signal() phải được thực thi một
cách toàn vẹn và đơn nhất (atomically)
• Trên môi trường có một CPU có thể sử dụng giải
pháp che ngắt
• Trên môi trường nhiều CPU, có thể sử dụng giải
pháp khoá (compare_and_swap hoặc spinlocks)
43
BẾ TẮC (DEADLOCKS)
• Xảy ra khi có nhiều tiến trình bị phong toả, và mỗi
tiến trình đó chỉ có thể bị đánh thức bởi một tiến
trình bị phong toả khác
• Tiến trình P0 và P1 cùng truy cập vào semaphore S 
và Q, giá trị hiện thời của S và Q là 1
44
CHẾT ĐÓI (STARVATION)
• Thuật ngữ khác: phong toả vĩnh viễn (indefinite 
blocking)
• Là hiện tượng xảy ra khi tiến trình chờ vô định
trong semaphore
• Có thể xuất hiện nếu đánh thức tiến trình trong
hàng chờ của semaphore theo thứ tự LIFO (last-in, 
first-out)
45
NHỮNG VẤN ĐỀ ĐỒNG BỘ KINH ĐIỂN
• Vấn đề bộ đệm giới hạn (the bounded-buffer 
proble)
• Vấn đề đọc – ghi (the readers and writers problem)
• Bữa ăn tối của triết gia (the dining-philosophers 
problem)
46
VẤN ĐỀ BỘ ĐỆM GIỚI HẠN
• Bài toán sản xuất – tiêu thụ
• Biến chung
• n – kích thước của bộ đệm
• mutex – kiểm soát việc truy cập vào bộ đệm
• empty và full để đếm số ô trống và đầy trong bộ đệm
47
48
49
VẤN ĐỀ ĐỌC GHI
• Vấn đề đọc ghi thứ nhất
• Tiến trình đọc được ưu tiên
• Nếu không có tiến trình ghi nào đang truy cập vào dữ
liệu, thì tiến trình đọc sẽ được cấp quyền truy cập dữ
liệu ngay khi yêu cầu
• Tiến trình ghi có thể bị chết đói (starvation)
• Vấn đề đọc ghi thứ hai
• Tiến trình ghi được ưu tiên
• Khi tiến trình ghi muốn truy cập vào dữ liệu, nó được
đưa vào đầu hàng đợi. Ngay khi dữ liệu sẵn sàng, tiến
trình ghi được cấp quyền truy cập.
• Tiến trình đợi có thể bị chế đói
50
VẤN ĐỀ ĐỌC GHI THỨ NHẤT
• Biến chung
• read_count
• Sử dụng bởi tiến trình đọc
• Đếm số lượng tiến trình đọc đang truy cập vào dữ liệu
• mutex
• Sử dụng bởi tiến trình đọc
• Kiểm soát truy cập vào readcount
• rw_mutex
• Sử dụng để block và release tiến trình ghi
• Tiến trình đọc truy cập vào dữ liệu đầu tiên sẽ thiết lập giá trị
để block
• Tiến trình đọc cuối cùng truy cập vào dữ liệu sẽ thiết lập giá trị
để release
51
52
53
BỮA ĂN TỐI CỦA TRIẾT GIA
• Mỗi triết gia chỉ suy nghĩ (thinking) hoặc ăn (eat)
• Các triết gia không trao đổi với nhau
54
GIẢI PHÁP DÙNG SEMAPHORE
55
DEADLOCK?
GIẢI PHÁP CHO VẤN ĐỀ BẾ TẮC
• Chỉ cho phép tối đa 4 triết gia ăn cùng một lúc
• Chỉ cho phép triết gia nhặt đũa khi cả 2 chiếc đang
không bị sử dụng
• Giải pháp phi đối xứng (asymmetric solution)
• Đánh số các triết gia
• Triết gia có số thứ tự lẻ phải lấy chiếc đũa phía bên trái
trước
• Triết gia có số thứ tự chẵn phải lấy chiếc đũa phía bên
phải trước
• Vấn đề “chết đói” (starvation) chưa được giải quyết
56
HẠN CHẾ CỦA SEMAPHORE
• Sử dụng semaphore không đúng cách có thể dẫn
đến bế tắc hoặc lỗi do trình tự thực hiện của các
tiến trình
• Sử dụng không đúng cách gây ra bởi lỗi lập trình
hoặc do người lập trình không cộng tác
57
MONITOR
(PHƯƠNG PHÁP DÙNG TRÌNH THƯ KÝ)
• Cấu trúc trong ngôn ngữ lập trình bậc cao dùng để
phục vụ các thao tác đồng bộ hoá
• Các thành phần của monitor 
• Initialization code: thực thi một lần duy nhất khi tạo
monitor
• Private data (bao gồm private procedures): chỉ có thể sử
dụng bên trong monitor
• Monitor procedures: hàm/thủ tục có thể được gọi từ
bên ngoài monitor
• Monitor entry queue: hàng đợi các tiến trình đang chờ
thực thi monitor procedures
58
59
60
MONITOR
• Monitor đảm bảo tại một thời điểm chỉ có duy nhất
một tiến trình được hoạt động bên trong monitor
• Các hàm/thủ tục trong monitor chỉ có thể truy cập
vào các biến cục bộ và các tham số hình thức
61
CONDITION
• Khai báo
• Sử dụng: 2 toán tử wait và signal
• x.wait(): chuyển tiến trình sang trạng thái chờ
• x.signal(): tiến trình gọi x.signal() sẽ đánh thức tiến trình
đã gọi x.wait()
• Đánh thức duy nhất một tiến trình đang chờ
• Nếu không có tiến trình chờ, x.signal() không có tác dụng
• Chú ý: signal() trong semaphore luôn làm thay đổi giá trị
semaphore
62
SIGNAL WAIT/CONTINUE
• Giả sử có 2 tiến trình P và Q
• Q gọi x.wait()
• P gọi x.signal()
• Hai khả năng
• Signal-and-wait: P chờ đến khi Q rời monitor hoặc chờ
điều kiện khác
• Signal-and-continue: Q chờ đến khi P rời monitor hoặc
chờ điều kiện khác
63
TỰ ĐỌC
• Giải quyết bài toán bữa tối của triết gia bằng
monitor
• Cài đặt monitor bằng semaphore
64