[He Dieu Hanh] On Tap He Dieu Hanh

ÔN TẬP GIỮA KÌ MÔN HỆ ĐIỀU HÀNH

I.                    NỘI DUNG

·        Quản lý tiến trình (Chương 3 – trang 40)

-          Chiến lược  Điều Phối FIFO

-          Chiến lược phân phối xoay vòng (Round Robin)

-          Điều phối với độ ưu tiên

-          Chiến lược công việc ngắn nhất (Shortest-job-first SJF)

-          Chiến lược điều phối với nhiều mức độ ưu tiên

·        Bộ nhớ ảo (Chương 7)

Bài tập Thay thế trang (Trang 128)

Các thuật toán thay thế trang

-          Thuật toán FIFO (Trình tự)

-          Thuật toán tối ưu (Nhìn về tương lai) (không chịu belaly, số lỗi phát sinh là thấp nhất)

-          Thuật toán “Lâu nhất chưa sử dụng” (Least-recently-used LRU)

-          Các thuật toán xấp xỉ LRU

·        Các thuật toán đọc đĩa (CHương 12)

-          Lập lịch FCFS: (189)

-          Lập lịch SSTF (shortest-seek-time-first) (189)

-          Lập lịch SCAN (Elevator)

-          Lập lịch C-SCAN

-          Lập lịch LOOK:

·         TẮc nghẼn (Deadlock) (Chương 5- Trang 80)

-          GIẢI THUẬT TÌM TRẠNG THÁI AN TOÀN

-          Điều kiện xuất hiện tắc nghẽn

TÓM TẮT

1.      Quản lý tiến trình

a)     Chiến lược điều phối FIFO (Firt In First Out) (Vào trước thì ra trước)

Nguyên tắc:

-          CPU cấp phát cho tiến trình đầu tiên trong danh sách có yêu cầu (tiến trình vào sớm nhất)

-          Thuật toán điều phối trên nguyên tắc độc quyền

-          CPU được giải phóng khi tiến trình tự nguyện giải phón hoặc cớ 1 yêu cầu nhập xuất

-          Không phù hợp với các hệ phân chia thời gian

b)     Chiến lược điều phối xoay vòng (Round Robin)

Nguyên tắc:

-          Danh sách sẵn sàng xử lý như 1 danh sách vòng

-          Lần lượt cấp cho các tiến trình 1 khoảng thời gian gọi là quantum

-          Khi 1 tiến trình sử dụng hết thời gian quantum, HDH thu hồi CPU và cấp phát cho tiến trình tiếp theo

-          Nếu tiến trình bị khóa hoặc kết thúc trước khoảng thời gian quantum thì HDH lập tức cấp phát CPU cho tiến trình tiếp theo

-          Khi tiến trình tiêu thụ hết thời gian giành cho nó mà chưa hoàn thành thì được đưa vào cuối danh sách và chờ đến lượt

-          Là một giải thuật điều phối không độc quyền

Chú ý. Nếu quantum nhỏ sẽ làm phát sinh nhiều sự chuyển đổi giữa các tiến trình làm hệ thống hoạt động kém hiểu quả

Nếu quantum lớn sẽ làm tăng thời gian hồi đáp và giảm khả năng tương tác của hệ thống

c)     Chiến lược điều phối với độ ưu tiên

Nguyên tắc:

-          Mỗi tiến trình sẽ được gán cho 1 độ ưu tiên, Tiến trình có độ ưu tiên cao nhất sẽ được chọn để cấp CPU đầu tiên

-          Độ ưu tiên có thể dc định nghĩa nội tại hay do các yếu tố bên ngoài

-          CÓ thể theo nguyên tắc độc quyền hoặc không độc quyền

Bộ nhớ ảo:      Thay thế trang

a)     Thuật toán FIFO

-         Ghi nhận thời điểm một trang được mang vào bộ nhớ chính. Khi cần thay thế trang, trang ở trong bộ nhớ lâu nhất sẽ được chọn

-           Dễ hiểu dễ cài đặt

-          Số lượng lỗi trang tăng lên khi số lượng khung trang tăng lên (Nghịch lý Belady)

b)     Thuật toán tối ưu

-          Thay thế trang sẽ lâu được sử dụng nhất trong tương lai

-         Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất, nó cũng không gánh chịu nghịch lý Belady, tuy nhiên, đây là một thuật toán không khả thi trong thực tế, vì không thể biết trước chuỗi truy xuất của tiến trình!

c)      Thuật toán “Lâu nhất chưa sử dụng” (Least-recently-used LRU)

d)     

·        Tắc nghẽn (DealLock)

a)     Tắc nghẽn là gì?

b)     ĐIều kiện xảy ra tắc nghẽn

Coffman, Elphick và Shoshani đã đưa ra 4 điều kiện cần có thể làm xuất hiện tắc nghẽn:

-       Có sử dụng tài nguyên không thể chia sẻ (Mutual exclusion): Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình, khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.

-       Sự chiếm giữ và yêu cầu thêm tài nguyên (Wait for): Các tiến trình tiếp tục chiếm giữ các tài nguyên đã cấp phát cho nó trong khi chờ được cấp phát thêm một số tài nguyên mới.

-       Không thu hồi tài nguyên từ tiến trình đang giữ chúng (No preemption): Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sử dụng chúng xong.

-       Tồn tại một chu kỳ trong đồ thị cấp phát tài nguyên (Circular wait): có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại.

Khi có đủ 4 điều kiện này, thì tắc nghẽn xảy ra. Nếu thiếu một trong 4 điều kiện trên thì không có tắc nghẽn.

c)     Phương pháp xử lý tắc nghẽn

Chủ yếu có ba hướng tiếp cận để xử lý tắc nghẽn:

-         Sử dụng một nghi thức (protocol) để bảo đảm rằng hệ thống không bao giờ xảy ra tắc nghẽn.

-         Cho phép xảy ra tắc nghẽn và tìm cách sữa chữa tắc nghẽn.

-         Hoàn toàn bỏ qua việc xử lý tắc nghẽn, xem như hệ thống không bao giờ xảy ra tắc nghẽn.

d)      

e)