TRƯỜNG ĐẠI HỌC SÀI GÒN
CHƯƠNG 2 BÀI: ĐỒNG BỘ HÓA TIẾN TRÌNH
GV: LƯƠNG MINH HUẤN
NỘI DUNG
I. Tổng quan giao tiếp tiến trình
II. Tài nguyên găng, đoạn găng
III. Vấn đề đồng bộ hóa
IV. Giải pháp phần mềm
V. Các giải pháp phần cứng
VI. Semaphore
VII.Monitors
VIII.Giải pháp trao đổi thông điệp.
IX. Các ví dụ kinh điển
I. TỔNG QUAN GIAO TIẾP TIẾN TRÌNH
việc thực thi của các tiến trình khác.
➢Tiến trình độc lập: không ảnh hưởng và không bị ảnh hưởng bởi
➢Tiến trình hợp tác (không độc lập): có thể ảnh hưởng và bị ảnh
➢Ư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): thời gian I/O và thời gian CPU
▪ Tính module hóa
▪ Tiện lợi
hưởng bởi việc thực thi của các tiến trình khác.
HỢP TÁC BẰNG VIỆC CHIA SẺ
file và cơ sở dữ liệu dùng chung.
➢Các tiến trình sử dụng và cập nhập dữ liệu chia sẻ như các biến,
➢Thao tác ghi phải độc lập từng đôi một để ngăn ngừa tình trạng
➢Các miền găng dùng để cung cấp sự toàn vẹn dữ liệu.
đụng độ, có thể dẫn đến tính không toàn vẹn dữ liệu.
➢Một tiến trình đòi hỏi miền găng phải không bị chờ mãi mãi:
deadlock hoặc starvation.
HỢP TÁC BẰNG VIỆC GIAO TIẾP
➢Có khả năng deadlock
▪ Mỗi tiến trình đều chờ thông điệp từ một tiến trình khác.
➢Giao tiếp cung cấp phương cách để đồng bộ hóa nhiều hoạt động.
▪ Hai tiến trình gởi thông điệp cho nhau trong khi một tiến trình khác
chờ thông điệp.
➢Có khả năng xảy ra tình trạng đói (starvation)
CÁC VẤN ĐỀ
▪ Nhiều tiến trình truy xuất đồng thời một tài nguyên mang bản chất
không chia sẻ được.
• Vấn đề tranh đoạt điều khiển (race condition)
▪ Kết quả?
• Khó biết, nhưng thường là sai.
▪ Luôn luôn nguy hiểm?
• Nếu cân nhắc kỹ càng có thể giảm bớt sự nguy hiểm.
➢Tranh chấp
CÁC VẤN ĐỀ
▪ Các tiến trình không biết tương quan xử lý của nhau để điều chỉnh
hoạt động nhịp nhàng.
• Phối hợp xử lý (Rendez-vous)
▪ Kết quả: khó biết, thường không ăn khớp.
➢Phối hợp
TRANH ĐOẠT ĐIỀU KHIỂN
➢Ai sẽ thắng?
PHỐI HỢP HÀNH ĐỘNG
PHỐI HỢP HÀNH ĐỘNG
II. TÀI NGUYÊN GĂNG – ĐOẠN GĂNG
➢Những tài nguyên có nguy cơ bị hư hỏng, sai lệch khi được hệ điều hành chia sẻ đồng thời cho nhiều tiến trình được gọi là tài nguyên găng (critical resource).
➢Ví dụ:
➢Tài nguyên găng có thể là thiết bị vật lý hoặc dữ liệu dùng chung
TÀI NGUYÊN GĂNG
➢Tài nguyên găng là biến SCA đã bị tranh chấp.
➢Trường hợp chỉ còn 1 vé (SCA=1):
ĐOẠN GĂNG
▪ Tiểu trình (tiến trình) được gọi là đi vào miền găng.
▪ Loại trừ hỗ tương và miền găng là hai khái niệm cùng một mục đích.
➢Đoạn găng (Critical Section) hay miền găng là đoạn mã có tác động đến các tài nguyên găng, chỉ cho phép một tiểu trình (tiến trình) thi hành tại một thời điểm.
ĐOẠN GĂNG
➢Cấu trúc chương trình khi có đoạn găng
III. VẤN ĐỀ ĐỒNG BỘ HÓA
➢Mục đích là để đảm bảo không có một tiến trình nằm trong đoạn
➢Khi có nhiều tiến trình sử dụng tài nguyên găng thì phải đồng bộ.
găng.
▪ Loại trừ lẫn nhau (Mutual Exclusion).
▪ Tiến triển (Progress)
▪ Chờ đợi hữu hạn (Bounded waiting).
➢Cần thỏa mãn 3 điều kiện:
III. VẤN ĐỀ ĐỒNG BỘ HÓA
găng cùng lúc.
➢Mutual Exclusion: Không có hai tiến trình cùng ở trong miền
➢Progess: Một tiến trình tạm dừng bên ngoài miền găng không
➢Bounded Waiting: Không có tiến trình nào phải chờ vô hạn để
được ngăn cản các tiến trình khác vào miền găng
được vào miền găng.
CÁC GIẢI PHÁP ĐỒNG BỘ HÓA
▪ Phần mềm
• Giải pháp của Peterson
• Sử dụng các biến cờ hiệu
• Sử dụng việc kiểm tra luân phiên
▪ Phần cứng
• Cấm ngắt
• Chỉ thị TSL
➢Nhóm giải pháp Busy Waiting: tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng. Không đòi hỏi sự trợ giúp của hệ điều hành.
CÁC GIẢI PHÁP ĐỒNG BỘ HÓA
▪ Semophore
▪ Monitor
▪ Message
➢Nhóm giải pháp Sleep wakeup: từ bỏ CPU khi chưa được vào CS (miền găng). Khi CS trống sẽ được đánh thức để vào CS. Cần được hệ điều hành hổ trợ.
IV. GIẢI PHÁP PHẦN MỀM
➢Sử dụng biến cờ hiệu:
IV. GIẢI PHÁP PHẦN MỀM
➢Không bảo đảm mutual exclusion.
➢Có thể mở rộng cho n tiến trình.
➢Bản thân đoạn code kiểm tra và dành quyền cũng là miền găng
(CS).
IV. GIẢI PHÁP PHẦN MỀM
➢Kiểm tra luân phiên:
IV. GIẢI PHÁP PHẦN MỀM
IV. GIẢI PHÁP PHẦN MỀM
➢Bảo đảm mutual exclusion.
▪ Chỉ có 1 biến turn tại 1 thời điểm, chỉ cho 1 tiến trình vào CS.
➢Chỉ dành cho 2 tiến trình
▪ Mở cửa cho tiến trình khác thì tự đóng lấy chính mình.
➢Không bảo đảm progress.
IV. GIẢI PHÁP PHẦN MỀM
➢Giải quyết P0, P1 chia sẻ 2 biến chung, kết hợp 2 ý tưởng ở trên.
▪ int turn; //đến phiên ai
▪ int interest[2] = FALSE; //interest[i] = T : Pi muốn vào CS
➢Giải pháp Peterson
IV. GIẢI PHÁP PHẦN MỀM
IV. GIẢI PHÁP PHẦN MỀM
➢ Giải pháp phần mềm Peterson đáp ứng được cả 3 điều kiện:
➢ Mutual Exclusion :
▪ Pi chỉ có thể vào CS khi: interest[j] == F hay turn == i
▪ Nếu cả 2 muốn về thì do turn chỉ có thể nhận giá trị 0 hay 1 nên chỉ có 1
tiến trình vào CS
➢ Progress
▪ Sử dụng 2 biến interest[i] riêng biệt => trạng thái đối phương không khóa
được mình.
➢ Bounded Wait : interest[i] và turn đều có thay đổi giá trị.
➢ Không thể mở rộng cho N tiến trình
IV. GIẢI PHÁP PHẦN MỀM
▪ Không cần sự hổ trợ của hệ thống.
▪ Khó mở rộng.
▪ Dễ dẫn đến sai.
➢Nhìn chung đối với các giải pháp phần mềm:
V. GIẢI PHÁP PHẦN CỨNG
➢Disable Interrupt: cấm mọi ngắt, kể cả ngắt đồng hồ
➢Giải pháp cấm ngắt:
➢Enable Interrupt: cho phép ngắt.
V. GIẢI PHÁP PHẦN CỨNG
➢Nếu tiến trình bị khóa trong CS ?
▪ System Halt
➢Thiếu thận trọng
▪ Quá ...liều !
▪ Máy có N CPUs ?
➢Không bảo đảm được Mutual Exclusion
➢Cho phép tiến trình sử dụng một đặc quyền
V. GIẢI PHÁP PHẦN CỨNG
▪ CPU hỗ trợ primitive Test and Set Lock
• Trả về giá trị hiện hành của 1 biến, và đặt lại giá trị True cho biến
• Thực hiện một cách không thể phân chia
➢Giải pháp chỉ thị TSL:
TSL (boolean &target)
{
TSL = target;
target = TRUE;
}
V. GIẢI PHÁP PHẦN CỨNG
➢Áp dụng TSL
V. GIẢI PHÁP PHẦN CỨNG
▪ Dễ mở rộng cho n tiến trình.
▪ Cần được sự hổ trợ của cơ chế phần cứng.
• Đối với các máy có nhiều vi xử lý, điều này không dễ.
➢Nhìn chung đối với các giải pháp phần cứng:
VI. SEMAPHORE
➢Các đặc tính: Semaphore s;
▪ Có 1 giá trị nguyên dương
▪ Chỉ được thao tác bởi 2 primitives :
• Down(s)
• Up(s)
▪ Các primitive Down và Up được thực hiện không thể phân chia
➢Được đề nghị bởi Dijkstra năm 1965
VI. SEMAPHORE
▪ Các tiến trình “yêu cầu” semaphore : gọi Down(s)
• Nếu không hoàn tất được Down(s) : chưa được cấp resource
– Blocked, được đưa vào s.L
➢Semaphore được xem như là một resource
▪ Sleep() & Wakeup()
➢Cần có sự hỗ trợ của HĐH
VI. SEMAPHORE
VI. SEMAPHORE
➢Tổ chức “độc quyền truy xuất”
VI. SEMAPHORE
➢Tổ chức “hò hẹn”
VI. SEMAPHORE
▪ Dễ dùng cho N tiến trình
➢Là một cơ chế tốt để thực hiện đồng bộ
▪ MutualExclusion : Down & Up
▪ Rendez-vous : Down & Up
▪ Chưa phân biệt qua mô hình
➢Khó sử dụng đúng
▪ Dễ nhầm lẫn
➢Nhưng ý nghĩa sử dụng không rõ ràng
VII. MONITOR
➢Là cơ chế đồng bộ hóa do NNLT cung cấp
▪ Hỗ trợ các chức năng như Semaphore
▪ Dễ sử dụng và kiểm soát hơn Semaphore
• Đảm bảo Mutual Exclusion một cách tự động
• Sử dụng biến điều kiện để thực hiện Synchronization
➢Đề xuất bởi Hoare(1974) & Brinch (1975)
MONITOR : NGỮ NGHĨA VÀ TÍNH CHẤT
▪ Các CTDL, đối tượngdùng chung
▪ Các phương thứcxử lý các đối tượng này
▪ Đảm bảo tính encapsulation
➢Là một module chương trình định nghĩa
▪ P1 : M.C() // i=5
▪ P2: M.B() // printf(j)
➢Các tiến trình muốn truyxuất dữ liệu bên trong monitor phải dùng các phương thức của monitor :
MONITOR : NGỮ NGHĨA VÀ TÍNH CHẤT
▪ Tại 1 thời điểm chỉ có 1 tiến trình thực hiện các phương thức của
Monitor
▪ Các tiến trình không vào được Monitor sẽ được đưa vào Entry queue của
Monitor
➢Tự động bảo đảm Mutual Exclusion
▪ P1 : M.A();
▪ P6 : M.B();
▪ P7 : M.A();
▪ P8 : M.C();
➢Ví dụ
MONITOR : NGỮ NGHĨA VÀ TÍNH CHẤT
MONITOR : NGỮ NGHĨA VÀ TÍNH CHẤT
▪ Wait(c) : Tiến trình gọi hàm
sẽ bị blocked
▪ Signal(c): Giải phóng 1 tiến trình đang bị blocked trên biến điều kiện c
▪ C.queue: danh sách các tiến
trình blocked trên c
➢Hỗ trợ Synchronization với các condition variables
MONITOR : NGỮ NGHĨA VÀ TÍNH CHẤT
gọi Signal?
▪ Blocked. Nhường quyền vào monitor chotiến trình được đánh thức.
▪ Tiếp tục xử lý hết chu kỳ,
rồi blocked
➢Trạng thái tiến trình sau khi
SỬ DỤNG MONITOR
VIII. GIẢI PHÁP TRAO ĐỔI THÔNG ĐIỆP
➢Đồng bộ hóa trên môi trường phân tán
➢Được hỗ trợ bởi HĐH
▪ Cài đặt theo mode blocking
➢2 primitive Send & Receive
IX. VÍ DỤ KINH ĐIỂN
➢Readers –Writers
➢Producer –Consumer
➢Dinning Philosophers
PRODUCER -CONSUMER (BOUNDED-BUFFER PROBLEM)
➢Mô tả : 2 tiến trình P và C hoạt
▪ P sản xuất hàng và đặt vào Buffer
▪ C lấy hàng từ Buffer đi tiêu thụ
▪ Buffer có kích thước giới hạn
động đồng hành
▪ P và C đồng thời truy cập Buffer ?
▪ P thêm hàng vào Buffer đầy ?
▪ C lấy hàng từ Buffer trống ?
➢Tình huống
PRODUCER –CONSUMMER: GIẢI PHÁP SEMAPHORE
▪ BufferSize = N; // số chỗ trong bộ đệm
▪ semaphore mutex = 1 ; // kiểm soát truy xuất độc quyền
▪ semaphore empty = BufferSize; // số chỗ trống
▪ semaphore full = 0; // số chỗ đầy
▪ int Buffer[BufferSize];// bộ đệm dùng chung
➢Các biến chung giữa P và C
PRODUCER –CONSUMMER: GIẢI PHÁP SEMAPHORE
PRODUCER –CONSUMMER: GIẢI PHÁP SEMAPHORE
PRODUCER –CONSUMMER : GIẢI PHÁP MONITOR
PRODUCER –CONSUMMER : GIẢI PHÁP MONITOR
PRODUCER –CONSUMMER: GIẢI PHÁP MESSAGE
READERS & WRITERS
➢ Mô tả: N tiến trình Ws và Rs hoạt động đồng hành
▪ Rs và Ws chia sẻ CSDL
▪ W cập nhật nội dung CSDL
▪ Rs truy cập nội dung CSDL
➢ Tình huống
▪ Các Rs cùng truy cập CSDL ?
▪ W đang cập nhật CSDL thì các Rs truy cập CSDL ?
▪ Các Rs đang truy cập CSDL thì W muốn cập nhật CSDL ?
READERS-WRITERS VỚI “ACTIVE READERS”
READERS-WRITERS VỚI MỘT “ACTIVE WRITER”
Ưu tiên ai hơn đây?
READERS & WRITERS
➢W hiện tại kết thúc cập nhật CSDL : ai vào?
▪ Cho W khác vào, các Rs phải đợi
• Ưu tiên Writer, Reader có thể starvation
▪ Cho các Rs vào, Ws khác phải đợi
• Ưu tiên Reader, Writer có thể starvation
➢W độc quyền truy xuất CSDL
READERS & WRITERS : GIẢI PHÁP SEMAPHORE
▪ semaphore db = 1; // Kiểm tra truy xuất CSDL
➢Các biến dùng chung giữa Rs và Ws
READERS & WRITERS : GIẢI PHÁP SEMAPHORE
READERS & WRITERS : GIẢI PHÁP SEMAPHORE
▪ semaphore db = 1; // Kiểm tra truy xuất CSDL
➢Các biến dùng chung giữa Rs và Ws
▪ int rc; // Số lượng tiến trình Reader
▪ semaphore mutex = 1; // Kiểm tra truy xuất rc
➢Các biến dùng chung giữa Rs
READERS & WRITERS : GIẢI PHÁP SEMAPHORE
R&W : Giải pháp Semaphore (Thinking...)
R&W: GIẢI PHÁP MONITOR
R&W: GIẢI PHÁP MONITOR
R&W: GIẢI PHÁP MONITOR
DINING PHILOSOPHERS
spaghetti
▪ Trên bàn có 5 cái nĩa được đặt giữa 5 cái đĩa
(xem hình)
▪ Để ăn món spaghetti mỗi người cần có 2 cái
nĩa
➢Năm triết gia ngồi chung quanh bàn ăn món
▪ Thinking...
▪ Eating...
➢Triết gia thứ i:
Dining Philosophers: Tình huống nguy hiểm
▪ Tranh chấp
▪ Cần đồng bộ hóa hoạt động của các triết gia
➢2 triết gia “giành giật” cùng 1 cái nĩa
Dining Philosophers : Giải pháp đồng bộ
semaphore fork[5] = 1;
Philosopher (i)
{
while(true)
{
down(fork[i]);
down(fork[i+1 mod 5])
eat;
up(fork[i]);
up(fork[i+1 mod 5]);
think;
}
DINING PHILOSOPHERS : THÁCH THỨC
▪ Không có deadlock
▪ Không có starvation
➢Cần đồng bộ sao cho:
