Báo cáo bài tập lớn: Xây dựng chương trình mô phỏng một số các giải thuật lập lịch CPU | Môn Hệ điều hành - Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61552889
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN ĐIỆN TỬ - VIỄN THÔNG BÁO CÁO
BÀI TẬP LỚN HỆ ĐIỀU HÀNH Đề tài:
XÂY DỰNG CHƯƠNG TRÌNH MÔ PHỎNG MỘT SỐ CÁC GIẢI
THUẬT LẬP LỊCH CPU.
Giáo viên hướng dẫn: TS. Nguyễn Thanh Bình Sinh viên thực hiện:
Hoàng Văn Thịnh – 20214100 Kiều Cao Kỳ – 20192954 lOMoAR cPSD| 61552889 Mục lục
MỞ ĐẦU ......................................................................................................................................... 3
1.Đề tài ....................................................................................................................................... 3
2.Mục tiêu của đề tài:................................................................................................................. 3
3.Nội dung đề tài........................................................................................................................ 3
CHƯƠNG I: CƠ SỞ LÝ THUYẾT ................................................................................................ 4
1. Tiến trình: .............................................................................................................................. 4
1.1. Khái niệm: .................................................................................................................... 4
1.2. Quản lý tiến trình: ......................................................................................................... 5
1.3. Các trạng thái của tiến trình: ......................................................................................... 5
1.4. Cơ chế điều phối độc quyền và không độc quyền ........................................................ 6
2. Lập lịch CPU ......................................................................................................................... 7
2.1. Khái niệm giờ CPU: ..................................................................................................... 7
2.2. Mục đích: ...................................................................................................................... 7
2.3. Khái niệm lập lịch cho CPU: ........................................................................................ 7
CHƯƠNG II: PHÂN TÍCH THIẾT KẾ HỆ THỐNG ..................................................................... 8
1. Mô hình cài đặt thuật toán ..................................................................................................... 8
2. Thuật toán .............................................................................................................................. 8
2.1. First Come First Serve (FCFS) ..................................................................................... 8
2.2. Shortest Job First (SJF) ................................................................................................. 9
2.3. Shortest Remain Time First (SRTF) ............................................................................. 9
2.4. Round Robin (RR) ...................................................................................................... 10
2.5. Priority ........................................................................................................................ 10
CHƯƠNG III: TRIỂN KHAI GIẢI THUẬT ................................................................................ 11
1. Môi trường làm việc ............................................................................................................ 11
2. Triển khai và kết quả............................................................................................................ 11
2.1. First Come First Serve ................................................................................................ 11
2.2. Shortest Job First (SJF) ............................................................................................... 12
2.3. Shortest Remain Time First (SRTF) ........................................................................... 14
2.4. Round Robin(RR) ....................................................................................................... 17
2.5. Priority ........................................................................................................................ 19 lOMoAR cPSD| 61552889
3. Đánh giá kết quả .................................................................................................................. 21
CHƯƠNG IV: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................. 22
1. Kết luận ................................................................................................................................ 22
2. Hướng phát triển .................................................................................................................. 22 MỞ ĐẦU 1. Đề tài
Xây dựng chương trình mô phỏng một số các giải thuật lập lịch CPU.
2. Mục tiêu của đề tài:
• Nghiên cứu về tiến trình, cơ chế hoạt động của các tiến trình.
• Nghiên cứu về cơ chế hoạt động, nguyên lý của các thuật toán lập lịch CPU (FCFS, SJF, SRTF, RR, Priority).
• Xây dựng chương trình mô phỏng các giải thuật trên bằng ngôn ngữ C/C++.
3. Nội dung đề tài
Tìm hiểu lý thuyết, xây dựng một chương trình mô phỏng hoạt động của các giải thuật
lập lịch CPU. Qua đó nghiên cứu thêm về tiến trình, hệ điều hành. lOMoAR cPSD| 61552889
CHƯƠNG I: CƠ SỞ LÝ THUYẾT 1. Tiến trình: 1.1. Khái niệm:
Tất cả các máy tính hiện đại đều có thể thực hiện nhiều việc cùng một lúc. Trong khi
thực hiện chương trình của người sử dụng, máy tính còn có thể đọc dữ liệu từ đĩa và đưa
ra màn hình hoặc máy in. Trong môi trường đa chương trình (multiprogramming system),
một CPU có thể chuyển từ chương trình này sang chương trình khác, thực hiện mỗi chương
trình trong khoảng 1% hoặc 1/10 mili giây. Nếu nói chính xác, thì tại một thời điểm, CPU
chỉ thực hiện được một chương trình. Nhưng nếu xét trong khoảng thời gian phần trăm
giây thì CPU có thể thực hiện nhiều công việc. Để hổ trợ hoạt động đa nhiệm, hệ thống
máy tính cần phải có khả năng thực hiện nhiều tác vụ xử lý đồng thời nhưng việc điều
khiển hoạt động song hành ở cấp độ phần cứng là rất khó khăn.Vì vậy,các nhà thiết kế hệ
điều hành đề xuất một mô hình song hành giả lập bằng cách chuyển đổi bộ xử lý qua lại
giữa các chương trình để duy trì hoạt động của nhiều chương trình tại cùng một thời
điểm.Trong mô hình này các chương trình của hệ thống được tổ chức thành các tiến trình(process).
Có thể chia thành hai loại: tiến trình tuần tự (MS_DOS) và tiến trình song song(
uniprocesser và multiprocesser). Tiến trình tuần tự : là các tiến trình mà điểm khởi tạo
của nó là điểm kết thúc của tiến trình trước đó. Tiến trình song song : là các tiến trình mà
điểm khởi tạo của tiến trình này nằm ở thân của các tiến trình khác, tức là có thể khởi tạo
một tiến trình mới khi các tiến trình trước đó chưa kết thúc. Trong này tiến trình song song
được chia thành nhiều loại: ̣
• Tiến trình song song độc lập
• Tiến trình song song có quan hệ thông tin
• Tiến trình song song phân cấp
Trong mô hình này hệ điều hành phải giải quyết vấn đề cấp phát tài nguyên cho các
tiến trình. Các tiến trình hoạt động song song sử dụng chung tài nguyên theo nguyên tắc
lần lượt, mỗi tiến trình sau một khoảng thời gian chiếm giữ tài nguyên phải tự động trả lại
tài nguyên cho tiến trình kia. Công việc phân phối tài nguyên cho các tiến trình gọi là lập lOMoAR cPSD| 61552889
lịch cho CPU. Bao gồm các giải thuật First Come First Serve (FCFS), Shortest Job First
(SJF), Shortest Remain Time First (SRTF), Round Robin (RR), Priority,…
1.2. Quản lý tiến trình:
Tất cả các hệ điều hành đa chương, từ các hệ điều hành đơn người sử dụng đến các
hệ điều hành có thể hỗ trợ đến hàng ngàn người sử dụng, đều phải xây dựng dựa trên khái
niệm tiến trình. Vì thế, một yêu cầu quan trọng trong thiết kế hệ điều hành là thành phần
quản lý tiến trình của hệ điều hành phải đáp ứng tất cả những gì liên quan đến tiến trình:
 Hệ điều hành phải cho phép thực hiện nhiều tiến trình đồng thời để khai
