TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA SƯ PHẠM TOÁN – TIN

NHÓM 4
BÁO CÁO TỔNG KẾT NGHIÊN CỨU CHUYÊN ĐỀ:

MÔ PHỎNG CÁC GIẢI THUẬT ĐỊNH THỜI CHO
PROCESS

NGÀNH: SƯ PHẠM
LỚP: ĐHSTIN15L2

GIẢNG VIÊN HƯỚNG DẪN: Ths. NGUYỄN THỊ THÙY LINH

Đồng Tháp, tháng 02 năm 2016


Nhóm 4: Mô phỏng các giải thuật định thời cho process

DANH SÁNH SINH VIÊN NHÓM 4
STT

MSSV

HỌ TÊN

GHI CHÚ

Nhóm trưởng
ĐT:0982.355767
E-mail:

ĐT: 0986.980565
Tô Lâm Điền
E-mail:
ĐT: 01696.390929
Huỳnh Bửu Tâm
E-mail:
ĐT: 01666.435474
Chau Sa Rath
E-mail:

1

Lê Thế Nam

2
3
4

Bảng phân công công việc:
STT

CÔNG VIỆC

1

Viết thuật toán

2

Trình bày quyển báo cáo, in ấn, ghi

đĩa CD

Lớp ĐHSTIN15L2

GHI CHÚ
Lê Thế Nam
Huỳnh Bửu Tâm
Tô Lâm Điền
Chau Sa Rath

2


Nhóm 4: Mô phỏng các giải thuật định thời cho process

MỤC LỤC

Lớp ĐHSTIN15L2

3


Nhóm 4: Mô phỏng các giải thuật định thời cho process

1. MỞ ĐẦU
Hệ điều hành là môn học quan trọng và cần thiết. Giúp người học hiểu về hệ
điều hành của máy tính, hiểu cơ chế xử lý của các tiến trình đưa vào hệ điều hành của
một máy tính điện tử bất kì. Quá trình xử lý của các tiến trình trong CPU là quá trình
quan trọng, ảnh hưởng đến tốc độ, thời gian xử lý và công việc thường ngày trên máy
tính.Vì thế, tiến trình, quan hệ giữa các tiến trình và cách điều phối tiến trình rất quan

trọng. Đặc biệt hiện nay, trong môi trường xử lý đa chương, có thể xảy ra tình huống
nhiều tiến trình đồng thời sẵn sàng để xử lý. Hiện nay em đang nhận được đề tài: mô
phỏng các giải thuật định thời cho process tiến trình chờ phân phối xử lý. Trong chiến
lược một hàng đợi này có nhiều thuật toán xử lý, nhóm đã chọn 3 thuật toán chính
FCFS, SJF, độ ưu tiên để tìm hiểu. Sau khi tìm hiểu về đề tài này giúp em hiểu thêm
vể các cơ chế điều phối tiến trình trong CPU,và cơ chế xử lý các tiến trình.

Lớp ĐHSTIN15L2

4


Nhóm 4: Mô phỏng các giải thuật định thời cho process

2. NỘI DUNG ĐỀ TÀI
2.1. Đặt vấn đề
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 ở rộng và tạo giao diện tiện
lợi với người sử 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.
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, 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 hệ phân chia thời gian (time-sharing) là chuyển đồi CPU
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 xử lý.
Để 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ện
nhiệ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ều
phối là bộ điều phối (dispatcher). Bộ điều 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ý.
Vì những lợi ích 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 của chúng, chúng em quyết định chọn đề tài: mô phỏng
các giải thuật định thời cho process.

2.2. Phương pháp giải quyết vấn đề
- Tìm hiểu rỏ về tiến trình:Tiến trình, các loại tiến trình, mô hình tiến trình,
cách thực hiện mô hình, quản lý tiến trình.
- Tìm hiểu cơ chế các chiến lược điều phối: First Come First Serve (FCFS),
Short Job First (SJF), Độ ưu tiên.
- Xây dựng chương trình mô phỏng các giải thuật đã tìm hiểu và kết quả demo
bằng ngôn ngữ lập trình C++ .

2.3. Giới thiệu tiến trình (process)
2.3.1. Tiến trình là gì?
Những hệ điều hành ban đầu cho phép chỉ một chương trình được thực thi tại
một thời điểm. Chương trình này có toàn quyền điều khiển hệ thống và có thể truy
xuất tới tất cả tài nguyên của hệ thống. Những hệ điều hành hiện đại cho phép nhiều
chương trình được nạp vào bộ nhớ và được thực thi đồng hành. Sự phát triển này yêu
cầu sự điều khiển mạnh mẽ hơn và phân chia tài nguyên nhiều hơn giữa các tiến trình
sao cho cân bằng và hiệu quả. Yêu cầu này dẫn đến khái niệm tiến trình Process .

Lớp ĐHSTIN15L2

5


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Hình
1: (a)


đa

chương với 4 chương trình
(b)Mô hình khái niệm với 4 chương trình độc lập
(c)Tại một thời điểm chỉ có1 chương trình hoạt động
Tiến trình là một chương trình đang xử lý, sở hữu một con trỏ lệnh, tập các thanh ghi
và các biến. Để hoàn thành công việc của mình, một tiến trình có thể cần đến một số
tài nguyên như CPU, bộ nhớ chính, các tập tin và thiết bị nhập/xuất.

