LỜI NÓI ĐẦU

Hệ điều hành là một hệ thống vô cùng phức tạp , quá trình cập nhật
và sử lý thông tin diễn ra rất nhanh . Các quá trình sử lý của CPU
đều được thông qua các bộ điều phối , thế gới ngày càng hiện đại
công nghệ ngày càng phát triển CPU ngày càng được nâng cấp
mạnh mẽ về cô nghệ chế tạo . Tuy nhiên CPU vẫn phải tuân theo
những nguyên tắc xử lý nhất quán dựa trên các thuật toán xử lý
tiến trình . CPU từ chỗ đơn nhiệm (đơn chương) đã và đang được
nâng cấp xử lý đa nhiệm , đa chương . Ngoài ra CPU đần được
nâng tầm về khả năng sử lý . Hiệu xuất được nâng cao , tiết kiệm
thời gian , tài nguyên.
Điều phối tiến trình là một tập hợp chuỗi các thuật toán nhằm
điều khiển hoạt động của CPU trong điều phối tiến trình .
Với mục tiêu nhiên cứu về các thuật toán và mô phỏng các thuật
toán trên nền tảng tubor C , C++ , C# , Dev – C . Bên cạnh đó là tìm
hiểu các nguyên tắc chung của điều phối tiến trình.


MỤC LỤC
1.
2.
3.

4.

LỜI NÓI ĐẦU ……………………………………………………… 01
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪ……………………. 02
I . LÝ DO , MỤC ĐÍCH & CƠ SỞ LÝ THUYẾT …….…………. 03
1 : Khái niệm về hệ điều hành ………………………………. 03
2 : Mục tiêu của đề tài ………………………………….. ……03

3 : Cơ sở lý thuyết ………………………………………. ……04
4 : Trạng thái lý thuyết của tiến trình………………………...04
5 : Quy trình trạng thái của tiến trình ……………………….05
6 : Các chế độ xử lý tiến trình………………………….............06
II ĐIỀU PHỐI & MÔ PHỎNG ĐIỀU PHỐI TIỀN TRÌNH..……...09
1 : Cơ chế điều phối………………………………………….... 09
2 :Ưu , nhược điểm các thuật toán điều phối ………………..09
2.2.1 : Thuật toán FCFS
2.2.2 : Thuật toán SJN
2.2.3 : Thuật toán Robin Round (RR)
2.2.4 : Thuật toán SRTF
3 : Khái niệm về mô phỏng ……………………………………10
4 : Thuật toán mô phỏng ………………………………………10
4.1 : Khái niệm
4.2 : Các thuật toán cơ bản
4.3 : Cài đặt công cụ mô phỏng
5 : Cài đặt thuật toán ………………………………………….
5.1 : Thuật toán SJN
5.2 : Kết quả mô phỏng


I : LÝ DO , MỤC TIÊU & CƠ SỞ LÝ THUYẾT CỦA ĐỀ TÀI
1.Lý do :
Hệ điều hành là một phần tất yếu trong xã hội hiện nay , nơi mà
mọi thông tin đều được cập nhật và sử lý hằng ngày hằng giờ
thậm chí hằng mili giây thông qua các hệ thống máy tính , hệ thống
thông tin trên toàn thế giới.
Với chức năng phân phối và sử lý các nguồn tài nguyên hệ thống đã
và đang tạo ra những sự thuận tiện cho người dùng thông qua việc
phân phối tài nguyên bộ nhớ , sử lý nhanh một cách nhanh chóng hiệu

