Lý thuyết Lập lịch CPU và Ứng dụng Giải quyết Bài toán Lập lịch

Lập lịch CPU: Tìm hiểu lý thuyết cơ bản và các giải pháp tối ưu hóa hiệu suất bộ xử lý. Khám phá các thuật toán lập lịch CPU phổ biến nhất.

• Tác giả: Nguyễn Văn Kiên
• Người hướng dẫn: T.S Vũ Vinh Quang
• Trường học: Trường Đại Học Công Nghệ Thông Tin Và Truyền Thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Lý thuyết lập lịch và ứng dụng giải quyết bài toán lập lịch cho CPU
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2013
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT TOÁN
• 1.1. Khái niệm cơ bản
• 1.2. Khái niệm về độ phức tạp thuật toán
• 1.3. Cách tính độ phức tạp
• 1.4. Vấn đề phân lớp các bài toán
• 1.4.1. Tổng quan về sự phân lớp các bài toán
• 1.4.2. Khái niệm dẫn về được
• 1.4.3. Lớp các bài toán P và NP
• 1.4.3.1. Một số khái niệm
• 1.4.4. Một số bài toán đã được chứng minh là NP – khó, NP - đầy đủ
• 1.4.5. Thuật toán xấp xỉ
• 1.4.5.1. Thuật toán  - xấp xỉ tuyệt đối
• 1.4.5.2. Thuật toán  - xấp xỉ
• 2. LÝ THUYẾT LẬP LỊCH
• 2.1. Mô hình bài toán lập lịch
• 2.2. Các thuật toán lập lịch kinh điển
• 2.3. Một số thuật toán lập lịch cho CPU
• 2.3.1. Mô hình bài toán lập lịch cho CPU
• 2.3.2. Một số thuật toán lập lịch cho CPU
• 2.3.2.1. Lập lịch FCFS
• 2.3.2.2. Lập lịch SJF
• 2.3.2.3. Lập lịch theo độ ưu tiên
• 2.3.2.4. Lập lịch RR
• 2.3.2.5. Lập lịch với hàng đợi nhiều cấp
• 2.3.2.6. Lập lịch hàng đợi phản hồi đa cấp
• 3. KẾT QUẢ CÀI ĐẶT MỘT SỐ THUẬT TOÁN LẬP LỊCH CPU
• 3.1. Giới thiệu sơ lược về ngôn ngữ lập trình C# và công cụ lập trình Visual Studio.Giới thiệu về ngôn ngữ lập trình C#
• 3.2. Giới thiệu về công cụ lập trình Visual Studio
• 3.3. Phân tích thuật toán cài đặt CPU
• 3.3.1. Thuật toán FCFS
• 3.3.2. Thuật toán SJF
• 3.3.3. Thuật toán RR
• 3.4. Sơ đồ thuật toán CPU
• 3.5. Kết quả cài đặt thuật toán CPU
• 3.5.1. Các thành phần của chương trình
• 3.5.2. Cấu trúc chi tiết
• 3.5.3. Sử dụng chương trình
• TÀI LIỆU THAM KHẢO
• 3.6. Thuật toán cài đặt
• 3.7. Các hàm và phương thức cơ bản của chương trình

Tóm tắt

I. Tổng quan về Lập lịch CPU Nền tảng cốt lõi hệ điều hành

Lập lịch CPU là một trong những chức năng cơ bản và quan trọng nhất của một hệ điều hành đa nhiệm. Chức năng này quyết định tiến trình nào trong hàng đợi sẵn sàng sẽ được cấp phát CPU để thực thi. Hiệu quả của các thuật toán lập lịch ảnh hưởng trực tiếp đến hiệu suất tổng thể của hệ thống, từ tốc độ phản hồi cho người dùng đến thông lượng xử lý công việc. Một chiến lược lập lịch tối ưu phải cân bằng giữa nhiều yếu tố như thời gian chờ, thời gian hoàn thành và việc sử dụng tài nguyên CPU. Nội dung phần này sẽ đi sâu vào các khái niệm nền tảng và các tiêu chí dùng để đánh giá hiệu quả của một giải pháp lập lịch.

1.1. Vai trò của bộ lập lịch CPU trong quản lý tiến trình

