Báo Cáo Hệ Điều Hành Nhúng Đề Tài Triển Khai Thuật Toán Lập Lịch Phản Hồi Hàng Đợi Đa Cấp.pdf

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 (3.03 MB, 44 trang )

<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

<b> TRƯỜNG ĐẠI H C BÁCH KHOA HÀ N I </b>Ọ ỘTRƯỜNG ĐIỆN – ĐIỆN TỬ

<b>BÁO CÁO </b>

<b>HỆ ĐIỀU HÀNH NHÚNG </b>

ĐỀ<b> TÀI: TRI N KHAI THU T TOÁN L P L CH PH N H</b>Ể Ậ Ậ Ị Ả <b>ỒI HÀNG ĐỢI ĐA CẤP </b>

<b>Người hướng dẫn </b> TS. Nguyễn Thanh Bình

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

<b>LỜI NĨI ĐẦU </b>

Trong kì 20222, chúng em được học mơn Hệ điều hành dưới sự hướng dẫn củathầy Nguyễn Thanh Bình, sau kì học chúng em đã học được rất nhiều kiến thức hay ngoài những kiến thức về mơn học chúng em cịn biết thêm nhiều kiến thức bổ ích trong cuộc sống.

Qua q trình học, môn học đã giúp chúng em hiểu cơ bản về chức năng và các nhiệm vụ mà hệ điều hành cần thực hiện. Hệ điều hành thực hiện ba chức năng chính sau: quản lý tài nguyên của máy tính (CPU, bộ nhớ, ổ đĩa và và các thiết bị I/O), thiết lập giao diện người dùng và thực thi và cung cấp dịch vụ cho các ứng dụng phầnmềm.Môn học đã bước đầu cung cấp cho chúng em các kiến thức về hệ thống và rèn luyện khả năng tìm hiểu các kiến thức bên ngồi. Song, do trình độ, khả năng, kiến thức cịn yếu nên chúng em cịn gặp nhiều khó khăn trong q trình học.

Trong bài tập lớn này, nhóm em tìm đã hiểu thực hiện bộ lập lịch hàng đợi phảnhồi đa cấp Multilevel Feedback Queue Scheduling (MLFQ).

Trong q trình tìm hiểu nhóm em đã cố gắng thực hiện, nhưng do kiến thức còn hạn chế vẫn nên bài tập lớn của chúng em còn nhiều chổ thiếu sót chưa hồn thiện. Nhóm em kính mong thầy có thể đóng góp và giúp chúng em đỡ khắc phục, hoàn thiệnhơn. Cuối cùng, chúng em xin chân thành cảm ơn thầy đã dạy và hướng dẫn chúng em môn học hệ điều hành trong kì này.

Nhóm chúng em chân thành cảm ơn Thầy! .

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

<b>MỤC L C </b>Ụ

LỜI NÓI ĐẦU ... 2

DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT ... 5

1.3 Mục tiêu của đề tài ... 9

CHƯƠNG 2. CƠ CỞ LÝ THUYẾT ... 11

2.1 Giới thiệu chung ... 11

2.1.1 Khái niệm tiến trình ... 11

2.1.2 Phân loại tiến trình ... 11

2.1.3 Trạng thái tiến trình ... 11

2.1.4 Khái niệm lập lịch cho CPU ... 12

2.1.5 Mục đích của lập lịch cho CPU ... 12

2.1.6 Các tiêu chuẩn của lập lịch ... 13

2.1.7 Các nguyên lý lập lịch ... 13

2.2 Các thuật toán lập lịch ... 14

2.2.1 First-Come, First-Served (FCFS) ... 14

2.2.2 Shortest-Job-First (SJF) ... 16

2.2.3 Shortest Remain Time First (SRTF) ... 20

2.2.4 Highest response Ratio Next (HRN) ... 21

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

CHƯƠNG 3. TRIỂN KHAI THUẬT TOÁN LẬP LỊCH HÀNG ĐỢI PHẢN HỒI ĐA

CẤP ... 30

3.1 Thiết kế bộ lập lịch hàng đợi phản hồi đa cấp ... 30

3.1.1 Yêu cầu thiết kế ... 30

3.1.2 Cách thức hoạt động của bộ lập lịch MLFQ ... 31

3.1.2.1. CPU xử lý một tiến trình ... 32

3.1.2.2. CPU phải xử lý nhiều tiến trình cùng lúc ... 33

3.1.2.3. Cơ chế thay đổi hàng đợi ưu tiên của tiến trình ... 36

3.2 Phần mềm Visual Studio ... 37

3.2.1 Khái quát phần mềm Visual Studio ... 37

3.2.2 Một số tính năng của phần mềm Visual Studio ... 37

3.3 Triển khai bộ lập lịch hàng đợi phản hồi đa cấp trong Visual Studio ... 38

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

<b>DANH MỤC </b>KÝ HIỆU<b> VÀ CHỮ VIẾT TẮT </b>

CPU Central Processing Unit Bộ lý trung tâm xử

FCFS First-Come, First-Server Vào trước, phục vụ trước SJF Shortest Job Next Tiến trình ngắn nhất tiếp theo SRTF Shortest Remaining Time First Thời gian còn lại ngắn nhất

MLFQ Multilevel Feedback Queue Hàng đợi phản hồi đa cấp

HRN Highest Response Ratio Next Hệ số phản hồi cao nhất tiếp theo

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

Hình 2. 7 Các mức độ ưu tiên trong thuật toán đa hàng đợi ... 26

Hình 2. 8 Mơ tả thuật toán MLFQ với cấp 3 ... 27

Hình 3. 1 Cấu trúc bộ lập lịch MLFQ ... 30

Hình 3. 2 Tiến trình được xử lý trong hàng đợi thứ nhất ... 31

Hình 3. 3 Tiến trình được xử lý trong hàng đợi thứ hai ... 31

Hình 3. 4 Mơ quá trình tả xử lý tại các hàng đợi ... 32

Hình 3. 5 Mơ q trình tả xử lý tại hàng đợi ưu tiên thứ hai ... 32

Hình 3. 6 Mơ q trình tả xử lý tại hàng đợi ưu tiên thứ ba ... 33

Hình 3. 7 Mơ q trình tả xử lý tiến trình khi có tiên cao độ ưu hơn ... 33

Hình 3. 8 Mơ q trình tả xử lý tiến trình khi có tiên độ ưu thấp hơn ... 34

Hình 3. 9 Tiến trình trong hàng đợi ưu tiên thấp hơn vượt quá thời gian ... 34

Hình 3. 10 Tiến trình thay đổi hàng đợi ưu tiên ... 35

Hình 3. 11 Phần mềm Visual Studio ... 35

Hình 4. 1 Nhập dữ liệu đầu vào... 47

Hình 4. 2 Tiến trình khi ở hàng đợi thứ nhất ... 47

Hình 4. 3 Các tiến trình đang được thực thi hàng ở đợi thứ nhất ... 48

Hình 4. 4 Các tiến trình khi ở hàng đợi thứ hai ... 49

Hình 4. 5 Các tiến trình lần lượt thực thi ở hàng đợi thứ hai ... 49

Hình 4. 6 Các tiến trình khi ở hàng đợi thứ ba ... 50

Hình 4. 7 Các tiến trình lần lượt được thực thi ở hàng đợi thứ ba ... 51

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

Hình 4. 8 Các tiến trình đang chờ ở hàng đợi thứ hai ... 51

Hình 4. 9 Đẩy tiến trình P5 lên hàng đợi thứ nhất ... 52

Hình 4. 10 Các tiến trình đang chờ thực thi ở hàng đợi thứ ba ... 52

Hình 4. 11 Đẩy tiến trình P2 lên hàng đợi thứ hai ... 53

Hình 4. 12 Chương trình đang thực hiện ... 54

Hình 4. 13 Chương trình sau khi kết thúc việc xử lý ... 55

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

<b>DANH MỤC BẢNG BIỂU </b>

Bảng 2. 1: Tiến trình thực hiện với FCFS ... 15

Bảng 2. 2: Tiến trình thực hiện với SJF ... 17

Bảng 2. 3: Tiến trình thực hiện với SRTF ... 20

Bảng 2. 4: Tiến trình thực hiện với Priority Scheduling ... 22

Bảng 2. 5: Tiến trình thực hiện với RR ... 24

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

<b>CHƯƠNG 1. MỞ ĐẦU </b>