quả , bên cạnh đó việc tạo lập môi trường ảo giúp các hệ thống máy
tính ngày càng hiện đại hơn thông minh hơn đã và đang góp phần
không nhỏ cho cuộc sống con người .
Hệ điều này chủ yếu quản lý các trang thái sử lý thông tin của CPU
trong môi trường đa chương , đa nhiệm việc sử lý thông tin sẽ nảy sinh
các trường hợp yêu cầu sử lý đồng thời . Việc phân chia thời gian (time
–sharing) là các thức chuyển đổi CPU một cách nhanh chóng qua các
tiến trình giúp người sử dụng có thế sử lý song song nhiều chương
trình giúp tiết kiệm thời gian, chi phí sử dụng giảm lãng phí tài
nguyên .
Tuy nhiên để CPU hoạt động hiệu quả tránh hao phí tài nguyên ,
thời gian Hệ Điều Hành phải sử dụng các thuật toán để nhận diện các
tiến trình sẽ được sử 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 .Đồng thời bộ điều phối sẽ chuyển đổi các ngữ
cảnh và chuyển cho CPU tiến trình tiếp theo được chọn bởi bộ điều
phối để sử lý .
Vì việc điều phối tiến trình trong CPU là một quá trình phức tạp
nhưng đặc biệt quan trọng do đó em lựa chọn đề tài :Mô phỏng thuật
toán điều phối tiến trình trong hệ điều hành .
2. Mục tiêu của đề tài
- Tìm hiểu các giải thuật : First – Come- First –Severed (FCSFS-


Đến trước phục vụ trước ), Shortest Job Next (SJN – Công việc ngắn
nhất phục vụ trước),Deadline Scheduling(Điều phối có thời hạn),Round
Robin (Điều phối xoay vòng )
- Ưu , nhược điểm của các giải thuật điều phối tiến trình CPU
- Cài đặt và mô phỏng giải thuật điều phối tiến trình CPU
3 : Cơ sở lý thuyết
Trong việc điều phối tiến trình bộ điều phối không cung cấp cơ

chế mặt khác bộ điều phối đưa ra quyết định .Có rất nhiều hệ điều hành
khác nhau với những chiến lược khác nhau nhằm thực hiện điều phối
tiến trình trong CPU nhưng tất cả đều theo một bộ nguyên tắc chung
bao gồm.
- Sự công bằng trong phân phối CPU tương ứng việc cấp phát
CPU một cách đồng đều không có tiến trình nào được ưu tiên một cách
tuyệt đối , không có tiến trình nào phải chờ quá lâu để được cấp phát
CPU.
-Thời gian đáp ứng hợp lý : thời gian phản hồi đến người sử
dụng là cực tiểu hay nói cách khác thời gian người sử dụng nhận được
tiến trình đã sử lý là ngắn nhất
- Hiệu quả nhất : Sự dụng 100% thời gian của CPU
- Thời gian lưu lại trên hệ thống là nhỏ nhất : cực tiểu hóa thời
gian hoàn tất xử lý trong CPU
- Năng lực tối đa : tăng khả năng sử lý nhiều tiến trình trong
một khoảng thời gian
Đó là những những bộ nguyên tắc mà mọi hệ điều hành cần đạt
đến tuy nhiên ngay cả thời điểm hiện nay việc sử lý cùng một lúc nhiều
tiến trình đôi khi cũng dẫn đến hệ điều hành quá tải , việc nâng cấp hệ
điều hành cũng đã dần dần mang lại những hiệu quả tích cực bất chấp
việc đó đôi khi lại mâu thuẫn lẫn nhau.
4. Trạng thái lý thuyết của tiến trình
Quy trình quản lý tiến trình
Trong hệ điều hành quá trình điều phối tiến trình trong CPU và quá trình mà
mọi tiến trình trong quá trình sử lý sẽ trải qua các giai đoạn sau
1.
2.

Tạo lập tiến trình
Running :chỉ thị tiến trình đang được sử lý



3.
4.
5.

Blocked : tiến trình chờ cấp phát tài nguyên hoặc chờ dữ liệu hoàn
thành
Ready : CPU sử lý tiến trình
Kết thúc : Hoàn thành việc sử lý

5. Quy trình các trạng thái tiến trình
Từ khi được đưa vào hệ thống cho đến khi kết thúc tiến trình tồn tại ở các
trạng thái khác nhau. 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 đó. Tiến trình hai
trạng thái: Một số ít hệ điều hành chỉ cho phép tiến trình tồn tại ở một trong
hai trạng thái: Not Running và Running. Khi hệ điều hành tạo ra một tiến
trình mới, hệ điều hành đưa tiến trình đó vào hệ thống ở trạng thái Not
Running, tiến trình ở trạng thái này để chờ được chuyển sang trạng thái
Running. Vì một lý do nào đó, tiến trình đang thực hiện bị ngắt thì bộ điều
phối tiến trình của hệ điều hành sẽ thu hồi lại processor của tiến trình này và
chọn một tiến trình ở trạng thái Not running để cấp processor cho nó và
chuyển nó sang trạng thái Running. Tiến trình bị thu hồi processor sẽ được
chuyển về lại trạng thái Not running.
Tại một thời điểm xác định chỉ có duy nhất một tiến trình ở trạng thái Runnig,
nhưng có thể có nhiều tiến trình ở trạng thái Not running, các tiến trình ở
trạng thái Not running được chứa trong một hàng đợi (Queue). Tiến trình
đang ở trạng thái Running bị chuyển sang trạng thái Not running sẽ được
đưa vào hàng đợi. Hình vẽ sau đây mô tả việc chuyển trạng thái tiến trình
trong các hệ điều hành sử dụng 2 trạng thái tiến trình.