Trong một hệ thống máy tính hiện đại, nhiều tiến trình cùng tồn tại và cạnh tranh để giành quyền sử dụng CPU. Hệ điều hành phải quản lý sự cạnh tranh này một cách hiệu quả. Đây chính là nhiệm vụ của bộ lập lịch CPU (còn gọi là bộ lập lịch ngắn hạn - short-term scheduler). Chức năng cốt lõi của nó là lựa chọn một tiến trình từ hàng đợi sẵn sàng (ready queue) và cấp phát CPU cho tiến trình đó. Sự cần thiết của lập lịch CPU xuất phát từ yêu cầu thực thi nhiều công việc cùng lúc, đảm bảo hệ thống có thể xử lý đa luồng dữ liệu. Trong môi trường thời gian thực, việc lập lịch còn phải đảm bảo các tiến trình đáp ứng đúng thời hạn, một yếu tố quan trọng để giữ hệ thống ổn định. Theo tài liệu nghiên cứu của Nguyễn Văn Kiên, "sự cần thiết của thuật toán lập lịch xuất phát từ yêu cầu cho hầu hết các hệ thống hiện đại để thực thi nhiều hơn một công việc tại cùng một thời điểm". Do đó, một cơ chế lập lịch CPU hiệu quả là yếu tố quyết định để tối ưu hóa việc sử dụng tài nguyên và nâng cao trải nghiệm người dùng.

1.2. Các tiêu chí quan trọng để đánh giá thuật toán lập lịch

Để đánh giá và so sánh hiệu quả của các thuật toán lập lịch CPU, nhiều tiêu chí khác nhau được sử dụng. Mỗi tiêu chí phản ánh một khía cạnh về hiệu suất của hệ thống. Các tiêu chí chính bao gồm: Sử dụng CPU (CPU utilization) - giữ cho CPU bận rộn nhất có thể; Thông lượng (Throughput) - số lượng tiến trình hoàn thành trong một đơn vị thời gian; Thời gian hoàn thành (Turnaround time) - tổng thời gian từ khi tiến trình được gửi đến khi hoàn thành; Thời gian chờ đợi (Waiting time) - tổng thời gian một tiến trình phải chờ trong hàng đợi sẵn sàng; và Thời gian đáp ứng (Response time) - thời gian từ khi gửi yêu cầu đến khi có phản hồi đầu tiên. Mục tiêu của một thuật toán lập lịch tốt là tối đa hóa việc sử dụng CPU và thông lượng, đồng thời tối thiểu hóa thời gian hoàn thành, thời gian chờ đợi và thời gian đáp ứng. Tuy nhiên, việc tối ưu hóa một tiêu chí thường ảnh hưởng tiêu cực đến các tiêu chí khác, đòi hỏi sự cân bằng hợp lý tùy thuộc vào yêu cầu của từng hệ thống cụ thể.

II. Thách thức khi tối ưu hóa hiệu suất lập lịch cho CPU

Việc thiết kế một thuật toán lập lịch CPU tối ưu không phải là nhiệm vụ đơn giản. Các nhà phát triển hệ điều hành phải đối mặt với nhiều thách thức cố hữu. Một trong những vấn đề lớn nhất là sự đánh đổi giữa các mục tiêu hiệu suất khác nhau. Ví dụ, việc giảm thời gian đáp ứng cho các tiến trình tương tác có thể làm tăng thời gian hoàn thành của các công việc chạy nền. Hơn nữa, các vấn đề như "đói CPU" (starvation) và chi phí của việc chuyển đổi ngữ cảnh cũng là những yếu tố phức tạp cần được xem xét kỹ lưỡng để xây dựng một hệ thống ổn định và hiệu quả.

2.1. Phân tích hiện tượng đói CPU Starvation và cách khắc phục

Hiện tượng đói CPU (Starvation) hay nghẽn không hạn định (indefinite blocking) là một vấn đề nghiêm trọng trong các thuật toán lập lịch dựa trên độ ưu tiên. Nó xảy ra khi một tiến trình có độ ưu tiên thấp phải chờ đợi vô thời hạn vì luôn có các tiến trình với độ ưu tiên cao hơn được đưa vào hàng đợi sẵn sàng. Trong một hệ thống tải cao, dòng tiến trình ưu tiên cao liên tục có thể ngăn chặn hoàn toàn việc cấp phát CPU cho các tiến trình ưu tiên thấp. Luận văn gốc đề cập: "Thuật toán lập lịch theo độ ưu tiên có thể để lại nhiều tiến trình có độ ưu tiên thấp chờ CPU không hạn định". Để giải quyết vấn đề này, một kỹ thuật phổ biến được áp dụng là sự hóa già (aging). Kỹ thuật này sẽ tăng dần độ ưu tiên của các tiến trình đã chờ đợi trong hệ thống một thời gian dài. Ví dụ, độ ưu tiên của một tiến trình có thể được tăng lên sau mỗi khoảng thời gian nhất định, đảm bảo rằng cuối cùng nó sẽ đạt được độ ưu tiên đủ cao để được thực thi.