<b>1.1 Giới thiệu chung </b>

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 để cho các chương trình ứng dụng khác chạy trên nó. Với chức năng 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 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 hệ thống máy tính điện tử.

Một trong những chức năng quan trọng của hệ điều hành là quản lý CPU. Trong mơi trường xử lý đa chương trình, 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 các hệ phân chia thời gian (time-sharing) là chuyển đổiCPU qua lại giữa các tiến trình một cách thường xuyên để nhiều người sử dụng có thể tương tác cùng lúc với từng chương trình trong quá trình lý. xử

Để thực hiện được mục tiêu 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ệnnhiệm vụ 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 điềuphối là bộ điều phối (dispatcher). Bộ phân phối sẽ chịu trách nhiệm chuyển đổi ngữ cảnh và trao CPU cho tiến trình được chọn bởi bộ điều phối để xử lý.

Có nhiều loại giải thuật để lập lịch CPU, mỗi loại đều có ưu, nhược điểm riêng. Vì vậy, nhóm em chọn dùng giải thuật lập lịch phản hồi đa cấp để kết hợp linh hoạt các giải thuật, tận dụng tối ưu các ưu điểm và loại bỏ các nhựơc điểm của mỗi giải thuật nhằm điều hòa các tiêu chuẩn của lập lịch,

Lập lịch là cách tổ chức các tiến trình thực hiện một cách hợp lý, đảm bảo các tiến trình được thực hiện kịp thời. Mỗi một khoảng thời gian nhất định, máy tính chỉ thực hiện một tiến trình. Khi có nhiều tiến trình cần xử lý, bộ lập lịch có chức năng phân bổ, sắp xếp thứ tự các tiến trình.

Một vấn đề khác đặt ra là khi có nhiều tiến trình đều mong muốn lý cùng một xửthời điểm thì nên thực hiện tiến trình nào trước, tiến trình nào sau, khi đó cần một cơ chế để điều phối các tiến trình.

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

Giải thuật lập lịch hàng đợi phản hồi đa cấp là một giải thuật được sử dụng rất phổ biến đối với các hệ điều hành hiện nay. Nhóm chúng em thực hiện mơ giải thuật để quan sát và hiểu rõ hơn về cách thực hiện của giải thuật.

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

<b>CHƯƠNG 2. CƠ CỞ LÝ THUYẾT </b>

<b>2.1 Giới thiệu chung </b>

2.1.1 Khái niệm tiến trình

Một tiến trình được định nghĩa là một thực thể chương trình đang được chạy trong hệ thống, chiếm dụng tài nguyên của hệ thống (Thời gian sử dụng CPU, bộ nhớ,…) Ví dụ, một web server chạy trong thiết bị là một tiến trình, hoặc một chương trình soạn thảo văn bản đang chạy trong thiết bị cũng là một tiến trình.

2.1.2 Phân loại tiến trình

− Tiến trình tuần tự (MS_DOS): là các tiến trình mà điểm khởitạo của nó là điểmkết thúc của tiến trình trước đó

− Tiến trình song song (uniprocesser và multiprocessor): là các tiến trình mà điểm khởi tạo của tiến trình này mằn ở 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

− 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 cần thiết và giờ CPU.

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

− Đợ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 dữ liệu vào/ra, đợi tài nguyên bổ sung...). 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 mình, các tiến trình sẽ tuân thủ theo sơ đồ thực hiện sau:

Sửdụng CPU Sử dụng CPU Sử dụng CPU Bắt đầu

Đợi I/O Đợi I/OHình 2. 2 Sơ đồ thực hiện tiến trình

Kết thúc

2.1.4 Khái niệm lập lịch cho CPU

Lập lịch cho CPU là cơ chế để chọn tiến trình phải được thực hiện tiếp theo và phân CPU cho bổ tiến trình đó. Tác này vụ được thực hiện bởi bộ lập lịch CPU hoặc bộ lập lịch ngắn hạn. Mỗi tiến trình ở trạng thái sẵn sàng được gắn một thứ tự ưu tiên dựa vào các yếu tố sau: 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.

Lập lịch cho CPU là cơ sở của các hệ điều hành đa chương trình. Trong môi trường hệ điều hành đa nhiệm, bộ phận điều phối tiến trình có nhiệm vụ xem xét và quyết định khi nào thì dừng tiến trình hiện tại để thu hồi processsor và chuyển processor cho tiến trình khác. Và khi đã có processor thì chọn tiến trình ở trạng thái sẵn sàng để cấp processor cho nó.

