Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Chương 6: ĐỒNG BỘ HOÁ
TIẾN TRÌNH
6.2
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Tóm tắt nội dung

Giới thiệu

Tổng quan về đồng bộ hóa tiến
trình

Vấn đề đoạn găng

Các giải pháp

Các bài toán đồng bộ hóa
nguyên thủy
6.3
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Giới thiệu
Một tiến trình cộng tác là một tiến trình ảnh

Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Mã của tiến trình người sản xuất
6.6
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Mã của tiến trình người tiêu thụ

6.7
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Điều kiện cạnh tranh (race condition)


count++ được cài đặt trên ngôn ngữ máy :
register1 = count
register1 = register1 + 1
count = register1

Tương tự cài đặt count - - như sau:
register2 = count
register2 = register2 - 1
count = register2


Đoạn găng
1. Điều kiện cạnh tranh - Nhiều quá trình truy xuất cùng
thao tác dữ liệu đồng hành để chia sẽ dữ liệu và kết
quả của việc thực thi phụ thuộc vào thứ tự xác định
ở đó việc truy xuất xảy ra.
2. Đoạn găng – Phân đoạn mã chia sẽ dữ liệu được truy
cập trong các tiến trình đồng thời.
3. Phần đi vào – Vùng mã thực hiện yêu cầu quyền để
đi vào đoạn găng của nó.
4. Phần kết thúc – Vùng mã được chạy sau khi ra khỏi
đoạn găng.
6.10
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Đoạn găng
6.11
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Đoạn găng
1. Loại trừ hỗ tương -Nếu tiến trình Pi đang thực thi trong đoạn
găng của nó thì không tiến trình nào khác được thực thi
trong đoạn găng đó.
2. Tiến trình - Nếu không có tiến trình nào đang thực thi trong
đoạn găng và ở đó tồn tại vài tiến trình mà muốn tham gia
vào đoạn găng, sau đó chọn lựa những tiến trình sẽ đi vào
đoạn găng tiếp theo không thể trì hoãn vô hạn định.


Biến turn cho biết quá trình diễn biến được
tiến hành trong đoạn găng.

Mảng flag được dùng để hiển thị một tiến trình
sẵn sàng đi vào đoạn găng. flag[i] = true nghĩa
là process P
i
đang sẵn sàng!
6.14
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Giải pháp “chờ đợi bận”
Giải thuật 1:
Để hai tiến trình chia sẽ một biến số nguyên
chung turn được khởi tạo bằng 0 hoặc 1.
Nếu turn = 0 thì P
i
được phép thực thi trong
đoạn găng của nó.
Giải pháp này đảm bảo rằng chỉ một tiến trình
tại một thời điểm có thể ở trong đoạn găng
của nó.
6.15
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006

Kết hợp hai ý tưởng trong giải thuật 1 và 2  được
một giải pháp đúng với vấn đề đoạn găng, hai
yêu cầu được thỏa mãn.
Các tiến trình chia sẽ hai biến:
Boolean flag[2]
Int turn;
Khởi tạo flag[0] = flag[1] = false
Giá trị turn = 0 hoặc 1.
6.19
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Giải thuật 3 (giải pháp Peterson)
6.20
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Giải pháp Peterson
6.21
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Giải pháp nhiều tiến trình (giải thuật Bakery):
Phát triển cho môi trường phân tán.
Cấu trúc dữ liệu chung là:
Boolean choosing[n];
Int number [n];

6.24
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Đồng bộ hoá phần cứng
6.25
Silberschatz, Galvin and Gagne ©2007
Operating System Concepts with Java – 7
th
Edition, Nov 15, 2006
Chỉ thị Swap
Thao tác trên nội dung của hai từ.
Giống như chỉ thị TestAndSet, nó được thực thi
theo tính nguyên tử.
Void Swap(boolean &a, boolean &b)
{ Boolean temp =a;
A=b;
B=temp;
}

Hình 0-9:Định nghĩa chỉ thị Swap