Hình 2: Tiến trình (Process)
Cần phân biệt hai khái niệm chương trình và tiến trình. Một chương trình là
một thực thể thụ động, chứa đựng các chỉ thị điều khiển máy tính để tiến hành một
công việc nào đó; khi cho thực hiện các chỉ thị này, chương trình chuyển thành tiến
trình là một thực thể hoạt động, với con trỏ lệnh xác định chỉ thị kế tiếp sẽ thi hành,
kèm theo tập các tài nguyên phục vụ cho hoạt động của tiến trình.
Về mặt ý niệm, có thể xem như mỗi tiến trình sở hữu một bộ xử lý ảo cho riêng
nó, nhưng trong thực tế, chỉ có một bộ xử lý thật sự được chuyển đổi qua lại giữa các
tiến trình. Sự chuyển đổi nhanh chóng này được gọi là sự đa chương
(multiprogramming). Hệ điều hành chịu trách nhiệm sử dụng một thuật toán định thời
CPU để quyết định thời điểm cần dừng hoạt động của tiến trình đang xử lý để phục vụ
một tiến trình khác, và lựa chọn tiến trình tiếp theo sẽ được phục vụ. Bộ phận thực
hiện chức năng này của hệ điều hành được gọi là bộ định thời (scheduler).

Lớp ĐHSTIN15L2

6


Nhóm 4: Mô phỏng các giải thuật định thời cho process

Một hệ điều hành phức tạp hơn được mong đợi nhiều hơn trong việc thực hiện
các hành vi của người dùng. Mặc dù quan tâm chủ yếu của hệ điều hành là thực thi
chương trình người dùng, nhưng nó cũng quan tâm đến các công việc khác nhau bên
ngoài nhân. Do đó, một hệ thống chứa tập hợp các quá trình: quá trình hệ điều hành
thực thi mã hệ thống, quá trình người dùng thực thi mã người dùng. Tất cả quá trình
này có tiềm năng thực thi đồng hành, với một CPU hay nhiều CPU được đa hợp giữa
chúng. Bằng cách chuyển đổi CPU giữa các quá trình, hệ điều hành có thể làm cho
máy tính hoạt động với năng suất cao hơn.

2.3.2. Phân loại tiến trình
Các tiến trình trong hệ thống có thể chia thành hai loại:
-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 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. Tiến trình song song được chia thành nhiều loại:
+ Tiến trình song song độc lập: Các tiến trình hoạt động song song nhưng
không có quan hệ thông tin với nhau, trong trường hợp này hệ điều hành phải thiết lập
cơ chế bảo vệ dữ liệu của các tiến trình, và cấp phát tài nguyên cho các tiến trình một
cách hợp lý.

Hình 3: Mô phỏng tiến trình song song độc lập
- Tiến trình song song có quan hệ thông tin: Trong quá trình hoạt động các tiến
trình trao đổi thông tin với nhau.Hai tiến trình A và B được gọi là có quan hệ thông tin
với nhau nếu tiến trình này có gửi thông báo cho tiến trình kia. Tiến trình gửi thông
báo có thể không cần biết tiến trình nhận có tồn tại hay không? ở đâu? và đang ở giai
đoạn nào?

Lớp ĐHSTIN15L2


7


Nhóm 4: Mô phỏng các giải thuật định thời cho process

Hình 4: Mô phỏng tiến trình song song có quan hệ thông tin
- Tiến trình song song phân cấp: Trong qua trình hoạt động một tiến trình có thể
khởi tạo các tiến trình khác hoạt động song song với nó, tiến trình khởi tạo được gọi là
tiến trình cha, tiến trình được tạo gọi là tiến trình con. 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 con. Tiến trình con nhận
tài nguyên ở đâu? từ tiến trình cha hay từ hệ thống.

Hình 5: Mô phỏng tiến trình song song phân cấp
- Tiến trình song song đồng mức: Là 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.

Hình 6: Sự thực hiện đồng thời của các tiến trình trong hệ thống đơn xử lý
Lớp ĐHSTIN15L2

8


Nhóm 4: Mô phỏng các giải thuật định thời cho process

Hình 7: Sự thực hiện đồng thời của các tiến trình trong hệ thống đa xử lý

2.3.3. Các trạng thái 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á 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ý
Mỗi quá trình có thể ở một trong những trạng thái sau:

 Mới (new): quá trình đang được tạo ra
 Đang chạy (running): các chỉ thị đang được thực thi
 Chờ (waiting): quá trình đang chờ sự kiện xảy ra (như hoàn thành việc
nhập/xuất hay nhận tín hiệu)
 Sẵn sàng (ready): quá trình đang chờ được gán tới một bộ xử lý.
 Kết thúc (terminated): quá trình hoàn thành việc thực thi.
Các tên trạng thái này là bất kỳ, và chúng khác nhau ở các hệ điều hành khác
nhau. Tuy nhiên, các trạng thái mà chúng hiện diện được tìm thấy trên tất cả hệ thống.
Các hệ điều hành xác định mô tả trạng thái quá trình. Chỉ một quá trình có thể đang
chạy tức thì trên bất kỳ bộ xử lý nào mặc dù nhiều quá trình có thể ở trạng thái sẳn
sàng và chờ.

Hình 8: Lưu đồ các trạng thái của một quá trình

Lớp ĐHSTIN15L2

9