2.1.5 Mục đích của lập lịch cho CPU Cơ chế lập lịch cần đạt được các mục tiêu sau:

− Đúng đắn, nghĩa là cơ chế lập lịchcầnphục vụ các tiến trình một cách “cơng bằng”, tránh tình huống có tiến trình bị rơi vào tình trạng chờ vơ hạn.

− Đảm bảo khả năng thông qua lớn nhất, tức là tiến tới phục vụ số lượng tiến trình nhiều nhất có thể trong một đơn vị thời gian.

− Thời gian phản ứng cần phải nhỏ nhất 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 việc sử dụng tài nguyên, cần cố gắng nâng cao hiệu suất sử dụng tài nguyên, theo đó cần ưu tiên tiến trình sử dụng tài nguyên giá thành thấp.

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

− Đảm bảo cân đối giữa thời gian trả và lời hiệu suất sử dụng tài nguyên. Cách tốt nhất để giảm thời gian trả là có tài nguyên trữ khi có yêu cầu có thể lời đủ dự đểcấp phát ngay lập tức, nhưng điều đó cũng dẫn tới lãng phí tài ngun. − Cần quan tâm các tiến trình đang sử dụng tài ngun quan trọng, tránh tình trạng

tiến trình có mức ưu tiên thấp chiếm tài nguyên mà tiến trình mức ưu tiên cao hơn cần. Nếu tài nguyên đó là khơng chia sẻ thì hệ điều hành cần tạo điều kiện để tiến trình giải phóng tài ngun nhanh nhất.

2.1.6 Các tiêu chuẩn của lập lịch

− CPU utilization: Giữ CPU bận nhiều nhất có thể. Việc sử dụng CPU có thể từ 0 đến 100%.

− Throughput: Nếu CPU bận thực thi các quá trình thì công việc đang được thực hiện. Thước đo của công việc là số lượng tiến trình được hồn thành trên một đơn vị thời gian gọi là thông lượng (throughput). Thông lượng càng lớn càng tốt. − Turnaround time: Khoảng thời gian từ thời điểm gửi tiến trình tới khi tiến trình

❖ Điều phối preemptive: Nguyên lý này cho phép một tiến trình khi nhận được CPU sẽ có quyền độc chiếm CPU đến khi hồn tất xử lý hoặc tự giải phóng CPU. Khi đó quyết định điều phối sẻ xảy ra các trường hợp sau.

• Khi một tiến trình chuyển từ trạng thái đang chạy sang trạng thái sẵn sàng (ví dụ:khi xảy ra ngắt)

• Khi một tiến trình chuyển từ trạng thái chờ sang trạng thái sẵn sàng (ví dụ: khi hồn thành I / O)

• Khi một tiến trình chuyển từ trạng thái đang chạy sang trạng thái chờ (ví dụ: do kết quả của một yêu cầu I / O hoặc yêu cầu wait() để kết thúc một tiến trình con) • Khi một tiến trình kết thúc.

Các nguyên lý preemptive dễ cài đặt thuật tốn. Tuy nhiên lại khơng thích hợp cho hệ thống tổng quát nhiều người dùng.Vì nếu cho tiến trình thời gian chiếm giữ CPU tùy ý thì sẻ ngăn cản quá trình lý xử của các tiến trình cịn lại.

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

❖ Điều phối nonpreemptive: Ngược với nguyên lý preemptive,điều phối theo nguyên lý nonpreemptive cho phép tạm dừng hoạt động của tiến trình đang sẵn sàng lý. xửKhi một tiến trình nhận CPU nó vẫn được sử dụng CPU cho đến khi hồn tất hoặc tựnguyện giải phóng CPU, nhưng mộttiến trình khác có độ ưu tiên cao hơn có thểdành quyền sử dụng CPU của tiến trình ban đầu. Như vậy tiến trình có thể 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:

Các thuật toán điều phối theo nguyên tắc nonpreemption ngăn cản tình trạng một tiến trình độc chiếm CPU.

<b>2.2 Các thuật toán lập lịch</b>

2.2.1 First-Come, First-Served (FCFS)

