Các tiêu chí lập lịch CPU ✅ 2023
Thủ Thuật về Các tiêu chí lập lịch CPU Mới Nhất
Bùi Phương Thảo đang tìm kiếm từ khóa Các tiêu chí lập lịch CPU được Cập Nhật vào lúc : 2022-11-28 02:50:10 . Với phương châm chia sẻ Kinh Nghiệm về trong nội dung bài viết một cách Chi Tiết 2022. Nếu sau khi đọc tài liệu vẫn ko hiểu thì hoàn toàn có thể lại Comment ở cuối bài để Ad lý giải và hướng dẫn lại nha.Lập trình mô phỏng những phương pháp lập lịch cho CPU
Bạ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
KHOA CÔNG NGHỆ THÔNG TIN
…o0o…
BÀI TẬP LỚN MÔN
NGUYÊN LÝ HỆ ĐIỀU HÀNH
ĐỀ TÀI
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
GV HƯỚNG DẪN: NGUYỄN THANH HẢI
…HÀ NỘI 2012…
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
…o0o…
BÀI TẬP LỚN MÔN
NGUYÊN LÝ HỆ ĐIỀU HÀNH
ĐỀ TÀI
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
2
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô
phỏng những phương pháp lập lịch cho CPU.
CHƯƠNG 1. CƠ SỞ LÝ THUYẾT......................................................................4
1.1. GIỚI THIỆU .............................................................................................5
1.1.1. Mục tiêu lập lịch..............................................................................5
1.1.2. Các đặc điểm của tiến trình..............................................................5
1.1.3. Điều phối không độc quyền và
điều phối độc quyền........................6
1.2. CÁC KHÁI NIỆM CƠ BẢN.........................................................................7
1.2.1. Khái niệm giờ CPU..........................................................................7
1.2.2. Các trạng thái của tiến trình liên quan đến giờ CPU........................7
1.2.3. Khái niệm lập lịch cho CPU.............................................................8
1.3. CÁC THUẬT TOÁN LẬP
LỊCH..................................................................9
1.3.1. First Come First Served(FCFS)........................................................9
1.3.2. Round robin(RR)...........................................................................10
1.3.3. Shortest Job First(SJF)...................................................................11
1.3.4. Shortest Remain Time(SRT)..........................................................11
CHƯƠNG 2. CÀI ĐẶT THUẬT
TOÁN............................................................12
2.1. MÔ HÌNH CÀI ĐẶT THUẬT TOÁN............................................................12
2.1.1. Cấu trúc tài 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
Nhóm 15 _ ĐH HTTT1 _ K6
LỜI NÓI ĐẦU
Hệ điều hành là phần gắn bó trực tiếp với phần cứng và là môi trường tự nhiên thiên nhiên để cho
những chương
trình ứng dụng khác chạy trên nó. Với hiệu suất cao quản lý và phân phối
tài nguyên một cách hợp lý, đồng thời giả lập một máy tính mở rộng và tạo giao
diện tiện lợi với người tiêu dùng, hệ điều hành là một thành phần then chốt không thể
thiếu được trong mỗi một khối mạng lưới hệ thống máy tính điện tử.
Một trong những hiệu suất cao quan trọng của hệ điều hành là quản lý CPU. Trong
môi trường tự nhiên thiên nhiên xử lý đa chương, hoàn toàn có thể xảy ra tình huống nhiều tiến trình đồng thời sẵn
sàng để xử lý. Mục tiêu của những hệ
phân chia thời gian(time-sharing) là quy đổi
CPU qua lại Một trong những tiến trình một cách thường xuyên để nhiều người tiêu dùng có
thể tương tác cùng lúc với từng chương trình trong quá trình xử lý.
Để thực hiện được tiềm năng này, hệ điều hành phải lựa chọn tiến trình được xử
lý tiếp theo. Bộ điều phối sẽ sử dụng một giải thuật điều phối thích hợp để thực hiện
trách nhiệm này. Một thành phần khác của hệ điều hành cũng tiềm ẩn trong công tác thao tác
điều phối là bộ điều phối(dispatcher). Bộ
phân phối sẽ phụ trách quy đổi
ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý.
Vì những quyền lợi lớn lao mà giải thuật điều phối CPU đem lại và để tìm hiểu kĩ
hơn về nguyên tắc hoạt động và sinh hoạt giải trí của chúng, chúng em sẽ cùng nhau tìm hiểu, nghiên
cứu đề tài: Lập trình mô phỏng những 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 những thuật toán: First Come First Served(FCFS), Round Robin(RR),
Shortest Job
First(SJF), Shortest Remain Time(SRT).
-
Chỉ ra được ưu và nhược điểm cả những thuật toán lập lịch CPU.
Mặc dù nhóm 15 chúng em đã nỗ lực tìm hiểu kiến thức và kỹ năng, tài liệu về những phương
pháp lập lịch CPU, cũng như nỗ lực trong quá trình hoàn thiện bài tập. Song do
kiến thức và kỹ năng, trình độ của chúng em còn nhiều hạn chế nên chắc như đinh không tránh khỏi
những sai sót. Chúng em mong sự hướng dẫn của thầy giáo và góp ý của những bạn, để
chúng em hoàn toàn có thể hoàn thiện hơn bài tập.
Chương 1.
CƠ SỞ LÝ THUYẾT
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
1.1. Giới thiệu
1.1.1.
Mục tiêu lập lịch
Bộ điều phối không đáp ứng cơ chế, mà đưa ra những quyết định. Các hệ điều
hành xây dựng nhiều kế hoạch rất khác nhau để thực hiện việc điều phối, nhưng tựu
chung cần đạt được những tiềm năng sau:
- Sự công minh: những tiến trình chia sẻ CPU một cách công minh không còn tiến
trình nào phải đợi vô hạn để được cấp phát CPU.
- Tính hiệu suất cao: 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 trả lời cho những tương tác của
người tiêu dùng.
- Thời gian lưu lại trong khối mạng lưới hệ thống: cực tiểu hóa thời gian hoàn tất những tác vụ xử
lý theo lô.
- Thông lượng tối đa: cực lớn hóa số việc làm đượ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ả những tiềm năng kể trên vì bản thân
chúng có sự xích míc với nhau mà chỉ hoàn toàn 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 và sinh hoạt giải trí của những tiến trình là một vấn đề rất phức tạp, đòi hỏi hệ
điều hành khi xử lý và xử lý phải xem xét nhiều yếu tố rất khác nhau để hoàn toàn có thể đạt được
những tiềm năng đề ra. Một số đặc tính của tiến trình cần phải quan tâm như tiêu
chuẩn điều phối:
- Tính hướng xuất/nhập của tiến trình: Khi một tiến trình được nhận CPU, chủ
yếu nó chỉ sử dụng CPU đến khi phát sinh một yêu cầu nhập xuất. Hoạt động
của
những tiến trình như vậy thường gồm có nhiều lượt sử dụng CPU, mỗi lượt trong một
thời gian khá ngắn.
- Tính hướng xử lý của tiến trình: Khi một tiến trình được nhận CPU, nó có
khuynh hướng sử dụng CPU đến khi hết thời gian dành riêng cho nó? Hoạt động của những
tiến trình như vậy thường gồm có một số trong những ít lượt sử dụng CPU, nhưng mỗi lượt
trong thuở nào gian đủ dài.
- 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 trả lời tức thời đối với những yêu cầu của tớ, trong khi những tiến
5
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
trình của những tác vụ được xử lý theo lô nói chung hoàn toàn có thể trì hoãn trong thuở nào gian
hoàn toàn có thể đồng ý được.
- Độ ưu tiên của tiến trình: Các tiến trình hoàn toàn có thể được phân cấp theo một số trong những tiêu
chuẩn đánh giá nào đó, một cách hợp lý, những tiến trình quan trọng hơn(có độ ưu tiên
cao hơn) cần phải ưu tiên cao hơn.
- Thời gian đã sử dụng CPU
của tiến trình: một số trong những quan điểm ưu tiên chọn những
tiến trình đã sử dụng CPU nhiều thời gian nhất vì kỳ vọng chúng sẽ cần ít thời gian
nhất để hoàn tất và rời khỏi khối mạng lưới hệ thống. Tuy nhiên cũng luôn có thể có quan điểm nhận định rằng những
tiến trình nhận được CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất,
do vậy ưu tiên chọn chúng.
- Thời gian còn sót lại tiến trình cần để hoàn tất: Có thể giảm thiểu thời gian chờ
trung bình của những tiến trình bằng phương pháp cho những tiến trình cần ít thời
gian nhất để
hoàn tất được thực hiện trước. Tuy nhiên đáng tiếc là rất hiếm lúc biết được tiến
trình cần bao nhiêu thời gian nữa để kết thúc xử lý.
1.1.3.
Đ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 quy đổi CPU giữa
những tiến trình. Hệ điều hành những thể thực hiện cơ chế điều phối theo nguyên tắc độ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 được 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 những 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 tắc độc quyền, điều phối theo
nguyên tắc không độc quyền được cho phép tạm dừng hoạt động và sinh hoạt giải trí 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 hoàn toà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
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
thể bị tạm dừng hoạt động và sinh hoạt giải trí bất thần 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 bị
blocked.
- 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ờ (blocked) sang trạng thái 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.
Trong những khối mạng lưới hệ thống sử dụng nguyên tắc điều phối độc quyền hoàn toàn có thể xảy ra tình
trạng những tác vụ cần thời gian xử lý ngắn phải chờ 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 phù phù hợp với những hệ xử lý theo
lô.
Đối với những khối mạng lưới hệ thống tương tác (time sharing), những hệ thời gian thực (real time),
nên phải sử dụng nguyên tắc điều phối không độc quyền để những tiến trình quan trọng
có thời cơ trả lời kịp thời. Tuy nhiên thực hiện hiện điều phối theo nguyên tắc 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 ngân sách khi quy đổi CPU qua lại Một trong những 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
độ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 và sinh hoạt giải trí được gọi là giờ CPU.
Tại mỗi thời điểm nhất, chỉ có một tiến trình được phân phối giờ CPU để hoạt
động(thực hiện những lệnh của tớ).
1.2.2.
Các trạng thái của tiến trình liên quan đến giờ CPU
Trong chính sá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
đến giờ CPU gồm có:
Running
Ready
Waiting
7
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những 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ẵn sàng(ready): là trạng thái mà tiến trình được phân phối đầy đủ mọi tài
nguyên thiết yếu và đang chờ giờ CPU.
Thực hiện(running): là trạng thái mà tiến trình được phân
phối đầy đủ mọi tài
nguyên thiết yếu và giờ CPU.
Đợi(waiting): là trạng thái tiến trình không thực hiện được vì thiếu một vài điều
kiện nào đó(đợi tài liệu vào/ra, đợi tài nguyên tương hỗ update…). Khi sự kiện mà nó chờ
đợi xuất hiện, tiến trình sẽ quay lại trạng thái sẵn sàng.
Như vậy, trong suốt thời gian tồn tại của tớ, những tiến trình sẽ tuân thủ theo sơ
đồ thực hiện sau:
Sử dụng CPU
Bắt đầu
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 những tiến trình
Một tiến trình đang trong trạng thái thực hiện, nó hoàn toàn có thể rời khỏi trạng thái bởi
một trong ba nguyên do:
- Tiến trình đã hoàn thành xong việc làm, 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ờ đón 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 riêng 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 rất khác nhau, khối mạng lưới hệ thống thường tổ chức
những từ trạng thái(thực chất là những khối điều khiển tiến trình) để ghi nhận tình trạng
8
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
sử dụng tài nguyên và trạng thái
tiến trình. Các từ trạng thái được tổ chức theo kiểu
hàng đợi như sau:
Read
Queue
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 những tiến trình
Như vậy lập lịch cho CPU nghĩa là tổ chức một hàng đợi những tiến trình sẵn
sàng để phân phối giờ CPU cho chúng nhờ vào độ ưu tiên của những tiến trình; sao
cho hiệu suất sử dụng CPU là tối ưu nhất.
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 nhờ vào những 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.
1.3. Các Thuật Toán Lập Lịch
1.3.1.
First Come First Served(FCFS)
Trong thuật toán này, độ ưu tiên phục vụ tiến trình địa thế căn cứ vào thời điểm hình
thành tiến trình. Hàng đợi những 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 tới lúc kết thúc hoặc bị ngắt.
Ready list
A
B
C
CPU
9
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
Hình 1.4: Điều phối FIFO
Ưu điểm: giờ CPU không biến thành phân phối lại(không biến thành ngắt) và ngân sách 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: là thời gian trung
bình chờ phục vụ của những 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 chờ trung bình sẽ tăng vô hạn khi khối mạng lưới hệ thống tiếp cận tới hạn kĩ năng
phục vụ của tớ.
- Nếu độ phát tán thời gian thực hiện tiến trình tăng thì thời gian chờ đón trung
bình cũng tăng theo.
- Khi có tiến trình dài, ít bị ngắt thì những tiến trình khác phải chờ đón lâu hơn.
1.3.2. Round robin(RR)
Giải thuật định thời luân phiên (round-robin scheduling algorithm-RR) được
thiết kế đặc biệt cho khối mạng lưới 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 Một trong những 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 tán vòng
quanh hàng đợi sẵn sàng, cấp phép CPU tới mỗi quá trình có khoảng chừng thời gian tối đa
bằng một định mức thời gian.
Để setup định thời RR, tất cả chúng ta quản lý hàng đợi sẳn sàng như một hàng đợi
FIFO của những 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ó một chu kỳ luân hồi 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. trái lại, nếu
chu kỳ luân hồi CPU của quá trình đang chạy dài hơn thế nữa 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
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
A
B
C
A
CPU
Hình 1.5: Round Robin
Ưu điểm :
- Các quá trình sẽ được luân phiên cho CPU xử lý nên thời gian chờ đón sẽ ít.
- Đối với những quá trình liên quan đến nhập/xuất người tiêu dùng thì rất hiệu suất cao.
- Việc setup không thật phức tạp.
Nhược điểm :
- Thời gian chờ đón trung bình của thuật toán RR thường là quá dài.
- Nếu thời gian định mức cho việc xử lý quá lớn thì RR thành FIFO.
- Nếu
thời gian quá ngắn so với thời gian xử lý của một tiến trình trong danh
sách hàng đợi thì việc chờ đón và xử lý luân phiên sẽ nhiều.
- Qui tắc là định mức thời gian nên dài hơn thế nữa 80% chu kỳ luân hồi CPU.
1.3.3. 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 việc làm
ngắn nhất trước (shortest-job-first-SJF). Giải thuật này gán tới mỗi quá trình chiều
dài của chu kỳ luân hồi 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ỳ luân hồi CPU sau đó ngắn nhất. Nếu hai quá trình có cùng chiều dài
chu kỳ luân hồi CPU sau đó, định thời FIFO được dùng. Chú ý rằng thuật ngữ phù hợp hơn
là chu kỳ luân hồi CPU sau đó ngắn nhất (shortest next CPU burst) vì định thời được thực
hiện bằng phương pháp xem xét chiều dài của chu kỳ luân hồi CPU sau đó của quá trình hơn là toàn
bộ chiều dài của nó.
Ưu điểm :
- Giải thuật được xem là tối ưu, thời gian chờ đón trung bình giảm.
- Tận dụng hết năng lực của CPU.
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 setup tại cấp định thời CPU
ngắn vì không còn cách nào để biết chiều dài chu kỳ luân hồi CPU tiếp theo.
- Giải thuật SJF hoàn toàn 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òn có nhiều dị bản rất khác nhau và sẽ tối ưu hay là 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 những tiến trình
nhờ vào thời gian thiết yếu để 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 nên phải thường xuyên update
11
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
thông tin về giời gian đã thực hiện của tiến trình. Đồng thời, chính sá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 đi tình ưu việc của thuật toán.
Ưu điểm :
- Thời gian chờ
đợi,tồn tại trong khối mạng lưới hệ thống của mỗi tiến trình đều ngắn.
- Thuật toán tối ưu nhất.
Nhược điểm :
- Việc setup thuật toán khá phức tạp.
- Cần quản lý ngặt nghèo việc điều phối những tiến trình.
- Quản lý thời gian đến của mỗi tiến trình.
Chương 2.
CÀI ĐẶT THUẬT TOÁN
2.1. Mô hình setup thuật toán
2.1.1.
Cấu trúc tài liệu
Quản lý tiến trình:
Cấu trúc tài liệu đề xuất cho việc quản lý tiến trình được xây dựng thành một
cấu trúc nhằm mục đích tạo điều kiện cho
việc quản lý những tiến trình được thuận tiện và đơn giản.
Code:
struct process
int id;
int timexh;
int timeth;
;
Id: chứa số thứ tự tiến trình trong list.
timexh: thời gian xuất hiện tiến trình.
timeth: thời gian thực hiện tiến trình.
Input:
Input được tổ chức theo cấu trúc mảng nhằm mục đích tàng trữ những giá trị khi nhập những
tiến trình và là tài liệu để phục hồi lại những tiến trình nhằm mục đích để tránh những trường hợp
sai lệnh và mất tài liệu khi xử lý.
Code:
process*
input(int &n)
12
Nhóm 15 _ ĐH HTTT1 _ K6
Đề tài: Lập trình mô phỏng những phương pháp lập lịch cho CPU.
{ int i,j;
process *a,tg;
a=new process[n];
gotoxy(8,1);cout<<"Ten TT";
gotoxy(18,1);cout<<"Time XH";
gotoxy(28,1); cout<<"Time TH";
for(i=0;i
