1. Tương tranh giữa các process
1.1. Giới thiệu về tương tranh
1.1.1. Thường có nhiều process chạy song hành, nhưng mỗi process có không gian chạy độc lập
1.1.1.1. Rất tốt cho việc bảo vệ chúng lẫn nhau nhất lý khi các process này là những chương trình độc lập.
1.1.2. Nếu 2 hay nhiều process cần giao tiếp nhau. Có 2 cơ chế giao tiếp chính giữa các process
1.1.2.1. Truy xuất bộ nhớ dùng chung
1.1.2.2. Gởi/nhận thông báo
1.1.3. Truy xuất bộ nhớ chung là 1 trong nhiều hoạt động tương tranh giữa các process
1.1.3.1. Nếu nhiều process truy xuất đồng thời với 1 tài nguyên dùng chung chung mà không có sự kiểm soát thì dễ xảy ra lỗi làm hư hỏng tài nguyên
1.1.4. Danh sách liên tiếp của 2 loại đoạn code
1.1.4.1. Đoạn code truy xuất các biến cục bộ của chương trình
1.1.4.2. Đoạn code truy xuất tài nguyên dùng chung và có thể tranh chấp với process khác
1.2. Loại trừ tương hỗ giữa các đoạn code CS
1.2.1. Không cho phép hơn 1 vùng CS của các process đó cùng truy xuất tài nguyên xác định tại từng thời điểm
1.2.1.1. Phương pháp này được gọi là loại trừ tương hỗ giữa các đoạn CS (Mutual Exclusion)
1.2.2. Có nhiều phương pháp loại trừ , và được chia làm 2 nhóm chính
1.2.2.1. Nhóm các phương pháp dừng chờ chủ động (busy waiting)
1.2.2.1.1. Khi 1 process cần thực hiện đoạn code CS tương tranh với process khác thì nó phải dừng chờ đến khi process khác chạy xong đoạn code CS
1.2.2.2. Nhóm các phương pháp dừng chờ thụ động (sleep/wakeup)
1.2.2.2.1. Dừng chờ process khác, nó xin ngủ (trả CPU) và nằm bất động. Khi process khác thực hiện xong vùng CS, hệ thống sẽ đánh thức process ngủ để bắt đầu thực hiện đoạn lệnh CS
1.3. Các phương pháp dừng chờ chủ động (busy waiting)
1.3.1. Phương pháp dựa trên Interrupt
1.3.1.1. Tính chất cơ bản của CPU là sau khi thi hành 1 lệnh máy, nó sẽ tự động thi hành lệnh máy kế tiếp mà không để ý bất kỳ thứ gì bên ngoài.
1.3.1.2. Nếu CPU đang thi hành chương trình real-time hay nhạy cảm với thời gian, nó cần có khả năng phớt lờ yêu cầu ngắt.
1.3.1.2.1. Clear Interrupt
1.3.1.2.2. Set interrupt
1.3.2. Phương pháp dùng biến khóa
1.3.2.1. Mỗi vùng CS được bảo vệ bởi 1 biến khóa, biến này lúc đầu = 0 để xác định rằng chưa process nào thi hành vùng CS.
1.3.2.1.1. Nếu biến khóa = 0 thì set lên 1 và tiếp tục thi hành vùng CS đến khi hoàn thành sẽ set lại biến khóa = 0
1.3.2.1.2. Trường hợp biến khóa = 1 thì phải chờ process khác thi hành xong vùng CS.
1.3.3. Phương pháp dùng lệnh TSL
1.3.3.1. Phân tích lỗi của phương pháp dùng biến khóa, ta nhận thấy nếu 2 lệnh kiểm tra biến khóa và set nó lên 1 được đảm bảo thi hành theo cơ chế nguyên tử, không chia cắt, thì lỗi của slide trước không thể xảy ra, nghĩa là phương pháp dùng biến khóa sẽ chạy đúng.
1.3.4. Phương pháp luân phiên
1.3.4.1. Cho các process luân phiên thi hành vùng CS, từng thời điểm chỉ 1 process được thi hành CS.
1.3.4.2. Tạo 1 biến "turn" chứa chỉ số process được phép thi hành CS tại từng thời điểm. Lúc đầu turn được set = 0.
1.3.5. Phương pháp Peterson
1.4. Đồng bộ các process : Bài toán Sản xuất-Tiêu dùng
1.4.1. Trong hệ thống có 2 loại phần tử
1.4.1.1. Sản xuất chuyên tạo sản phẩm mới và để vào kho chứa.
1.4.1.2. Tiêu dùng chuyên lấy sản phẩm từ kho chứa ra để sử dụng.
1.5. 5 Các phương pháp dừng chờ thụ động (sleep-wakeup)
1.5.1. Phương pháp dùng Semaphore
1.5.1.1. Semaphore là đối tượng được cung cấp sẵn bởi hệ thống, đối tượng này gồm
1.5.1.1.1. 1 thuộc tính chứa giá trị nguyên dương, ta gọi là biến semaphore s
1.5.1.1.2. Hàm down(s) có chức năng giảm s 1 đơn vị, nếu giảm không được thì phải chờ đến khi có điều kiện giảm được thì làm lại.
1.5.1.1.3. Hàm up(s) có chức năng tăng s 1 đơn vị, nếu sau khi tăng mà s = 1 thì phải đánh thức các process đang ngủ vì đã thực hiện down(s) trước đây mà chưa được
1.5.1.2. Ta có thể dùng Semaphore để giải quyết tương tranh giữa nhiều process như sau
1.5.1.2.1. Kết hợp 1 semaphore nhị phân với vùng CS tương ứng. Semaphore này sẽ được gán trị đầu là 1 và sau này nó chỉ có thể chứa 2 trị
1.5.1.2.2. Hàm In_Control() để kiểm soát vào vùng CS của process sẽ là lời gọi hàm down (s)
1.5.1.2.3. Hàm Out_Control() để kiểm soát ra vùng CS của process sẽ là lời gọi hàm up (s)
1.5.1.3. tại 1 thời điểm chỉ có 1 process down(s) được và vào vùng CS, các process khác nếu down(s) đều bị thất bại và phải ngủ chờ.
1.5.1.3.1. Khi process đầu tiên thực hiện xong CS, nó thực hiện up(s) và sẽ đánh thức các process ngủ dậy. Trong các process dậy này, chỉ có 1 process thực hiện thành công lệnh down(s) để vào vùng CS.
1.5.2. Phương pháp dùng Monitor
1.5.2.1. Monitor là đối tượng được cung cấp sẵn bởi hệ thống
1.5.2.2. Sự khác biệt giữa Monitor và 1 đối tượng (module phần mềm) bình thường được thể hiện bởi 2 tính chất sau
1.5.2.2.1. 2 tác vụ định sẵn có thể truy xuất biến điều kiện
1.5.2.3. Monitor chỉ cho phép tối đa 1 process được vào thi hành 1 tác vụ nào đó của Monitor tại từng thời điểm
1.5.2.3.1. Dễ dàng giải quyết việc loại trừ tương hỗ giữa các process khi chúng truy xuất đồng thời 1 tài nguyên dùng chung nào đó bằng cách đặt mỗi đoạn CS vào 1 tác vụ riêng và đặt tất cả các tác vụ này trong một Monitor nào đó.
1.5.3. Phương pháp gởi/nhận thông báo
1.5.3.1. Hệ thống cung cấp 2 hàm chức năng
1.5.3.1.1. Send (proc_id, message) cho phép gởi 1 chuỗi byte tới prcoess proc_id
1.5.3.1.2. Receive (proc_id, message) cho phép chờ nhận chuỗi byte từ process proc_id gởi tới.
1.6. Các bài toán IPC kinh điển và giải quyết
1.6.1. Bài toán IPC kinh điển
1.6.1.1. Bài toán 5 SV ăn cơm
1.6.1.2. Bài toán đọc/ghi database
1.6.1.2.1. Có nhiều process cần đọc/ghi database
1.6.1.2.2. Làm sao cho việc đọc/ghi database của các process thỏa các điều kiện sau
1.6.1.2.3. Cách giải quyết đơn giản nhất
1.6.1.3. Bài toán ở tiệm hớt tóc
2. Quản lý process & Thread
2.1. Khái niệm process
2.1.1. Danh sách các lệnh để giải quyết
2.1.2. Process gồm 2 thành phần chính
2.1.2.1. Danh sách các lệnh cấu thành thuật giải của chương trình
2.1.2.2. Danh sách các lệnh cấu thành thuật giải của dữ liệu
2.1.3. Process tuần tự chỉ chứa 1 luồng thi hành lệnh cho
2.1.3.1. 1 chương trình từ điểm nhập
2.1.3.2. 1 chương trình ở điểm kết thúc
2.1.4. Khi chương trěnh được nạp vafp RAM và CPU bắt đầu
2.1.4.1. Thi hành chương trình ở điểm nhập thì chương trình trở thành process
2.1.4.2. CPU thực thi hết lệnh này tới lệnh khác từ trên xuống hay theo sự điều khiển của lệnh đang thực thi
2.2. Tạo, xóa process
2.2.1. Tạo procces
2.2.1.1. Một process được tạo từ những sự kiện sau
2.2.1.1.1. Do hệ thống tự tạo theo nhu cầu quản lý hệ thống
2.2.1.1.2. Do người kích hoạt 1 phần mềm
2.2.1.1.3. Do 1 thuật giải của 1 phần mềm đang chạy
2.2.2. Xóa process
2.2.2.1. Một process được xóa từ những sự kiện sau
2.2.2.1.1. Nội tại
2.2.2.1.2. Bên ngoài
2.3. Trạng thái process
2.3.1. Có 2 cấp trạng thái
2.3.1.1. Trạng thái vĩ mô
2.3.1.1.1. Thường có 3 trạng thái nổi tiếng
2.3.1.2. Trạng thái vi mô
2.3.2. Các sự kiện gây ra chuyển trạng thái
2.3.2.1. Thực hiện I/O tốc độ chậm
2.3.2.2. Chạy hết khe thời gian
2.3.2.3. I/O sẵn sàng phục vụ
2.3.3. Để quản lý từng process
2.3.3.1. HĐH sẽ 1 record dữ liệu gồm nhiều field
2.3.3.2. Mỗi field chứa 1 thông tin trạng thái mà HĐH muốn quản lý
2.3.4. Field đặc biệt trong record quản lý là field chứa mã trạng thái vĩ mô của process tương ứng
2.3.4.1. Để HĐH biết process đang chạy hay đang Ready | Blocked.
2.4. Khái niệm thread
2.4.1. Process tuần tự chỉ chứa 1 luồng thi hành lệnh (Thread) cho 1 chương trình từ điểm nhập đến điểm kết thúc.
2.4.2. Khác biệt giữa gọi hàm và tạo thread mới
2.4.2.1. Process mono-thread (chỉ chứa 1 luồng màu đỏ)
2.4.2.2. Process multi-thread (chứa 1 luồng chính màu đỏ và 1 luồng con màu xanh)
2.5. Lập lịch chạy các process
2.5.1. Dùng cơ chế phân chia thời gian (time-sharing) để chạy các process đồng thời trên 1 CPU.
2.5.2. Dùng timer để tính khe thời gian
2.5.2.1. Mỗi lần hết khe hay process hiện hành chờ I/O, trình lập lịch sẽ thực hiện công việc “chuyển ngữ cảnh process” để dừng process hiện hành và cho phép process khác chạy.
2.5.2.1.1. “Chuyển ngữ cảnh process” gồm các bước chính yếu sau đây
2.5.2.1.2. Công việc “chuyển ngữ cảnh process” là xác định, CPU có tốc độ càng cao thì thực hiện chuyển ngữ cảnh càng nhanh
2.5.3. Độ lớn của khe thời gian được xác định bằng cách dùng hòa giữa 2 yêu cầu mâu thuẫn nhau
2.5.3.1. Sao cho các ứng dụng chạy hiệu quả nhất
2.5.3.1.1. Chọn khe càng lớn càng tốt để tỉ lệ thời gian process chạy thực sự/thời gian chuyển ngữ cảnh trong từng khe là lớn nhất.
2.5.3.2. Sao cho ứng dụng tương tác nhanh với người dùng để lừa họ rằng ứng dụng luôn luôn chạy
2.5.3.2.1. Chọn khe càng nhỏ càng tốt để khoảng cách thời gian giữa 2 lần chạy liên tiếp của process là nhỏ nhất.
2.6. Các phương pháp lập lịch
2.6.1. Chúng ta sẽ nghiên cứu 4 phương pháp điền hình
2.6.1.1. Phương pháp Round-robin
2.6.1.1.1. Xử lý các process theo tinh thần bình đẳng.
2.6.1.2. Phương pháp dựa vào quyền ưu tiên
2.6.1.2.1. Xử lý các process theo quyền ơu tiên của từng process
2.6.1.3. Phương pháp dùng nhiều hàng chờ quyền ưu tiên
2.6.1.3.1. Dung hòa giữa 2 phương pháp Round-robin và dựa vào quyền ưu tiên để khắc phục các khuyết điểm của chúng.
2.6.1.4. Phương pháp cho process ngắn chạy trước.
2.6.1.4.1. Cho người dùng cảm thấy hệ thống chạy hiệu quả nhất.
3. DEADLOCK & XỬ LÝ
3.1. Định nghĩa deadlock
3.1.1. Deadlock là trạng thái của hệ thống mà ở ₫ó có ít nhất 2 process ₫ang dừng chờ lẫn nhau và như thế chúng không thể chạy tiếp ₫ược.
3.2. Bốn ₫iều kiện cần và ₫ủ ₫ể gây ra deadlock
3.2.1. Loại trừ tương hỗ ₫oạn code CS truy xuất tài nguyên dùng chung của các process chạy ₫ồng thời.
3.2.2. Process giữ tài nguyên cũ ₫ang chiếm dụng trong khi cố gắng xin thêm tài nguyên mới.
3.2.3. Hệ thống có dùng tài nguyên “non-preemptive”, là loại tài nguyên mà sau khi ₫ã giao cho 1 process nào ₫ó truy xuất Hệ thống không ₫ược quyền lấy lại tạm thời ₫ể cho process khác truy xuất.
3.2.4. Đã xuất hiện vòng khép kín giữa các process chờ nhau
3.3. Chiến lược phát hiện & chữa trị deadlock
3.3.1. Giải thuật ₫ơn giản cho hệ thống mà mỗi loại tài nguyên chỉ có tối ₫a 1 tài nguyên (hệ thống có 1 CPU, 1 ₫ĩa cứng, 1 máy in, 1 scanner,...).
3.3.1.1. Hệ thống sẽ xây dựng và quản lý ₫ồ thị miêu tả sự phụ thuộc giữa các process theo thời gian. Đồ thị này có các thành phần sau
3.3.1.1.1. Mỗi process hay mỗi tài nguyên là 1 nút của ₫ồ thị, cung có hướng từ nút i ₫ến j miêu tả phần tử i phụ thuộc phần tử j
3.3.2. . Giải thuật tổng quát cho hệ thống mà mỗi loại tài nguyên có thể có nhiều tài nguyên (hệ thống có 8 CPU, 4 ₫ĩa cứng, 5 máy in, 3 scanner,...)
3.3.2.1. Trạng thái sử dụng các tài nguyên của các process tại từng thời ₫iểm ₫ược xác ₫ịnh bởi 4 thông số sau ₫ây
3.3.2.1.1. vector miêu tả số lượng tài nguyên tổng thể ₫ã ₫ược gắn vào máy E(E1, E2,...,Em), trong ₫ó Ei là số lượng tài nguyên loại i mà hệ thống ₫ược trang bị.
3.3.2.1.2. vector miêu tả số lượng tài nguyên chưa dùng (₫ang rãnh) A(A1, A2,...,Am), trong ₫ó Ai là số lượng tài nguyên loại i còn ₫ang rãnh. Như vậy, vector A ≤ E theo nghĩa ∀j, Aj ≤ Ej.
3.3.2.2. Chữa trị deadlock
3.3.2.2.1. Dùng cơ chề "Preemption" tài nguyãn có liên quan : không tổng quát vì không khả thi nếu tài nguyêm liên quan là tài nguyên dạng “non-preemptive”.
3.3.2.2.2. Giết 1 hay n process rồi cho chúng chạy lại từ ₫ầu : chọn process nào ₫ể giết? Giết process sẽ làm mất tính nhất quán dữ liệu (vì bị process hiệu chỉnh 1 phần rồi).
3.3.2.2.3. Rollback process về checkpoint thích hợp tốn bộ nhớ lưu trữ trạng thái process ở những checkpoint.
3.3.2.3. Né tránh deadlock
3.3.2.3.1. Trạng thái an toàn là trạng thái mà ở ₫ó chưa có deadlock và tồn tại ít nhất 1 khả năng chạy các process sao cho chúng hoàn tất chức năng
3.4. Chiến lược né tránh deadlock
3.4.1. Tìm cách cấp phát tài nguyên sao cho về nguyên tắc không thể gây ra deadlock về sau
3.5. Chiến lược phòng ngừa deadlock
3.5.1. ₫ừng tạo cơ hội cho các process phải loại trừ tương hỗ lẫn nhau khi thi hành ₫oạn code CS truy xuất. Tài nguyên dùng chung, thí dụ dùng kỹ thuật 'Spooling' máy in. Kỹ thuật này không có tính tổng quát cao vì không thích hợp cho mọi tài nguyên.
3.5.2. Đừng giữ tài nguyên cũ (đang chiếm giữ) khi xin và chờ tài nguyên mới
3.5.3. Đừng sử dụng tài nguyên dạng "Nopreemptive" ⇒ không khả thi.