Tiến trình ba trạng thái: Đa số hệ điều hành đều cho phép tiến trình tồn tại ở
một trong ba trạng thái, đó là: ready, running, blocked:
• Trạng thái Ready (sẵn sàng): Ngay sau khi khởi tạo tiến trình, đưa
tiến trình vào hệ thống và cấp phát đầy đủ tài nguyên (trừ processor) cho tiến
trình,
hệ điều hành đưa tiến trình vào trạng thái ready. Hay nói cách khác, trạng
thái
ready là trạng thái của một tiến trình trong hệ thống đang chờ được cấp
processor
để bắt đầu thực hiện.
• Trạng thái Running (thực hiện): Là trạng thái mà tiến trình đang được sở


hữu processor để hoạt động, hay nói cách khác là các chỉ thị của tiến trình
đang được thực hiện/ xử lý bởi processor.
• Trạng thái Blocked (khoá): Là trạng thái mà tiến trình đang chờ để được
cấp phát thêm tài nguyên, để một sự kiện nào đó xảy ra, hay một quá trình
vào/ra kết thúc.
Quá trình chuyển trạng thái của các tiến trình trong được mô tả bởi sơ đồ
sau:
Trong đó:
1. (Admit) Tiến trình được khởi tạo, được đưa vào hệ thống, được cấp phát
đầy đủ tài nguyên chỉ thiếu processor.
2. (Dispatch) Tiến trình được cấp processor để bắt đầu thực hiện/ xử lý.
3. (Release) Tiến trình hoàn thành xử lý và kết thúc.
4. (Time_out) Tiến trình bị bộ điều phối tiến trình thu hồi processor, do hết
thời gian được quyền sử dụng processor, để cấp phát cho tiến trình khác.
5. (Event wait) Tiến trình đang chờ một sự kiện nào đó xảy ra hay đang chờ
một thao vào/ra kết thúc hay tài nguyên mà tiến trình yêu cầu chưa được hệ
điều hành đáp ứng.

6. (Event Occurs) Sự kiện mà tiến trình chờ đã xảy ra, thao tác vào/ra mà tiến
trình đợi đã kết thúc, hay tài nguyên mà tiến trình yêu cầu đã được hệ điều
hành đáp ứng,
Bộ phận điều phối tiến trình thu hồi processor từ một tiến trình đang thực
hiện trong các trường hợp sau:
• Tiến trình đang thực hiện hết thời gian (time-out) được quyền sử dụng
processor mà bộ phận điều phối dành cho nó.
• Có một tiến trình mới phát sinh và tiến trình mới này có độ ưu tiên cao hơn
tiến trình hiện tại.
• Có một tiến trình mới phát sinh và tiến trình này mới cần một khoảng thời
gian của processor nhỏ hơn nhiều so với khoảng thời gian còn lại mà tiến
trình hiện tại cần processor.
Tại một thời điểm xác định trong hệ thống có thể có nhiều tiến trình đang ở
trạng thái Ready hoặc Blocked nhưng chỉ có một tiến trình ở trạng thái
Running. Các tiến trình ở trạng thái Ready và Blocked được chứa trong các
hàng đợi (Queue) riêng.
Có nhiều lý do để một tiến trình đang ở trạng thái running chuyển sang trạng
thái blocked, do đó đa số các hệ điều hành đều thiết kế một hệ thống hàng đợi