Nhóm 4: Mô phỏng các giải thuật định thời cho process

2.3.4. Chế độ xử lý của tiến trình
Để đảm bảo hệ thống hoạt động đúng đắn, hệ điều hành cần bảo vệ khỏi sự xâm
phạm của các tiến trình. Bản thâm các tiến trình cần được bảo vệ tránh khỏi sự ảnh
hưởng qua lại giữa các tiến trình. Một cách để phân biệt đó là sử dụng 2 chế độ xử lý

cho các tiến trình: chế độ xử lý đọc quyền và chế độ xử lý không đọc quyền nhờ vào sự
hổ trợ của phần cứng.

2.3.5. Các thao tác điều khiển tiến trình
2.3.5.1 Tạo lập tiến trình
Trong quá trình xử lý một tiến trình có thể tạo lập một tiến trình mới bằng cách
gọi lời gọi hệ thống tương ứng. Tiến trình gọi lới gọi hệ thống để tạo tiến trình mới
được gọi là tiến trình cha, tiến trình được tạo là tiến trình con. Mỗi tiến trình con đến
lượt nó có thể tạo tiến trình mới… quá trình này sẽ tiếp tục tạo ra cây tiến trình.

Hình 9 : Một cây tiến trình trong UNIX
Các công việc hệ điều hành cần thực hiện khi tạo lập tiến trình:
- Định danh cho tiến trinh mới phát sinh.
- Đưa tiến trình vào dánh sách quản lý của hệ thống.
- Xác định độ ưu tiên cho tiến trình.
- Tạo PCB cho tiến trình.
- Cấp phát tài nguyên ban đầu cho tiến trình.
 Khi một tiến trình tạo lập một tiến trình con,tiến trình con có thể sẽ được hệ
điều hành trực tiếp cấp phát tài nguyên hoặc được tiến trình cha cho thừa hưởng một
số tài nguyên ban đầu.
 Khi một tiến trình tạo tiến trình mới ,tiến trình ban đầu có thể xử lý theo một
trong hai khả năng sau:
- Tiến trình cho tiếp tục xử lý đồng hành với tiến trình con.
- Tiến trình cha chờ đến khi một tiến trình con nào đó hoặc tất cả các tiến trình
con có kết thúc xử lý.
Lớp ĐHSTIN15L2

10



Nhóm 4: Mô phỏng các giải thuật định thời cho process
Các hệ điều hành khác nhau có thể lựa chọn các cài đặt khác nhau để thực hiện
một thao tác lập trình một cây tiến trình.

2.3.5.2 Kết thúc tiến trình
Một tiến trình kết thúc xử lý khi nó hoàn tất chỉ thị cuối cùng và sử dụng một
lời gọi hệ thống để yêu cầu hệ điều hành hủy bỏ nó. Đôi khi một tiến trình có thể yêu
cầu hệ điều hành kết thúc xử lý của một tiến trình khác. Khi một tiến trình kết thúc, hệ
điều hành thực hiện các công việc:
 Thu hồi các tài nguyên của hệ thống đả cấp phát cho tiến trình.
 Hủy tiến trình khỏi tất cả các danh sách quản lý của hệ thống.
 Hủy bỏ PCB của tiên trình.
Hầu hết các hệ điều hành không cho phép các tiến trình con tiếp tục tồn tại nếu
tiến trình cha đả kết thúc.Trong những hệ thống như thế,hệ điều hành sẽ tự động phát
sinh một loạt các thao tác kết thúc tiến trình con.

2.4. Định thời biểu CPU
2.4.1 Giới thiệu
Trong môi trường đa chương, 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 (timesharing) là chuyển đổi CPU qua lại giữa các tiến trình một cách
thường xuyên để nhiều người 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ý.

2.4.2. Mục đích:
Sự công bằng (Fairness): Các tiến trình chia sẽ CPU một cách công bằng,
không có tiến trình nào phải chờ đợi vô hạn để được cấp phát CPU.
Tính hiệu quả (Efficiency): Hệ thống phải tận dụng được 100% thời gian
CPU.
Thời gian đáp ứng hợp lý (Response time): Cực tiểu hoá thời gian hồi đáp cho
các tương tác của người dùng.

Thời gian lưu lại trong hệ thống (Turnaround Time) : Cực tiểu hóa thời gian
hoàn tất các công việc xử lý theo lô.
Thông lượng tối đa (Throughput): Cực đại hóa số lượng công việc đượ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ả 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.4.3. Các đặc điểm của tiến trình
Điều phối hoạt động của 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 khi giải quyết phải xem xét các yếu tố khác nhau để có thể đạt được mục
tiêu đề ra. Một số đặc tính cần được quan tâm như tiêu chuẩn điều phối:

Lớp ĐHSTIN15L2

11


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Tính hướng nhập xuất của tiến trình: khi một tiến trình nhận được CPU,chủ
yếu nó chỉ sử dụng CPU cho đến khi phát sinh một yêu cầu nhập xuất. Hoạt động của
các tiến trình như thế thường bao gốm 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 nhận dược CPU, nó có
khuynh hướng sử dụng CPU đến khi hết thời gian dành cho nó. Hoạt động của tiến
trình như thế thường bao gồm một số ít lượt sử dụng CPU, nhưng mỗi lượt trong một
thời 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 hồi đáp tức thời đối với các yêu cầu của họ, trong khi các tiesn
trình của tác vụ được xử lý theo lô nói chungcos thể trì hoãn trong một thời gian chấp
nhận được.