Giải thuật lập lịch first come, first serve (FCFS) hiểu đơn giản là: đến trước thì được phục vụ trước, tiến trình nào yêu cầu CPU trước thì sẽ được cấp phát CPU trước,tiến trình yêu cầu CPU sau thì phải đợi tiến trình hiện tại hồn thành. Với điều này, nó ứng dụng nonpreemptive mode tức là một tiến trình sẽ chiếm CPU cho- đến khi nào nó giải phóng CPU, bằng cách kết thúc hay yêu cầu nhập/xuất xảy ra.

Hình 2. 3 Thuật tốn FCFS

- Ví dụ minh hoạ:

Ta có ba tiến trình được tuần tự đưa vào với các tên gọi là P<small>1 </small>P P<small>2 3 </small>và Burst time của chúng lần lượt là 24 3 3. Ta có các dữ liệu đầu vào cụ thể như bảng sau:

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

Bảng 2. 1: Tiến trình thực hiện với FCFS

<b>Process Burst time P<small>1 </small></b> 24

Ứng dụng biểuđồ Gantt:

<b>TH1. Thứ tự</b> vào của các tiến trình là P<small>1 </small>P<small>2 </small>P<small>3 </small>

Như vậy, xuất phát từ bên trái, ta sẽ nạp P vào để xử lý Khởi điểm, mốc thời<small>1 </small> . gian luôn luôn mặc định bằng 0. Vì trong dữ liệu từ bảng thì P chiếm 24, tức là một<small>1 </small>

đoạn khá lớn. Sau đó, tiến trình tiếp theo sẽ được đưa vào, với burst time của P<small>2 </small>bằng 3, tức là trên biểu đồ Gantt, ta lấy 24 + 3 = 27. Sau khi P2 hồn thành, nó sẽ đưa tiếp P<small>3 </small>

vào, và P<small>3 </small>chiếm 3 nên trên đây, ta lấy tiếp 27 + 3 = 30. Như vậy, giản đồ đã cung cấpcho ta một cái nhìn trực quan nhằm minh họa cụ thể burst time của lần lượt các tiến trình P<small>1 </small>P<small>2 </small>P .<small>3</small>

Tiếp theo là xác định thời gian đợi của từng tiến trình. Chúng ta có thể căn cứ vào con số bên trái của từng tiến trình trong giản đồ bên trên. Như vậy: thời gian đợi lần lượt của P<small>1 </small>P<small>2 </small>P<small>3 </small>là 0 24 27. Bước cuối cùng của thuật toán, là xác đó định thời gian đợi trung bình của cả q trình. Ta có thời gian đợi trung bình là: (0 + 24 + 27) / 3 = 17.

<b>TH2. Thứ tự</b> vào của các tiến trình là P2 P3 P1

Ta xác định được thời gian đợi ở lần này của từng tiến trình P<small>2 </small>P P<small>3 1 </small>sẽ là 0 3 6(căn cứ vào con số bên trái của từng tiến trình). Ta có thể xác định thời gian đợi trung bình: (0 + 3 + 6) / 3 = 3.

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

Con số đã giảm đi rất nhiều so với ban đầu. Như vậy, với thuật tốn FCFS thì thời gian đợi trung bình khơng sẽ phải lúc nào cũng tối ưu nhất cho ta mà còn tùy thuộcvào thứ tự vào của các tiến trình.

Và do thuật tốn FCFS này ứng dụng nonpreemptive, nên nó sẽ đặc biệt phiền hà khi sử dụng trong những hệ thống chia sẻ thời gian. Vì mỗi lần thực hiện, nó u cầutồn quyền sử dụng CPU, và điều này sẽ gây nên khó dễ khăn cho hệ thống nếu có mộtngười dùng nạp q nhiều tiến trình mà các tiến trình đó có burst time lớn trong phiên sử dụng của mình.

− Ưu điểm:

• Đơn giản, dễ hiểu.

• Giữ cho CPU thực hiện liên tục các tiến trình. • CPU không phân bị phối lại (khơng bị ngắt).

• 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:

• Thời gian chờ trung bình (Waiting time) cao.

• Throughput CPU thấp vì FCFS chỉ xử lý được một tiến trình trong một thờigian.

• Respone time và Turnaround time của các tiến trình đến sau dài phụ thuộc nhiều vào thời gian thực hiện của tiến trình đếntrước nó.

