Các tiêu chí lập lịch CPU
Lập trình mô phỏng các phương pháp lập lịch cho CPUBạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (325.21 KB, 24 trang ) TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI BÀI TẬP LỚN MÔN NGUYÊN LÝ HỆ ĐIỀU HÀNH THỰC HIỆN: NHÓM 15_LỚP ĐHHTTT1_K6 …HÀ NỘI 2012… Nhóm 15 _ ĐH HTTT1 _ K6 Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI BÀI TẬP LỚN MÔN NGUYÊN LÝ HỆ ĐIỀU HÀNH LẬP TRÌNH MÔ PHỎNG CÁC PHƯƠNG PHÁP LẬP LỊCH CHO CPU THỰC HIỆN: NHÓM 15_LỚP ĐHHTTT1_K6: 1. ĐỖ VĂN CHÍ 2. TRỊNH VIỆT HÙNG 3. ĐOÀN VĂN HUY 4. TRẦN XUÂN KHÁNH 5. HOÀNG VĂN PHẨM MỤC LỤC Đề tài: Lập trình mô
phỏng các phương pháp lập lịch cho CPU. 2.1.1. Cấu trúc dữ liệu..............................................................................12 2.1.2. Thuật toán xử lý chung..................................................................13 2.2. THUẬT TOÁN....................................................................................... 14 2.2.1. Thuật toán First Come First Served(FCFS) ...................................14 2.2.2. Thuật toán Round robin(RR).........................................................15 2.2.3. Thuật toán Shortest Job First(SJF).................................................18 2.2.4. Thuật toán Shortest Remain Time(SRT)........................................20 3 LỜI NÓI ĐẦU cứu đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. Nhóm 15 sẽ trình bày nội dung chính như sau: - Tìm hiểu các thuật toán: First Come First Served(FCFS), Round Robin(RR), - Chỉ ra được ưu và nhược điểm cả các thuật toán lập lịch CPU. Mặc dù nhóm 15 chúng em đã cố gắng tìm hiểu kiến thức, tài liệu về các phương Chương 1. CƠ SỞ LÝ THUYẾT Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. 1.1.1. Mục tiêu lập lịch Bộ điều phối không cung cấp cơ chế, mà đưa ra các quyết định. Các hệ điều hành xây dựng nhiều chiến lược khác nhau để thực hiện việc điều phối, nhưng tựu chung cần đạt được các mục tiêu sau: - Sự công bằng: các tiến trình chia sẻ CPU một cách công bằng không có tiến trình nào phải đợi vô hạn để được cấp phát CPU. - Tính hiệu quả: Hệ thống phải tận dụng được CPU 100% thời gian. - Thời gian đáp ứng hợp lý: cực tiểu hóa thời gian hồi đáp cho các tương tác của người sử dụng. - Thời gian lưu lại trong hệ thống: cực tiểu hóa thời gian hoàn tất các tác vụ xử lý theo lô. - Thông lượng tối đa: cực đại hóa số công việc được xử lý trong một đơn vị thời gian. Tuy nhiên thường không thể thỏa mãn tất cả các mục tiêu kể trên vì bản thân chúng có sự mâu thuẫn với nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó. 1.1.2. Các đặc điểm của tiến trình Điều phối hoạt động của các tiến trình là một vấn đề rất phức tạp, đòi hỏi hệ - Tiến trình tương tác hay xử lý theo lô: Người sử dụng theo kiểu tương tác thường yêu cầu được hồi đáp tức thời đối với các yêu cầu của họ, trong khi các tiến 5 Nhóm 15 _ ĐH HTTT1 _ K6 Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. chấp nhận được. Điều phối không độc quyền và điều phối độc quyền Thuật toán điều phối cần xem xét và quyết định thời điểm chuyển đổi CPU giữa khi nhận được CPU sẽ có quyền độc chiếm CPU đến khi hoàn tất xử lý hoặc tự nguyện giải phóng CPU. Khi đó quyết định điều phối CPU sẽ xảy ra trong các tình huống sau: - Khi tiến trình chuyển từ trạng thái đang xử lý (running) sang trạng thái bị blocked (ví dụ chờ một thao tác nhập xuất hay chờ một tiến trình con kết thúc…). - Khi tiến trình kết thúc. Điều phối không độc quyền: Ngược với nguyên lý độc quyền, điều phối theo nguyên lý không độc quyền cho phép tạm dừng hoạt động của một tiến trình sẵn sàng xử lý. Khi một tiến trình nhận được CPU, nó vẫn được sử dụng CPU đến khi hoàn tất hoặc tự nguyện giải phóng CPU, nhưng khi có một tiến trình khác có độ ưu tiên có thể dành quyền sử dụng CPU của tiến trình ban đầu. Như vậy là tiến trình có 6 Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. khác xử lý. Các quyết định điều phối xảy
ra khi: lô. Đối với các hệ thống tương tác (time sharing), các hệ thời gian thực (real time), cần phải sử dụng nguyên lý điều phối không độc quyền để các tiến trình quan trọng có cơ hội hồi đáp kịp thời. Tuy nhiên thực hiện hiện điều phối theo nguyên lý không độc quyền đòi hỏi nhưng cơ chế phức tạp trong việc phân định độ ưu tiên, và phát sinh thêm chi phí khi chuyển đổi CPU qua lại giữa các tiến trình. 1.2. Các khái niệm cơ bản 1.2.1. Khái niệm giờ CPU CPU là một loại tài nguyên quan trọng của máy tính. Mọi tiến trình muốn hoạt Các trạng thái của tiến trình liên quan đến giờ CPU Trong chế độ đa chương trình, có ba trạng thái của tiến trình liên quan mật thiết Ready 7 Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. Hình 1.1: Các trạng thái của tiến trình liên quan đến giờ CPU Sử dụng CPU Đợi I/O Sử dụng CPU ……… Kết thúc đợi I/O Hình 1.2: Sơ đồ thực hiện các tiến trình Một tiến trình đang trong trạng thái thực hiện, nó có thể rời khỏi trạng thái bởi một trong ba lý do: - Tiến trình đã hoàn thành công việc, khi đó nó trả lại giờ CPU và chuyển sang chờ xử lý kết thúc. - Tiến trình tự ngắt: Khi tiến trình chờ đợi một sự kiện nào đó, tiến trình sẽ được chuyển sang trạng thái thực hiện khi có xuất hiện sự kiện nó đang chờ. - Tiến trình sử dụng hết giờ CPU dành cho nó, khi đó nó sẽ được chuyển sang trạng thái sẵn sàng. Việc chuyển tiến trình sang trạng thái sẵn sàng về bản chất là thực hiện vệc phân phối lại giờ CPU. 1.2.3. Khái niệm lập lịch cho CPU Để điều khiển tiến trình ở nhiều trạng thái khác nhau, hệ thống thường tổ chức 8 Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. hàng đợi như sau: Read CP U I/O Queue I/O I/O Queue …… …… I/O I/O Queue I/O Hình 1.3: Sơ đồ tổ chức hàng đợi các tiến trình First Come First Served(FCFS) Trong thuật toán này, độ ưu tiên phục vụ tiến trình căn cứ vào thời điểm hình thành tiến trình. Hàng đợi các tiến trình được tổ chức theo kiểu FIFO(First In First Out – Vào trước ra trước, vào sau ra sau). Mọi tiến trình đều được phục vụ theo trình tự xuất hiện cho đến khi kết thúc hoặc bị ngắt. Ready list A B C CPU Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. Ưu điểm: giờ CPU không bị phân phối lại(không bị ngắt) và chi phí thực hiện Giải thuật định thời luân phiên (round-robin scheduling algorithm-RR) được thiết kế đặc biệt cho hệ thống chia sẻ thời gian. Tương tự như định thời FIFO nhưng sự trưng dụng CPU được thêm vào để chuyển CPU giữa các quá trình. Đơn vị thời gian nhỏ được gọi là định mức thời gian (time quantum) hay phần thời gian (time slice) được định nghĩa. Định mức thời gian thường từ 10 đến 100 mili giây. Hàng đợi sẵn sàng được xem như một hàng đợi vòng. Bộ định thời CPU di chuyển vòng quanh hàng đợi sẵn sàng, cấp phát CPU tới mỗi quá trình có khoảng thời gian tối đa bằng một định mức thời gian. Để cài đặt định thời RR, chúng ta quản lý hàng đợi sẳn sàng như một hàng đợi FIFO của các quá trình. Các quá trình mới được thêm vào đuôi hàng đợi. Bộ định thời CPU chọn quá trình đầu tiên từ hàng đợi sẵn sàng, đặt bộ đếm thời gian để ngắt sau 1 định mức thời gian và gửi tới quá trình. Sau đó, một trong hai trường hợp sẽ xảy ra. Quá trình có 1 chu kỳ CPU ít hơn 1 định mức thời gian. Trong trường hợp này, quá trình sẽ tự giải phóng . Sau đó, bộ định thời biểu sẽ xử lý quá trình tiếp theo trong hàng đợi sẵn sàng. Ngược lại, nếu chu kỳ CPU của quá trình đang chạy dài hơn 1 định mức thời gian thì độ đếm thời gian sẽ báo và gây ra một ngắt tới hệ điều hành. Chuyển đổi ngữ cảnh sẽ được thực thi và quá trình được đặt trở lại tại cuối của hàng đợi sẵn sàng. Sau đó, bộ định thời biểu CPU sẽ chọn quá trình tiếp theo trong hàng đợi sẵn sàng. Ready List 10 Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. A B C A CPU Hình 1.5: Round Robin Nhược điểm : - Cài đặt thuật toán phức tạp,tốn nhiều xử lý cho quá trình quản lý. - Mặc dù SJF là tối ưu nhưng nó không thể được cài đặt tại cấp định thời CPU ngắn vì không có cách nào để biết chiều dài chu kỳ CPU tiếp theo. - Giải thuật SJF có thể trưng dụng hoặc không trưng dụng CPU, dẫn tới giải thuật này có nhiều dị bản khác nhau và sẽ tối ưu hay không tối ưu phụ thuộc vào trưng dụng CPU. 1.3.4. Shortest Remain Time(SRT) Tương tự như SJF nhưng trong thuật toán này, độ ưu tiên thực
hiện các tiến trình Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. CPU cũng phải được áp dụng nếu không sẽ làm mất tình ưu việc của thuật toán. Chương 2. CÀI ĐẶT THUẬT TOÁN 2.1. Mô hình cài đặt thuật toán Cấu trúc dữ liệu Quản lý tiến trình: Input: Đề tài: Lập trình mô phỏng các phương pháp lập lịch cho CPU. process *a,tg; |