Độ ưu tiên của tiến trình: Các tiến trình có thể được phân cấp theo một đánh
giá nào đó, một cách hợp lý, các tiến trình quan trọng hơn (có độ ưu tiên hơn) cần
được ưu tiên hơn.
Thời gian sử dụng CPU của tiến trình: Một số 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ì hy vọng chúng sẽ cần ít thời gian
nhất đẻ hoàn tất và rời khỏi hệ thống. Tuy nhiên củng có quan điểm cho rắng các 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 lại tiến trình cần để hoàn tất: có thể giảm thiểu thời gian chờ
đợi trung bình của các tiến trình bằng cách cho các 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 khi biết được tiến trình
cần bao nhiêu thời gian nữa để kết thúc xử lý.

2.4.5. Cơ chế điều phối độc quyền và không độc quyền (preemptive
/nopreemptive)
 Cơ chế điều phối độc quyền
Nguyên lý: cơ chế 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 hoà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.
 Tiến trình chuyển từ trạng thái running  blockit.
 Kết thúc tiến trình.
Các giải thuật độc quyền dễ cài đặt thuật toá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 xử lý của các tiến trình còn lại.

 Cơ chế điều phối không độc quyền.
Ngược 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 tiến trình đang sẵn sang xử lý. Khi một tiến trình
nhận CPU nó vấn được sử dụng CPU cho đến khi hoàn tất hoặc tự nguyện giải phóng
CPU, nhưng một tiế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
Lớp ĐHSTIN15L2

12


Nhóm 4: Mô phỏng các giải thuật định thời cho process
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:
 Tiến trình chuyển từ trạng thái running  blocked.
 Một tiến trình chờ trạng thái xử lý.
 Chuyển từ trạng thái chờ (blocked)  ready.
 Khi một tiến trình kết thúc.
Các thuật toán điều phối theo nguyên tắc không đọc quyến ngăn cản tình trạng
một tiến trình đọc chiếm CPU.

2.4.6. Tổ chức định thời biểu
2.4.6.1. Các loại danh sách sử dụng điều phối tiến trình
Hệ điều hành sử dụng hai loại danh sách để thực hiện điều phối các tiến trình là
danh sách sẵn sàng (ready list) và danh sách chờ đợi (waiting list).
Khi một tiến trình bắt đầu đi vào hệ thống, nó được chèn vào danh sách tác
vụ(job list). Danh sách này bao gồm tất cả các tiền trình của hệ thống. Nhưng chỉ các
tiến trình đang thường trú trong bộ nhớ chính và ở trạng thái sẵn sàng tiếp nhận CPU
để hoạt động mới được đưa vào danh sách sẵn sàng.
Bộ điều phối sẽ chọn một tiến trình trong danh sách sẵn sàng và cấp CPU cho
tiến trình đó. Tiến trình được cấp CPU sẽ thực hiện xử lý, và có thể chuyển sang trạng
thái chờ khi xảy ra các sự kiện như đợi một thao tác nhập/xuất hoàn tất, yêu cầu tài
nguyên chưa được thỏa mãn, yêu cầu tạm dừng… Khi đó tiến trình sẽ được chuyển
sang một danh sách chờ đợi.
Hệ điều hành chỉ sử dụng một danh sách sẵn sàng cho toàn hệ thống, nhưng

mỗi một tài nguyên (thiết bị ngoại vi) có một danh sách chờ đợi riêng bao gốm các
tiến trình chờ được cấp phát tài nguyên đó.

Hình 1 :Các danh sách điều phối.
Lớp ĐHSTIN15L2

13


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Quá trình xử lý của một tiến trình trải qua những chu kì chuyển đổi qua lại giữa
những danh sách sẵn sàng và danh sách chờ đợi. Sơ đồ dưới đây mô tả sự điều phối
các tiến trình dựa trên các danh sách của hệ thống.
Thoạt đầu tiến trình mới được đặt trong danh sách các tiến trình sẵn sàng (ready
list), nó sẽ đợi trong danh sách này cho đến khi được chọn để cập phát CPU và bắt xử
lý. Sau đó có thể xảy ra một trong các tình huống sau:
 Tiến trình phát sinh một yêu cầu một tài nguyên mà hệ thống chưa thể đáp
ứng, khi đó tiến trình sẽ được chuyển sang danh sách các tiến trình đang chờ tài
nguyên tương ứng.
 Tiến trình có thể bị bắt buộc tạm dừng xử lý do một lý do ngắt xảy ra, khi đó
tiến trình được đưa trở lại vào danh sách sẵn sàng để chờ được cấp CPU cho lượt tiếp
theo.
Hình
: Sơ
đồ

2

chuyển đổi giữa các danh sách định thời biểu
Trong trường hợp đầu tiên, tiến trình cuối cùng sẽ chuyển từ trạng thái blocked

sang trạng thái ready và lại được đưa trở vào danh sách sẵn sàng. Tiến trình lặp lại chu
kỳ này cho đến khi hoàn tất công việc thì đƣợc hệ thống hủy bỏ khỏi mọi danh sách
định thời biểu.

2.4.6.2. Các cấp độ điều phối.
Thực ra công việc điều phối được hệ điều hành thực hiện ở hai mức độ: Điều
phối tác vụ và điều phối tiến trình.

 Điều phối tác vụ
