i dung NNộội dung
BÀI GIẢNG NGUYÊN LÝ HỆ ĐIỀU HÀNH
(cid:132) Cơ sở
(cid:132) Vấn đề đoạn găng
(cid:132) Giải pháp của Peterson
Chương 6: Đồng bộ hóa tiến trình
(cid:132) Phần cứng đồng bộ hóa
(cid:132) Kỹ thuật cờ báo (Semaphores)
Phạm Quang Dũng
Bộ môn Khoa học máy tính Khoa Công nghệ thông tin Trường Đại học Nông nghiệp Hà Nội Website: fita.hua.edu.vn/pqdung
5.2
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
6.1. Cơ sCơ sởở 6.1.
Producer Producer
(cid:132) Sự truy nhập đồng thời đến dữ liệu chia sẻ có thể gây ra sự
(cid:132) Để duy trì tính nhất quán dữ liệu cần có cơ chế đảm bảo thực
(cid:132) Giả sử rằng chúng ta muốn đưa ra một giải pháp cho vấn đề
(cid:122) Khởi tạo count=0.
(cid:122) Nó được tăng bởi tiến trình sản xuất khi thêm vào buffer 1 phần tử.
(cid:122) Nó bị giảm bởi tiến trình tiêu thụ khi lấy khỏi buffer 1 phần tử
while (true) { mâu thuẫn. /* produce an item and put in nextProduced */ while (count == BUFFER_SIZE) hiện các tiến trình hợp tác theo thứ tự. ; // do nothing buffer [in] = nextProduced; tiến trình sản xuất - tiến trình tiêu thụ mà đều điền vào buffer. in = (in + 1) % BUFFER_SIZE; Chúng ta có thể làm được bằng cách có một biến nguyên count count++; để theo dõi số phần tử trong buffer. }
5.3
5.4
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
1
i tranh đua (Race condition)
Consumer Consumer
TrTrạạng th
ng tháái tranh đua
(cid:132) count++ có thể được thực thi như sau:
register1 = count register1 = register1 + 1 count = register1
(cid:132) count-- có thể được thực thi như sau:
register2 = count register2 = register2 - 1 count = register2
(cid:132) Xét sự thực hiện đan xen với ban đầu “count = 5”:
while (true) { while (count == 0) ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--;
S0: producer execute register1 = count S1: producer execute register1 = register1 + 1 S2: consumer execute register2 = count S3: consumer execute register2 = register2 - 1 S4: producer execute count = register1 S5: consumer execute count = register2
{register1 = 5} {register1 = 6} {register2 = 5} {register2 = 4} {count = 6} {count = 4}
/* consume the item in nextConsumed }
5.5
5.6
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
n găng (Critical-Section)
6.2. Vấấn đn đềề đo đoạạn găng 6.2. V
CCấấu tru trúúc tc tổổng qu
ng quáát ct củủa tia tiếến trn trìình Pnh Pii
(cid:132) Xét hệ thống gồm n tiến trình {P0, P1, …, Pn-1}.
(cid:132) Mỗi tiến trình có một đoạn mã, gọi là đoạn găng, mà tại đó tiến
do {
đoạn vào
(cid:132) Đặc điểm quan trọng của hệ thống là tại mỗi thời điểm chỉ có 1
trình có thể thay đổi các biến chung, cập nhật bảng, ghi tệp…
đoạn găng tiến trình thực hiện trong đoạn găng của nó.
đoạn ra
(cid:132) Vấn đề đoạn găng là thiết kế một giao thức mà các tiến trình sử
⇔ sự thực hiện các đoạn găng là loại trừ lẫn nhau theo thời gian.
đoạn còn lại dụng để hợp tác. Mỗi tiến trình phải yêu cầu sự cho phép để } while (TRUE) ; bước vào đoạn găng của nó. Đoạn mã thực hiện yêu cầu này được gọi là đoạn vào. Sau đoạn găng có thể có đoạn ra.
5.7
5.8
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
2
GiGiảải phi phááp cho v
n găng p cho vấấn đn đềề đo đoạạn găng
CCáác phương ph
c phương phááp xp xửử lý đo
n găng lý đoạạn găng
(cid:132) kernel không ưu tiên trước: không cho phép một tiến trình bị ưu tiên
trước khi nó đang chạy trong kernel mode; tiến trình đó sẽ chạy cho
đến khi nó thoát khỏi kernel mode.
Một giải pháp cho vấn đề đoạn găng phải thỏa mãn 3 yêu cầu:
1. Loại trừ lẫn nhau: nếu tiến trình Pi đang thực hiện trong đoạn găng của nó thì các tiến trình khác không được thực hiện trong
(cid:122) Không gây tình trạng đua tranh trong cấu trúc
(cid:122) Windows 2000/XP, UNIX cũ, Linux trước phiên bản 2.6
đoạn găng của chúng.
2. Chọn tiến trình tiếp theo được vào đoạn găng: nếu không
(cid:132) kernel có ưu tiên trước: cho phép một tiến trình bị ưu tiên trước khi
nó đang chạy trong kernel mode.
(cid:122) Cần thiết kế cẩn thận để tránh tình trạng đua tranh, nhất là với kiến trúc đa
xử lý đối xứng (SMP). Vì sao?
(cid:122) Thích hợp hơn với lập trình thời gian thực, vì nó sẽ cho phép 1 tiến trình
có tiến trình nào đang trong đoạn găng của nó và một số tiến trình muốn vào đoạn găng của chúng thì chỉ những tiến trình đang không trong đoạn còn lại mới là ứng cử viên.
3. Chờ đợi có hạn: tồn tại giới hạn số lần các tiến trình khác
thời gian thực ưu tiên trước 1 tiến trình khác đang chạy trong kernel.
(cid:122) Linux 2.6, một số phiên bản thương mại của UNIX (Solaris, IRIX)
được phép vào đoạn găng của chúng sau khi một tiến trình yêu cầu vào đoạn găng đến trước khi yêu cầu đó được đáp ứng.
5.9
5.10
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
a Peterson 6.3. Giảải phi phááp cp củủa Peterson 6.3. Gi
ThuThuậật tot toáán cho ti
n cho tiếến trn trììnhnh PPii
(cid:132) Giải pháp cho 2 tiến trình P0, P1
(cid:132) Giả sử các lệnh LOAD và STORE là nguyên tử (atomic); nghĩa
while (true) {
(cid:132) Hai tiến trình chia sẻ 2 biến:
(cid:122) int turn;
là không thể bị ngắt. flag[i] = TRUE; turn = j; while (flag[j] && turn == j);
(cid:122) boolean flag[2]
ĐOẠN_GĂNG
(cid:132) Biến turn bằng 0/1. turn==i thì Pi được phép vào đoạn găng. (cid:132) flag[i]=true cho biết tiến trình Pi sẵn sàng vào đoạn găng.
flag[i] = FALSE;
ĐOẠN_CÒN_LẠI
Chứng minh thuật toán trên thỏa mãn cả 3 điều kiện của giải pháp?
}
5.11
5.12
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
3
6.4. Phầần cn cứứng đng đồồng bng bộộ hhóóaa 6.4. Ph
nh TestAndSet LLệệnh TestAndSet
(cid:132) Nhiều HĐH cung cấp sự hỗ trợ phần cứng cho mã đoạn găng
(cid:132) Định nghĩa:
(cid:132) Đơn bộ xử lý – có thể vô hiệu các ngắt
(cid:122) Đoạn mã đang chạy thực hiện mà không bị giành ưu tiên
(cid:122) Nói chung rất không hiệu quả với các hệ thống đa bộ xử lý
(cid:23) Việc chuyển thông điệp đến tất cả các bộ xử lý tốn rất nhiều
thời gian, làm trễ sự vào đoạn găng của các tiến trình
(cid:132) Nhiều HĐH hiện đại cung cấp các lệnh phần cứng nguyên tử
(cid:23) Nguyên tử = không thể bị ngắt
(cid:122) Hoặc là test từ nhớ (memory word) và set giá trị
(cid:122) Hoặc là hoán đổi (swap) nội dung của 2 từ nhớ
boolean TestAndSet (boolean *target) { boolean rv = *target; *target = TRUE; return rv; }
5.13
5.14
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
TestAndSet GiGiảải phi phááp dp dùùngng TestAndSet
nh Swap LLệệnh Swap
(cid:132) Biến boolean chia sẻ là lock, được khởi tạo là false. (cid:132) Giải pháp cho mỗi tiến trình:
(cid:132) Định nghĩa:
while (true) { void Swap (boolean *a, boolean *b) while (TestAndSet (&lock)) { ; /* do nothing boolean temp = *a; *a = *b; // đoạn găng *b = temp; } lock = FALSE;
// đoạn còn lại
}
5.15
5.16
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
4
Swap GiGiảải phi phááp dp dùùngng Swap
6.5. K6.5. Kỹỹ thuthuậật dt dùùng cng cờờ bbááoo (Semaphore)
(cid:132) Công cụ đồng bộ hóa dễ dùng hơn với người lập trình ứng dụng.
(cid:132) Biến boolean chia sẻ là lock, được khởi tạo là false; Mỗi tiến
(cid:132) Semaphore S – biến integer
(cid:132) Hai hoạt động nguyên tử chuẩn có thể thay đổi S:
(cid:132) Giải pháp cho mỗi tiến trình:
(cid:122) wait() và signal(), còn được gọi là P() và V()
while (true) {
key = TRUE;
wait (S) {
while (key == TRUE)
while S <= 0
Swap (&lock, &key);
; // no-op
// đoạn găng
S--;
}
lock = FALSE;
signal (S) {
// đoạn còn lại
S++;
}
}
trình có một biến boolean cục bộ là key.
5.17
5.18
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
Semaphore –– Công c Semaphore
Công cụụ đ đồồng bng bộộ hhóóa ta tổổng qu
ng quáátt
c thi Semaphore ThThựực thi Semaphore
(cid:132) Counting semaphore – giá trị S có thể không bị giới hạn
(cid:132) Phải đảm bảo rằng không thể có 2 tiến trình có thể thực hiện
(cid:132) Binary semaphore – giá trị S chỉ có thể bằng 0 hoặc 1; dễ thực
(cid:132) Do đó, sự thực thi trở thành vấn đề đoạn găng: mã của wait và
(cid:122) Còn được gọi là khóa loại trừ (mutex locks)
wait () và signal () trên cùng semaphore tại cùng thời điểm. hiện hơn
(cid:132) Có thể thực thi counting semaphore S như binary semaphore
(cid:132) Khi 1 tiến trình trong đoạn găng, các tiến trình khác cố gắng
(cid:132) Cung cấp sự loại trừ lẫn nhau
(cid:122) Semaphore S; // khởi tạo bằng 1
signal được đặt trong đoạn găng.
(cid:122) wait (S);
Đoạn găng
signal (S);
vào đoạn găng phải lặp liên tục trong mã đoạn vào, làm lãng phí các chu kỳ CPU – gọi là busy waiting.
5.19
5.20
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
5
Busy waiting (tiếp)
ThThựực thi Semaphore không c
c thi Semaphore không cóó Busy waiting
ThThựực thi Semaphore
c thi Semaphore không c
Busy waiting không cóó Busy waiting
(cid:132) Với mỗi semaphore có một waiting queue. Mỗi phần tử trong
(cid:132) Sự thực thi của wait: wait (S){
(cid:122) value (kiểu integer)
value--; if (value < 0) {
(cid:122) pointer, con trỏ tới bản ghi kế tiếp trong list
thêm tiến trình này vào waiting queue block(); }
}
(cid:132) Hai hoạt động:
(cid:122) block – đặt tiến trình gọi vào waiting queue thích hợp
(cid:23) Khi tiến trình thực hiện wait(), nếu giá trị S không dương thì
(cid:132) Sự thực thi của signal: signal (S){
thay vì đợi busy waiting, tiến trình có thể gọi block()
(cid:23) Trạng thái tiến trình được chuyển thành waiting
value++; if (value <= 0) {
(cid:122) wakeup – loại 1 tiến trình khỏi waiting queue và đặt nó vào
ready queue.
loại tiến trình P khỏi waiting queue wakeup(P); }
(cid:23) Khi 1 tiến trình khác gọi signal (), tiến trình được khởi động
}
lại bởi wakeup()
waiting queue có 2 trường dữ liệu:
5.21
5.22
Phạm Quang Dũng ©2008
Phạm Quang Dũng ©2008
Bài giảng Nguyên lý Hệ điều hành
Bài giảng Nguyên lý Hệ điều hành
Starvation Deadlock vvàà Starvation Deadlock
(cid:132) Deadlock (bế tắc) – hai hoặc nhiều tiến trình đang đợi vô hạn một sự kiện chỉ có thể được gây ra bởi một trong những tiến trình đợi đó.
(cid:132) Gọi S và Q là hai semaphore được khởi tạo bằng 1
End of Chapter 6 End of Chapter 6
P0 wait (S); wait (Q); P1 wait (Q); wait (S);
. . .
. . .
signal (S); signal (Q);
signal (Q); signal (S);
(cid:132) Starvation – khóa vô hạn. Một tiến trình có thể không bao giờ được đưa ra khỏi waiting queue tương ứng của semaphore.
(cid:122) Có thể xuất hiện khi waiting queue tổ chức dạng LIFO
![Tài liệu giảng dạy Nhập môn công nghệ thông tin [chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2026/20260401/baobinh_011/135x160/73071775121582.jpg)