2.2. Tác động của chuyển đổi ngữ cảnh đến hiệu năng hệ thống

Mỗi khi CPU chuyển từ tiến trình này sang tiến trình khác, một quá trình gọi là chuyển đổi ngữ cảnh (context switch) sẽ diễn ra. Quá trình này bao gồm việc lưu trạng thái của tiến trình hiện tại và nạp trạng thái của tiến trình kế tiếp. Đây là một hoạt động tốn chi phí, vì không có công việc hữu ích nào được thực hiện trong suốt thời gian chuyển đổi. Tần suất chuyển đổi ngữ cảnh phụ thuộc rất nhiều vào thuật toán lập lịch CPU và các tham số của nó, chẳng hạn như định mức thời gian (time quantum) trong thuật toán Round Robin. Nếu định mức thời gian quá nhỏ, số lần chuyển đổi ngữ cảnh sẽ tăng lên đáng kể, làm lãng phí tài nguyên CPU và giảm hiệu suất chung của hệ điều hành. Do đó, việc lựa chọn tham số lập lịch phù hợp để cân bằng giữa độ phản hồi và chi phí chuyển đổi ngữ cảnh là một thách thức quan trọng trong việc tối ưu hóa hiệu suất hệ thống.

III. Các thuật toán Lập lịch CPU kinh điển và nguyên tắc hoạt động

Lý thuyết lập lịch đã phát triển nhiều thuật toán kinh điển, mỗi loại có ưu và nhược điểm riêng, phù hợp với các loại hệ thống khác nhau. Việc hiểu rõ nguyên tắc hoạt động của các thuật toán nền tảng như FCFS, SJF và RR là điều cần thiết để nắm bắt các cơ chế phức tạp hơn. Các thuật toán này là những viên gạch đầu tiên, đặt nền móng cho sự phát triển của các giải pháp lập lịch hiện đại. Chúng cung cấp các phương pháp tiếp cận cơ bản để giải quyết bài toán phân bổ tài nguyên CPU một cách công bằng và hiệu quả, từ đó tối ưu hóa các chỉ số hiệu năng quan trọng của hệ thống.

3.1. Giải thuật FCFS Nguyên lý đến trước phục vụ trước

Thuật toán FCFS (First-Come, First-Served) là giải thuật lập lịch CPU đơn giản nhất. Nguyên tắc của nó là tiến trình nào yêu cầu CPU trước sẽ được cấp phát CPU trước. Việc triển khai FCFS rất dễ dàng thông qua một hàng đợi FIFO (First-In, First-Out). Tuy nhiên, nhược điểm lớn của FCFS là thời gian chờ đợi trung bình thường rất dài và không tối ưu. Ví dụ được nêu trong tài liệu nghiên cứu cho thấy, với các tiến trình P1 (24ms), P2 (3ms), P3 (3ms) đến theo thứ tự, thời gian chờ đợi trung bình là 17ms. Nhưng nếu thứ tự đến là P2, P3, P1, thời gian chờ trung bình chỉ còn 3ms. Điều này cho thấy FCFS rất nhạy cảm với thứ tự đến của các tiến trình. Một vấn đề khác của FCFS là "hiệu ứng đoàn xe" (convoy effect), xảy ra khi một tiến trình cần nhiều thời gian CPU chiếm giữ tài nguyên, khiến các tiến trình ngắn khác phải chờ đợi, dẫn đến việc sử dụng CPU và thiết bị I/O kém hiệu quả. Vì vậy, FCFS là thuật toán lập lịch không khả dụng và không phù hợp cho các hệ thống chia sẻ thời gian.

3.2. Giải thuật SJF Ưu tiên công việc ngắn nhất để tối ưu