Quyết đinh lựa chọn tác vụ nào được đưa vào hệ thống, và nạp những tiến trình
của tác vụ đó vào bộ nhớ chính để thực hiện. Chức năng điều phối tác vụ quyết định
mức độ đa chương của hệ thống (số lượng tiến trình trong bộ nhớ chính). Khi hệ thống
tạo lập tiến trinh,hay có một tiến trình kết thúc xử lý chức năng và điều phối tác vụ có
tần suất hoạt động thấp.
Lớp ĐHSTIN15L2

14


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Để hệ thống hoạt động tốt, bộ điều phối tác vụ cần biết tính chất của tiến trình
là hướng nhập xuất hay hướng xử lý. Một tiến trình được gọi là hướng nhập xuất nếu
nó chủ yếu chỉ sử dụng CPU để thực hiện thao tác nhập xuất. Ngược lại một tiến trình
được gọi là hướng xử lý nếu nó chủ yếu chỉ sử dụng CPU để thực hiện các thao tác
tính toán. Để cân bằng hoạt động của CPU và các thiết bị ngoại vi,bộ điều phối tác vụ
nên lựa chọn các tiến trình để nạp vào bộ nhớ sao cho hệ thống là sự pha trộn hợp lý
giữa các tiến trình hướng nhập xuất và các tiến trình hướng xử lý.

 Điều phối tiến trình
Chọn một tiến trình ở trạng thái sẵn sàng (đã nạp vào bộ nhớ chính, và có đủ tài

nguyên để hoạt động) và cấp phát CPU cho tiến trình đó thực hiện. Bộ điều phối tiến
trình có tần suất hoạt động cao, sau mỗi lần xảy ra ngắt (do đồng hồ bào giờ, do các
thiết bị ngoại vi…) thường là 1 lần trong khoảng 100ms. Do vậy để nâng cao hiệu suất
của hệ thống, cần phải tăng tốc độ xử lý của bộ hệ điều phối tiến trình. Chức năng điều
phối tiến trình là một trong chức năng cơ bản, quan trọng nhất của hệ điều hành.
Trong nhiều hệ điều hành, có thể không có bộ điều phối tác vụ hoặc tách biệt
rất ít đối với bộ điều phối tiến trình. Một vài hệ điều hành lại đưa ra một cấp độ điều
phối trung gian kết hợp cả hai cấp độ điều phối tác vụ và tiến trình.

Hình 3: Cấp độ định thời biểu trung gian

2.4.7. Các chiến lược định thời biểu
Các chiến lược định thời biểu giải quyết vấn đề quyết định tiến trình nào trong
hàng đợi sẵn sàng được cấp phát CPU.

2.4.7.1. Chiến lược FCFS ( first-come, first-served-FCFS)
Giải thuật đơn giản nhất là đến trước, được phục vụ trước. Với cơ chế này, quá
trình yêu cầu CPU trước được cấp phát CPU trước. Việc cài đặt chính sách FCFS
được quản lý dễ dàng với hàng đợi FIFO. Khi một quá trình đi vào hàng đợi sẵn sàng,
PCB của nó được liên kết tới đuôi của hàng đợi. Khi CPU rảnh, nó được cấp phát tới
một quá trình tại đầu hàng đợi. Sau đó, quá trình đang chạy được lấy ra khỏi hàng đợi.
Mã của giải thuật FCFS đơn giản để viết và hiểu. Tuy nhiên, thời gian chờ đợi trung
bình dưới chính sách FCFS thường là dài.

Lớp ĐHSTIN15L2

15


Nhóm 4: Mô phỏng các giải thuật định thời cho process


Hình 11: Định thời biểu FCFS

Ví dụ: Xét tập hợp các quá trình sau đến tại thời điểm 0, với chiều dài thời gian
chu kỳ CPU được tính bằng mini giây.
Trường hợp 1: Giả sử các quá trình đến theo thứ tự P1, P2, P3
Tiến trình
P1
P2
P3

Thời điểm vào Ready List
0
1
2

Thời gian xử Lý
24
3
3

Bảng 1: Ví dụ1 về FCFS
P1, P2, P3 được phục vụ theo thứ tự FCFS, thứ tự cấp phát CPU cho các tiến
trình như sau:

P1
0

24


P2
27

P3
30

Bảng 2: Giản đồ Gannt ví dụ 1 về chiến lược FCFS
Tính thời gian chờ để được xử lý: P1 (0ms), P2 (23ms), P3 (25ms)
Thời gian chờ trung bình = (0+23+25) /3=16ms
Số lần chuyển đổi ngữ cảnh =2
Trường hợp 2: Giả sử các quá trình đến theo thứ tự P2, P3, P1
Tiến trình
P2
P3
P1

Thời điểm vào Ready List
0
1
2

Thời gian xử Lý
3
3
24

Bảng 2: Ví dụ 2 về FCFS
P2, P3, P1 được phục vụ theo thứ tự FCFS, thứ tự cấp phát CPU cho các tiến
trình như sau:


P2
0

3

P3
6

P1
30

Bảng 3: Giản đồ Gannt ví dụ 1 về chiến lược FCFS
Tính thời gian chờ để được xử lý: P1 (4ms), P2 (0ms), P3 (2ms)
Thời gian chờ trung bình = (4+0+2) /3=2ms
Số lần chuyển đổi ngữ cảnh =2
Lớp ĐHSTIN15L2

