TR NG Đ I H C BÁCH KHOAƯỜ Ạ Ọ
KHOA CÔNG NGH THÔNG TINỆ
B MÔN M NG VÀ TRUY N THÔNGỘ Ạ Ề

Đ ÁN H ĐI U HÀNHỒ Ệ Ề
Đ tàiề:
Xây d ng ch ng trình mô ph ng cácự ươ ỏ
gi i thu t đ nh th i cho CPUả ậ ị ờ
Sinh viên : Lê Ph ng Ti nươ ế 07T2
Hà Ph c Vi tướ ệ 07T1
Cán b h ng d n ộ ướ ẫ : Ths Nguy n Văn Nguyênễ
Đà N ng 2010ẵ
4B môn M ng và Truy n Thôngộ ạ ề
M C L CỤ Ụ
T NG QUAN V Đ TÀIỔ Ề Ề
CH NG 1. T NG QUAN V Đ TÀIƯƠ Ổ Ề Ề ..............................................................5
1.1. B IỐ C NHẢ VÀ LÝ DO TH CỰ HI NỆ ĐỀ TÀI......................................................................5
1.2. M CỤ TIÊU C AỦ ĐỀ TÀI..............................................................................................5
CH NG 2. C S LÝ THUY TƯƠ Ơ Ở Ế ......................................................................6
2.1. GI IỚ THI UỆ..............................................................................................................6
2.1.1. M c tiêu l p l chụ ậ ị ................................................................................6
2.1.2. Các đ c đi m c a ti n trìnhặ ể ủ ế ..............................................................6
2.1.3. Đi u ph i không đ c quy n và đi u ph i đ c quy nề ố ộ ề ề ố ộ ề .....................7
2.2. CÁC KHÁI NI MỆ CƠ B NẢ............................................................................................9
2.2.1. Khái ni m gi CPUệ ờ ............................................................................9
2.2.2. Các tr ng thái c a ti n trình liên quan đ n gi CPUạ ủ ế ế ờ .......................9
2.2.3. Khái ni m l p l ch cho CPUệ ậ ị ............................................................11
2.3. CÁC THU TẬ TOÁN L PẬ L CHỊ..................................................................................12
2.3.1. First Come First Served(FCFS)........................................................12
2.3.2. Round robin(RR)...............................................................................12
2.3.3. Shortest Job First(SJF)......................................................................14
2.3.4. Shortest Remain Time(SRT).............................................................15
CH NG 3. CÀI Đ T THU T TOÁNƯƠ Ặ Ậ ..............................................................16
3.1. MÔ HÌNH CÀI Đ TẶ THU TẬ TOÁN................................................................................16
3.1.1. C u trúc d li uấ ữ ệ ...............................................................................16
3.1.2. Thu t toán x lý chungậ ử ....................................................................18
3.2. THU TẬ TOÁN..........................................................................................................20
3.2.1. First In First Out(FIFO)....................................................................20
3.2.2. Round Robin(RR).............................................................................22
3.2.3. Shortest Job First(SRT)....................................................................24
3.2.4. Shortest Remain Time(SRT).............................................................26
CH NG 4. XÂY D NG CH NG TRÌNH DEMOƯƠ Ự ƯƠ .....................................28
4.1. CÁC MODUN CHÍNH.................................................................................................28
4.2. MÔI TR NGƯỜ PHÁT TRI NỂ.......................................................................................28
4.3. GIAO DI NỆ C AỦ CH NGƯƠ TRÌNH...............................................................................28
4.3.1. About.................................................................................................28
4.3.2. Input..................................................................................................29
4.3.3. Output................................................................................................31
4.3.4. Control..............................................................................................31
4.4. ĐÁNH GIÁ VÀ NH NẬ XÉT.........................................................................................33
Lê Ph ng Ti n – Hà Ph c Vi tươ ế ướ ệ
Xây d ng ch ng trình mô ph ng gi i thu t đ nh th i CPUự ươ ỏ ả ậ ị ờ 5
Ch ng 1.ươ T NG QUAN V Đ TÀIỔ Ề Ề
1.1. B i c nh và lý do th c hi n đ tàiố ả ự ệ ề
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 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 đ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, 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ẵ ể ử ụ ủ ệ ờ ể
đ 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 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ý.ổ ữ ả ế ượ ọ ở ộ ề ố ể ử
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: Xâyơ ề ắ ạ ộ ủ ế ị ọ ề
d ng ch ng trình mô ph ng các gi i thu t đ nh th i cho CPU.ự ươ ỏ ả ậ ị ờ
1.2. M c tiêu c a đ tàiụ ủ ề
−Tìm hi u các gi i thu t: First In First Out(FIFO), Round Robin(RR),ể ả ậ
Shortest Job First(SJF), Shortest Remain Time(SRT).
−Ch ra đ c u và nh c đi m c các gi i thu t l p l ch CPU.ỉ ượ ư ượ ể ả ả ậ ậ ị
−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.
Lê Ph ng Ti n – Hà Ph c Vi tươ ế ướ ệ
6B môn M ng và Truy n Thôngộ ạ ề
Ch ng 2.ươ C S LÝ THUY TƠ Ở Ế
2.1. Gi i thi uớ ệ
2.1.1. M c tiêu l p l chụ ậ ị
B đi u ph i không cung c p c ch , mà đ a ra các quy t đ nh. Các h đi uộ ề ố ấ ơ ế ư ế ị ệ ề
hành xây d ng nhi u chi n l t khác nhau đ th c hi n vi c đi u ph i, nh ng t uự ề ế ượ ể ự ệ ệ ề ố ư ự
chung c n đ t đ c các m c tiêu sau:ầ ạ ượ ụ
−S công b ng: 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 đ i vô h n đ đ c c p phát CPUế ả ợ ạ ể ượ ấ
−Tính hi u qu : 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 h i đáp cho các t ngờ ứ ợ ự ể ờ ồ ươ
tác c a ng i s d ngủ ườ ử ụ
−Th i gian l u l i trong h th ng: c c ti u hóa th i gian hoàn t t các tácờ ư ạ ệ ố ự ể ờ ấ
v x lý theo lôụ ử
−Thông l ng t i đa: c c đ i hóa s 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 v i nhau mà ch có th th dung hòa chúng m c đ nào đó.ự ẩ ớ ỉ ể ể ở ứ ộ
2.1.2. 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 nhi u y u t khác nhau đ có th đ t đ cề ả ế ả ề ế ố ể ể ạ ượ
nh ng m c tiêu đ ra. M t s đ c tính c a ti n trình c n đ c 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?ủ ế ỉ ử ụ ế ộ ầ ậ ấ
Lê Ph ng Ti n – Hà Ph c Vi tươ ế ướ ệ
Xây d ng ch ng trình mô ph ng gi i thu t đ nh th i CPUự ươ ỏ ả ậ ị ờ 7
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 đ c nh n 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 các 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 ti n trình c a các tác v đ c x lý theo lô nói chung có 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ộ ư ủ ế ế ế ượ ấ ộ
s tiêu chu n đá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 cao h n) c n đ c u tiên cao 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 thowig gian nh t đ hoàn t t và r i kh i h th ng. Tuy nhiênẽ ầ ấ ể ấ ờ ỏ ệ ố
cũng có quan ddierm 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 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.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 chuy n đ i CPU gi aậ ề ố ầ ế ị ờ ể ể ổ ữ
các ti n trình. H đi u hành các th th c hi n c ch đi u ph i theo nguyên lý đ cế ệ ề ể ự ệ ơ ế ề ố ọ
quy n ho c không đ c quy n:ề ặ ọ ề
Lê Ph ng Ti n – Hà Ph c Vi tươ ế ướ ệ