Thuật toán SJF (Shortest-Job-First) gán CPU cho tiến trình có chu kỳ CPU kế tiếp ngắn nhất. Về mặt lý thuyết, SJF được chứng minh là tối ưu vì nó mang lại thời gian chờ đợi trung bình nhỏ nhất cho một tập hợp các tiến trình. Bằng cách ưu tiên một tiến trình ngắn, thời gian chờ của nó giảm nhiều hơn so với sự gia tăng thời gian chờ của các tiến trình dài, từ đó giảm giá trị trung bình chung. Tuy nhiên, thách thức lớn nhất của SJF là không thể biết trước chính xác độ dài của chu kỳ CPU tiếp theo. Một phương pháp tiếp cận là dự đoán giá trị này dựa trên các chu kỳ CPU trước đó, thường sử dụng công thức trung bình số mũ. Lập lịch SJF có hai biến thể: không khả dụng (non-preemptive), nơi tiến trình đang chạy sẽ hoàn thành chu kỳ CPU của nó; và khả dụng (preemptive), còn được gọi là Shortest-Remaining-Time-First (SRTF), nơi CPU có thể bị chiếm dụng nếu một tiến trình mới đến có thời gian còn lại ngắn hơn tiến trình đang chạy.

3.3. Thuật toán Round Robin RR cho hệ thống chia sẻ thời gian

Thuật toán Round Robin (RR) được thiết kế đặc biệt cho các hệ thống chia sẻ thời gian. Nó tương tự như FCFS nhưng có thêm cơ chế khả dụng để chuyển đổi CPU giữa các tiến trình. Một đơn vị thời gian nhỏ, gọi là định mức thời gian (time quantum), được xác định (thường từ 10-100ms). Hàng đợi sẵn sàng được coi như một hàng đợi vòng. Bộ lập lịch sẽ cấp phát CPU cho mỗi tiến trình trong một khoảng thời gian không vượt quá một định mức. Nếu tiến trình chưa hoàn thành, nó sẽ bị chiếm quyền và đưa về cuối hàng đợi. Thuật toán này đảm bảo rằng mỗi tiến trình nhận được một phần thời gian CPU một cách công bằng. Hiệu suất của RR phụ thuộc rất nhiều vào kích thước của định mức thời gian. Nếu định mức quá lớn, RR hoạt động giống FCFS. Nếu quá nhỏ, chi phí chuyển đổi ngữ cảnh sẽ tăng cao, làm giảm hiệu suất chung. Do đó, việc lựa chọn một định mức thời gian hợp lý là rất quan trọng để tối ưu hóa thuật toán RR.

IV. Phương pháp Lập lịch CPU nâng cao cho hệ thống phức tạp

Đối với các hệ thống hiện đại với yêu cầu đa dạng, các thuật toán lập lịch kinh điển thường không đủ linh hoạt. Do đó, các phương pháp nâng cao đã được phát triển để giải quyết các vấn đề phức tạp hơn. Các phương pháp này thường kết hợp nhiều cơ chế khác nhau, chẳng hạn như sử dụng độ ưu tiên, phân chia tiến trình vào các hàng đợi riêng biệt, và cho phép tiến trình di chuyển giữa các hàng đợi để thích ứng với hành vi của chúng. Những giải pháp này mang lại khả năng tùy biến cao, giúp tối ưu hóa hiệu suất cho các loại tải công việc cụ thể.

4.1. Lập lịch theo độ ưu tiên Priority Scheduling và biến thể

Thuật toán lập lịch theo độ ưu tiên gán một giá trị ưu tiên cho mỗi tiến trình. CPU được cấp phát cho tiến trình có độ ưu tiên cao nhất. Các tiến trình có cùng độ ưu tiên thường được xử lý theo kiểu FCFS. Độ ưu tiên có thể được định nghĩa bên trong (dựa trên các thuộc tính như yêu cầu bộ nhớ, giới hạn thời gian) hoặc bên ngoài (dựa trên sự quan trọng của công việc). Thuật toán SJF có thể xem là một trường hợp đặc biệt của lập lịch ưu tiên, nơi độ ưu tiên là nghịch đảo của chu kỳ CPU kế tiếp. Tương tự SJF, lập lịch theo độ ưu tiên cũng có thể là khả dụng hoặc không khả dụng. Vấn đề chính của thuật toán này là nguy cơ đói CPU (starvation) đối với các tiến trình ưu tiên thấp. Để giải quyết, kỹ thuật sự hóa già (aging) được áp dụng để tăng dần độ ưu tiên của các tiến trình chờ đợi lâu, đảm bảo chúng cuối cùng cũng sẽ được thực thi.

4.2. Mô hình hàng đợi nhiều cấp Multilevel Queue hiệu quả