16


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Nhận xét: Trong trường hợp 1 thời gian chờ trung bình không đạt cực tiểu, vì
có sự biến đổi đáng kể đối với các giá trị về thời gian xử lý và thứ tự khác nhau của
các tiến trình đến trong danh sách sẵn sàng. Có thể xảy ra hiện tượng tích lũy thời gian
chờ khi các tiến trình P2, P3 yêu cầu thời gian xử lý ngắn phải chờ đợi một tiến trình
P1 yêu cầu thời gian xử lý dài kết thúc xử lý.
Giải thuật FCSF là giải thuật định thời không trưng dụng CPU. Một khi CPU
được cấp phát tới một quá trình, quá trình đó giữ CPU cho tới khi nó giải phóng CPU
bằng cách kết thúc hay yêu cầu nhập/xuất. Giải thuật FCFS đặc biệt không phù hợp
đối với hệ thống chia sẻ thời gian, ở đó mỗi người dùng nhận được sự chia sẻ CPU với

những khoảng thời gian đều nhau.Giải thuật này đặc biệt không phù hợp với các hệ
điều hành phân chia thời gian, trong các hệ này, cần cho phép mỗi tiến trình được cấp
phát CPU đều đặn trong từng khoảng thời gian.

2.4.7.2. Chiến lược định thời với độ ưu tiên
Mỗi tiến trình được gán cho một độ ưu tiên tương ứng, tiến trình có độ ưu tiên
cao nhất sẽ được chọn để cấp phát CPU đầu tiên.
Ở đây hệ điều hành thường tổ chức gán độ ưu tiên cho tiến trình theo nguyên
tắc kết hợp giữ gán tĩnh và gán động. Khi khởi tạo tiến trình được gán độ ưu tiên tĩnh,
sau đó phụ thuộc vào môi trường hoạt động của tiến trình và công tác điều phối tiến
trình của bộ phận điều phối mà hệ điều hành có thể thay đổi độ ưu tiên của tiến trình.
Khi hệ thống phát sinh một tiến trình ready mới, thì bộ phận điều phối sẽ so
sánh độ ưu tiên của tiến trình mới phát sinh với độ ưu tiên của tiến trình đang sở hữu
CPU (tạm gọi là tiến trình hiện tại). Nếu tiến trình mới có độ ưu tiên thấp hơn tiến
trình hiện tại thì bộ phận điều phối sẽ chèn nó vào ready list tại vị trí thích hợp. Nếu
tiến trình mới có độ ưu tiên cao hơn tiến trình hiện tại thì bộ điều phối sẽ thu hồi CPU
từ tiến trình hiện tại để cấp cho tiến trình mới yêu cầu, nếu là điều phối không độc
quyền, hoặc chèn tiến trình mới vào ready list tại vị trí thích hợp, nếu là điều phối
độc quyền.
Chiến lược này cũng phải sử dụng ready list, và ready list luôn được xếp theo
thứ tự giảm dần của độ ưu tiên kể từ đầu danh sách. Điều này có nghĩa là tiến trình
được chọn để cấp PCU là tiến trình ở đầu ready list.
Xét các tiến trình P1, P2, P3 đến theo thứ tự:
Tiến trình
P1
P2
P3
Lớp ĐHSTIN15L2

Thời điểm vào RL


Độ ưu tiên

Thời gian xử Lý

0
3
24
1
1
3
2
2
3
Bảng 4. Ví dụ về định thời biểu với độ ưu tiên
17


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Sử dụng giải thuật ưu tiên độc quyền, thứ tự cấp phát CPU như sau:

P1
0

24

P2
27

P3

30

Bảng 5. Giản đồ Gannt ví dụ về định thời biểu với độ ưu tiên độc quyền
Thời gian chờ trung bình là (0+23+25)/3 = 16 ms.
Sử dụng giải thuật ưu tiên không độc quyền, thứ tự cấp phát CPU như sau:

0

P1
1

P2
4

P3
7

P1
30

Bảng 6. Giản đồ Gannt ví dụ về định thời biểu với độ ưu tiên không độc quyền
Thời gian chờ trung bình là (6+0+2)/3 = 2.66 ms.
Nhận xét: Một giải thuật không độc quyền bao giờ cũng tối ưu hơn giải thuật
độc quyền. Tình trạng “đói CPU” starvation là một vấn đề chính yếu của các giải thuật
sử dụng độ ưu tiên. Các giải thuật này có thể để các tiến trình có độ ưu tiên thấp chờ
đợi CPU vô hạn! Để ngăn cản các tiến trình có độ ưu tiên cao chiếm dụng CPU vô
thời hạn, bộ định thời biểu sẽ giảm dần chỉ số độ ưu tiên của các tiến trình chờ sau mỗi
ngắt đồng hồ. Nếu chỉ số độ ưu tiên của tiến trình này giảm xuống thấp hơn tiến trình
có chỉ số độ ưu tiên cao thứ nhì, sẽ xảy ra sự chuyển đổi quyền sử dụng CPU. Quá
trình này gọi là sự “lão hóa” (aging) tiến trình.


