CƠ SỞ LÝ THUYẾT
Giới thiệu chung
Tiến trình là một chương trình đang được thực thi, sử dụng con trỏ lệnh, tập thanh ghi và các biến Để thực hiện nhiệm vụ, tiến trình cần tài nguyên hệ thống như CPU, bộ nhớ và thiết bị Hệ điều hành sử dụng bộ điều phối (scheduler) để xác định thời điểm dừng tiến trình hiện tại và lựa chọn tiến trình tiếp theo cần thực hiện.
1.1.2 Các trạng thái của tiến trình
Tại một thời điểm, tiến trình có thể nhận một trong các trạng thái sau đây:
- New: tiến trình vừa mới được tạo.
- Ready: tiến trình đang chờ được cấp phát CPU để xử lí.
- Running: tiến trình đang được xử lí.
- Waiting: tiến trình dừng để chờ được cấp phát tài nguyên, hoặc chờ thao tác nhập xuất hoàn tất hoặc chờ một sự kiện nào đó.
- End: tiến trình được hoàn tất xử lí.
Hình 1: Sơ đồ các trạng thái của tiến trình
Hình 1 mô tả cách chuyển trạng thái của tiến trình:
- Đầu tiên khi vừa được khởi tạo, tiến trình sẽ ở trạng thái NEW và được lưu trong bộ nhớ tạm
Sau khi tiến trình được tạo, nó sẽ chuyển sang trạng thái READY và được tải lên bộ nhớ chính Khi tiến trình đã sẵn sàng để chạy, nếu được cấp phát CPU, nó sẽ chuyển sang trạng thái RUNNING.
Khi có yêu cầu nhập xuất hoặc yêu cầu từ người dùng, tiến trình sẽ chuyển sang trạng thái WAITING Tiến trình sẽ tiếp tục chờ đợi trong bộ nhớ chính cho đến khi thao tác nhập xuất hoặc yêu cầu được xử lý xong, sau đó sẽ chuyển sang trạng thái READY.
- Sau khi tiến trình được thực thi xong, gặp lệnh thoát thì sẽ kết thúc, tiến trình từ trạng thái RUNNING chuyển sang trạng thái END.
1.1.3 Điều phối tiến trình Điều phối hoạt động các tiến trình là một vấn đề rất phức tạp, đòi hỏi hệ điều hành phải xem xét nhiều yếu tố khác nhau để có thể đạt được những mục đích đề ra Một số tiêu chuẩn điều phối của tiến trình cần được quan tâm như:
Tính hướng nhập/xuất của tiến trình, hay còn gọi là I/O – boundedness, cho thấy rằng phần lớn hoạt động của các tiến trình chủ yếu liên quan đến thao tác nhập xuất Thời gian cần thiết để thực hiện các thao tác này thường lớn hơn so với thời gian xử lý của tiến trình.
Tính hướng của xử lý tiến trình (CPU - boundedness) cho thấy rằng hầu hết các tiến trình chủ yếu thực hiện các thao tác tính toán và xử lý Thời gian cần thiết để xử lý tiến trình thường dài hơn so với thời gian thực hiện các thao tác nhập xuất.
Khi hệ thống có cả tiến trình tương tác và tiến trình xử lý theo lô, tiến trình xử lý theo lô có thể được tạm dừng để ưu tiên cho tiến trình tương tác, nhằm đảm bảo phản hồi ngay lập tức cho người dùng.
Độ ưu tiên của tiến trình là yếu tố quan trọng trong việc quản lý tài nguyên, nơi các tiến trình được phân cấp dựa trên các tiêu chí đánh giá cụ thể Việc xác định thứ tự ưu tiên hợp lý giúp đảm bảo rằng những tiến trình quan trọng hơn sẽ nhận được sự ưu tiên cao hơn, từ đó tối ưu hóa hiệu suất và hiệu quả hoạt động của hệ thống.
Trong việc quản lý tiến trình, có hai quan điểm chính về thời gian sử dụng CPU Một số ý kiến cho rằng nên ưu tiên các tiến trình đã sử dụng nhiều thời gian CPU, vì điều này có thể giúp chúng hoàn tất nhanh chóng và rời khỏi hệ thống Ngược lại, cũng có quan điểm cho rằng các tiến trình nhận được ít thời gian CPU thường là những tiến trình đã phải chờ đợi lâu nhất, do đó nên được ưu tiên xử lý trước.
Để giảm thiểu thời gian chờ trung bình của các tiến trình, cần ưu tiên thực hiện các tiến trình có thời gian hoàn tất ngắn nhất trước.
1.1.4 Điều phối cưỡng chế (Preemptive) và điều phối không cưỡng chế (Non- preemptive)
Thuật toán điều phối đóng vai trò quan trọng trong việc xác định thời điểm chuyển đổi CPU giữa các tiến trình Hệ điều hành có thể áp dụng cơ chế điều phối theo hai nguyên lý: độc quyền và không độc quyền Trong đó, điều phối cưỡng chế (Preemptive) được sử dụng khi tiến trình chuyển từ trạng thái đang chạy (running state) sang trạng thái sẵn sàng (ready state) hoặc từ trạng thái chờ (waiting state) sang trạng thái sẵn sàng.
Preemptive cho phép tạm dừng tiến trình đang xử lý trong CPU khi có tiến trình khác ưu tiên cao hơn, dẫn đến việc tiến trình cũ bị đưa vào hàng đợi Ngược lại, điều phối không cưỡng chế (Non-preemptive) chỉ xảy ra khi tiến trình chuyển từ trạng thái đang chạy sang trạng thái chờ, cho phép tiến trình chiếm giữ CPU cho đến khi hoàn tất hoặc tự nguyện giải phóng, mà không có tiến trình nào có quyền ngắt trong quá trình này.
Trong các hệ thống non-preemptive, tiến trình cần thời gian xử lý ngắn có thể phải chờ đợi tiến trình cần thời gian xử lý dài hoàn tất Nguyên lý này thường phù hợp với hệ thống xử lý theo lô Tuy nhiên, trong các hệ thống tương tác và thời gian thực, cần áp dụng nguyên lý preemptive scheduling để đảm bảo tiến trình quan trọng được đáp ứng kịp thời Việc thực hiện nguyên lý này yêu cầu cơ chế phức tạp để phân định độ ưu tiên và có thể phát sinh chi phí hệ thống do việc chuyển đổi CPU giữa các tiến trình.
1.1.5 Khái niệm lập lịch cho CPU
Trong hệ thống đa nhiệm, nhiều tiến trình có thể tồn tại trong bộ nhớ cùng lúc, nhưng chỉ một tiến trình được thực thi tại một thời điểm Do đó, việc phân chia và định thời để phân phối thời gian sử dụng CPU cho các tiến trình là rất cần thiết Lập lịch CPU đóng vai trò quan trọng trong việc chọn lựa tiến trình tiếp theo cần thực hiện và phân bổ tài nguyên CPU cho tiến trình đó.
1.1.6 Mục tiêu của lập lịch cho CPU?
Việc phân phối thời gian sử dụng CPU nhằm đáp ứng một số mục tiêu sau:
- Đảm bảo sự công bằng trong việc phục vụ các tiến trình, tránh tình trạng rơi vào trạng thái chờ vô hạn
- Tối đa hóa số lượng tiến trình được phục vụ trong một đơn vị thời gian
- Thời gian phản ứng chấp nhận được với tất cả các tiến trình tối thiểu chi phí, tài nguyên hệ thống.
Cân đối và nâng cao hiệu suất sử dụng tài nguyên là rất quan trọng, ưu tiên cho các tiến trình sử dụng ít tài nguyên để tránh tình trạng tiến trình ưu tiên thấp chiếm dụng tài nguyên cần thiết cho tiến trình ưu tiên cao Nếu tài nguyên không thể chia sẻ, hệ điều hành cần hỗ trợ để tiến trình giải phóng tài nguyên một cách nhanh chóng.
1.1.7 Tiêu chí đánh giá lập lịch
Cơ chế lập lịch có một số tiêu chí dùng để đánh giá như sau:
Các thuật toán lập lịch
1.2.1 First Come, First Served (FCFS) scheduling
Thuật toán First Come First Served (FCFS) là một phương pháp lập lịch trong hệ điều hành, tự động xử lý các yêu cầu và quy trình theo thứ tự đến Đây là thuật toán lập lịch CPU đơn giản và dễ hiểu nhất, trong đó các quy trình yêu cầu CPU đầu tiên sẽ được cấp phát tài nguyên CPU trước Quá trình này được quản lý thông qua hàng đợi FIFO.
Xét bộ 3 tiến trình có thời gian đến (arrival time) và thời gian liên tục (burst time) được đưa ra dưới đây:
Process Id Arrival time Burst time
Turn Around time = Exit time – Arrival time
Waiting time = Turn Around time – Burst time
Process Id Exit time Turn Around time Waiting time
Đặc điểm của phương pháp FCFS:
Hỗ trợ thuật toán lập lịch không ưu tiên và ưu tiên trước.
Dễ thực hiện và sử dụng.
Phương pháp này có hiệu suất kém và thời gian chờ đợi chung là khá cao. Ưu điểm Nhược điểm
- Dạng đơn giản nhất của thuật toán lập lịch CPU
- Ai đến trước được phục vụ trước
Thuật toán lập lịch CPU Non-Preemptive đảm bảo rằng một khi tiến trình được cấp phát cho CPU, nó sẽ không giải phóng CPU cho đến khi hoàn thành quá trình thực thi.
- Thời gian chờ trung bình cao.
- Các tiến trình ngắn ở phía sau hàng đợi phải đợi tiến trình dài ở phía trước kết thúc.
- Không phải là một kỹ thuật lý tưởng cho các hệ thống chia sẻ thời gian.
- Vì tính đơn giản của nó, FCFS có hiệu quả không cao.
Thuật toán Shortest Job First (SJF) là một phương pháp điều phối tiến trình CPU, trong đó tiến trình có thời gian thực hiện ngắn nhất được chọn để thực hiện tiếp theo Khi có hai tiến trình có thời gian thực hiện giống nhau, thuật toán FCFS sẽ được áp dụng Nhờ vào cách thức này, thời gian chờ trung bình cho một tập hợp các tiến trình sẽ thấp hơn so với thuật toán FCFS.
Hình 3: Thuật toán Shortest Job First
Về cơ bản, có hai loại phương pháp SJF là:
Trong lập lịch không chiếm đoạt (Non-Preemptive Scheduling), khi một chu kỳ CPU được phân bổ cho một quá trình, quá trình đó sẽ giữ quyền sử dụng CPU cho đến khi nó chuyển sang trạng thái chờ hoặc hoàn tất.
- Lấy ví dụ về quá trình dưới đây, mỗi tiến trình có burst time và thời gian đến của riêng nó
Process Arrival time Burst time
Sử dụng SJF ta có biểu đồ Grand
Tại thời điểm = 0, P4 đến và bắt đầu thực hiện:
Tại thời điểm = 1, tiến trình P3 đến Tuy nhiên, P4 vẫn cần 2 đơn vị thời gian thực thi để hoàn thành Nó sẽ tiếp tục thực hiện.
Tại thời điểm = 2, tiến trình P1 đến và được thêm vào hàng đợi P4 sẽ tiếp tục thực hiện
Tại thời điểm 3, tiến trình P4 hoàn tất việc thực thi So sánh burst time của P3 và P1 cho thấy P1 (8) có thời gian thực thi ngắn hơn P3 (6), do đó tiến trình P1 sẽ được thực hiện tiếp theo.
Tại thời điểm = 4, tiến trình P2 đến và được thêm vào hàng đợi P1 sẽ tiếp tục thực hiện.
Tại thời điểm = 9, P1 sẽ kết thúc quá trình thực thi Burst time của P3 và P2 được so sánh (2 < 8) => P2 được thực hiện vì burst time của nó là thấp hơn.
Tại thời điểm = 11, P2 sẽ kết thúc quá trình thực thi Tiến trình P3 được thực hiện.
Tại thời điểm = 19, P3 sẽ kết thúc quá trình thực thi.
Thời gian chờ trung bình = (0+1+5+10)/4 = 4
Trong lập lịch SJF (Shortest Job First) có thể ngắt quãng, các công việc sẽ được đưa vào hàng đợi ngay khi chúng đến Tiến trình có thời gian thực thi ngắn nhất sẽ được ưu tiên thực hiện trước Nếu một tiến trình mới có thời gian thực thi ngắn hơn xuất hiện, tiến trình hiện tại sẽ bị tạm dừng để CPU được phân bổ cho tiến trình ngắn hơn.
- Xét ví dụ dưới đây:
Process Arrival time Burst time
Tại thời điểm = 0, P4 đến và bắt đầu thực hiện.
Tại thời điểm = 1, tiến trình P3 đến Tuy nhiên, P4 có burst time ngắn hơn Nó sẽ tiếp tục thực hiện.
Tại thời điểm = 2, tiến trình P1 đến với burst time = 6 Burst time nhiều hơn tiến trình P4 Do đó, P4 sẽ tiếp tục thực thi.
Tại thời điểm 3, quá trình P4 sẽ kết thúc thực thi Burst time của P3 và P1 được so sánh, và tiến trình P1 được chọn thực hiện do burst time của nó thấp hơn.
Tại thời điểm 4, tiến trình P2 sẽ được thực hiện do burst time của nó thấp nhất so với P3 và P1, dẫn đến việc tiến trình P1 bị tạm dừng.
Process Arrival time Burst time
Tại thời điểm = 6, quá trình P2 thực hiện xong, burst time của P1 và P3 được so sánh Tiến trình P1 được thực hiện.
Tại thời điểm = 11, tiến trình P1 thực hiện xong, tiến trình P3 bắt đầu được thực hiện.
Tại thời điểm = 19, tiến trình P3 kết thúc thực hiện.
Thời gian chờ trung bình = (3+10)/4 = 3.25
Nhận xét về SJF Ưu điểm của SJF Nhược điểm của SJF
- SJF thường được sử dụng trong một hệ thống hàng loạt để lập lịch trình dài hạn.
- Phương pháp SJF đưa ra thời gian chờ trung bình thấp nhất cho một tập hợp các quy trình cụ thể.
- Nó thích hợp cho các công việc chạy theo lô, nơi mà thời gian chạy được biết trước.
- Đối với hệ thống lập lịch dài hạn theo lô, có thể thu được ước tính thời gian liên tục từ mô tả công việc.
- Đối với lập lịch ngắn hạn, chúng ta cần dự đoán giá trị của burst time tiếp theo sử dụng phương pháp trung bình hàm mũ.
- Thời gian hoàn thành công việc phải được biết sớm hơn, nhưng khó có thể đoán trước được.
SJF (Shortest Job First) khó có thể áp dụng cho việc lập lịch CPU trong thời gian ngắn do không có phương pháp cụ thể nào để dự đoán độ dài của CPU burst tiếp theo.
- Thuật toán này có thể gây ra thời gian hoàn thành rất lâu hoặc starvation.
- Yêu cầu kiến thức về thời gian một quy trình hoặc công việc sẽ chạy.
- Thời gian đã trôi qua phải được ghi lại, điều này dẫn đến nhiều chi phí hơn cho bộ xử lý.
1.2.3 Shortest Remaining Time First (SRTF)
Phiên bản Preemptive của lập lịch Shortest Job First (SJF) được gọi là Shortest Remaining Time First (SRTF) Trong phương pháp SRTF, quá trình thực thi có thể bị tạm dừng sau một khoảng thời gian nhất định Khi có các tiến trình mới xuất hiện, bộ lập lịch ngắn hạn sẽ ưu tiên tiến trình có thời gian thực hiện còn lại ít nhất trong danh sách các tiến trình sẵn có, bao gồm cả tiến trình đang chạy.
Khi tất cả các tiến trình trong hàng đợi sẵn sàng, thuật toán sẽ hoạt động như lập lịch SJF mà không có quyền ưu tiên Bối cảnh của tiến trình được lưu trong Khối điều khiển tiến trình (PCB) khi tiến trình bị tạm dừng và sẽ được truy cập trong lần thực thi tiếp theo.
Khi có hai hoặc nhiều tiến trình yêu cầu chạy đồng thời, thuật toán sẽ ưu tiên tiến trình có thời gian thực hiện ngắn hơn để thực hiện trước.
Khi một tiến trình đang thực thi và có các tiến trình khác yêu cầu chạy, thuật toán sẽ so sánh thời gian thực hiện còn lại của tiến trình hiện tại với thời gian thực hiện của các tiến trình yêu cầu Tiến trình nào có thời gian thực hiện ngắn nhất sẽ được ưu tiên chạy trước.
Chỉ số thời gian chờ chỉ được xem xét trong lần chạy đầu tiên và lần so sánh đầu tiên Sau khi một tiến trình đã bắt đầu thực thi, thời gian chờ của nó không còn được quan tâm Tương tự, các tiến trình đã được so sánh thời gian thực hiện trong một lượt nào đó cũng không còn giá trị lập lịch cho chỉ số thời gian chờ.
Ví dụ: Có năm công việc: P1, P2, P3, P4, P5 và P6 Thời gian đến và thời gian thực hiện của chúng được trình bày trong bảng dưới đây.
Thời gian chờ trung bình = 24/6
Biểu đồ Gantt được lập theo thời gian đến và thực hiện được đưa ra trong bảng.
Tại thời điểm 0, tiến trình duy nhất khả dụng là P1 với thời gian thực hiện CPU là 8 Do P1 là tiến trình duy nhất trong danh sách, nó đã được thực hiện theo đúng kế hoạch.
GIỚI THIỆU CHUNG VỀ HỆ ĐIỀU HÀNH XV6 VÀ PHẦN MỀM QEMU
Hệ điều hành XV6
Xv6 là phiên bản hiện đại của Unix Sixth Edition, được phát triển bằng ngôn ngữ ANSI C cho hệ thống đa xử lý x86 và RISC-V Phiên bản này được thiết kế với mục đích giáo dục trong khóa học Kỹ thuật Hệ điều hành tại Viện Công nghệ Massachusetts (MIT).
Lịch sử và bối cảnh
Trong nhiều năm, MIT không có khóa học về hệ điều hành Vào mùa thu năm
Năm 2002, một chương trình giáo dục được phát triển nhằm giảng dạy kỹ thuật hệ điều hành, sử dụng Sixth Edition Unix (V6) làm nền tảng Các khóa học này dựa trên bài bình luận nổi tiếng của John Lions, mang đến kiến thức sâu sắc về hệ điều hành cho học viên.
Vào mùa hè năm 2006, V6 đã đối mặt với những thách thức sư phạm và quyết định thay thế bằng hệ điều hành mới Xv6 Được viết bằng ANSI C và chạy trên máy Intel x86 đa xử lý, Xv6 mang lại trải nghiệm học tập tốt hơn cho sinh viên so với V6 trước đó Việc sử dụng kiến trúc x86 giúp thống nhất khóa học và hỗ trợ đa xử lý yêu cầu xử lý đồng thời với các khóa và luồng, thay vì các giải pháp đặc biệt cho bộ đơn xử lý Hệ thống mới này cũng cho phép viết các phiên bản rõ ràng hơn cho các phần như bộ lập lịch và hệ thống tệp, cải thiện tính khả dụng và hiệu quả trong giảng dạy.
Hình 7: Các lệnh gọi hệ thống của xv6
Cách thức hoạt động của bộ lập lịch trên được mô tả như sau:
• Mỗi CPU xử lý một bộ lập lịch
• Sau quá trình khởi tạo được thực hiện bởi hàm mpmain, CPU sẽ biên dịch bộ lập lịch
• Bộ lập lịch không trả về giá trị mà thực hiện một vòng lặp với các công việc sau:
1− Chọn tiến trình để chạy.
2− Chuyển sang tiến trình được chọn để bắt đầu chạy.
3− Trả quyền kiểm soát lại cho bộ lập lịch.
Phần mềm Qemu
QEMU là một bộ giả lập mã nguồn mở, cung cấp môi trường máy ảo với khả năng hỗ trợ nhiều thiết bị phần cứng, bao gồm cả máy tính 32-bit và 64-bit Phần mềm này cho phép người dùng chạy nhiều hệ điều hành khác nhau trên cùng một máy nhờ vào trình biên dịch nhị phân động.
QEMU supports a wide range of hardware devices, including both 32-bit and 64-bit PC architectures, as well as PowerPC processors (such as PREP and G3 Beige PowerMac), Sparc processors, Malta boards, and MIPS architectures.
Magnum, bộ tích phân ARM và baseboard, bộ xử lý PXA270, máy tính bảng N800 và N810, vv
QEMU cho phép người dùng thực hiện nhiều lệnh phức tạp, hỗ trợ nhiều định dạng hình ảnh đĩa và cung cấp khả năng truy cập trực tiếp vào thiết bị máy chủ.
Những tính năng chính của phần mềm QEMU:
- Tạo máy ảo dựa trên trình biên dịch nhị phân động
- Hỗ trợ nhiều thiết bị phần cứng
- Có khả năng xử lý nhiều lệnh phức tạp từ người dùng
- Hỗ trợ nhiều định dạng ảnh đĩa
- Truy cập trực tiếp vào thiết bị máy chủ
The xv6 operating system is built on Ubuntu, and to successfully build this OS, users must install QEMU This can be accomplished by executing the following command in the terminal: `sudo apt-get install qemu-kvm qemu/virt-manager virt-viewer libvirt-bin`.
Hình 8: Cài đặt phần mềm Qemu trên ubuntu.
Lập lịch trong Xv6
Mỗi CPU xử lý 1 bộ lập lịch.
Hình 9: Mô tả quan hệ chuyển đổi giữa các tiến trình trong một CPU
Quá trình chuyển đổi giữa các tiến trình trong Xv6 được mô tả qua hình 9, bao gồm việc chuyển từ luồng kernel của tiến trình hiện tại đến luồng trình lập lịch của CPU và ngược lại Hai hàm chính thực hiện quá trình này là hàm Sched, dùng để đưa tiến trình yêu cầu vào trình lập lịch, và hàm Scheduler, giúp chuyển tiến trình từ bộ lập lịch sang tiến trình tiếp theo được xử lý.
Bộ lập lịch xv6 áp dụng chính sách lập lịch đơn giản theo hình thức quy đổi vòng tròn, trong đó các tiến trình sẽ được thực hiện tuần tự và quay trở lại tiến trình đầu tiên Mỗi tiến trình được lập lịch trong khoảng thời gian khoảng 10ms.
