KHOA CÔNG NGHỆ THÔNG TIN
TRƯỜNG ĐẠIHỌC BÁCH KHOA TP HỒ CHÍ MINHTRƯỜNG ĐẠI HỌC BÁCH KHOA TP HỒ CHÍ MINH
HỆ ĐIỀU HÀNH
Giao tiếp giữa các tiến trìnhpg
Một số khái niệm cơ bản*
 Tiến trình độc lập không ảnh hưởng và không bị ảnh
hưởn
g bởi việc thực thi của các tiến trình khác.g
 Tiến trình hợp tác (không độc lập) có thể ảnh hưởng
và bị ảnh hưởng bởi việc thực thi của các tiến trình
khác.
 Ưu điểm của việc hợp tác tiến trình:

Chia sẻ thông tin

Tăng tốc tính toán (xử lý song song)
Tí h d l hó

Tính module hóa

Tiện lợi
2
Một số khái niệm cơ bản*
 Các tiến trình sử dụng và cập nhập dữ liệu chia sẻ
như các biến, file và cơ sở dữ liệu dùng chung.
ể Thao tác ghi phải độc lập từng đôi một để ngăn ngừa
tình trạng đụng độ, có thể dẫn đến tính không toàn
vẹndữ liệuvẹn dữ liệu.
 Các miền găng dùng để cung cấp sự toàn vẹn dữ liệu.

Mộttiếntrìnhđòi hỏimiềngăng phải không bị chờMột tiến trình đòi hỏi miền găng phải không bị chờ

được quyền thực thi trong miền găng của nó (ngay cả
với nhiều bộ xử lý).
 Vì vậy mỗi tiến trình phải yêu cầu quyền trước khi
vào miền găng.
7
Ngữ cảnh miền găng
 Đoạn mã thể hiện yêu cầu này được gọi làEntry
Section
(ES).()
 Miền găng (CS) có thể theo sau là Leave/Exit
Section (LS).Section (LS).
 Phần đoạn mã còn lại là Remainder Section (RS).
 Vấn đề củamiềngăng là thiếtkế mộtgiaothứcmà Vấn đề của miền găng là thiết kế một giao thức mà
các tiến trình có thể sử dụng để hành động của chúng
sẽ không phụ thuộcvàothứ tự mà sự thi hành củasẽ không phụ thuộc vào thứ tự mà sự thi hành của
chúng được chen vào.
8
Giải pháp cho vấn đề miền găng
 Có 3 yêu cầu mà một giải pháp đúng cần phải thỏa
mãn:
ế1. Mutual Exclusion: không có 2 tiến trình cùng ở
trong miền găng một lúc
2 PMộttiế tìhbê ài iề ă2. Progress: Một tiến trình bên ngoài miền găng
không được ngăn cản các tiến trình khác vào
mi
ền găngg g
3. Bounded Waiting: không có tiến trình nào phải
chờ vô hạn để vào miền găng
 Chỉ cần một trong ba điều kiện trên sai thì giải
há đ là i

Giải thuật 1
 Biến chia sẻ

int turn; /* khởi đầu turn = 0 */
á i đhùøii l i

nếu turn = i  P
i
được phép vào critical section
 Process P
i
do {do {
while (turn != i) ;
critical section
();()
turn = j;
remainder section();
i(1)} while (1);

Thoả mãn mutual exclusion (1)
12
Thoa man mutual exclusion (1)
 Progress (2) & bounded-waiting (3) ?
Giải thuật 1
Process P0:
do
Process P1:
do
do
while(turn !=0 );

i
ocess
i
do {
flag[i] = true;
iwhile (flag[j]) ;
Critical_Section();
flag [i] = false;ag [ ] a se;
Remainder_Section();
} while (1);
14
Giải thuật 3 (Peterson)
 Biến chia sẻ: kết hợp cả giải thuật 1 và 2.
 Process P
i
do {
flag [i]= true;
turn = j;
while (flag [j] and turn == j) ;(g[j] j);
Critical_Section();
flag [i] = false;
Remainder_Section();
} while (1);
15
Giải thuật Bakery: N process
 Trước khi vào CS, process Pi nhận một con số. Process nào giữ
con số nhỏ nhất thì được vào CS
 Trường hợp Pi và Pj cùng nhận được một chỉ số:

Nếui<jthìPiđươcvàotrước ngươc lai Pj đươc vào

}
17
}
Semaphores
 Là một công cụ đồng bộ hóa được cung cấp bởi
HĐH không đòi hỏi “busy waiting”.
ế Một semaphore S là một biến nguyên mà ngoài lệnh
khởi tạo ra, chỉ có thể được truy xuất thông qua hai
thao tác độc quyềntruyxuất và nguyên tố:thao tác độc quyền truy xuất và nguyên tố:

wait(S)

signal(S)signal(S)
18
Semaphores
 Truy cập với 2 thao tác
wai
t (S): ( )
while S 0 do no-op;
S--;
signal (S):
S++;
Để t á h “b iti ” khi ộttiế tì h hải đ ióẽ Để tránh “busy waiting”: khi một tiến trình phải đợi, nó sẽ
được đặt vào hàng đợi block.
 Khi một tiến trình phải đợi một semaphore S, nó sẽ bị block ộ p ợ ộ p, ị
và đặt vào hàng đợi của semaphore tương ứng.
 Thao tác signal lấy một tiến trình từ trong hàng đợi và đặt nó
àt d háhátiế tì hở t thái ẵ à
19
vào trong danh sách các tiến trình ở trạng thái sẵn sàng.

Tình huống:
một tập các process bò blocked, mỗi process giữ tài
nguyên và đang chờ tài nguyên mà process khác trong tập đang
giữ.g

Ví dụ 1
– Giả sử hệ thống có 2 file trênđóa.Gia sư hệ thong co 2 file tren đóa.
– P1 và P2 mỗi process đang mở một file và yêu cầu mở file kia.

Ví du 2

Ví dụ 2
– Semaphore A và B, khởi tạo bằng 1
P0 P1
wait (A); wait(B);wait (A); wait(B);
wait (B); wait(A);
-8.22-
Mô hình hóa hệ thống

Hệ thống gồm các loại
tài nguyên
, kí hiệu
R
1
,
R
2
,…,
R
m

Cac tac vụ yeu cau (request) va hoan tra (release) đeu la
system call. Ví dụ
– request/release device
– open/close file
-8.23-
– open/close file
– allocate/free memory
– wait/signal
Điều kiện cần để xảy ra deadlock
Bốn điều kiện cần (necessary condition) để xảy ra
deadlock
1. Mutual exclusion:
ít nhất một tài nguyên được giữ
theo nonsharable modetheo nonsharable mode.
2. Hold and wait:
một process đang giữ ít nhất một tài pgg
nguyên và đợi thêm tài nguyên do quá trình khác
đang giữ.
-8.24-
Điều kiện cần để xảy ra deadlock (tt)
3. No preemption:
tài nguyên không thể bò lấy lại, mà
chỉ có thể được trả lại từ process đang giữ tài
nguyênđó khi nó muốnnguyen đo khi no muon.
4 Circular wait:
tồn tai một chu trình củacácyêucầu
4. Circular wait:
ton tại một chu trình cua cac yeu cau
tài nguyên và tài nguyên đã được cấp phát.
P