gồm nhiều hàng đợi, mỗi hành đợi dùng để chứ những tiến trình đang đợi
cùng một sự kiện nào đó.
6. Các chế độ sử lý
Trong việc điều phối tiến trình bộ điều phối không cung cấp cơ chế mặt khác
bộ điều phối đưa ra quyết định .Có rất nhiều hệ điều hành khác nhau với
những chiến lược khác nhau nhằm thực hiện điều phối tiến trình trong CPU
nhưng tất cả đều theo một bộ nguyên tắc chung bao gồm.
- Sự công bằng trong phân phối CPU tương ứng việc cấp phát
CPU một cách đồng đều không có tiến trình nào được ưu tiên một cách
tuyệt đối , không có tiến trình nào phải chờ quá lâu để được cấp phát

CPU.
-Thời gian đáp ứng hợp lý : thời gian phản hồi đến người sử
dụng là cực tiểu hay nói cách khác thời gian người sử dụng nhận được
tiến trình đã sử lý là ngắn nhất
- Hiệu quả nhất : Sự dụng 100% thời gian của CPU
- Thời gian lưu lại trên hệ thống là nhỏ nhất : cực tiểu hóa thời
gian hoàn tất xử lý trong CPU
- Năng lực tối đa : tăng khả năng sử lý nhiều tiến trình trong
một khoảng thời gian
Đó là những những bộ nguyên tắc mà mọi hệ điều hành cần đạt
đến tuy nhiên ngay cả thời điểm hiện nay việc sử lý cùng một lúc nhiều
tiến trình đôi khi cũng dẫn đến hệ điều hành quá tải , việc nâng cấp hệ
điều hành cũng đã dần dần mang lại những hiệu quả tích cực bất chấp
việc đó đôi khi lại mâu thuẫn lẫn nhau.
Tuy nhiên trong hệ điều hành thì có những sự ưu tiên riêng biệt nhằm bảo
đảm an toàn cho hệ điều hành cũng như những sai sót trong quá trình sử lý .
Do vậy Hệ điều hành sử dụng chế độ : Đặc quyền và Không đặc quyền , khi đó
người sử dụng sẽ được sử lý thông tin với chế độ không đặc quyền , sau khi
CPU hoàn tất tiến trình thì thông tin sử lý sẽ được chuyển qua cho người
dùng bằng chế độ không đặc quyền điều đó giúp hệ thống được bảo đảm an
toàn trước những sai sót do người dùng có thể tạo ra . Ta có thể thấy rõ sự
khác nhau từng bước của quá trình điều phối như sau :
- Đ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.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 đ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.
Các giải thuật đọc quyền thường đơn giản và đẽ cài đặt.Tuy nhiên chúng
thường không thích hợp với các 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ữ CPU một thời gian không xác định,có thể ngăn cản những tiến trinh
còn lại trong hệ thống cosmoojy cơ hội để xử lý.
- Đ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 dọc quyền cho phéo tạm dừng hoạt động của một tiến trình
sẵn sàng xử lý.Khi một tiến trình nhận được một 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 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 thông báo trước,để tiến trình khác xử lý.Cadc quyết định điều
phối xảy ra khi:
+ Khi tiến trình chuyể từ trạng thái đang xử lý(running) sang trạng thái bị
khóa 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ờ (bloked) sang trạng thái ready(ví
dụng một thao tác nhập xuất hoàn tất).
+ Khi tiến trình kết thúc.
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ờ 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 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 lts điều phối độc quyền để các 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 chi phí khi chuyển đổi CPU qua lịa giữa các tiến trình.