Thuật toán lập lịch hàng đợi nhiều cấp phân chia hàng đợi sẵn sàng thành nhiều hàng đợi riêng biệt. Các tiến trình được gán vĩnh viễn vào một hàng đợi dựa trên các thuộc tính của chúng, ví dụ như loại tiến trình (tương tác hoặc chạy nền), kích thước bộ nhớ, hoặc độ ưu tiên. Mỗi hàng đợi có thể có thuật toán lập lịch riêng. Ví dụ, hàng đợi cho các tiến trình tương tác có thể sử dụng thuật toán RR, trong khi hàng đợi cho các tiến trình nền sử dụng FCFS. Ngoài ra, cần có một cơ chế lập lịch giữa các hàng đợi, thường là lập lịch ưu tiên cố định và khả dụng. Chẳng hạn, hàng đợi tương tác có độ ưu tiên tuyệt đối so với hàng đợi nền. Mô hình này cho phép hệ thống áp dụng các chính sách lập lịch khác nhau cho các lớp công việc khác nhau, nhưng nó thiếu tính linh hoạt vì các tiến trình không thể di chuyển giữa các hàng đợi.

4.3. Giải pháp hàng đợi phản hồi đa cấp Multilevel Feedback Queue

Để khắc phục sự thiếu linh hoạt của hàng đợi nhiều cấp, thuật toán lập lịch hàng đợi phản hồi đa cấp cho phép các tiến trình di chuyển giữa các hàng đợi. Ý tưởng chính là tách biệt các tiến trình dựa trên đặc điểm chu kỳ CPU của chúng. Một tiến trình sử dụng quá nhiều thời gian CPU sẽ bị chuyển xuống hàng đợi có độ ưu tiên thấp hơn. Ngược lại, một tiến trình đã chờ quá lâu ở hàng đợi ưu tiên thấp có thể được nâng lên hàng đợi cao hơn. Đây là một hình thức của sự hóa già giúp ngăn chặn đói CPU. Ví dụ, một hệ thống có thể có ba hàng đợi: Q0 (RR với định mức 8ms), Q1 (RR với định mức 16ms), và Q2 (FCFS). Một tiến trình mới sẽ vào Q0, nếu không hoàn thành, nó sẽ bị chuyển xuống Q1, và sau đó là Q2. Thuật toán này rất linh hoạt và được coi là thuật toán lập lịch CPU phổ biến nhất vì nó có thể được cấu hình để phù hợp với nhiều loại hệ thống khác nhau.

V. Hướng dẫn chọn giải pháp Lập lịch CPU phù hợp thực tiễn

Lý thuyết cung cấp nhiều thuật toán, nhưng việc áp dụng vào thực tế đòi hỏi sự cân nhắc kỹ lưỡng về đặc thù của hệ thống. Không có một thuật toán nào là tốt nhất cho mọi trường hợp. Việc lựa chọn phụ thuộc vào mục tiêu của hệ thống: liệu nó ưu tiên thời gian đáp ứng nhanh cho người dùng, thông lượng cao cho các tác vụ xử lý hàng loạt, hay sự công bằng cho tất cả các tiến trình? Phân tích và so sánh hiệu năng của các thuật toán trong các kịch bản cụ thể là bước quan trọng để đưa ra quyết định tối ưu, đảm bảo hệ thống hoạt động ổn định và hiệu quả.

5.1. So sánh hiệu năng qua chỉ số thời gian chờ đợi trung bình

Một trong những cách phổ biến nhất để so sánh các thuật toán lập lịch CPU là đo lường thời gian chờ đợi trung bình. Chỉ số này phản ánh trực tiếp trải nghiệm của người dùng và hiệu quả sử dụng tài nguyên. Dựa trên các ví dụ trong tài liệu gốc, ta có thể thấy sự khác biệt rõ rệt. Với cùng một tập tiến trình, FCFS có thể cho kết quả rất tệ (17ms) hoặc tốt (3ms) tùy thuộc vào thứ tự đến. SJF luôn cho kết quả tối ưu về mặt lý thuyết (ví dụ, 7ms so với 10.25ms của FCFS trong một kịch bản khác). Trong khi đó, RR cung cấp một hiệu suất cân bằng hơn nhưng thường có thời gian chờ đợi trung bình dài hơn SJF. Việc so sánh này cho thấy SJF là lựa chọn lý tưởng nếu có thể dự đoán được thời gian thực thi, trong khi RR phù hợp hơn cho các hệ thống tương tác cần đảm bảo tính công bằng và thời gian đáp ứng nhanh, dù phải hy sinh một phần hiệu suất hệ thống tổng thể.