• Là một thuật toán lập lịch cho CPU sau khi tiến trình đã được cấp phát cho CPU, nó khơng bao sẽ giờ giải phóng CPU cho đến khi nó kết thúc q trình thực thi.

• 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 FCFS nên hiệu quả khơng cao.

• Thờigian đợi không tối ưu phụ thuộc vào thứ tự của các tiến trình. 2.2.2 Shortest-Job-First (SJF)

Một hướng giải quyết khác cho vấn đề điều phối tiến trình CPU là thuật tốn shortest-job-first (SJF). Khi CPU được cấp, nó sẽ đưa vào tiến trình có chiều dài burst time nhỏ nhất để xử lý.

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

Nếu trong các tiến trình cần nạp vào có 2 tiến trình giống nhau burst time, nó vềsẽ áp dụng thuật tốn FCFS để giải quyết vấn đề này. Lấy một ví dụ về SJF, ta có bảngcác tiến trình cần nạp vào như hình bên dưới, với quy ước các burst time của lần lượt các tiến trình cần nạp vào có đơn vị đồng nhất là milisecond.

Bảng 2. 2: Tiến trình thực hiện với SJF

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

Thuật toán SJF đã được chứng minh là sẽ cho ra thời gian chờ trung bình cho các tiến trình cần xử lý với một số con tối thiểu nhất. Bằng cách chuyển cách tiến trình ngắn hơn lên trước các tiến trình tốn thời gian dài, nó đã giảm một cách đáng kể thời gian chờ cho các tiến trình ngắn, kéo theo giảm rõ rệt thời gian chờ trung bình. Vấn đề khó khăn thực sự đối với giải thuật SJF này đó là việc xác định độ dài tiếp theo cần đưa vào để CPU xử lý.

Ta có thể sử dụng phương pháp trung bình hàm mũ (exponential averaging) có cơng thức dưới đây để dự đoán thời gian sử dụng CPU (CPU burst) với giả thiết nhữngCPU burst càng mới càng phản ánh gần hành vi của tiến trình trong tương lai:

𝑟<small>𝑛+1 </small>= 𝛼𝑡<small>𝑛 </small>+ 1 ( − 𝛼)𝑟<small>𝑛</small>, 0 ≤ 𝛼 ≤ 1

Với

t

<small>n</small>là dài độ của CPU burst thứ n và

t

<small>n+1</small>là giá trị dự đoán cho CPU burst tiếp theo.

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

Hình 2. 5 Dự đoán độ dài của CPU burts tiếp theo

Để hiểu hơn phương pháp trung bình hàm mũ, chúng ta có thể mởrộng cơng thức cho

Với SJF, thuật tốn này đồng thời có thể ở trạng thái preemptive hoặcnonpreemptive. Sự chọn lựa xảy ra khi có một tiến trình mới được đưa vào danh sáchsẵn sàng trong khi một tiến trình khác đang xử lý. Tiến trình mới có thể sỡ hữu một yêu cầu thời gian sử dụng CPU cho lần tiếp theo (CPU-burst) ngắn hơn thời gian cịn lại mà tiến trình hiện hành cần xử lý. Giải thuật nonpreemptive SJF sẽ dừng hoạt động của tiếntrình hiện hành, trong khi giải thuật preemptive sẽ cho phép tiến trình hiện hành tiếp tụcxử lý.

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">

− Ưu điểm:

• Thời gian chờ đợi trung bình (Waiting time) ưu tối nhất so với các giải thuật cịn lại.

• Thờigian xử lý của các tiến trình có thời gian xử lý nhỏ thấp.

• 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.

• Cung cấp thơng lượng (Throughput) tối đa trong hầu hết các trường hợp.• Đố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

• 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. • Tiến trình có thời gian thực thi dài có thể bị trì hỗn vơ hạn định nếu các tiến

trình có thời gian thực thi ngắn liên tục vào

• Khơng thích hợp cho môi trường time-sharing khi không dùng preemption (Các tiến trình CPU bound có “độ ưu tiên” thấp, nhưng một tiến trình khơng thực hiện I/O có thể độc chiếm CPU nếu nó là tiến trình đầu tiên vào hệ thống) 2.2.3 Shortest Remain Time First (SRTF)