II ĐIỀU PHỐI &MÔ PHỎNG ĐIỀU PHỐI TIẾN TRÌNH
1 .Cơ chế điều phối
Trong HĐH đa chương , đa nhiệm việc phân phối hợp lý tài nguyên bộ nhớ &
điều phối tiến trình sử lý thông tin hết sức quan trọng nhằm tăng dần hiệu
suất sử lý của CPU và cả hệ thống . HĐH sử dụng đến bộ điều phối tiến trình
khi đó một tiến trình đang được thực thi mà mất quyền sử dung CPU (chuyển
trang thái sẵn sàng hoặc phong tỏa) thì ngay lập tức tiến trình khác sẽ được
cấp phát CPU để được sử lý .Bên cạnh đó việc lưu lại ngữ cảnh của tiến trình
giúp HĐH thu hẹp thời gian LOAD tiến trình lên các thanh ghi giúp dữ liệu
mau chóng được sử lý bảo đảm thời gian thực cho HĐH .
2. Ưu nhược điểm các thuật toán điều phối .
2.1 Đến trước phục vụ trước (FCFS)
Trong thuật toán FCFS, độ ưu tiên của tiến trình sẽ được quyết
định bởi thời điểm trương trình được đưa vào hàng đợi, nói cách khác
các tiến trình sẽ được sử lý một các tuần tự theo thứ tự trước sau có
nghĩa là tiến trình nào đến trước được sử lý trước và khi sử lý xong thì
sẽ chuyển sang tiến trình tiếp theo .
* Ưu điểm :
- Thao tác đơn giản
- Giờ của CPU không bị phân phối lại , chi phí tổ chức thực hiện
thấp nhất
* Nhược điểm :
- Không hiệu quả , tiến trình dài với tiến trình ngắn đều phải chờ
đợi trong hàng chờ
- Thời gian chờ đợi trung bình lớn,khi tăng thời gian thực hiện



các tiến trình thì thời
gian chờ đợi cũng tăng theo.
2.2 Ngắn nhất phục vụ trước (SJN)
Là hình thức sử lý tiến trình thông qua việc tính toán thời gian đòi hỏi
để CPU sử lý trong suốt quá trình, với mục đích cự tiểu hóa thời gian chờ đợi
trung bình , tăng hiệu suất sử lý của CPU cũng như toàn hệ thống.
* Ưu điểm :
- So với FCFS, SJN là giảm tối đa thời gian chờ đợi trung bình
- Nhanh chóng sử lý và loại bỏ các tiến trình ngắn giải phóng số
lượng các tiền trình trong hàng đợi .
* Nhược điểm :
- SJN sẽ làm giảm số phần tử trong hàng đợi , dẫn đến khi các
phần tử khác thêm vào sẽ nảy sinh việc phân phối lại dẫn đến các tiến trình
dài sẽ có xu thế bị đẩy về sau chờ sử lý
2.3 Thuật toán Robin Round
* Ưu điểm : Được thiết kế để áp dụng cho các hệ phân chia thời
gian (time-sharing) z RR hoạt động theo chế độ preemptive z Tham số
lượng tử thời gian (time quantum) tquantum: Mỗi tiến trình được sử
dụng CPU trong nhiều nhất bằng tquantum, sau đó đến lượt tiến trình
khác.
* Nhược điểm : Hiệu quả của RR phụ thuộc độ lớn của tquantum
z Nếu tquantum nhỏ thì hiệu quả của RR giảm vì bộ điều phối phải thực
hiện nhiều thao tác chuyển trạng thái, lãng phí thời gian CPU z Nếu
tquantum lớn thì số thao tác chuyển trạng thái giảm đi z Nếu
tquantum rất nhỏ (ví dụ 1ms) thì RR được gọi là processor sharing
3 : Khái niệm mô phỏng điều phối tiến trình
Khái niệm : Mô phỏng là việc áp dụng một mô hình nào đó để tạo ra kết
quả ,chứ không có nghĩa là thử nghiệm một hệt thống nào đó đang cần nhiên
cứu
Công cụ : Trước tiên ta phải xác đinh nguồn mô phỏng , qua đó chọn

công cụ cho hợp lí
Ngôn ngữ mô phỏng : trong điều phối tiến trình ngôn ngữ mô phỏng thường
là
C+, C++ hay C#.
4 : Thuật toán mô phỏng


4.1 Khái niệm
Là thuật toán dựa trên nền tảng các ngôn ngữ lập trình ,
nhằm tạo ra môi trường ảo để máy tính mô phỏng lại quá trình xử
lý thông tin cũng như quá trình làm việc .
4.2: Thuật toán mô phỏng SJN
Sử dụng phần mềm Code block với ngôn ngữ C# , nhằm
tạo ra các phần mô phỏng trên môi trường MS.DOS . Code
block có khả năng dịch ngôn ngữ lập trình giúp giảm thời gian
cũng như bảo đảm khả năng chạy chương trình
4.3 : Cài đặt công cụ mô phỏng

*.Giới thiệu
CodeBlock là một IDE được viết bằng C++ sử dụng framework wxWidget.
Điểm nổi bật của CB bao gồm:
•