5.2. Lựa chọn thuật toán lập lịch cho từng loại hệ thống

Việc lựa chọn thuật toán lập lịch tối ưu phụ thuộc vào bản chất của hệ điều hành. Đối với hệ thống xử lý theo lô (batch system), nơi thông lượng và thời gian hoàn thành là quan trọng nhất, các thuật toán không khả dụng như FCFS hoặc SJF có thể là lựa chọn phù hợp. Ngược lại, đối với hệ thống tương tác và chia sẻ thời gian, ưu tiên hàng đầu là thời gian đáp ứng nhanh và tính công bằng. Trong trường hợp này, các thuật toán khả dụng như Round Robin (RR), lập lịch theo độ ưu tiên khả dụng, hoặc hàng đợi phản hồi đa cấp là lựa chọn tốt hơn. Các hệ thống thời gian thực (real-time systems) có yêu cầu nghiêm ngặt nhất, đòi hỏi các thuật toán phải đảm bảo các tiến trình hoàn thành trước thời hạn của chúng, thường sử dụng các biến thể của lập lịch ưu tiên.

Trích đoạn nội dung tài liệu

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Văn Kiên LÝ THUYẾT LẬP LỊCH VÀ ỨNG DỤNG GIẢI QUYẾT BÀI TOÁN LẬP LỊCH CHO CPU LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH 1 Số hóa bởi Trung tâm Học liệu http://lrc.vn Thái Nguyên 2013 LỜI CẢM ƠN Em xin chân thành cảm ơn Trƣờng Đại Học Công Nghệ Thông Tin và truyền thông đã tạo điều kiện cho em thực hiện luận văn này. Em cũng xin chân thành cảm ơn tới toàn thể thầy cô giáo ở Viện công nghệ thông tin và trƣờng Đại học công nghệ thông tin và truyền thông đã tận tình giảng dạy và hƣớng dẫn, trang bị cho em những kiến thức cần thiết trong quá trình thực hiện luận văn đƣợc thành công. Dựa trên sự chỉ bảo tận tình của T.S Vũ Vinh Quang dựa trên những kiến thức đã học, và tìm hiểu đƣợc, em đã hoàn thành luận văn theo đúng thời gian quy định. Tuy nhiên trong quá trình thiết kế và thực hiện luận văn không tránh khỏi sai sót, do thời gian có hạn và khả năng còn hạn chế.

Em mong quý thầy cô và các bạn thông cảm và có những ý kiến quý báu nhằm hoàn thiện hơn cho sản phẩm. Em xin chân thành cảm ơn. Thái nguyên, ngày 18 tháng 7 năm 2013 Học viên Nguyễn Văn Kiên 2 Số hóa bởi Trung tâm Học liệu http://lrc.vn LỜI CAM ĐOAN Em xin cam đoan luận văn tốt nghiệp: “Lý thuyết lập lịch và ứng dụng giải quyết bài toán lập lịch cho CPU” do em tự thực hiện dƣới sự hƣớng dẫn của thầy giáo Vũ Vinh Quang. Các kết quả và số liệu hoàn toàn trung thực.

Ngoài các tài liệu tham khảo đã dẫn ra ở cuối luận văn em đảm bảo rằng không sao chép các công trình hay luận văn tốt nghiệp của ngƣời khác. Nếu phát hiện có sự sai phạm với điều cam đoan trên, em xin hoàn toàn chịu trách nhiệm. 3 Số hóa bởi Trung tâm Học liệu http://lrc.vn MỤC LỤC LỜI CẢM ƠN. 1 LỜI CAM ĐOAN.

8 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT TOÁN. Khái niệm cơ bản. Kh¸i niÖm vÒ ®é phøc t¹p thuËt to¸n. Cách tính độ phức tạp.

Vấn đề phân lớp các bài toán. Tổng quan về sự phân lớp các bài toán. Khái niệm dẫn về đƣợc. Lớp các bài toán P và NP.

Một số khái niệm. Một số bài toán đã đƣợc chứng minh là NP – khó, NP - đầy đủ. Thuật toán xấp xỉ. Thuật toán  - xấp xỉ tuyệt đối.

Thuật toán  - xấp xỉ. 28 LÝ THUYẾT LẬP LỊCH. Mô hình bài toán lập lịch. Các thuật toán lập lịch kinh điển.

Một số thuật toán lập lịch cho CPU. Mô hình bài toán lập lịch cho CPU. Một số thuật toán lập lịch cho CPU. 35 4 Số hóa bởi Trung tâm Học liệu http://lrc.