thác tối đa thời gian xử lý của processor nhưng cũng cung cấp được thời gian hồi đáp hợp lý.
 Hệ điều hành phải cấp phát tài nguyên để tiến trình hoạt động một cách hiệu
quả với một chính sách hợp lý nhưng không xảy ra tình trạng tắc nghẽn trong hệ thống.
 Hệ điều hành có thể được yêu cầu để hỗ trợ truyền thông liên tiến trình và
người sử dụng tạo ra tiến trình.
Hệ điều hành phải có nhiệm vụ tạo ra tiến trình, điều khiển sự hoạt động của tiến trình và kết thúc tiến trình.
Một số hệ điều hành phân biệt hai khái niệm tiến trình và tiểu trình. Tiến trình liên quan
đến quyền sở hữu tài nguyên, tiểu trình liên quan đến sự thực hiện chương trình.
Trong các hệ điều hành đa chương, có nhiều tiến trình tồn tại trên bộ nhớ chính, các tiến
trình này luân phiên giữa hai trạng thái: sử dụng processor và đợi thực hiện vào/ra hay một
vài sự kiện nào đó xảy ra.
1.3. Các trạng thái của tiến trình:
Trạng thái của tiến trình tại một thời điểm được xác định bởi hoạt động hiện thời
của tiến trình tại thời điểm đó. Trong quá trình sống, một tiến trình thay đổi trạng thái do
nhiều nguyên nhân như : phải chờ một sự kiện nào đó xảy ra, hay đợi một thao tác nhập/xuất
hoàn tất, buộc phải dừng hoạt động do đã hết thời gian xử lý …
Tại một thời điểm một tiến trình có thể nhận một trong các trạng thái sau đây:
• New: tiến trình đang được tạo lập.
• Running: các chỉ thị của tiến trình đang được xử lý.
• Waiting: tiến trình chờ được cấp phát tài nguyên, hay chờ một sự kiện xảy ra.
• Ready: tiến trình chờ được cấp phát CPU để xử lý.
• Halt: tiến trình hoàn tất xử lý
Các trạng thái của tiến trình được biểu diễn qua sơ đồ sau: lOMoAR cPSD| 61552889
Hình 1: Các trạng thái của tiến trình
1.4. Cơ chế điều phối độc quyền và không độ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
các tiến trình. Hệ điều hành có thể thực hiện cơ chế điều phối theo nguyên lý độc quyền hoặc không độc quyền:
- Điều phối độc quyền: Nguyên lý điều phối độc quyền cho phép một tiến
trình 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 xử lý (Running) sang trạng thái
chờ (Waiting) (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
Các giải thuật độc quyền thường đơn giản và dễ cài đặt. Tuy nhiên, chúng
thường không thích hợp với hệ thống tổng quát, nhiều người dùng, vì nếu
cho phép một tiến trình có quyền xử lý bao lâu tùy ý, có nghĩa là tiến trình
này đã giữ cho CPU một khoảng thời gian không xác định, có thể ngăn cản
những tiến trình còn lại trong hệ thống có một cơ hội để xử lý.
- Điều phối không độc quyền: Ngược lại 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 đang xử lý. Khi 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. 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ó thể bị tạm dừng hoạt động bất cứ lúc nào mà
không được báo trước, để tiến trình khác xử lý. Các quyết định điều phối xảy ra khi:
• Khi tiến trình chuyển từ trạng thái đang xử lý (Running) sang trạng thái chờ (Waiting).
• Khi tiến trình chuyên từ tr ạng thái đang xử lý (Running) sang trạng
thái Ready (vì xảy ra một ngắt).
• Khi tiến trình chuyển từ trạng thái chờ (Waiting) sang trạng thái sẵn
sàng(Ready) (Ví dụ một thao tác nhập xuất hoàn tất).
• Khi tiến trình kết thúc. lOMoAR cPSD| 61552889
Trong các hệ thống sử dụng nguyên lý điều phối độc quyền có thể xảy ra tình trạng
các tác vụ cần thời gian xử lý ngắn phải chờ các tác vụ xử lý với thời gian rất dài hoàn tất.
Nguyên lý điều phối độc quyền thường chỉ thích hợp với các hệ xử lý theo 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 đ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 ưu tiên và phát sinh thêm chi
phí chuyển đổi qua lại giữa các tiến trình 2. Lập lịch CPU
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 động được đều
phải có sự phục vụ của CPU (để xử lý, tính toán...). Thời gian mà CPU phục vụ cho
tiến trình hoạt động được gọi là giờ CPU.
Tại mỗi thời điểm duy nhất, chỉ có một tiến trình được phân phối giờ CPU để hoạt
động (Thực hiện các lệnh của mình). 2.2. Mục đích:
• Sử dụng CPU (lớn nhất): Hệ thống phải làm cho CPU hoạt động nhiều nhất có thể.
• Thông lượng (lớn nhất): Hệ thống phải hoàn thành được nhiều tiến trình nhất
trong một đơn vị thời gian.
• Thời gian hoàn thành (nhỏ nhất): Khoảng thời gian từ thời điểm tiến trình đến
hệ thống tới khi quá trình hoàn thành là nhỏ nhất.
• Thời gian chờ đợi (nhỏ nhất): Tổng thời gian tiến trình chờ đợi trong hàng đợi
sẵn sàng của hệ thống là nhỏ nhất.
• Thời gian đáp ứng (nhỏ nhất): Thời gian từ lúc gửi yêu cầu đến khi nhận được
phản hồi đầu tiên từ hệ thống là nhỏ nhất.
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 nhau mà chỉ có thể dung hòa chúng ở mức độ nào đó.
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 các
trạng thái (thực chất là các khối điều khiển tiến trình) để ghi nhận tình trạng sử dụng tài
nguyên và trạng thái tiến trình.
Như vậy, lập lịch cho CPU có nghĩa là tổ chức một hàng đợi các tiến trình sẵn sàng
để phân phối giờ CPU cho chúng dựa trên độ ưu tiên của các tiến trình; sao cho hiệu suất
sử dụng CPU là tối ưu nhất. lOMoAR cPSD| 61552889
Mỗi tiến trình ở trạng thái sẵn sàng sẽ được gắn với một thứ tự ưu tiên. Thứ tự ưu
tiên này được xác định dựa vào các yếu tố như: thời điểm hình thành tiến trình, thời gian
thực hiện tiến trình, thời gian kết thúc tiến trình.
CHƯƠNG II: PHÂN TÍCH THIẾT KẾ HỆ THỐNG
1. Mô hình cài đặt thuật toán Thuật toán xử lý chung
Việc cài đặt thuật toán được mô phỏng theo cách làm việc của CPU và tất cả các thuật
toán con đều theo mô hình thuật toán này:
• Tiến trình ở đầu danh sách được ưu tiên xử lý trước và nó chiếm dụng CPU tại thời điểm đó.
• Việc đi kèm theo là xem xét thời gian xử lý các tiến trình đã hết chưa. Nếu
đã hết thì nghĩa là đã hoàn thành việc xử lý, ngược lại thì tiếp tục xử lý theo thuật toán.
• Xong mỗi chu kỳ của CPU (1 quantum) thì cập nhập lại danh sách để loại
bỏ các tiến trình đã hoàn thành hay sắp xếp hay thêm các tiến trình mới vào. 2. Thuật toán
2.1. First Come First Serve (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).
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. lOMoAR cPSD| 61552889
Hình 2: Thuật toán FCFS
Ưu điểm của thuật toán này là giờ CPU không bị phân phối lại (không bị ngắt) và
chi phí thực hiện thấp nhất (vì không phải thay đổi thứ tự ưu tiên phục vụ, thứ tự ưu tiên là
thứ tự của tiến trình trong hàng đợi).
Nhược điểm của thuật toán này là thời gian trung bình chờ phục vụ của các tiến
trình là như nhau (không kể tiến trình ngắn hay dài), do đó dẫn tới ba điểm sau: • Thời
gian phục vụ trung bình sẽ tăng vô hạn khi hệ thống tiếp cận với khả năng phục vụ của mình.
• Nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đợi trung bình cũng tăng theo.
• Khi có tiến trình dài, ít bị ngắt thì các tiến trình khác phải chờ đợi lâu hơn.
2.2. Shortest Job First (SJF)
Một tiếp cận khác đối với việc định thời CPU là giải thuật định thời công việc ngắn
nhất nhất trước (Shortest Job First). Giải thuật này tham chiếu tới mỗi độ dài quá trình của
chu kỳ CPU tiếp theo cho quá trình sau đó. Khi CPU sẵn dùng, nó được gán tới quá trình
có chu kỳ CPU kế tiếp ngắn nhất. Nếu hai quá trình có cùng chiều dài chu kỳ CPU kế tiếp,
định thời FIFO được sử dụng.
Hình 3: Thuật toán SJF
2.3. Shortest Remain Time First (SRTF)
Tương tự như SJF nhưng thuật toán này, độ ưu tiên thực hiện các tiến trình dựa vào
thời gian cần thiết để thực hiện nốt tiến trình (bằng tổng thời gian trừ đi thời gian đã thực
hiện). Như vậy, trong thuật toán này cần phải thường xuyên cập nhập thông tin về thời gian
đã thực hiện của tiến trình.
Đồng thời, chế độ phân bổ lại giờ CPU cũng phải được áp dụng nếu không sẽ làm
mất tính ưu việt của thuật toán. Ưu điểm:
• Thời gian chờ đợi, tồn tại trong hệ thống của mỗi tiến trình đều ngắn. Nhược điểm: lOMoAR cPSD| 61552889
• Việc cài đặt thuật toán khá phức tạp.
• Cần quản lý chặt chẽ việc điều phối các tiến trình.
• Quản lý thời gian đến của mỗi tiến trình. 2.4. Round Robin (RR)
Đối với thuật giải RR, mỗi tiến trình trước khi bắt đầu được đưa vào CPU xử lý, sẽ
được cấp phát cho một đơn vị thời gian chiếm dụng CPU nhất định.Ta gọi chung giá trị
hằng số này với cái tên là quantum. Điểm khác biệt của RR với FCFS đó là RR tuân thủ
theo cơ chế không độc quyền (preemtive). Như vậy, khi một tiến trình sử dụng hết thời
gian quantum mà nó được cấp phát, thì dù vẫn còn phải xử lý tiếp, phần dư của nó cũng sẽ
được chuyển về phía sau trong danh sách hàng đợi. Sau đó, căn cứ vào danh sách Ready
list đã nạp trước đó, CPU sẽ lấy tiếp tiến trình kế cận để đưa vào xử lý, với mức quantum
là như nhau cho tất cả các tiến trình. Ưu điểm:
• Công bằng trong việc chia sẻ thời gian CPU giữa các tiến trình.
• Đáp ứng nhanh cho yêu cầu ngắn và trung bình.
• Cho phép ưu tiên giữa các tiến trình.
• Cấu trúc đơn giản và dễ hiểu. Nhược điểm:
• Hiệu suất giảm đối với các tiến trình dài hạn.
• Có thể gây ra hiện tượng "lặp lại" (trường hợp tiến trình không kết thúc trong quantum).
• Không xử lý hiệu quả các tiến trình ưu tiên cao hơn.
• Thời gian chờ có thể tăng khi số lượng tiến trình lớn hoặc quantum quá nhỏ. 2.5. Priority
Trong giải thuật này, mỗi tiến trình được gắn với một số hiệu ưu tiến (số nguyên),
số hiệu ưu tiên càng nhỏ thì mức độ ưu tiên càng cao. CPU sẽ được phân phối cho tiến
trình có độ ưu tiên cao nhất trước. Ưu điểm:
• Quản lý hiệu quả: Tối ưu hóa việc phân công tài nguyên để đảm bảo rằng
các nhiệm vụ quan trọng hoặc khẩn cấp được thực hiện trước.
• Xử lý các tình huống khẩn cấp: Giải thuật này cho phép xử lý và đáp ứng
các tình huống khẩn cấp một cách nhanh chóng, hiệu quả và kịp thời. •
Đơn giản và dễ triển khai: Có nhiều phương pháp và cấu trúc dữ liệu có
thể được sử dụng để thực hiện giải thuật ưu tiên, từ danh sách ưu tiên đơn
giản đến hàng đợi ưu tiên phức tạp. Nhược điểm
• Tiến trình có độ ưu tiên thấp phải chờ đợi rất lâu (thậm chí không thực hiện). lOMoAR cPSD| 61552889
• Trong trường hợp có 2 hay nhiều tiến trình có cùng mức độ ưu tiên và cần
xử lý đồng thời thì giải thuật này chưa cung cấp được giải pháp.
CHƯƠNG III: TRIỂN KHAI GIẢI THUẬT
1. Môi trường làm việc
Lập trình bằng ngôn ngữ C/C++, Phần mềm Dev-C và giao diện console để hiển thị kết quả.
2. Triển khai và kết quả
2.1. First Come First Serve Thuật toán:
• Bước 1: Nhập vào số lượng tiến trình vào hàng đợi sẵn sàng
• Bước 2: Với mỗi tiến trình trong hàng đợi sẵn sàng, gán tên và thời gian quay vòng
(Turnarround time) cho chúng.
• Bước 3: Đặt thời gian chờ đợi cho tiến trình thứ nhất là 0 và thời gian chiếm giữ
CPU cũng như thời gian quay vòng của tiến trình. • Bước 4: Với mỗi tiến trình
trong hàng đợi, cần tính toán
a). Waiting time (n) = waiting time (n-1) + Burst time (n-1)
b). Turnaround time (n)= waiting time(n)+Burst time(n)
• Bước 5: Tính các giá trị :
a) Average waiting time = Total waiting Time / Number of process
b) Average Turnaround time = Total Turnaround Time / Number of process • Bước 6: Kết thúc 1. #include 2. #include 3. int main() { 4.
int bt[20], wt[20], tat[20], i, n; 5. float wtavg, tatavg; 6.
printf("\nEnter the number of processes -- "); 7. scanf("%d", &n); 8. for(i = 0; i < n; i++) { 9.
printf("\nEnter Burst Time for Process %d -- ", i); 10. scanf("%d", &bt[i]); 11. } lOMoAR cPSD| 61552889 12. wt[0] = wtavg = 0; 13. tat[0] = tatavg = bt[0]; 14. for(i = 1; i < n; i++) { 15. wt[i] = wt[i-1] + bt[i-1]; 16. tat[i] = tat[i-1] + bt[i]; 17. wtavg = wtavg + wt[i]; 18. tatavg = tatavg + tat[i]; 19. } 20.
printf("\t PROCESS \tBURST TIME \t WAITING TIME\t TURNAROUND TIME\n"); 21. for(i = 0; i < n; i++) 22.
printf("\n\t P%d \t\t %d \t\t %d \t\t %d", i, bt[i], wt[i], tat[i]); 23.
printf("\nAverage Waiting Time -- %f", wtavg/n); 24.
printf("\nAverage Turnaround Time -- %f", tatavg/n); 25. getch(); 26. return 0; 27. }
Hình 4: Kết quả cho thuật toán FCFS
2.2. Shortest Job First (SJF) Thuật toán:
• Bước 1: Nhập vào số lượng tiến trình vào hàng đợi sẵn sàng lOMoAR cPSD| 61552889
• Bước 2: Với mỗi tiến trình trong hàng đợi sẵn sàng, gán tên và CPU burst time.
• Bước 3: Khởi động hàng đợi với Burst time của các tiến trình được sắp xếp theo thứ tự tăng dần.
• Bước 4: Đặt waiting time của tiến trình thứ nhất là 0 và Turnaround tiem của nó bằng Burst time
• Bước 5: Với mỗi tiến trình trong hàng đợi, cần tính toán
a). Waiting time (n) = waiting time (n-1) + Burst time (n-1)
b). Turnaround time (n)= waiting time(n)+Burst time(n)
• Bước 6: Tính các giá trị :
a) Average waiting time = Total waiting Time / Number of process
b) Average Turnaround time = Total Turnaround Time / Number of process • Bước 7: Kết thúc 1. #include 2. int main() {
3. int p[20], bt[20], wt[20], tat[20], i, k, n, temp; 4. float wtavg, tatavg; 5.
6. printf("\nEnter the number of processes -- "); 7. scanf("%d", &n); 8. 9. if (n <= 0) { 10.
printf("Invalid number of processes. Exiting..."); 11. return 0; 12. } 13. 14. for (i = 0; i < n; i++) { 15. p[i] = i; 16.
printf("Enter Burst Time for Process %d -- ", i); 17.
scanf("%d", &bt[i]); 18. } 19. 20. for (i = 0; i < n; i++) 21.
for (k = i + 1; k < n; k++) 22. if (bt[i] > bt[k]) { 23. temp = bt[i]; 24. bt[i] = bt[k]; 25. bt[k] = temp; 26. temp = p[i]; 27. p[i] = p[k]; 28. p[k] = temp; 29. } 30. 31. wt[0] = wtavg = 0; 32. tat[0] = tatavg = bt[0]; lOMoAR cPSD| 61552889 33. 34. for (i = 1; i < n; i++) { 35.
wt[i] = wt[i - 1] + bt[i - 1]; 36. tat[i] = tat[i - 1] + bt[i]; 37. wtavg += wt[i]; 38. tatavg += tat[i]; 39. } 40.
printf("\n\t PROCESS \tBURST TIME \t WAITING TIME\t TURNAROUND TIME\n"); 41. for (i = 0; i < n; i++) 42.
printf("\n\t P%d \t\t %d \t\t %d \t\t %d", p[i], bt[i], wt[i],tat[i]); 43.
printf("\nAverage Waiting Time -- %f", wtavg / n); 44.
printf("\nAverage Turnaround Time -- %f", tatavg / n); 45. 46. return 0; 47. }
Hình 5: Kết quả cho thuật toán SJF
2.3. Shortest Remain Time First (SRTF) 1. #include 2. 3. #include 4. 5. using namespace std; 6.
7. void findWaitingTime(int processes[][3], int n, int wt[]) { 8. lOMoAR cPSD| 61552889 9. int rt[n]; 10.
11. for (int i = 0; i < n; i++) 12. 13. rt[i] = processes[i][1]; 14.
15. int complete = 0, t = 0, minm = INT_MAX, short_index = 0; 16. 17. bool check = false; 18. 19. while (complete != n) { 20.
21. for (int j = 0; j < n; j++) { 22.
23. if (processes[j][2] <= t && rt[j] < minm && rt[j] > 0) { 24. 25. minm = rt[j]; 26. 27. short_index = j; 28. 29. check = true; 30. 31. } 32. 33. } 34. 35. if (!check) { 36. 37. t++; 38. 39. continue; 40. 41. } 42. 43. rt[short_index] -= 1; 44. 45. minm = rt[short_index]; 46. 47. if (minm == 0) 48. 49. minm = INT_MAX; 50. lOMoAR cPSD| 61552889
51. if (rt[short_index] == 0) { 52. 53. complete += 1; 54. 55. check = false; 56. 57. } 58. 59. int fint = t + 1; 60. 61. wt[short_index] = fint - processes[short_index][1] - processes[short_index][2]; 62.
63. if (wt[short_index] < 0) 64. 65. wt[short_index] = 0; 66. 67. t++; 68. 69. } 70. 71. } 72.
73. void findTurnAroundTime(int processes[][3], int n, int wt[], int tat[]) { 74.
75. for (int i = 0; i < n; i++) 76.
77. tat[i] = processes[i][1] + wt[i]; 78. 79. } 80.
81. void findavgTime(int processes[][3], int n) { 82. 83. int wt[n], tat[n]; 84.
85. findWaitingTime(processes, n, wt); 86.
87. findTurnAroundTime(processes, n, wt, tat); 88.
89. cout << "Processes Burst Time Waiting Time Turn-Around Time" << endl; 90.
91. int total_wt = 0, total_tat = 0; 92.
93. for (int i = 0; i < n; i++) { 94. lOMoAR cPSD| 61552889 95. total_wt += wt[i]; 96. 97. total_tat += tat[i]; 98.
99. cout << " " << processes[i][0] << "\t\t"
<< processes[i][1] <<
"\t\t" << wt[i] << "\t\t" << tat[i] << endl; 100. 101. } 102.
103. cout << "\nAverage waiting time = " << (float)total_wt / n << endl; 104. 105.
cout << "Average turn around time
= " << (float)total_tat / n << endl; 106. 107. } 108. 109. int main() { 110. 111.
int proc[][3] = {{1, 6, 1}, {2, 8, 1}, {3, 7, 2}, {4, 3, 3}}; 112. 113.
int n = sizeof(proc) / sizeof(proc[0]); 114. 115. findavgTime(proc, n); 116. 117. return 0; 118. 119. }
Hình 6: Kết quả cho thuật toán SRTF 2.4. Round Robin(RR) Thuật toán:
• Bước 1: Nhập vào số lượng tiến trình vào hàng đợi sẵn sàng và quantum time hoặc time slice.
• Bước 2: Với mỗi tiến trình trong hàng đợi sẵn sàng, gán tên và CPU burst time. lOMoAR cPSD| 61552889
• Bước 3: Tính số lượng time slides cho mỗi tiến trình trong đó,
a)Số lượng time slides của P(n) = burst time (n)/time slide
b)Nếu burst time (n) < time slide thì số lượng time slides = 1
• Bước 4: Giả thiết hàng đợi vòng tròn, hãy tính
a). Waiting time (n) = waiting time (n-1) + Burst time (n-1) + khoảng thời gian khác
nhau khi tiến trình (n-1) rời khỏi CPU
b). Turnaround time (n)= waiting time(n)+Burst time(n)+ khoảng thời gian khác
nhau khi tiến trình (n) rời khỏi CPU
• Bước 5: Tính các giá trị
a) Average waiting time = Total waiting Time / Number of process
b) Average Turnaround time = Total Turnaround Time / Number of process • Bước 6: Kết thúc 1. #include 2. 3. int main() {
4. int i, j, n, bu[10], wa[10], tat[10], t, ct[10], max; 5. float awt = 0, att = 0, temp = 0; 6.
7. printf("Enter the number of processes -- "); 8. scanf("%d", &n); 9. 10.
printf("\nEnter the size of time slice -- "); 11. scanf("%d", &t); 12. 13. for (i = 0; i < n; i++) { 14.
printf("\nEnter Burst Time for process %d -- ", i + 1); 15. scanf("%d", &bu[i]); 16. ct[i] = bu[i]; 17. } 18. 19. max = bu[0]; 20. for (i = 1; i < n; i++) 21. if (max < bu[i]) 22. max = bu[i]; 23. 24.
for (j = 0; j < (max / t) + 1; j++) 25. for (i = 0; i < n; i++) 26. if (bu[i] != 0) 27. if (bu[i] <= t) { 28. tat[i] = temp + bu[i]; lOMoAR cPSD| 61552889 29. temp = temp + bu[i]; 30. bu[i] = 0; 31. } else { 32. bu[i] = bu[i] - t; 33. temp = temp + t; 34. } 35. for (i = 0; i < n; i++) { 36. wa[i] = tat[i] - ct[i]; 37. att += tat[i]; 38. awt += wa[i]; 39. } 40. 41. printf("\n\tPROCESS\tBURST TIME\tWAITING TIME\tTURNAROUND TIME\n"); 42. for (i = 0; i < n; i++) 43.
printf("\t%d\t%d\t\t%d\t\t%d\n", i + 1, ct[i], wa[i], tat[i]); 44. 45.
printf("\nThe Average Turnaround time is -- %f", att / n); 46.
printf("\nThe Average Waiting time is -- %f", awt / n); 47. 48. return 0; 49. }
Hình 7: Kết quả cho thuật toán RR 2.5. Priority Thuật toán: lOMoAR cPSD| 61552889
• Bước 1: Nhập vào số lượng tiến trình vào hàng đợi sẵn sàng.
• Bước 2: Với mỗi tiến trình trong hàng đợi sẵn sàng, gán tên và CPU burst time.
• Bước 3: Sắp xếp hàng đợi sẵng sàng theo thứ tự ưu tiên
• Bước 4: Thiết lập waiting time của tiến trình đầu tiên bằng 0 và burst time của nó bằng turnaround time
• Bước 5: Với mỗi tiến trình trong hàng đợi sẵn sàng, tính
a). Waiting time (n) = waiting time (n-1) + Burst time (n-1)
b). Turnaround time (n)= waiting time(n)+Burst time(n)
• Bước 6: Tính các giá trị
a) Average waiting time = Total waiting Time / Number of process
b) Average Turnaround time = Total Turnaround Time / Number of process • Bước 7: Kết thúc 1. #include 2. 3. int main() {
4. int p[20], bt[20], pri[20], wt[20], tat[20], i, k, n, temp; 5. float wtavg, tatavg; 6.
7. printf("Enter the number of processes --- "); 8. scanf("%d", &n); 9. 10. for (i = 0; i < n; i++) { 11. p[i] = i; 12.
printf("Enter the Burst Time & Priority of Process %d --- ", i); 13.
scanf("%d %d", &bt[i], &pri[i]); 14. } 15. 16. for (i = 0; i < n; i++) 17.
for (k = i + 1; k < n; k++) 18. if (pri[i] > pri[k]) { 19. temp = p[i]; 20. p[i] = p[k]; 21. p[k] = temp; 22. 23. temp = bt[i]; 24. bt[i] = bt[k]; 25. bt[k] = temp; 26. 27. temp = pri[i]; 28. pri[i] = pri[k]; 29. pri[k] = temp; 30. } 31.