•
•
•

1. Cross-platform, nó có thể run trên mọi hệ điều hành, bao gồm : Mac,
Linux, Windows, …
2. Rất gọn nhẹ, chỉ có đúng 70mb.

3. Có thể chọn bất cứ compiler để biên dịch source, mặc định là gcc.
4. Hỗ trợ format source code rất tiện lợi cho việc copy code từ các site
khác về, và chỉnh sữa lại.

*. Cài đặt


Bước 1: Tải Code Block tại : www.codeblocks.org/downloads
Bước 2: Cài đặt Code::Blocks
- Click đúp vào file vừa tải về để bắt đầu quá trình cài đặt
- Click next liên tiếp, màn hình thông báo cài đặt mặc định vào C:\Program
Files\CodeBlocks
- Chọn cài FULL để có đầy đủ các tính năng
- Mở chương trình lên sau khi cài đặt xong.
Bước 3: Khởi động Code::Blocks
- Có 1 cửa sổ hiển thị lên yêu cầu bạn chọn Trình biên dịch mặc định của Code::Blocks

- Để tạo 1 project mới bạn làm như sau: Vào menu File -> New -> Project..


- Chọn Console Application và nhấn nút Go để bắt đầu.
- Chọn next liên tiếp tới khi bạn gặp cửa sổ yêu cầu chọn ngôn ngữ C/C++

- Sau khi nhấn Next, Code::Blocks sẽ yêu cầu bạn điền các thông tin của Project.
- Click Next lần nữa để lựa chọn trình biên dịch cho Project vừa tạo.

- Bạn có thể không cần làm gì ở bước này. Mặc định, Code::Blocks sẽ chọn trình biên dịch
mặc định mà bạn đã thiết lập lúc cài đặt ban đầu.
- Mở file main.cpp ở cửa sổ bên trái để vào giao diện viết code cho chương trình.



- Ở cửa sổ bên phải, bạn có thể viết 1 ví dụ đơn giản in ra màn hình câu: "Hello world !",
Sau đó nhấn F9 để chạy và xem kết quả.

Bước 5: Debug.
Trong trường hợp chương trình chạy không như ý của bạn, sử dụng công cụ
debugger để xác định cụ thể. Chức năng debug cơ bản có tại tab debug ở cuối
màn hình. Nhiều chức năng khác nhau có tại menu debug. Một vài tính năng
chính của debug như:
• Chạy tới con trỏ màn hình (Run to cursor )
• Thêm cửa sổ theo dõi
• Theo dõi giá trị của biến,…

5. Cài đặt thuật toán SJN
5.1 : Cấu trúc dữ liệu mô phỏng
Nguyên tắc chung : Mọi thuật toán đều phải tuân thủ theo các bước
sau


Begin

Xử lý tiến trình đầu danh
sách

Kiểm tra danh sách rỗng

ĐÚNG
Sai
Xử lý thuật toán


Câp nhật lại danh
Sach trong hàng chờ

End


Bước 1 : Khởi tạo chương trình và chọn file-> New-> Project -> consoler.

Hình 4.1a Giao diện môi trường mô phỏng và khai báo SJN
Bước 2 : Khai báo thư viện
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <queue>
#define INP "input.txt" (đường dẫn tập tin input.txt)
Chú ý : Tập tin input.txt bao gồm những thông tin sau
4 - là số tiến trình (P1, P2 , P3 , P4)
1 2 - Là tiến trình được chọn - Quatum của CPU
P1 0 20 3 - Tiên trình – Thời gian vào – Thời gian xử lý – độ ưu tiên
P2 3 6 2
P3 3 5 1
P4 7 4 0
Bước 2 : Khai báo input - output
int quantum;
int set;
void input(ListP &pr, int &n, int &timeOUT);
void output_input(ListP pr, int n);
void output_SJN_preemptive(ListP pr, int n, int timeOUT);