Lập lịch FCFS. Lập lịch SJF. Lập lịch theo độ ƣu tiên. Lập lịch RR.

Lập lịch với hàng đợi nhiều cấp. Lập lịch hàng đợi phản hồi đa cấp. 51 KẾT QUẢ CÀI ĐẶT MỘT SỐ THUẬT TOÁN LẬP LỊCH CPU. Giới thiệu sơ lƣợc về ngôn ngữ lập trình C# và công cụ lập trình Visual Studio.Giới thiệu về ngôn ngữ lập trình C#.

Giới thiệu về công cụ lập trình Visual Studio. Phân tích thuật toán cài đặt CPU. Thuật toán FCFS.2 Thuật toán SJF. Thuật toán RR.

Sơ đồ thuật toán CPU. Kết quả cài đặt thuật toán CPU. Các thành phần của chƣơng trình. Cấu trúc chi tiết.

Sử dụng chƣơng trình. 66 TÀI LIỆU THAM KHẢO. Thuật toán cài đặt. Các hàm và phƣơng thức cơ bản của chƣơng trình.

77 5 Số hóa bởi Trung tâm Học liệu http://lrc.vn LỜI NÓI ĐẦU Máy tính điện tử ra đời vào những năm 40 của thế kỷ XX. Ban đầu, phạm vi sử dụng máy tính còn rất hẹp, đa phần chỉ nhằm phục vụ mục đích nghiên cứu khoa học. Hơn nữa, để vận hành hệ thống cần phải sử dụng các công cụ phần cứng đặc biệt và thao tác vận hành rất phức tạp. Cùng phát triển song song với sự phát triển của kỹ thuật điện tử, các thế hệ máy tính về sau đƣợc cải tiến ngày một tinh vi hơn, có tốc độ xử lý nhanh hơn, kích thƣớc nhỏ gọn hơn, tiêu tốn ít năng lƣợng hơn và đã làm nên một cuộc cách mạng trong lĩnh vực xử lý, tính toán, điều khiển động…Với các hệ máy tính này đòi hỏi phải có sự điều khiển, vận hành một cách tự động để phát huy hiệu quả của nó một cách tối ƣu nhất.

Nhƣ vậy, cần phải có một chƣơng trình phần mềm đảm bảo việc giải quyết các vấn đề trên. Đó chính là các hệ điều hành máy tính. Mỗi hệ điều hành đều cần có thuật toán lập lịch cho riêng chúng. Thuật toán thƣờng đƣợc thực hiện để cân bằng cho hệ thống máy tính đƣợc hiệu quả.

Sự cần thiết của thuật toán lập lịch xuất phát từ yêu cầu cho hầu hết các hệ thống hiện đại để thực thi nhiều hơn một công việc tại cùng một thời điểm và có thể truyền tải nhiều luồng dữ liệu một lúc. Trong môi trƣờng thời gian thực, chẳng hạn nhƣ các hệ thống nhúng điều khiển tự động trong ngành công nghiệp (Robot) thì lập lịch cũng phải đảm bảo rằng quá trình có thể đáp ứng đúng thời hạn, điều này là rất quan trọng để giữ hệ thống ổn định. Việc nghiên cứu các thuật toán lập lịch dành CPU này mở ra nhiều hƣớng mới cho khoa học và ứng dụng của nó trong thực tiễn cuộc sống. Đƣợc sự đồng ý của Thầy hƣớng dẫn, Em chọn đề tài “Lý thuyết lập lịch và ứng dụng giải quyết bài toán lập lịch cho CPU” làm đề tài luận văn cao học.

Nội dung chính của đề tài bao gồm: Chƣơng 1: Trình bày một số khái niệm về thuật toán và các nguyên tắc đánh giá độ phức tạp của thuật toán, vấn đề phân lớp các bài toán theo độ phức tạp của thuật toán. Đầy là phần lý thuyết quan trọng làm cơ sở để nghiên cứu trong các chƣơng tiếp sau của luận văn. 6 Số hóa bởi Trung tâm Học liệu http://lrc.vn Chƣơng 2: Trình bày lý thuyết cơ bản về bài toán lập lịch, các thuật toán giải bài toán lập lịch cơ bản và trọng tâm là trình bày một số thuật toán lập lịch cho CPU. Đây chính là nội dung trọng tâm của luận văn Chƣơng 3: Đƣa ra kết quả cài đặt các thuật toán lập lịch cho CPU trên nền ngôn ngữ Visual Studio 10.