2.4.7.3. Chiến lược công việc ngắn nhất SJF
Nguyên tắc: Đây là một trường hợp đặp biệt của giải thuật điều phối với độ ưu
tiên p được gán cho mỗi tiến trình là mỗi tiến trình là nghịch đảo của thời gian xử lí
mà tiến trình yêu cầu: p=1/t. Khi CPU được tự do thì nó sẽ được cấp phát cho tiến
trình yêu cầu ít thời gian nhất để kết thúc tiến trình ngắn nhất. Giải thuật này cũng có
khả năng độc quyền hay không độc quyền. Sự lựa chọn xảy ra khi có một tiến trình
mới đưa vào danh sách sẵ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 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 SJF không độc quyền sẽ dừng
họat động của tiến trình hiện hành, trong khi giải thuật độc quyền sẽ cho phép tiến
trình hiện hành tiếp tục xử lí.

 SJF độc quyền: một CPU khi đƣợc giao cho một tiến trình, tiến trình sẽ
chiếm dụng CPU cho đến hết thời gian xử lý của nó.
 SJF hông độc quyền: nếu một tiến trình mới đến có thời gian sử dụng CPU
ngắn hơn thời gian thực hiện c n lại của tiến trình đang xử lý thì giao CPU cho tiến
trình mới đến.
Xét các tiến trình đến theo thứ tự:
Lớp ĐHSTIN15L2

18


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Tiến trình
P1
P2
P3
P4


Thời điểm vào RL

Thời gian xử lý (ms)

0
6
1
8
2
4
3
2
Bảng 7. Ví dụ về định thời biểu SJF

Sử dụng giải thuật SJF độc quyền, thứ tự cấp phát CPU như sau:

P1
0

P4

P3

6

8

P2
12


20

Bảng 8. Giản đồ Gannt ví dụ về định thời biểu SJF độc quyền
Thời gian chờ trung bình = (0+11+6+3)/4 = 5,0 ms.
Số lần chuyển đổi ngữ cảnh : 3
Sử dụng giải thuật SJF không độc quyền, thứ tự cấp phát CPU như sau:

P1
0

P4
3

P1
5

P3
8

P2
18

20

Bảng 9. Giản đồ Gannt ví dụ về định thời biểu SJF không độc quyền
Thời gian chờ trung bình = (2+11+6+0)/4 = 4,75 ms.
Số lần chuyển đổi ngữ cảnh : 4
Nhận xét: Giải thụât này cho phép đạt được thời gian chờ trung bình cực tiểu.
Khó khăn thực sự của giải thuật SJF là không thể biết được thời gian xử lí lần thứ n, t n+1 là giá trị dự đoán cho lần xử lí tiếp theo. Với hy vọng gia trị dữ đoán sẽ giống với

các giá trị trước đó, có thể sử dụng công thức:
Tn+1 = α tn+1(1-α)tn
Trong đó tn+1 chứa đựng thông tin gần nhất, tn chứa đựng các thông tin quá khứ
được tích luỹ, tham số ỏ kiểm soát trọng số hiện tại gần hay quá khứ ảnh hưởng đến
công thức dữ toán.

2.5. Thiết kế và cài đặt thuật toán
2.5.1. Phân tích yêu cầu
Tìm hiểu về bộ định thời trong quản lý tiến trình. Sử dụng các chiến lược định
thời biểu: FCFS, SJF độc quyền, ƯU TIÊN độc quyền.
Để làm rỏ các giải thuật:
- Nhập vào n tiến trình.P1,P2,……Pn với các thông tin sau:
+ Thời gian tính toán của mỗi process
Lớp ĐHSTIN15L2

19


Nhóm 4: Mô phỏng các giải thuật định thời cho process
+ Thời điểm process được đưa vào hệ thống
+ Các thông tin khác cần cho giải thuật (nếu thấy cần thiết)
- Sử dụng các thuật toán FCFS, SJF độc quyền, ưu tiên độc quyền để xử lý các
tiến trinh. Xuất ra thông tin của từng quá trình xử lý:
+ Thời gian đợi (waiting time) của mỗi process.
+ Thời gian đợi trung bình.
+ Thời gian quay vòng (turnaround time).
+ Thời gian quay vòng trung bình.
+ Thông năng (throughput).

2.5.2. Mô tả bài toán.

Chúng ta sẽ xây dựng chương trình đơn giản bằng C++. Mô phỏng kết quả xử
lý của các tiến trình thông qua thuật toán FCFS, SJF độc quyền, độ ưu tiên độc quyền.
Đầu vào: Các tiến trình p0,p1,p2,p3,….
+ Thời gian tính toán của mỗi tiến trình
+ Thời điểm tiến trình được đưa vào hệ thống
+ Các thông tin khác cần cho giải thuật (độ ưu tiên)
Đầu ra: Thời gian đợi (waiting time) của mỗi process, thời gian đợi trung bình,
thời gian quay vòng (turnaround time), thời gian quay vòng trung bình, thông năng
(throughput).

Lớp ĐHSTIN15L2

20


Nhóm 4: Mô phỏng các giải thuật định thời cho process

 Mô hình thuật toán:
XỬ LÝ

INPUT

OUTPUT

Thông tin các tiến trình nhập vào.
Số lượng tiến trình.
Sắp xếp tiến trình theo thời gian vào/xử lý/ưu
Giảntiên.
đồ Gantt.
Thời gian vào.