void output_SJN_nopreemptive(ListP pr, ListP RL, int n, int m, int timeOUT);
void OUTPUT(ListP pr, ListP RL, int n, int m, int timeOUT, int set);
void process_SJN_preemptive(ListP &pr, int n, int timeOUT);
void process_SJN_nopreemptive(ListP &pr, ListP &RL, int n, int &m, int timeOUT);
void PROCESS(ListP &pr, ListP &RL, int n, int &m, int timeOUT, int set);
void input(ListP &pr, int &n, int &timeOUT) {
timeOUT = 0;
ifstream in(INP);
if (in == NULL) {
cout << "Not input file !";
return;
}

Bước 3 : Khai báo các thông tin sử lý

in >> n;
in >> set;
in >> quantum;
pr = new process[n];
for (int i = 0; i < n; i++) {
in >> pr[i].name;
in >> pr[i].timeRL;
in >> pr[i].timeCPU;
in >> pr[i].priority;
if (timeOUT < pr[i].timeRL)
timeOUT = pr[i].timeRL + pr[i].timeCPU;
else
timeOUT += pr[i].timeCPU;

pr[i].index = i;
}
}
void output_input(ListP pr, int n) {
cout << endl << "---------------INPUT---------------" << endl << endl;
cout << "Name" << setw(10) << "TimeRL" << setw(10) << "TimeCPU" <<
setw(10)
<< "Priority" << endl;
for (int i = 0; i < n; i++)
cout << pr[i].name << setw(10) << pr[i].timeRL << setw(10)
<< pr[i].timeCPU << setw(10) << pr[i].priority << endl;
cout << "quantum = " << quantum << endl;
cout << endl << "---------------OUTPUT---------------" << endl << endl;
}
void output_SJN_preemptive(ListP pr, int n, int timeOUT) {
cout << "SJN preemptive" << endl << endl << "PROCESS" << endl << endl;
cout << "Name" << setw(10) << "TimeRL" << setw(10) << "TimeCPU" <<
setw(10)


<< "Priority" << setw(10) << "TimeIN" << setw(10) <<
"TimeOUT"

<< setw(10) << "Timewait" << setw(10) << "Timesave" <<

endl;

for (int i = 0; i < n; i++)
cout << pr[i].name << setw(10) << pr[i].timeRL << setw(10)
<< pr[i].timeCPU << setw(10) << pr[i].priority <<

setw(10)
<< pr[i].timeIN << setw(10) << pr[i].timeOUT <<
setw(10)
<< pr[i].timewait << setw(10) << pr[i].timesave <<
endl;
}
void output_SJN_nopreemptive(ListP pr, ListP RL, int n, int m, int timeOUT) {
cout << "SJN nopreemptive" << endl << endl << "OUTPUT" << endl << endl;
cout << "Name" << setw(10) << "TimeOUT" << setw(10) << "Timewait"
<< setw(10) << "Timesave" << endl;
for (int i = 0; i < n; i++)
cout << pr[i].name << setw(10) << pr[i].timeOUT << setw(10)<<
pr[i].timewait << setw(10) << pr[i].timesave << endl;
cout << endl << endl << "---PROCESS---" << endl << endl;cout << "Name" << setw(10) <<
"TimeRL" << setw(10) << "TimeCPU" << setw(10)
<< "Priority" << setw(10) << "TimeIN" << setw(10) << "TimeOUT" << endl;
for (int i = 0; i < m; i++)
cout << RL[i].name << setw(10) << RL[i].timeRL << setw(10)
<< RL[i].timeCPU << setw(10) << RL[i].priority <<
setw(10)
<< RL[i].timeIN << setw(10) << RL[i].timeOUT <<
endl;
}
void process_SJN_preemptive(ListP &pr, int n, int timeOUT) {
ListP RL = new process[n];
ListP pr1 = pr; //list temp of pr
int j = 0, m = 0;
int temptime = 0;
for (int t = 0; t <= timeOUT; t++) {
if (m > 0 && j < m) {

if (temptime < RL[j].timeCPU)
temptime++;
if (temptime == RL[j].timeCPU) {
RL[j].timeIN = t - RL[j].timeCPU;
RL[j].timeOUT = RL[j].timeIN + RL[j].timeCPU;
RL[j].timewait = RL[j].timeOUT - (RL[j].timeRL +
RL[j].timeCPU);


RL[j].timesave = RL[j].timeOUT - RL[j].timeRL;
temptime = 0;
j++;
}
}
for (int i = 0; i < n; i++)
if (t == pr1[i].timeRL) {
int k = m;
while (k > j + 1 && pr1[i].timeCPU < RL[k 1].timeCPU) {

RL[k] = RL[k - 1];
k--;

}
RL[k] = pr1[i];
m++;

}

}
pr = RL;


}