Giải thuật preemtive SJF còn được gọi là giải thuật Shortest-remaining-time- first. 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 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ật 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ũngphả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. Để hiểu rõ hơn về vấn đề này, chúng em đưa ra ví bên dụ dưới:

</div><span class="text_page_counter">Trang 21</span><div class="page_container" data-page="21">

Bảng 2. 3: Tiến trình thực hiện với SRTF

Giản đồ Gantt thể hiện kết quả của thuật toán SJF với cơ chế preemptive nhưsau:

Ta thấy trong hình, P được bắt đầu ở giây thứ 0, và quan sát dữ liệu đầu vào, ta<small>1 </small>

thấy nó đồng thời cũng là tiến trình duy nhất vào đầu tiên. Tiến trình P<small>2 </small>tiến vào ở giây thứ 1. Thời gian đợi cho P là 7 ms, lớn hơn nhiều so với P<small>1 2 </small>(P<small>2 </small>chỉ chiếm 4 ms). Suyrộng ra, ta có tổng thời gian chờ cho ví dụ này là [(10-1) + (1-1) + (17-2) + (5- 3)]/4=26/4=6.5 ms.

− Ưu điểm:

• Thời gian chờ đợi (Waiting time), tồn tại trong hệ thống của mỗi tiến trình đều ngắn.

• CPU đạt thơng lượng (Throughput) cao.

• Tránh được một tiến trình thời gian thực hiện lớn độc chiếm CPU. • Thờigian xử lý của tiến trình có thời gian nhỏ thấp.

− Nhược điểm:

• Việc cài đặt thuật tốn khá phức tạp.

• Cần quản lý chặt chẽ việc điềuphối các tiến trình.

• Trong việc tính tốn thời gian thực hiện cịn lại của tiến trình. • Thờigian đợi các tiến trình có thời gian lý dài rất xử lớn.2.2.4 Highest response Ratio Next (HRN)

Nguyên tắc Highest response Ratio Next (HRN) dùng để khắc phục một số nhược điểm trong nguyên tắc SJF, đặc biệt sự q ưu tiên các bài tốn có thời gian thực

</div><span class="text_page_counter">Trang 22</span><div class="page_container" data-page="22">

hiện ngắn. HRN là nguyên tắc khơng hốn đổi và mức ưu tiên động, theo đó mức ưu tiên của tiến trình phụ thuộc khơng chỉ thời gian cần thực hiện nó mà cịn cả thời gian nó phải chờ được phục vụ.

Cơng thức tính tốn như sau: p = (tw + ts)/ts Trong đó:

• tw thời gian chờ.• ts thời gian thực thi.

Dễ thấy mức ưu tiên càng cao khi thời gian thực hiện càng ngắn hoặc khi thời gian chờ càng lớn.

2.2.5 Priority Scheduling

Thuật toán SJF là một trường hợp đặc biệt của thuật toán lập lịch ưu tiên chung. Một mức độ ưu tiên được liên kết với mỗi quá trình và CPU được phân bổ cho q trình có mức độ ưu tiên cao nhất. Các tiến trình ưu tiên bằng nhau được lên lịch theo thứ tự FCFS. Thuật toán SJF chỉ đơn giản là một thuật toán tiên trong ưu đó mức độ ưu tiên (p) là nghịch đảo của CPU burst tiếp theo. CPU burst càng lớn thì mức độ ưu tiên càng thấp và ngược lại.

Lưu ý rằng mức độ ưu tiên thường được biểu thị bằng một số dải số cố định, chẳng hạn như đến hoặc 0 7 0 đến 4,095. Tuy nhiên, khơng có thỏa thuận chung nào vềviệc 0 là tiên cao ưu nhất hay thấp nhất. Một số tài liệu sử dụng số thấp để biểu thị mức độ ưu tiên thấp; một số khác sử dụng số thấp cho mức độ ưu tiên cao. Trong báo cáo, chúng em giả định rằng các số thấp hơn thể hiện mức độ ưu tiên cao hơn.

Ví dụ, hãy xem xét tập hợp các tiến trình sau, được giả định là đã đến tại thời điểm 0 theo thứ tự P1, P2, ···, P5, với thời lượng CPU burst được tính bằng mili giây:

Bảng 2. 4: Tiến trình thực hiện với Priority Scheduling

<b>Process Arrival Time Burst Time </b>

</div>