Bài giảng Nguyên lý hệ điều hành - Chương 2: Quản lý tiến trình

3/12/2008 Nguyên lý Hệ điều hành 2 1. Tiến trình „ Khái niệm về tiến trình „ Lập lịch tiến trình „ Các thao tác trên tiến trình „ Hợp tác giữa các tiến trình „ Luồng „ Truyền thông giữa các tiến trình 3/12/2008 Nguyên lý Hệ điều hành 3 1.1. Khái niệm về tiến trình „ Một HĐH thực hiện nhiều chương trình ‰ Hệ thống xử lý theo lô: công việc (job) ‰ Hệ thống chia sẻ thời gian: tác vụ(task) „ Ở đây chúng ta dùng tiến trình và công việc với cùng ý nghĩa 3/12/2008 Nguyên lý Hệ điều hành 4 Tiến trình „ Chương trình đang được thực hiện ‰ Phần văn bản ‰ Ngăn xếp ‰ Phần dữ liệu ‰ Giá trị bộ đếm chương trình, thanh ghi „ CPU xử lý tiến trình tuần tự „ Thực thể hoạt động ‰ vs. chương trình Nguyên lý Hệ điều hành 5 Cấu trúc bộ nhớ tiến trình 3/12/2008 Nguyên lý Hệ điều hành 6 Trạng thái tiến trình „ Tiến trình thay đổi trạng thái trong khi thực hiện ‰ New ‰ Running ‰ Waiting ‰ Ready ‰ Terminated „ Tại một thời điểm chỉ có một tiến trình ở trạng thái running 3/12/2008 Nguyên lý Hệ điều hành 7 Trạng thái tiến trình 3/12/2008 Nguyên lý Hệ điều hành 8 Khối điều khiển tiến trình (PCB) 3/12/2008 Nguyên lý Hệ điều hành 9 Chuyển đổi CPU giữa các tiến trình 3/12/2008 Nguyên lý Hệ điều hành 10 1.2. Lập lịch tiến trình „ Mục đích của đa chương trình ‰ Tăng tính tận dụng CPU „ Mục đích của phân chia thời gian ‰ Người dùng có thể tương tác với tiến trình trong lúc nó đang thực thi ÆXử lý nhiều tiến trình Æ Lập lịch tiến trình 3/12/2008 Nguyên lý Hệ điều hành 11 Các hàng đợi lập lịch tiến trình „ Hàng đợi công việc ‰ Một tập các tiến trình trong hệ thống „ Hàng đợi sẵn sàng ‰ Tập các tiến trình trong bộ nhớ trong, sẵn sàng và chỉ chờ thực hiện „ Hàng đợi thiết bị ‰ Tập các tiến trình chờ một thiết bị vào/ra „ Các tiến trình di trú từ hàng đợi này đến hàng đợi khác 3/12/2008 Nguyên lý Hệ điều hành 12 Hàng đợi sẵn sàng và các hàng đợi thiết bị khác nhau 3/12/2008 Nguyên lý Hệ điều hành 13 Biểu diễn việc lập lịch tiến trình - Biểu đồ hàng đợi 3/12/2008 Nguyên lý Hệ điều hành 14 Vòng đời của một tiến trình ‰ Khởi tạo: hàng đợi sẵn sàng ‰ Các sự kiện có thể xảy ra khi tiến trình đã được gán CPU „ Sinh ra một yêu cầu I/O, đi vào hàng đợi I/O „ Tạo ra một tiến trình con và đợi cho nó kết thúc „ Bị tước quyền sử dụng CPU ‰ Tiếp tục vòng lặp đến khi kết thúc „ Bị xóa khỏi tất cả các hàng đợi „ PCB và tất cả các tài nguyên bị thu hồi. 3/12/2008 Nguyên lý Hệ điều hành 15 Các bộ lập lịch „ Tiến trình lưu trú trong nhiều loại hàng đợi ‰ Các bộ lập lịch chọn các tiến trình từ các hàng đợi 3/12/2008 Nguyên lý Hệ điều hành 16 Các bộ lập lịch (tt) „ Bộ lập lịch dài hạn ‰ Lập lịch công việc – job scheduler ‰ Chọn các tiến trình trong tập tiến trình và tải nó vào bộ nhớ để thực hiện. „ Bộ lập lịch ngắn hạn (lập lịch CPU) ‰ Chọn trong số các tiến trình trong hàng đợi sẵn sàng để thực hiện. 3/12/2008 Nguyên lý Hệ điều hành 17 Bộ lập lịch ngắn hạn vs. dài hạn „ Tần số thực thi ‰ Ngắn hạn: „ Thường xuyên „ Đòi hỏi thực thi nhanh ‰ Dài hạn: „ Không thường xuyên bằng „ Thể hiện mức độ “đa chương trình” 3/12/2008 Nguyên lý Hệ điều hành 18 Bộ lập lịch dài hạn „ Hai loại tiến trình: ‰ Giới hạn I/O ‰ Giới hạn CPU „ Chọn một kết hợp tốt các tiến trình giới hạn vào/ra và các tiến trình giới hạn CPU. „ Một số hệ thống phân chia thời gian không có bộ lập lịch dài hạn (Unix) 3/12/2008 Nguyên lý Hệ điều hành 19 Bộ lập lịch trung hạn „ Sử dụng trong một số HĐH phân chia thời gian 3/12/2008 Nguyên lý Hệ điều hành 20 Chuyển đổi ngữ cảnh „ Chuyển đổi CPU cho một tiến trình khác ‰ Ngữ cảnh tiến trình „ Hoạt động chuyển đổi ngữ cảnh ‰ Kernel lưu lại ngữ cảnh của tiến trình cũ trong PCB và tải ngữ cảnh được lưu của tiến trình mới được lập lịch 3/12/2008 Nguyên lý Hệ điều hành 21 Chuyển đổi ngữ cảnh (tt) „ Thời gian chuyển đổi ngữ cảnh: lãng phí ‰ Phụ thuộc vào máy, thông thường từ 1 đến 1000 micro giây ‰ Phụ thuộc vào sự hỗ trợ của phần cứng ‰ Các kĩ thuật quản lý bộ nhớ ‰ Bottleneck Æ sử dụng các cấu trúc mới như thread để tránh nút cổ chai này 3/12/2008 Nguyên lý Hệ điều hành 22 1.3. Các thao tác trên tiến trình „ Tạo tiến trình „ Hủy tiến trình 3/12/2008 Nguyên lý Hệ điều hành 23 Tạo tiến trình „ Một tiến trình có thể tạo ra nhiều tiến trình con, qua lời gọi hệ thống create_process ‰ Tiến trình cha ‰ Tiến trình con 3/12/2008 Nguyên lý Hệ điều hành 24 Cây tiến trình 3/12/2008 Nguyên lý Hệ điều hành 25 Tạo tiến trình(tt) „ Chia sẻ tài nguyên ‰ Tất cả các tài nguyên ‰ Một phần tài nguyên ‰ Không chia sẻ tài nguyên „ Thực thi ‰ Thực thi đồng thời ‰ Tiến trình tuần tự 3/12/2008 Nguyên lý Hệ điều hành 26 Tạo tiến trình trong Unix „ Mỗi tiến trình có một ID (PID) „ Gọi lời gọi hệ thống fork() để tạo tiến trình mới ‰ Tiến trình cha có thể đợi hoặc thực hiện đồng thời với tiến trình con ‰ Không gian địa chỉ của tiến trình con là một BẢN SAO của không gian địa chỉ tiến trình cha ‰ Mã trả về từ fork() ‰ Tiến trình con có thể gọi lời gọi hệ thống execlp() để tải một chương trình mới vào thực hiện 3/12/2008 Nguyên lý Hệ điều hành 27 3/12/2008 Nguyên lý Hệ điều hành 28 Hủy tiến trình „ Tiến trình thực thi xong ‰ HĐH thực hiện lệnh exit ‰ (có thể) trả về dữ liệu cho tiến trình cha ‰ Hủy các tài nguyên đã được phân phối cho tiến trình „ Tiến trình bị hủy bởi một tiến trình khác (tiến trình cha) ‰ Tiến trình cha cần biết chỉ số của tiến trình con 3/12/2008 Nguyên lý Hệ điều hành 29 Hủy tiến trình (tt) „ Tiến trình cha dừng sự hoạt động của tiến trình con vì ‰ Tiến trình con dùng quá tài nguyên cho phép ‰ Nhiệm vụ của tiến trình con không còn quan trọng ‰ Tiến trình cha thoát và HĐH thực thi cơ chế “hủy theo dây chuyền”(cascading termination) „ Không thực hiện cơ chế hủy theo dây chuyền, tiến trình init thành tiến trình cha 3/12/2008 Nguyên lý Hệ điều hành 30 1.4. Hợp tác giữa các tiến trình „ Các tiến trình cộng tác ‰ Tiến trình độc lập „ Không bị ảnh hưởng bởi tiến trình khác „ Không chia sẻ dữ liệu ‰ Tiến trình hợp tác „ Bị ảnh hưởng bởi tiến trình khác „ Dùng chung dữ liệu „ Cần các kĩ thuật giao tiếp/ đồng bộ tiến trình 3/12/2008 Nguyên lý Hệ điều hành 31 Vì sao hợp tác tiến trình? „ Chia sẻ thông tin ‰ Đồng thời truy cập đến tài nguyên chia sẻ „ Tăng tốc độ tính toán ‰ Chia thành các bài toán con, thực thi song song ‰ Chỉ có được trong các hệ thống có nhiều thành phần xử lý (đa CPU, đa kênh vào/ra) „ Tính module hóa: Chia nhỏ các chức năng „ Tiện dụng ‰ Có thể thực hiện nhiều nhiệm vụ tại một thời điểm 3/12/2008 Nguyên lý Hệ điều hành 32 Bài toán “Producer - Consumer” (1) „ Nhà sản xuất (producer) ‰ Sinh sản phẩm (thông tin) „ Người tiêu dùng (consumer) ‰ Dùng thông tin do Nhà sản xuất sinh ra „ Bộ đệm chung ‰ Không giới hạn ‰ Giới hạn ‰ Hỗ trợ bởi hệ điều hành (thông qua IPC) ‰ Do lập trình viên tạo ra bằng cách sử dụng bộ nhớ chia sẻ 3/12/2008 Nguyên lý Hệ điều hành 33 Bài toán Producer – Consumer(2) „ Các biến chia sẻ 3/12/2008 Nguyên lý Hệ điều hành 34 Bài toán Producer – Consumer (3) „ Mã cho Producer 3/12/2008 Nguyên lý Hệ điều hành 35 Bài toán Producer – Consumer (4) „ Mã lệnh cho Consumer 3/12/2008 Nguyên lý Hệ điều hành 36 1.5. Truyền thông giữa các tiến trình „ Các tiến trình có thể giao tiếp thông qua tính năng truyền thông giữa các tiến trình (IPC) của HĐH „ IPC cho phép các tiến trình không gian địa chỉ giao tiếp và đồng bộ „ Hệ thống truyền thông báo 3/12/2008 Nguyên lý Hệ điều hành 37 Hệ thống truyền thông báo (1) „ Giao tiếp giữa các tiến trình người dùng không cần chia sẻ dữ liệu mà thông qua việc truyền thông báo „ Hai thao tác chính ‰ Gửi ‰ Nhận 3/12/2008 Nguyên lý Hệ điều hành 38 Hệ thống truyền thông báo (2) „ Thông báo ‰ Kích thước cố định ‰ Kích thước thay đổi „ Hai tiến trình P & Q truyền thông bằng cách gửi và nhận thông báo ‰ Tạo thành một kết nối truyền thông 3/12/2008 Nguyên lý Hệ điều hành 39 Hệ thống truyền thông báo (3) „ Các phương pháp để thiết lập liên kết và các thao tác gửi/nhận ‰ Truyền thông trực tiếp/ gián tiếp ‰ Truyền thông đối xứng/ bất đối xứng ‰ Gửi bản sao hay gửi tham chiếu ‰ Các thông điệp kích thước cố định hoặc thay đổi 3/12/2008 Nguyên lý Hệ điều hành 40 Định danh Các tiến trình muốn giao tiếp với nhau cần có một cách thức để tham chiếu đến nhau! 3/12/2008 Nguyên lý Hệ điều hành 41 Truyền thông trực tiếp (1) „ Phải khai báo tên của người nhận/gửi trong khi giao tiếp ‰ send (P, message) ‰ receive (Q, message) „ Tính chất ‰ Tự động thiết lập liên kết khi cần giao tiếp ‰ Mỗi liên kết có đúng hai tiến trình ‰ Có đúng một liên kết giữa bất kì 2 cặp tiến trình 3/12/2008 Nguyên lý Hệ điều hành 42 Truyền thông trực tiếp (2) „ Hệ thống vừa xét: đối xứng địa chỉ „ Hệ thống bất đối xứng địa chỉ ‰ Chỉ có người gửi định danh người nhận ‰ Người nhận không cần định danh người gửi „ Send(P, message) „ Receive(id, message) ‰ Thay đổi tên một tiến trìnhÆ duyệt lại toàn bộ các tiến trình 3/12/2008 Nguyên lý Hệ điều hành 43 Truyền thông gián tiếp (1) „ Gửi và nhận thông qua hòm thư hoặc cổng „ Mỗi hòm thư có một số định danh „ Các thao tác gửi/nhận ‰ Send(A, message) – A là hòm thư ‰ Receive(A, message) – nhận một thông báo từ hòm thư A 3/12/2008 Nguyên lý Hệ điều hành 44 Truyền thông gián tiếp (2) „ Tính chất ‰ Một liên kết được thiết lập giữa hai tiến trình chỉ khi cả hai là thành viên của một hòm thư ‰ Một liên kết có thể có nhiều hơn hai tiến trình ‰ Giữa hai tiến trình có thể có nhiều liên kết 3/12/2008 Nguyên lý Hệ điều hành 45 Đồng bộ hóa „ Truyền thông báo có thể là phong tỏa hay không phong tỏa(đồng bộ hoặc không đồng bộ) ‰ Phong tỏa gửi ‰ Không phong tỏa gửi ‰ Phong tỏa nhận ‰ Không phong tỏa nhận 3/12/2008 Nguyên lý Hệ điều hành 46 Lưu trữ bộ đệm „ Hàng đợi tạm: các cách thiết kế ‰ Zero capacity ‰ Bounded capacity ‰ Unbounded capacity 3/12/2008 Nguyên lý Hệ điều hành 47 1.6. Luồng „ Tại sao đa luồng? ‰ Trình duyệt Web „ Hiển thị ảnh, hoặc văn bản „ Nhận dữ liệu từ mạng ‰ Trình word „ Hiển thị văn bản „ Đọc kí tự từ người dùng „ Thực hiện kiểm tra ngữ pháp và chính tả ngầm 3/12/2008 Nguyên lý Hệ điều hành 48 Tiến trình đơn luồng và tiến trình đa luồng 3/12/2008 Nguyên lý Hệ điều hành 49 Tại sao đa luồng? (2) „ Một ứng dụng đơn cần thực hiện một số nhiệm vụ tương tự đồng thời ‰ Ví dụ: Máy chủ web „ Giải pháp đa tiến trình trước đây ‰ Nặng nề hơn ‰ Lãng phí do các tiến trình cùng thực hiện một số nhiệm vụ tương tự 3/12/2008 Nguyên lý Hệ điều hành 50 Lợi ích „ Tính đáp ứng „ Chia sẻ tài nguyên „ Kinh tế ‰ Phân phối tài nguyên và bộ nhớ cho tiến trình tốn kém „ Tận dụng các kiến trúc đa xử lý 3/12/2008 Nguyên lý Hệ điều hành 51 Luồng mức người dùng (User-Thread) „ Quản lý luồng được thực hiện bởi thư viện luồng ở mức người dùng „ Examples - POSIX Pthreads - Mach C-threads - Solaris threads 3/12/2008 Nguyên lý Hệ điều hành 52 Luồng mức nhân „ Hỗ trợ trực tiếp bởi hệ điều hành „ Examples - Windows 95/98/NT/2000 - Solaris - Tru64 UNIX - BeOS - Linux 3/12/2008 Nguyên lý Hệ điều hành 53 Các mô hình đa luồng „ Mô hình Many-to-One „ Mô hình One-to-One „ Mô hình Many-to-Many 3/12/2008 Nguyên lý Hệ điều hành 54 Mô hình Many-to-One 3/12/2008 Nguyên lý Hệ điều hành 55 Mô hình One-to-One 3/12/2008 Nguyên lý Hệ điều hành 56 Mô hình Many-to-Many 3/12/2008 Nguyên lý Hệ điều hành 57 Pthreads „ Chuẩn Posix (IEEE 1003.1c), API cho việc tạo và đồng bộ tiến trình „ API xác định giao diện của thư viện,thực thi tùy thuộc vào cài đặt thư viện. „ Phổ biến trong dòng hệ điều hành Unix. 3/12/2008 Nguyên lý Hệ điều hành 58 3/12/2008 Nguyên lý Hệ điều hành 59 2. Lập lịch CPU „ Các khái niệm cơ bản „ Điều kiện lập lịch „ Các thuật toán lập lịch 3/12/2008 Nguyên lý Hệ điều hành 60 2.1. Các khái niệm cơ bản „ Tận dụng tối đa CPU trong đa chương trình „ Chu kỳ của các CPU-I/O burst – Việc thực thi tiến trình là một chu kì của các thực thi bởi CPU và chờ đợi vào ra „ Phân phối CPU burst 3/12/2008 Nguyên lý Hệ điều hành 61 Luân phiên giữa các CPU và I/O burst 3/12/2008 Nguyên lý Hệ điều hành 62 Biểu đồ tần suất của các CPU burst theo thời gian 3/12/2008 Nguyên lý Hệ điều hành 63 Bộ lập lịch CPU „ Chọn trong số các tiến trình trong bộ nhớ trong và ở trạng thái ready để thực hiện (trao quyền sử dụng CPU cho tiến trình đó) „ Việc lập lịch có thể được thực hiện trong một số trường hợp 1. Tiến trình trạng thái running chuyển sang waiting 2. Tiến trình trạng thái running chuyển sang trạng thái ready 3. Có một tiến trình ở trạng thái waiting chuyển sang trạng thái ready 4. Tiến trình hiện tại kết thúc thực thi „ Lập lịch trong chỉ trong các trường hợp 1 và 4 gọi là lập lịch không chiếm đoạt (hay còn gọi là cộng tác) „ Các trường hợp còn lại gọi là lập lịch chiếm đoạt 3/12/2008 Nguyên lý Hệ điều hành 64 Bộ điều vận „ Bộ điều vận có nhiệm vụ chuyển điều khiển CPU cho tiến trình được lựa chọn bởi bộ lập lịch ngắn hạn „ Chức năng của bộ điều vận bao gồm ‰ Chuyển đổi ngữ cảnh ‰ Chuyển sang user mode ‰ Chuyển điều khiển đến một vị trí xác định trong chương trình người dùng để khởi động lại chương trình „ Độ trễ điều vận ‰ Thời gian dừng một tiến trình để bắt đầu thực thi tiến trình khác 3/12/2008 Nguyên lý Hệ điều hành 65 2.2. Điều kiện lập lịch „ Tính tận dụng CPU ‰ Thông thường từ 40-90% „ Thông lượng „ Thời gian quay vòng (turnaround time) „ Thời gian chờ „ Thời gian phản ứng 3/12/2008 Nguyên lý Hệ điều hành 66 Vấn đề tối ưu các điều kiện „ Cực đại hóa tính tận dụng CPU „ Cực đại hóa thông lượng „ Cực tiểu hóa thời gian quay vòng „ Cực tiểu hóa thời gian đợi „ Cực tiểu hóa thời gian phản ứng 3/12/2008 Nguyên lý Hệ điều hành 67 2.3. Các thuật toán lập lịch „ Đến trước – Phục vụ trước (FCFS) „ Công việc ngắn nhất trước (SJF) „ Lập lịch với độ ưu tiên „ Lập lịch Round-Robin(RR) „ Lập lịch đa hàng đợi „ Lập lịch với hàng đợi phản hồi 3/12/2008 Nguyên lý Hệ điều hành 68 “Đến trước – Phục vụ trước” (FCFS) „ Ba tiến trình đến theo thứ tự là P1, P2, P3 ‰ Thời gian thực hiện của P1, P2 và P3 lần lượt là 24, 3 và 3 „ Biểu đồ Gantt trong lập lịch FCFS „ Thời gian chờ của P1 = 0; P2= 24; P3 = 27 „ Thời gian chờ trung bình: (0 + 24 + 27)/3= 17 P1 P2 P3 24 27 300 3/12/2008 Nguyên lý Hệ điều hành 69 “Đến trước – Phục vụ trước” (FCFS) (tt) „ Nếu các tiến trình đến theo thứ tự P2, P3, P1 „ Biểu đồ Gantt cho lập lịch „ Thời gian chờ của P1 = 6; P2 = 0; P3 = 3 „ Thời gian chờ trung bình: (6 + 0 + 3)/3 = 3 „ Tốt hơn nhiều so với trường hợp trên „ Convoy effect P1P3P2 63 300 3/12/2008 Nguyên lý Hệ điều hành 70 Công việc ngắn nhất trước (SJF) „ Liên kết mỗi tiến trình độ dài của “CPU burst” tiếp theo. Sử dụng độ dài này để lập lịch tiến trình với thời gian ngắn nhất. „ Hai dạng ‰ Không chiếm đoạt – Một khi CPU đã được gán cho tiến trình, CPU không thể bị chiếm đoạt bởi một tiến trình nào khác. ‰ Chiếm đoạt – Nếu một tiến trình mới đến với độ dài CPU burst nhỏ hơn thời gian thực thi còn lại của tiến trình sở hữu CPU, tiến trình mới được chiếm hữa CPU – Dạng “Thời gian còn lại ngắn nhất trước” (SRJF) „ SJF tối ưu thời gian chờ 3/12/2008 Nguyên lý Hệ điều hành 71 SJF không chiếm đoạt: Ví dụ „ SJF (không chiếm đoạt) „ Thời gian chờ trung bình:(0 + 6 + 3 + 7)/4 = 4 P1 P3 P2 73 160 P4 8 12 3/12/2008 Nguyên lý Hệ điều hành 72 SJF chiếm đoạt: Ví dụ „ SJF (chiếm đoạt) „ Thời gian chờ trung bình= (9 + 1 + 0 + 2)/4=3 P1 P3P2 42 110 P4 5 7 P2 P1 16 3/12/2008 Nguyên lý Hệ điều hành 73 Xác định độ dài của CPU burst tiếp theo „ Ước lượng độ dài nhờ độ dài của các CPU burst trước đó :Define 4. 10 , 3. burst CPU next the for value predicted 2. burst CPU of lenght actual 1. 1 ≤≤ = = + αα τ n th n nt ( ) .11 nnn t ταατ −+== 3/12/2008 Nguyên lý Hệ điều hành 74 Xác định độ dài của CPU burst tiếp theo 3/12/2008 Nguyên lý Hệ điều hành 75 Lập lịch với độ ưu tiên „ Mỗi tiến trình liên kết với một độ ưu tiên (số nguyên) xác định „ CPU được phân phối cho tiến trình với độ ưu tiên cao nhất (giá trị độ ưu tiến nhỏ nhất) ‰ Chiếm đoạt ‰ Không chiếm đoạt „ SJF là lập lịch với độ ưu tiên trong đó độ ưu tiên chính là khoảng CPU burst tiếp theo „ Vấn đề: “Chết đói” – Những tiến trình với độ ưu tiên thấp có thể sẽ không bao giờ được gán CPU ‰ Giải pháp: các tiến trình tăng độ ưu tiên theo thời gian 3/12/2008 Nguyên lý Hệ điều hành 76 Round Robin (RR) „ Mỗi tiến trình được gán một lượng tử thời gian (thường từ 10 – 100 mili giây) „ Hết lượng tử thời gian, tiến trình hiện tại bị tước CPU và đặt vào hàng đợi sẵn sàng „ Hiệu năng ‰ FIFO ‰ Q phải đủ lớn so với thời gian chuyển giao ngữ cảnh 3/12/2008 Nguyên lý Hệ điều hành 77 Ví dụ: RR với lượng tử thời gian = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 „ Biểu đồ Gantt: RR có thời gian quay vòng trung bình cap hơn SJF nhưng có tính phản ứng tốt hơn P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 3/12/2008 Nguyên lý Hệ điều hành 78 Thời gian lượng tử và thời gian chuyển đổi ngữ cảnh 3/12/2008 Nguyên lý Hệ điều hành 79 Biến đổi thời gian quay vòng theo thời gian lượng tử 3/12/2008 Nguyên lý Hệ điều hành 80 Lập lịch với Hàng đợi nhiều mức „ Sử dụng nhiều hơn một hàng đợi sẵn sàng ‰ Ví dụ: hàng đợi nền trước (foreground queue) cho các chương trình tương tác, hàng đợi nền sau (background) cho các chương trình duy trì hệ thống, các chương trình theo lô „ Sử dụng các thuật toán lập lịch khác nhau cho các hàng đợi ‰ Ví dụ: RR cho hàng đợi nền trước, FCFS „ Chia thời gian cho các hàng đợi ‰ Ví dụ: 80% thời gian cho hàng đợi nền trước, 20% cho nền sau 3/12/2008 Nguyên lý Hệ điều hành 81 Hàng đợi nhiều mức 3/12/2008 Nguyên lý Hệ điều hành 82 Hàng đợi nhiều mức phản hồi „ Không cố định tiến trình trên một hàng đợi „ Ví dụ: các hàng đợi với các độ ưu tiên khác nhau ‰ Các tiến trình gắn với Vào/Ra ở hàng đợi có độ ưu tiên cao ‰ Chuyển các tiến trình sử dụng CPU đến các hàng đợi có độ ưu tiên thấp ‰ Chuyển các tiến trình phải đợi lâu đều đặn lên phía trên 3/12/2008 Nguyên lý Hệ điều hành 83 Lập lịch các luồng trong Java „ JVM sử dụng thuật toán Preemptive, và dựa trên độ ưu tiên trong lập lịch „ Hàng đợi FIFO được sử dụng nếu có nhiều luồng cùng mức ưu tiên 3/12/2008 Nguyên lý Hệ điều hành 84 Lập lịch các luồng trong Java JVM lập lịch khi: 1. Tiến trình đang chạy ra khỏi trạng thái runnable 2. Một tiến trình có độ ưu tiên cao hơn vào trạng thái runnable 3/12/2008 Nguyên lý Hệ điều hành 85 Time-Slicing Do JVM không hỗ trợ cắt thời gian (Time- Slicing), hàm yield() có thể được sử dụng: while (true) { // perform CPU-intensive task . . . Thread.yield(); } Thread.yield()chuyển điều khiển cho luồng khác 3/12/2008 Nguyên lý Hệ điều hành 86 Các độ ưu tiên của luồng Priority Ý nghĩa Thread.MIN_PRIORITY Nhỏ nhất Thread.MAX_PRIORITY Lớn nhất Thread.NORM_PRIORITY Ngầm định Phương thức setPriority() setPriority(Thread.NORM_PRIORIT Y + 2) 3/12/2008 Nguyên lý Hệ điều hành 87 Nội dung đã học „ Lý do lập lịch „ Các dạng lập lịch ‰ FCFS ‰ SJF ‰ RR ‰ MFQ „ Lập lịch trong Java 3/12/2008 Nguyên lý Hệ điều hành 88 3. Đồng bộ hóa tiến trình „ Nền tảng „ Vấn đề “Đoạn tới hạn” „ Giải pháp của Peterson „ Đồng bộ nhờ phần cứng „ Semaphores „ 3 bài toán đồng bộ điển hình „ Monitors 3/12/2008 Nguyên lý Hệ điều hành 89 3.1. Nền tảng „ Truy nhập đồng thời đến dữ liệu chia sẻ có thể gây ra sự không nhất quán về dữ liệu ÆCần các kĩ thuật để việc thực thi tuần tự của các tiến trình cộng tác „ Vấn đề cộng tác tiến trình (phần 1) ‰ Bài toán “Sản xuất – Tiêu dùng” ‰ Bộ nhớ chia sẻ (có giới hạn) ‰ Biến count lưu số các items trong buffer 3/12/2008 Nguyên lý Hệ điều hành 90 Mã nguồn cho Producer và Consumer „ Producer while (true) { //produce an item while (count == BUFFER_SIZE); // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++; } „ Consumer while (1) { while (count == 0) ; // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /*consume the item in } 3/12/2008 Nguyên lý Hệ điều hành 91 Chạy đua „ count++ có thể được thực hiện như sau register1 = count register1 = register1 + 1 count = register1 „ count– có thể được thực hiện như sau register2 = count register2 = register2 - 1 count = register2 „ Giả sử ban đầu “count = 5”: S0: producer thực thi register1 = count {register1 = 5} S1: producer thực thi register1 = register1 + 1 {register1 = 6} S2: consumer thực thi register2 = count {register2 = 5} S3: consumer thực thi register2 = register2 - 1 {register2 = 4} S4: producer thực thi count = register1 {count = 6 } S5: consumer thực thi count = register2 {count = 4} 3/12/2008 Nguyên lý Hệ điều hành 92 Chạy đua „ Chạy đua: Tình huống nhiều tiến trình cùng truy cập và xử lý dữ liệu dùng chung đồng thời. Giá trị cuối cùng của dữ liệu phụ thuộc vào tiến trình sẽ kết thúc cuối. „ Để tránh việc chạy đua, các tiến trình đồng thời cần phải được đồng bộ hóa 3/12/2008 Nguyên lý Hệ điều hành 93 3.2. Vấn đề đoạn tới hạn „ n tiến trình cùng muốn truy cập đến dữ liệu chia sẻ „ Mỗi tiến trình có một đoạn mã gọi là “đoạn tới hạn”, trong “đoạn tới hạn”dữ liệu chia sẻ mới được truy cập tới. „ Vấn đề - đảm bảo rằng khi một tiến trình đang trong đoạn tới hạn của nó, các tiến trình khác không được phép thực thi đoạn tới hạn của chúng. 3/12/2008 Nguyên lý Hệ điều hành 94 Giải pháp cho vấn đề “đoạn tới hạn” 1. Loại trừ lẫn nhau. Nếu tiến trình Pi đang trong đoạn tới hạn, không tiến trình nào khác được phép ở trong đoạn tới hạn. 2. Phát triển. Nếu không tiến trình nào ở trong đoạn tới hạn và có một số tiến trình muốn vào đoạn tới hạn, việc lựa chọn một tiến trình vào đoạn tới hạn sẽ không bị trì hoãn mãi. 3. Chờ đợi có cận. Phải có một cận về số lần mà các tiến trình khác được phép vào đoạn tới hạn sau khi một tiến trình đã yêu cầu vào đoạn tới hạn và trước khi yêu cầu đó được đáp ứng. y Giả thiết rằng mỗi tiến trình thực thi với tốc độ khác không y Không có giả thiết về mối tương quan tốc độ của n tiến trình. 3/12/2008 Nguyên lý Hệ điều hành 95 3.3. Giải pháp của Peterson „ Giải pháp đồng bộ cho hai tiến trình „ Giả sử hai lệnh LOAD và STORE là các lệnh nguyên tử (thao tác không thể phân chia) „ Các tiến trình chia sẻ các biến sau: ‰ int turn; ‰ Boolean flag[2] „ Biến turn cho biết tiến trình nào được vào đoạn tới hạn. „ Mảng flag chỉ xem liệu một tiến trình có sẵn sàng vào đoạn tới hạn hay không. ‰ flag[i] = true là tiến trình Pi sẵn sàng vào đoạn tới hạn! 3/12/2008 Nguyên lý Hệ điều hành 96 Thuật toán cho tiến trình Pi do { flag[i] = TRUE; turn = j; while ( flag[j] && turn == j); CRITICAL SECTION flag[i] = FALSE; REMAINDER SECTION } while (TRUE); 3/12/2008 Nguyên lý Hệ điều hành 97 3.4. Đồng bộ hóa nhờ phần cứng „ Nhiều hệ thống cung cấp sự hỗ trợ của phần cứng cho vấn đề đoạn tới hạn „ Các hệ đơn xử lý – có thể bỏ chức năng ngắt ‰ Mã được thực thi mà không có sự chiếm đoạt ‰ Thông thường không hiệu quả trên các hệ thống đa xử lý „ Các hệ điều hành với chiến lược này thường không khả cỡ „ Các máy tính hiện đại cung cấp các lệnh phần cứng nguyên tử „ Nguyên tử = không phân chia ‰ Kiểm tra từ nhớ và thiết lập giá trị ‰ Tráo đổi nội dung của hai từ nhớ 3/12/2008 Nguyên lý Hệ điều hành 98 Lệnh TestAndSet „ Định nghĩa: boolean TestAndSet (boolean *target) { boolean rv = *target; *target = TRUE; return rv: } 3/12/2008 Nguyên lý Hệ điều hành 99 Giải pháp dùng TestAndSet „ Biến chia sẻ lock, được khởi tạo bằng false „ Giải pháp: do { while ( TestAndSet (&lock )) ; /* do nothing // critical section lock = FALSE; // remainder section } while ( TRUE); 3/12/2008 Nguyên lý Hệ điều hành 100 Lệnh Swap „ Định nghĩa: void Swap (boolean *a, boolean *b) { boolean temp = *a; *a = *b; *b = temp: } 3/12/2008 Nguyên lý Hệ điều hành 101 Giải pháp dùng Swap „ Biến chia sẻ lock, được khởi tạo bằng false; mỗi tiến trình có một biến Boolean cục bộ „ Giải pháp: do { key = TRUE; while ( key == TRUE) Swap (&lock, &key ); // critical section lock = FALSE; // remainder section } while ( TRUE); 3/12/2008 Nguyên lý Hệ điều hành 102 3.5. Semaphores „ Công cụ đồng bộ không đòi hỏi “chờ-bận” „ Semaphore S – biến nguyên „ Hai thao tác “nguyên tử” để sửa đổi S: wait (S) { while S <= 0; // no-op S--; } signal (S) { S++; } 3/12/2008 Nguyên lý Hệ điều hành 103 Semaphore – Công cụ đồng bộ tổng quát „ Hai loại semaphore ‰ Semaphore đếm „ Giá trị của semaphore là số các tài nguyên available ‰ Semaphore nhị phân „ Semaphore chỉ nhận hai giá trị 0 và 1 „ Còn được gọi là mutex lock „ Loại trừ lẫn nhau dùng semaphore ‰ Semaphore S; // initialized to 1 ‰ wait (S); Critical Section signal (S); 3/12/2008 Nguyên lý Hệ điều hành 104 Cài đặt Semaphore „ Cần đảm bảo rằng không có hai tiến trình nào có thể cùng thực thi wait() và signal() trên cùng 1 semaphore tại cùng 1 thời điểm „ Thực thi semaphore bản thân nó cũng là bài toán đoạn tới hạn ‰ Mã cho wait() và signal() được đặt trong đoạn tới hạn ‰ Có thể cài đặt cơ chế “chờ-bận” hoặc không „ Chờ-bận ‰ Mã nguồn đơn giản ‰ Chấp nhận được trong TH đoạn tới hạn ít khi được truy nhập tới 3/12/2008 Nguyên lý Hệ điều hành 105 Cài đặt Semaphore không chờ-bận „ Mỗi semaphore liên kết với một hàng đợi. Mỗi phần tử của hàng đợi có hai phần ‰ Giá trị (kiểu nguyên) ‰ Con trỏ đến bản ghi tiếp theo trong danh sách „ Hai thao tác: ‰ Block – đặt tiến trình gọi thao tác này vào hàng đợi semaphore. ‰ Wakeup – gỡ bỏ một trong số các tiến trình trong hàng đợi và đặt nó vào hàng đợi sẵn sàng 3/12/2008 Nguyên lý Hệ điều hành 106 Cài đặt Semaphore không chờ-bận „ Implementation of wait: Wait (S) { value--; if (value < 0) { //add this process to waiting //queue block(); } „ Implementation of signal: Signal (S) { value++; if (value <= 0) { //remove a process P from //the waiting queue wakeup(P); } 3/12/2008 Nguyên lý Hệ điều hành 107 Bế tắc và Chết đói „ Bế tắc – hai hay nhiều tiến trình chờ vô hạn trên một sự kiện gây ra bởi một trong các tiến trình đang chờ „ S và Q là hai semaphores được khởi tạo bằng 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S); . . . . . . signal (S); signal (Q); signal (Q); signal (S); „ Chết đói – bị block vô hạn. Một tiến trình có thể bị gỡ khỏi hàng đợi của semaphore. 3/12/2008 Nguyên lý Hệ điều hành 108 3.6. Các bài toán đồng bộ kinh điển „ Bộ đệm giới hạn „ Bài toán đọc và ghi „ Bài toán “bữa ăn của các triết gia” 3/12/2008 Nguyên lý Hệ điều hành 109 Bài toán “Bộ đệm giới hạn” „ N bộ đệm, mỗi bộ đệm có item „ Semaphore mutex được khởi tạo bằng 1 „ Semaphore full được khởi tạo bằng 0 „ Semaphore empty được khởi tạo bằng N. 3/12/2008 Nguyên lý Hệ điều hành 110 Bài toán “Bộ đệm giới hạn” „ Tiến trình “producer” do { // produce an item wait (empty); wait (mutex); // add the item to the buffer signal (mutex); signal (full); } while (true); „ Tiến trình “consumer” do { wait (full); wait (mutex); // remove an item from buffer signal (mutex); signal (empty); // consume the removed item } while (true); 3/12/2008 Nguyên lý Hệ điều hành 111 Bài toán “Đọc-ghi” „ Một tập dữ liệu được chia sẻ giữa một số tiến trình đồng thời ‰ Reader – chỉ đọc dữ liệu; không thực hiện bất kì một thao tác cập nhật. ‰ Writers – có thể vừa đọc vừa ghi. „ Vấn đề ‰ Cho phép nhiều reader đọc cùng một thời điểm. Chỉ có một writer có thể truy nhập đến dữ liệu chia sẻ tại cùng một thời điểm. „ Dữ liệu chia sẻ ‰ Tập dữ liệu ‰ Semaphore mutex được khởi tạo bằng 1. ‰ Semaphore wrt được khởi tạo bằng 1. ‰ Số nguyên readcount được khởi tạo bằng 0. 3/12/2008 Nguyên lý Hệ điều hành 112 Bài toán “Đọc-ghi” „ Tiến trình ghi (writer) do { wait (wrt) ; // writing is performed signal (wrt) ; } while (true) „ Tiến trình đọc (reader) do { wait (mutex) ; readcount ++ ; if (readercount == 1) wait (wrt) ; signal (mutex) // reading is performed wait (mutex) ; readcount - - ; if redacount == 0) signal (wrt) ; signal (mutex) ; } while (true) 3/12/2008 Nguyên lý Hệ điều hành 113 Bài toán “Bữa ăn của các triết gia” „ Dữ liệu chia sẻ ‰ Cơm (tập dữ liệu) ‰ Semaphore chopstick [5] được khởi tạo bằng 1 3/12/2008 Nguyên lý Hệ điều hành 114 Bài toán “Bữa ăn của các triết gia” „ Mã lệnh cho Triết gia thứ I Do { wait ( chopstick[i] ); wait ( chopStick[ (i + 1) % 5] ); // eat signal ( chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); // think } while (true) ; 3/12/2008 Nguyên lý Hệ điều hành 115 Vấn đề của Semaphores „ Không sử dụng đúng các thao tác trên semaphore ‰ signal (mutex) . wait (mutex) ‰ wait (mutex) wait (mutex) ‰ Bỏ qua wait (mutex) hay signal (mutex) (hoặc cả hai) 3/12/2008 Nguyên lý Hệ điều hành 116 3.7. Monitors „ Trừu tượng mức cao cung cấp phương thức hữu hiệu cho đồng bộ tiến trình „ Chỉ có một tiến trình chỉ có thể active trong monitor tại một thời gian monitor monitor-name { // shared variable declarations procedure P1 () { . } procedure Pn () {} Initialization code ( .) { } } } 3/12/2008 Nguyên lý Hệ điều hành 117 Monitor 3/12/2008 Nguyên lý Hệ điều hành 118 Các biến điều kiện „ condition x, y; „ Hai thao tác trên biến điều kiện: ‰ x.wait () – tiến trình gọi thao tác này sẽ bị block. ‰ x.signal () – khôi phục thực thi của một trong số các tiến trình (nếu có) đã gọi thao tác x.wait () 3/12/2008 Nguyên lý Hệ điều hành 119 Monitor với các biến điều kiện 3/12/2008 Nguyên lý Hệ điều hành 120 Giải pháp cho bài toán “Bữa ăn của các triết gia” monitor DP { enum { THINKING; HUNGRY, EATING) state [5] ; condition self [5]; void pickup (int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self [i].wait; } void putdown (int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); } void test (int i) { if ( (state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING ; self[i].signal () ; } } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING; } } 3/12/2008 Nguyên lý Hệ điều hành 121 4. Bế tắc „ Vấn đề “Bế tắc” „ Mô hình hệ thống „ Các đặc điểm của bế tắc „ Các phương pháp xử lý bế tắc „ Ngăn chặn bế tắc „ Tránh bế tắc „ Khôi phục sau bế tắc 3/12/2008 Nguyên lý Hệ điều hành 122 4.1. Vấn đề “Bế tắc” „ Một tập các tiến trình bị block, mỗi tiến trình giữ một tài nguyên và chờ một tài nguyên bị chiếm giữ bởi một tiến trình khác trong tập „ Ví dụ ‰ Một hệ thống có 2 băng từ ‰ P1 và P2 mỗi tiến trình giữ một băng từ và đòi hỏi băng từ được giữ bởi tiến trình kia. „ Ví dụ ‰ semaphores A và B, được khởi tạo bằng 1 P0 P1 wait (A); wait(B) wait (B); wait(A 3/12/2008 Nguyên lý Hệ điều hành 123 4.2. Mô hình hệ thống „ Các kiểu tài nguyên R1, R2, . . ., Rm CPU cycles, memory space, I/O devices „ Mỗi tài nguyên Ri cóWi thể hiện. „ Mỗi tiến trình sử dụng tài nguyên như sau: ‰ request ‰ use ‰ release 3/12/2008 Nguyên lý Hệ điều hành 124 4.3. Các đặc điểm của bế tắc „ Bế tắc có thể xảy ra nếu cả bốn điều kiện sau xảy ra đồng thời ‰ Loại trừ lẫn nhau: chỉ một tiến trình được sử dụng tài nguyên tại một thời điểm. ‰ Giữ và chờ: một tiến trình giữ ít nhất một tài nguyên và chờ các tài nguyên khác đang được giữ bởi các tiến trình khác. ‰ Không chiếm đoạt: một tài nguyên chỉ có thể được giải phóng một cách tự nguyện bởi tiến trình giữ nó, sau khi tiến trình đó hoàn thành công việc của nó. ‰ Chờ đợi vòng tròn: Một tập các tiến trình đang chờ {P0, P1, , Pn} , trong đó P0 chờ một tài nguyên bị giữ bởi P1, P1 chờ một tài nguyên bị giữ bởi P2, , Pn–1chờ một tài nguyên được giữ bởi Pn, và Pn đang chờ một tài nguyên P0. 3/12/2008 Nguyên lý Hệ điều hành 125 Đồ thị phân phối tài nguyên „ Có một tập các đỉnh V và một tập các cạnh E ‰ V được chia thành hai tập: „ P = {P1, P2, , Pn}, tập chứa tất cả các tiến trình trong hệ thống. „ R = {R1, R2, , Rm}, tập chứa tất cả các kiểu tài nguyên trong hệ thống. ‰ Cạnh request – cạnh có hướng P1 → Rj ‰ Cạnh assignment – cạnh có hướng Rj→ Pi 3/12/2008 Nguyên lý Hệ điều hành 126 Đồ thị phân phối tài nguyên „ Tiến trình „ Kiểu tài nguyên với 4 thể hiện „ Pi yêu cầu một thể hiện của Rj „ Pi giữ một thể hiện của Rj Pi Pi Rj Rj 3/12/2008 Nguyên lý Hệ điều hành 127 Ví dụ về một đồ thị phân phối tài nguyên 3/12/2008 Nguyên lý Hệ điều hành 128 Đồ thị phân phối tài nguyên với một bế tắc 3/12/2008 Nguyên lý Hệ điều hành 129 Đồ thị với một chu trình nhưng không có bế tắc 3/12/2008 Nguyên lý Hệ điều hành 130 Tiên đề „ Nếu một đồ thị không có chu trình⇒ không có bế tắc. „ Nếu đồ thị có một chu trình⇒ ‰ Nếu mỗi tài nguyên chỉ có một thể hiện thì xuất hiện bế tắc. ‰ Nếu mỗi loại tài nguyên có một vài thể hiện thì có thể có bế tắc. 3/12/2008 Nguyên lý Hệ điều hành 131 4.4. Các phương pháp xử lý bế tắc „ Đảm bảo hệ thống sẽ không bao giờ đi vào trạng thái bế tắc „ Cho phép hệ thống vào trạng thái bế tắc sau đó khôi phục „ Bỏ qua vấn đề này và xem rằng bế tắc không bao giờ xảy ra trong hệ thống; được sử dụng bởi hầu hết các hệ điều hành, bao gồm cả UNIX. 3/12/2008 Nguyên lý Hệ điều hành 132 4.5. Ngăn chặn bế tắc „ Ràng buộc cách thức yêu cầu tài nguyên của các tiến trình ‰ Loại trừ lẫn nhau – không cần thỏa mãn với các tài nguyên có thể chia sẻ; cần thỏa mãn với các tài nguyên không thể chia sẻ (ví dụ máy in). ‰ Giữ và chờ – phải đảm bảo rằng khi một tiến trình yêu cầu một tài nguyên, nó không được giữ bất kì tài nguyên nào khác. „ Tiến trình phải yêu cầu và được phân phối tất cả các tài nguyên trước khi nó bắt đầu thực thi „ Cho phép tiến trình yêu cầu tài nguyên chỉ khi nó không chiếm hữu tài nguyên nào. „ Tính tận dụng tài nguyên thấp; có thể xảy ra “chết đói”. 3/12/2008 Nguyên lý Hệ điều hành 133 Ngăn chặn bế tắc (2) „ Không chiếm đoạt – ‰ Nếu một tiến trình hiện đang giữ một số tài nguyên nào đó và yêu cầu tài nguyên khác (chưa thể phân phối cho nó ngay lập tức), tất cả các tài nguyên đang bị giữ sẽ được giải phóng. ‰ Các tài nguyên bị chiếm đoạt được thêm vào danh sách các tài nguyên mà tiến trình đó đang chờ. ‰ Tiến trình sẽ bắt đầu thực thi lại chỉ khi nó có thể lấy lại các tài nguyên cũ cũng như chiếm cả tài nguyên mới mà nó đang yêu cầu. „ Chờ đợi vòng tròn – áp đặt một trình tự tổng thể của tất cả các loại tài nguyên, và ràng buộc các tiến trình yêu cầu tài nguyên theo thứ tự tăng dần. 3/12/2008 Nguyên lý Hệ điều hành 134 4.6. Tránh bế tắc „ Yêu cầu hệ thống phải có trước một số thông tin (prior information available). ‰ Mô hình đơn giản: mỗi tiến trình khai báo số tài nguyên lớn nhất thuộc mỗi loại mà nó cần. ‰ Thuật toán tránh bế tắc kiểm tra trạng thái phân phối tài nguyên để đảm bảo rằng không bao giờ có điều kiện “chờ đợi vòng tròn” xảy ra. ‰ Trạng thái phân phối tài nguyên được xác định bằng số các tài nguyên rỗi, số tài nguyên đã được phân phối và số cực đại yêu cầu của các tiến trình. 3/12/2008 Nguyên lý Hệ điều hành 135 Trạng thái an toàn „ Chừng nào một tiến trình yêu cầu một tài nguyên rỗi, cần xác định xem việc phân phối đó có đặt hệ thống vào trạng thái không an toàn không. „ Hệ thống trong trạng thái an toàn nếu tồn tại một “chuỗi an toàn” của tất cả các tiến trình. „ Chuỗi là an toàn đối với mỗi Pi, các tài nguyên mà Pi cần đều có thể phân phối bởi các tài nguyên đang rỗi hoặc các tài nguyên đăng bị chiếm hữu bởi tất cả các tiến trình Pj (với j<i). ‰ Nếu Pi cần tài nguyên không rỗi ngay lập tức, thì Pi có thể đợi cho đến khi tất cả các Pj hoàn thành. ‰ Khi Pj đã hoàn thành, Pi có thể chiếm hữu tài nguyên mà nó âần, thực thi và trả lại tài nguyên đã được phân phối và kết thúc. ‰ Khi Pi kết thức, Pi+1 có thể chiếm hữu tài nguyên mà nó cần. 3/12/2008 Nguyên lý Hệ điều hành 136 Tiên đề „ Nếu một hệ thống trong trạng thái an toàn⇒ không có bế tắc „ Nếu một hệ thống ở trong trạng thái không an toàn⇒ có thể có bế tắc. „ Tránh bế tắc⇒ đảm bảo rằng hệ thống không bao giờ rơi vào trạng thái không an toàn. 3/12/2008 Nguyên lý Hệ điều hành 137 Trạng thái an toàn, không an toàn và bế tắc 3/12/2008 Nguyên lý Hệ điều hành 138 Thuật toán đồ thị phân phối tài nguyên „ Claim Pi→ Rj chỉ rằng một tiến trình Pj có thể yêu cầu tài nguyên Rj; được biểu diễn bởi đường đứt quảng. „ Cạnh Claim được biến đổi thành cạnh request nếu một tiến trình yêu cầu một tài nguyên. „ Khi một tiến trình giải phóng tài nguyên, cạnh assignment được chuyển lại thành cạnh claim. „ Các tài nguyên phải có một độ ưu tiên trong hệ thống. 3/12/2008 Nguyên lý Hệ điều hành 139 Đồ thị phân phối tài nguyên để tránh bế tắc 3/12/2008 Nguyên lý Hệ điều hành 140 Trạng thái không an toàn trong đồ thị phân phối tài nguyên 3/12/2008 Nguyên lý Hệ điều hành 141 Thuật toán Banker „ Các tài nguyên có nhiều thể hiện. „ Mỗi tiến trình khi mới vào hệ thống cần phải khai báo số cực đại tài nguyên mà nó cần. „ Khi một tiến trình yêu cầu tài nguyên, hệ thống kiểm tra xem liệu việc phân phối tài nguyên đó có đảm bảo hệ thống trong trạng thái an toàn hay không ‰ Nếu không, tiến trình có thể phải chờ „ Khi một tiến trình đã được phân phối tài nguyên, nó phải trả lại các tài nguyên này trong một thời gian xác định. 3/12/2008 Nguyên lý Hệ điều hành 142 Cấu trúc dữ liệu cho thuật toán Banker „ Gọi n = số tiến trình, and m = số loại tài nguyên. ‰ Available: vector độ dài m. Nếu available [j] = k, có k thể hiện của tài nguyên Rj rỗi. ‰ Max: n x m matrix. Nếu Max [i,j] = k, tiến trình Pi có thể đòi hỏi nhiều nhất là k thể hiện của loại tài nguyên Rj. ‰ Allocation: n x m matrix. Nếu Allocation[i,j] = k , tiến trình Pi hiện được phân phối k thể hiện của Rj. ‰ Need: n x m matrix. Nếu Need[i,j] = k, tiến trình Pi có thể cần thêm k thể hiện của Rj để hoàn thành nhiệm vụ của nó. Need [i,j] = Max[i,j] – Allocation [i,j]. 3/12/2008 Nguyên lý Hệ điều hành 143 Thuật toán Safety 1. Gọi Work and Finish là các vectors có độ dài lần lượt là m và n. Khởi tạo: Work = Available Finish [i] = false for i - 1,3, , n. 2. Tìm i thỏa mãn hai điều kiện sau: (a) Finish [i] = false (b) Needi ≤ Work Nếu không tìm được i, nhảy đến bước 4. 3. Work = Work + Allocationi Finish[i] = true Nhảy đến bước 2. 4. Nếu Finish [i] == true với tất cả i, hệ thống trong trạng thái an toàn. 3/12/2008 Nguyên lý Hệ điều hành 144 Thuật toán phân phối yêu cầu tài nguyên cho tiến trình Pi Request = vector yêu cầu của Pi . Nếu Requesti [j] = k, Pi cần k thể hiện của Rj. 1. Nếu Requesti ≤ Needi nhảy đến bước 2. Nếu không, lỗi (tiến trình cần nhiều hơn số yêu cầu khai báo ban đầu). 2. Nếu Requesti ≤ Available, nhảy đến bước 3. Nếu không Pi phải chờ vì tất cả tài nguyên đều không rỗi. 3. Thử phân phối tài nguyên được yêu cầu cho Pi bằng cách thay đổi trạng thái như sau: Available = Available - Requesti ; Allocationi = Allocationi + Requesti ; Needi = Needi – Requesti ; z Nếu an toàn⇒ tài nguyên được phân phối cho Pi. z Nếu không an toàn⇒ Pi phải đợi, trạng thái phân phối tài nguyên cũ được khôi phục lại 3/12/2008 Nguyên lý Hệ điều hành 145 Ví dụ về thuật toán Banker „ 5 tiến trình từ P0 đến P4 „ 3 loại tài nguyên A (10 thể hiện), B (5 thể hiện), và C (7 thể hiện). „ Hệ thống tại thời điểm T0: Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 3/12/2008 Nguyên lý Hệ điều hành 146 Ví dụ (Cont.) „ Nội dung của ma trận Need. Need được định nghĩa là Max – Allocation. Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 „ Hệ thống trong trạng thái an toàn vì chuỗi < P1, P3, P4, P2, P0> thỏa mãn điều kiện an toàn. 3/12/2008 Nguyên lý Hệ điều hành 147 Ví dụ: P1 yêu cầu (1,0,2) (Cont.) „ Kiểm tra thấy Request ≤ Available (hay, (1,0,2) ≤ (3,3,2) ⇒ true). Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 „ Thực thi thuật toán safety cho thấy chuỗi <P1, P3, P4, P0, P2> thỏa mãn yêu cần an toàn. „ Yêu cầu (3,3,0) của P4 có thể được gán hay không? „ Yêu cầu (0,2,0) của P0 có thể được gán hay không? 3/12/2008 Nguyên lý Hệ điều hành 148 4.7. Khôi phục sau bế tắc „ Cho phép trạng thái vào trạng thái bế tắc „ Thuật toán phát hiện bế tắc „ Phương pháp khôi phục 3/12/2008 Nguyên lý Hệ điều hành 149 Mỗi loại tài nguyên có một thể hiện „ Duy trì đồ thị wait-for ‰ Các node là các tiến trình. ‰ Pi→ Pj nếu Pi đang chờ Pj. „ Định kì thực hiện thuật toán tìm chu trình trong đồ thị. „ Một giải thuật kiểm tra chu trình trong đồ thị cần n2 thao tác, ở đây n là số đỉnh trong đồ thị. 3/12/2008 Nguyên lý Hệ điều hành 150 Đồ thị phân phối tài nguyên và đồ thị Wait-for Đồ thị phân phối tài nguyên Đồ thị wait-for tương ứng 3/12/2008 Nguyên lý Hệ điều hành 151 Mỗi tài nguyên có nhiều hơn một thể hiện „ Available: Vector độ dài m chỉ số các trường hợp còn rỗi đối với mỗi tài nguyên. „ Allocation: Ma trận n x m xác định số tài nguyên của mỗi loại được phân phối cho tiến trình. „ Request: Ma trận n x m chỉ yêu cầu hiện tại của tiến trình. Nếu Request [ij] = k, tiến trình Pi đang cần thêm k trường hợp tài nguyên Rj. 3/12/2008 Nguyên lý Hệ điều hành 152 Thuật toán phát hiện 1. Gọi Work and Finish là các vector độ dài m và n tương ứng. Khởi tạo : (a) Work = Available (b) For i = 1,2, , n, if Allocationi ≠ 0, then Finish[i] = false;otherwise, Finish[i] = true. 2. Tìm một chỉ số i thỏa mãn: (a) Finish[i] == false (b) Requesti ≤ Work Nếu không tồn tại i nhảy đến bước 4. 3/12/2008 Nguyên lý Hệ điều hành 153 Thuật toán phát hiện (Cont.) 3.Work = Work + Allocationi Finish[i] = true go to step 2. 4.If Finish[i] == false, for some i, 1 ≤ i ≤ n, then hệ thống trong trạng thái bế tắc. Hơn nữa, if Finish[i] == false, then Pi bị bế tắc. Độ phức tạo của thuật toán là O(m x n2). 3/12/2008 Nguyên lý Hệ điều hành 154 Ví dụ về thuật toán phát hiện „ 5 tiến trình P0 đến P4; ba loại tài nguyên: A (7 trường hợp), B (2 trường hợp), and C (6 trường hợp). „ Hệ thống tại thời điểm T0: Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 „ Chuỗi dẫn đến Finish[i] = true với mọi i. 3/12/2008 Nguyên lý Hệ điều hành 155 Ví dụ (Cont.) „ P2 yêu cầu thêm một thể hiện của C. Request A B C P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 „ Trạng thái của hệ thống? ‰ Tồn tại bế tắc, bao gồm các tiến trình P1, P2, P3, và P4. 3/12/2008 Nguyên lý Hệ điều hành 156 Sử dụng thuật toán phát hiện „ Thời điểm, mức độ thường xuyên phụ thuộc vào: ‰ Mức độ thường xuyên của bế tắc? ‰ Bao nhiêu tiến trình cần phải quay lui? „ Một đối với mỗi chu trình (các chu trình không giao) „ Nếu thuật toán phát hiện được gọi tùy ý, có thể có rất nhiều chu trình trong đồ thị tài nguyên và vì thế chúng ta không thể phát hiện tiến trình nào trong số các tiến trình đó gây ra bế tắc. 3/12/2008 Nguyên lý Hệ điều hành 157 Khôi phục sau bế tắc: Kết thúc tiến trình „ Dừng thực thi của toàn bộ tiến trình bế tắc. „ Dừng một tiến trình một cho đến khi mất đi chu trình bế tắc. „ Thứ tự dừng? ‰ Độ ưu tiên của tiến trình. ‰ Tiến trình đã được thực thi và còn phải thực thi trong bao lâu. ‰ Các tài nguyên mà tiến trình hiện đang sử dụng. ‰ Các tài nguyên mà tiến trình cần thêm. ‰ Số tiến trình cần phải kết thúc. ‰ Tiến trình là tương tác hay batch? 3/12/2008 Nguyên lý Hệ điều hành 158 Khôi phục sau bế tắc: chiếm đoạt tài nguyên „ Lựa chọn một nạn nhân – cực tiểu hóa cost. „ Rollback – trở về trạng thái an toàn, khởi động lại tiến trình cho trạng thái đó. „ Chết đói – một tiến trình có thể luôn bị lựa chọn là nạn nhân 3/12/2008 Nguyên lý Hệ điều hành 159 Kết thúc chương 2