Nội dung đề tài là một lĩnh vực rộng và khó, với khoảng thời gian không nhiều cùng với kiến thức của bản thân còn hạn chế, trong đề tài này mới chỉ đề cập đến việc nghiên cứu thuật toán lập lịch chủ yếu là trên một máy và ứng dụng cho lập lịch CPU. 7 Số hóa bởi Trung tâm Học liệu http://lrc.vn CHƢƠNG 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN VÀ ĐỘ PHỨC TẠP THUẬT TOÁN Trong chƣơng 1, luận văn sẽ trình bày một số kiến thức cơ bản về thuật toán và độ phức tạp thuật toán, vấn đề phân lớp các bài toán dựa trên độ phức tạp thuật toán. Các kiến thức này đã đƣợc tham khảo trong các tài liệu [3], [4]. Đây là các kiến thức quan trọng để trình bày tiếp các nội dung trong chƣơng 2 và chƣơng 3 của luận văn.

Khái niệm cơ bản 1. Thuật toán Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đƣợc sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, từ dữ liệu đầu vào (Input) của bài toán, ta nhận đƣợc kết quả (Output) cần tìm. Ta đã biết 2 mô hình tính toán là máy Turing và máy xử lý thuật toán viết bằng ngôn ngữ tựa ALGOL. Ứng với hai mô hình tính toán này có 2 cách biểu diễn thuật toán: + Thuật toán đƣợc biểu diễn bằng ngôn ngữ máy Turing.

+ Thuật toán đƣợc biểu diễn bằng ngôn ngữ tựa ALGOL. Kh¸i niÖm vÒ ®é phøc t¹p thuËt to¸n. Chi phí phải trả cho một quá trình tính toán Trong quá trình xử lý thuật toán, ngƣời ta thƣờng quan tâm tới chi phí cho thời gian tính toán và chi phí cho không gian chứa dữ liệu tính toán (bộ nhớ). - Chi phí thời gian chính là tổng thời gian cần thiết để thực hiện xong một quá trình tính toán.

+ Với máy Turing: Chi phí thời gian là số bƣớc chuyển hình trạng từ hình trạng đầu q0 đến hình trạng kết thúc qn. 8 Số hóa bởi Trung tâm Học liệu http://lrc.vn + Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản cần thực hiện trong quá trình tính toán. - Chi phí không gian chính là số ô nhớ cần để thực hiện hoàn chỉnh trong quá trình tính toán. Gọi A là một thuật toán tƣơng ứng với một mô hình tính toán, gọi e là bộ dữ liệu vào đã đƣợc mã hóa theo cách nào đó.

Khi đó thuật toán A tính trên bộ dữ liệu e cần phải trả về giá thời gian và giá không gian trong đó ta kí hiệu + t A (e ) là giá phải trả về thời gian tính toán + lA (e ) là giá về không gian của bộ nhớ cần thiết sử dụng Khi đó tổng giá phải trả của thuật toán A tính trên bộ dữ liệu e chính bằng : T(A)= t A (e ) + lA (e ) b. Các khái niệm về độ phức tạp của thuật toán Độ phức tạp trong trƣờng hợp xấu nhất Cho một thuật toán A với đầu vào n, khi đó: - Độ phức tạp về bộ nhớ trong trƣờng hợp xấu nhất đƣợc định nghĩa là: LA (n ) = max{lA (e) || | e | £ n } tức là chi phí lớn nhất về bộ nhớ. - Độ phức tạp thời gian trong trƣờng hợp xấu nhất đƣợc định nghĩa là : T A (n ) = max{t A (e) || | e | £ n } tức là chi phí lớn nhất về thời gian. Độ phức tạp trung bình Là tổng số các độ phức tạp khác nhau ứng với các bộ dữ liệu chia cho tổng số.

Độ phức tạp tiệm cận Thuật toán A với đầu vào n gọi là có độ phức tạp O(f(n)) nếu $ hằng số C, N 0 :T A (n ) £ C .f (n ), " n ³ N 0 tức là T A (n ) có tốc độ tăng là O(f(n)) 9 Số hóa bởi Trung tâm Học liệu http://lrc.vn 10 Số hóa bởi Trung tâm Học liệu http://lrc.vn Độ phức tạp đa thức (Polynomial) Thuật toán đƣợc gọi là có độ phức tạp đa thức nếu tồn tại đa thức P(n) mà T A (n ) £ C .