Tính toán thông số.
Bảng thông tin xử lý các tiên trình.
Thời gian xử lý.
Xuất giản đồ Gantt và các thông số.
Thg đợi t.bình.
Độ ưu tiên.
Thg đợi lưu t.bình.

Hình 12: Mô hình thuật toán

- Khởi tạo một đối tượng là một tiến trình chứa các thuộc tính:
Tên đối tượng
tt
tg_vao
tg_cpu
tg_ra
uu_tien
tg_doi
tg_luu

Kiểu dữ liệu
Nguyên
Nguyên
Nguyên
Nguyên
Nguyên
Thực
Thực

Diên giải

Thứ tự tiến trình ( P1, P2…)
Thời điểm vào của tiến trình. (ms)
Thời gian sử dụng CPU của tiến trình. (ms)
Thời gian tiến trình hoàn thành trả CPU. (ms)
Độ ưu tiên của tiến trình (chiến lược ưu tiên).
Thời gian tiến trình đợi CPU. (ms)
Thời gian tiến trình lưu trên hệ thống. (ms)

Bảng 10: các thuộc tính của 1 tiến trình
- Khởi tạo các hàm và thủ tục:
Hàm và thủ tục
int nhap(int ch)
void xuat(int n)
void gantt(int n)
void sap_xep(int n)
void sap_xep_stt(int n)
void sap_xep_sjf(int n)
void tinh_toan(int n)
void Do_uu_tien(int n)
void fcfs(int n)
void sjf(int n)

Diễn giải
Nhập số lượng tiến trình và thông tin đầu vào. Xuất ra các
thông tin vừa nhập.(INPUT)
Xuất ra bảng thông xử lý các tiến trình thời gian ra, thời
gian đợi, thời gian lưu lại hệ thống. (OUTPUT)
Vẽ giản đồ Gantt cho chiến lược
Sắp xếp các tiến trình theo thứ tự tăng dần thời điểm vào
của tiến trình.

Sắp xếp các tiến trình theo thứ tứ tên tiến trình.
Sắp xếp các tiến trình theo thứ tự tăng dần thời gian sử
dụng CPU.
Tính toán các thông số thời gian đợi, thời gian lưu, thời
gian ra, thời gian đợi trung bình, thời gian lưu trung bình.
Chiến lược độ ưu tiên độc quyền
Chiến lước FCFS.
Chiến lược SJF độc quyền
Bảng 11: Các thủ tục cài đặt thuật toán

2.5.3. Giới thiệu DEMO và hướng dẫn sử dụng
 Giao diện chính của phần mềm
Lớp ĐHSTIN15L2

21


Nhóm 4: Mô phỏng các giải thuật định thời cho process
Khi chương trình được thực hiện sẽ yêu cầu người dùng chọn chiến lược mô
phỏng để thực hiện.

Hình 13: Giao diện khi chạy chương trình

 Hàm nhập dữ liệu
Hàm nhap() được thực hiện, người dùng cung cấp thông tin (Input):
+ Số lượng tiến trình.
+ Thời điểm vào Ready List của từng tiến trình.
+ Thời gian sử dụng CPU của từng tiếng trình.

Hình 14: Người dùng nhập dữ liệu các tiến trtình


 Hàm vẽ giản đồ Gantt
Chương trình gọi thủ tục Gantt(n) để vẽ giản đồ cho các chiến lược.
Lớp ĐHSTIN15L2

22


Nhóm 4: Mô phỏng các giải thuật định thời cho process

Hình 15: Giản đồ Gantt cho chiến lược

 Các hàm FCFS(n), SJF(n), DO_UU_TIEN(n)
Thực hiện tính toán thời gian ra tg_ra của tiến trình và lưu lại, sau đó gọi thủ
tục Gantt(n) để vẽ giản đồ Gantt cho chiến lược

 Hàm xuất kết quả
Hàm xuat(n) được thực thi sẽ trả về kết quả gồm bảng thông tin xử lý các tiến
trình và thời gian đợi trung binh, thời gian lưu lại trung binh.

Hình 16: Thông tin xử lý được trả về

Lớp ĐHSTIN15L2

23


Nhóm 4: Mô phỏng các giải thuật định thời cho process

3. KẾT LUẬN

3.1. Kết quả đạt được
3.1.1 Kết quả chiến lược FCFS

Hình 17: Kết quả chiến lược FCFS

3.1.1 Kết quả chiến lược độ ưu tiên độc quyền

Hình 17: Kết quả chiến lược độ ưu tiên độc quyền

Lớp ĐHSTIN15L2

24


Nhóm 4: Mô phỏng các giải thuật định thời cho process

3.1.1 Kết quả chiến lược SJF độc quyền

Hình 18: Kết quả chiến lược SJF độc quyền

3.2. Hạn chế
Trong khi thực hiện chương trình nghiên cứu các chiến lược định thời biểu
process nhưng do thời gian cũng như kiến thức còn hàn chế nên chỉ nghiên cứu 3
chiến lược và chưa có điều kiện đi sâu nghiên cứu chi tiết vào từng chiến lược cụ thể.

3.3. Hướng phát triển.
Trong thời gian tới nếu có thời gian và thêm kiến thức chúng em sẽ tiếp tục
nghiên cứu các chiến lược định thời biểu process còn lại và phát triển chương trình kết
hợp đồ họa để người dùng không nhàm chán với giao diện MS-DOS.


Lớp ĐHSTIN15L2

25