void process_SJN_nopreemptive(ListP &pr, ListP &RL, int n, int &m,
int timeOUT) {
RL = new process;
ListP pr1 = pr; //list temp of pr
process temp;
int j = 0;
m = 0;
int temptime = 0;
for (int t = 0; t <= timeOUT; t++) {
if (m > 0 && j < m) {
if (temptime < RL[j].timeCPU)
temptime++;
if (temptime == RL[j].timeCPU) {
RL[j].timeIN = t - RL[j].timeCPU;RL[j].timeOUT = RL[j].timeIN + RL[j].timeCPU;
RL[j].timewait = RL[j].timeOUT - (RL[j].timeRL + RL[j].timeCPU);
RL[j].timesave = RL[j].timeOUT - RL[j].timeRL;pr1[RL[j].index].timeOUT = t;
pr1[RL[j].index].timewait = pr1[RL[j].index].timeOUT- (pr1[RL[j].index].timeRL +
pr1[RL[j].index].timeCPU);
pr1[RL[j].index].timesave = pr1[RL[j].index].timeOUT - pr1[RL[j].index].timeRL;

}

temptime = 0;
j++;

}
for (int i = 0; i < n; i++)

if (t == pr1[i].timeRL) {
m++;


int k = m - 1;
RL = (process *) realloc(RL, m * sizeof(process));
if (temptime > 0 && pr1[i].timeCPU < RL[j].timeCPU - temptime) {
m++;
k = m - 1;
RL = (process *) realloc(RL, m * sizeof(process));
for (k = m - 1; k > j + 1; k--)
RL[k] = RL[k - 2];
RL[j + 1] = pr1[i];
RL[j + 2] = RL[j];
RL[j + 2].timeCPU -= temptime;
RL[j].timeIN = t - temptime;
RL[j].timeOUT = t;
RL[j].timeCPU = temptime;
temptime = 0;
j++;

}

} else {
while (k > j + 1 && pr1[i].timeCPU < RL[k - 1].timeCPU) {
RL[k] = RL[k - 1];
k--;
if (k == j + 1
&& pr1[i].timeCPU < RL[k - 1].timeCPU - temptime) {
RL[k] = RL[k - 1];

k--;
}
}
RL[k] = pr1[i];
}
}

}
void PROCESS(ListP &pr, ListP &RL, int n, int &m, int timeOUT, int select) {
switch (select) {
case 1:
process_SJN_preemptive(pr, n, timeOUT);
break;
case 2:
process_SJN_nopreemptive(pr, RL, n, m, timeOUT);
break;
}
}
void OUTPUT(ListP pr, ListP RL, int n, int m, int timeOUT, int select) {
switch (select) {
case 1:
output_SJN_preemptive(pr, n, timeOUT);
break;
case 2:
output_SJN_nopreemptive(pr, RL, n, m, timeOUT);


break;
}
cout << endl << "-----------------END-----------------" << endl << endl;

}
int main() {
ListP pr, RL;
int n, m, timeOUT;
input(pr, n, timeOUT);
output_input(pr, n);
PROCESS(pr, RL, n, m, timeOUT, set);
OUTPUT(pr, RL, n, m, timeOUT, set);
return 0;
}

4.1b : Kết quả mô phỏng
5.2:Những điều đề tài làm được và chưa làm được
a. Những điều đề tài làm được :
- Sử dụng thuât toán SJN để mô phỏng điều phối tiến trình.
- Thực hiện dễ dàng trong việc thay đổi chế độ điều phối nhưng
không can thiệp vào mã nguồn .
b. Những việc đề tài chưa làm được :
- Mô phỏng các thuật toán FCFS , RR ….
- Đồ họa hóa điều phối tiến trình .


5.3 : Kết luận
Mô phỏng điều phối tiến trình giúp em hiểu rõ thêm về quy trình sử lý các tiến
trình trong CPU và hệ điều hành . Tuy nhiên do thời gian chưa cho phép nên
em xin được mô phỏng các phương pháp điều phối tiến trình khác trong đồ
án sau .