Seminal chương 5 Đồng bộ hóa và giao tiếp dựa trên biến chia sẻ
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (7.11 MB, 89 trang )
Trường Đại Học Công Nghệ Thông Tin
Khoa Kỹ Thuật Máy Tính
HỆ THỐNG THỜI GIAN THỰC
Lớp: CE312.F11
GV : Phạm Văn Phước
Seminal Chương 5
ĐỒNG BỘ HÓA VÀ GIAO TIẾP
DỰA TRÊN BIẾN CHIA SẺ
1
Danh Sách Thành Viên Nhóm:
Trần Đại Dương
Nguyễn Viết Nam
Nguyễn Văn An
Nguyễn Văn Thể Mỹ
Phan Trần Như Ngọc
Võ Dương Quang
11520537
11520241
11520003
11520234
11520253
11520709
2
Mục tiêu
• Hiểu các yêu cầu cần thiết cho việc đồng bộ hóa và
giao tiếp dựa trên biến chia sẻ
– Busy waiting, semaphores, monitors, conditional
critical regions, deadlock, livelock, … trong OS
• Hiểu các phương thức đồng bộ hóa trong Java
3
Nội Dung Chương 5
5.1 Độc quyền truy xuất và đồng bộ hóa điều kiện
5.2 Busy waiting
5.3 Suspend and Resume
5.4 Semaphore
5.5 Conditional Critical Region
5.6 Monitors
5.7 + 5.8 POSIX Mutex và Condition Variables
5.9 Phương thức đồng bộ trong Java
5.10 Chia sẻ bộ nhớ đa xử lý
5.11 Hệ thống nhúng rà soát đơn giản
*Tổng kết
4
Phần 5.1
Độc quyền truy xuất và đồng bộ
hóa điều kiện
5
Đồng Bộ Hóa Và Giao Tiếp
• Tính chính xác của một chương trình song song
phụ thuộc vào việc đồng bộ hóa và giao tiếp giữa
các tác vụ
• Đồng bộ hóa: là việc thỏa mãn các ràng buộc
xen giữa các hành động của các tác vụ
• Giao tiếp (truyền thông): là việc truyền thông
tin từ tác vụ này tới tác vụ khác
• Giao tiếp giữa các tác vụ thường dựa trên biến
chia sẻ hoặc truyền thông điệp
6
Biến chia sẻ
• Biến chia sẻ: là đối tượng mà nhiều tác vụ có
thể cùng truy cập
– “Bạn đường của vùng nhớ chia sẻ”
– Vấn đề về tính tin cậy và tính an toàn
• Ví dụ: xem xét X := X + 1
– LOAD R1, X
– INC
R1
– STORE R1, X
; Nạp giá trị của X vào R1
; Tăng giá trị của R1 lên 1 giá trị
; Lưu giá trị của R1 vào X
• Tính “atomic” của phép toán cập nhật X?
7
Miền găng (Critical region)
• Miền găng: là một chuỗi các câu lệnh phải
thực thi để đảm bảo tính “atomic”
• Độc quyền truy xuất (Mutual exclusion):
là giải pháp bảo vệ miền găng
• Ví dụ: A thực hiện X := X + 1
B thực hiện X := X đồng thời với A
8
Đồng bộ hóa điều kiện
• Đồng bộ hóa điều kiện: là một đòi hỏi quan trọng và
cần thiết khi một tác vụ muốn thực hiện một hành
động một cách hợp lý chỉ khi một tác vụ khác đạt
được một số trạng thái nhất định
– Thực hiện “Độc quyền truy xuất”
• Ví dụ: bài toán Người sản xuất (A)/ Người tiêu dùng
(B)
– A không được sản xuất khi kho đầy hàng
– B không được tiêu dùng khi kho hết hàng
• Liệu có cần thực hiện độc quyền truy xuất trong bài
toán ở trên?
9
Phần 5.2
Busy waiting
10
Busy waiting
• Busy waiting: là một giải pháp việc đồng bộ
hóa điều kiện
– Sử dụng tối đa CPU
task_a() {
…
while (flag == 0);
…
}
task_b() {
…
flag = 1;
…
}
11
Busy waiting – Biến cờ hiệu (flag)
while(1) {
while(flag == 1); // Đang truy xuất
flag = 1;
critical_region();
flag = 0;
non_critical_region();
}
Điều gì xảy ra khi “flag = 1;” bị tạm hoãn?
12
Busy waiting – Chơi theo lượt
while(TRUE) {
}
while(TRUE) {
while(turn == 1);
while(turn == 0);
critical_region();
critical_region();
turn = 1;
turn = 0;
non_critical_region();
non_critical_region();
}
Điều gì xảy khi khi một tác vụ không vào miền găng?
13
Busy waiting – Peterson
while(TRUE) {
flag[i] = 1;
turn = j;
while(turn == j && flag[j] == 1);
critical_region();
flag[i] = 0;
non_critical_region();
}
14
Phần 5.3
Suspend and Resume
15
Suspend and Resume
100%
CPU
Busy Waiting
Suspend
Ex:
P1
P2
16
Suspend and Resume
• Trong Java có 2 hàm để hỗ trợ việc này là:
17
Suspend and Resume
P1
P2
18
Suspend and Resume
P1
P2
19
Suspend and Resume
Data Race
Condition
20
Suspend and Resume
Data Race
Condition
Ex:
70%
T
1
Dual Core
T
2
Dual Core
Done!
T
1
T
2
Dual Core
100%
T
1
Done!
T
2
Dual Core
21
Phần 5.4
Semaphore
22
Semaphore
Semaphore
Mutual Exclusion
Condition
Synchronization
23
Semaphore
• Nó được phát triển bởi Dijkstra (1968) và có
2 ưu điểm sau:
– Đơn giản hóa cơ chế đồng bộ hóa.
– Xóa bỏ những thứ cần thiết cho vòng lặp
busy-waiting
24
Semaphore
Semaphore
Wait
Signal
• Semaphore là biến số nguyên không âm, nó được điều
khiển bởi 2 thủ tục. Những thủ tục này được goi là wait
& signal
• Wait - Nếu giá trị semaphore (S) >= 0 thì giảm giá trị
xuống 1 đơn vị. Nếu không thì delay cho đến khi S
lớn hơn 0.
• Signal – Tăng giá trị của S lên 1
Semaphore thông thường được gọi là Counting Semaphores
Những toán tử này dùng để tăng và giảm biến Counting Semaphores
25
