Ch ng trình mô ph ng các gi i thu t đ nh th i ươ ỏ ả ậ ị ờ
L I C M NỜ Ả Ơ
Em xin t lòng c m n t i các th y cô giáo là cán b gi ng d y c a khoa Công nghỏ ả ơ ớ ầ ộ ả ạ ủ ệ
Thông tin- Tr ng Đ i h c Bách khoa. Đ c bi t, em xin bày t lòng bi t n sâu s c t iườ ạ ọ ặ ệ ỏ ế ơ ắ ớ
th y giáo Nguy n Võ Quang Đông, là ng i tr c ti p h ng d n em hoàn thành đ tàiầ ễ ườ ự ế ướ ẫ ề
này.
Do th i gian có h n nên không tránh kh i thi u sót, kính mong đ c s góp ý c aờ ạ ỏ ế ượ ự ủ
các th y cô đ đ tài tr nên hoàn thi n h n.ầ ể ề ở ệ ơ
Em xin chân thành c m n!ả ơ
Đà N ng, 12/2007 ẵ
SVTH: Tr n Văn Trungầ
Lớp : 03T3
Tr n Văn Trungầ, L p: 03T3 Trang :ớ1
Ch ng trình mô ph ng các gi i thu t đ nh th i ươ ỏ ả ậ ị ờ
M C L CỤ Ụ
L I C M NỜ Ả Ơ ................................................................................................................................ 1
L I NÓI Đ UỜ Ầ ................................................................................................................................ 2
Ch ng I : T ng quan v đ tàiươ ổ ề ề .................................................................................... 3
Ch ng II. C s lý thuy tươ ơ ở ế ..................................................................................................... 4
Ch ng III: Phân tích và thi t k h th ngươ ế ế ệ ố ........................................................................... 13
Ch ng IV K T LU Nươ Ế Ậ .................................................................................. 28
PH L CỤ Ụ ...................................................................................................................................... 29
TÀI LI U THAM KH OỆ Ả ............................................................................................................. 37
NH N XÉT C A GIÁO VIÊNẬ Ủ .................................................................................................... 38
L I NÓI Đ UỜ Ầ
Trong cu c s ng ngày nay và trong t ng lai, tin h c tr thành m t ph n không thộ ố ươ ọ ở ộ ầ ể
thi u. V i s bùng n c a công ngh thông tin đóng góp m t ph n không nh vào vi cế ớ ự ổ ủ ệ ộ ầ ỏ ệ
nâng cao năng su t, hi u qu cho s phát tri n cho các ngành khác nhau c a xã h i.ấ ệ ả ự ể ủ ộ
T i n c ta, m t đ t n c mà tin h c m i b t đ u phát tri n, cũng đã đ t đ cạ ướ ộ ấ ướ ọ ớ ắ ầ ể ạ ượ
nhi u thành t u trong lĩnh v c ng d ng t i các ngành giáo d c và đào t o, quân s , đ aề ự ự ứ ụ ạ ụ ạ ự ị
chính,…
Trong vòng b n th p k l i đây, h đi u hành dã có nh ng b c phát tri n đáng kố ậ ỷ ạ ệ ề ữ ướ ể ể
b i do hai lý do sau:ở
+ Đó là h đi u khi n các ho t đ ng bên trong các máy tính đi n t xu t phát t yêuệ ề ể ạ ộ ệ ử ấ ừ
c u c a các nhà tin h c và cũng do các chuyên gia cao c p c a ngành tin h c l p trìnhầ ủ ọ ấ ủ ọ ậ
nên.
+ Đó là h th ng đ u tiên k t khi ph n c ng đ c hình thành t o đi u ki n thu n l iệ ố ầ ể ừ ầ ứ ượ ạ ề ệ ậ ợ
cho ng i s d ng trong vi c phát tri n và th c hi n các ch ng trình máy tính c aườ ử ụ ệ ể ự ệ ươ ủ
mình.
H đi u hành có hai ch c năng chính là:ệ ề ứ
1. Qu n lý và chia s tài nguyênả ẻ
2. Gi l p m t máy tính m r ng.ả ậ ộ ở ộ
Và 7 thành ph n c a h đi u hành là:ầ ủ ệ ề
1. Qu n lý ti n trìnhả ế
2. Qu n lý b nh chínhả ộ ớ
3. Qu n lý nh p xu tả ậ ấ
4. Qu n lý t p tinả ậ
5. H th ng b o vệ ố ả ệ
6. Qu n lý m ngả ạ
7. H th ng d ch l nhệ ố ị ệ
Đ án này em xin trình bày ồ Vi t ch ng trình mô ph ng các gi i thu t đ nh th iế ươ ỏ ả ậ ị ờ
FIFO, SJF, RR,… nói v cách ho t đ ng c a các ti n trình trong h đi u hành.ề ạ ộ ủ ế ệ ề
Tr n Văn Trungầ, L p: 03T3 Trang :ớ2
Ch ng trình mô ph ng các gi i thu t đ nh th i ươ ỏ ả ậ ị ờ
Ch ng I : T ng quan v đ tàiươ ổ ề ề
1. Gi i thi u s l c v đ tàiớ ệ ơ ượ ề ề
V i đ tài ớ ề vi t ch ng trình mô ph ng các gi i thu t đ nh th i FIFO, RR, SJF,ế ươ ỏ ả ậ ị ờ
HRRN, MLFQ. Trình bày quá trình ho t đ ng c a các ti n trình trong CPU, các tr ngạ ộ ủ ế ạ
thái c a h th ng và vi c chuy n t tr ng thái này sang tr ng thái khác đ c th c hi nủ ệ ố ệ ể ừ ạ ạ ượ ự ệ
theo m t quá trình nào đó.ộ
2. M c tiêu đ tàiụ ề
M c tiêu c a đ tài là tìm hi u và nghiên c u s giao ti p gi a các ti n trình, làmụ ủ ề ể ứ ự ế ữ ế
th nào đ phân chia công vi c cho các ti n trình ch y trong h đi u hành. Vi t ch ngế ể ệ ế ạ ệ ề ế ươ
trình mô ph ng gi i thu t FIFO, RR, SJF, HRRN, MLFQ nói lên nguyên t c ho t đ ngỏ ả ậ ắ ạ ộ
c a gi i thu t này và nêu lên s khác nhau gi a các g i thu t.ủ ả ậ ự ử ả ậ
Gi i thi u h đi u hành nêu lên đ nh nghĩa, ch c năng c a h đi u hành.ớ ệ ệ ề ị ứ ủ ệ ề
2. H ng gi i quy tướ ả ế
Vì gi i h n v ki n th c cũng nh kinh nghi m trong vi c tìm hi u h đi u hành vàớ ạ ề ế ứ ư ệ ệ ể ệ ề
th i gian h n ch , nên em ch đi sâu tìm hi u đ c m t s gi i thu t.ờ ạ ế ỉ ể ượ ộ ố ả ậ
Trong đ tài này em s d ng ngôn ng C đ cài đ t ch ng trình minh ho .ề ử ụ ữ ể ặ ươ ạ
Tr n Văn Trungầ, L p: 03T3 Trang :ớ3
Ch ng trình mô ph ng các gi i thu t đ nh th i ươ ỏ ả ậ ị ờ
Ch ng II. ươ C s lý thuy tơ ở ế
I. H đi u hànhệ ề
Xét v ph ng di n ch c năng, các ch ng trình máy tính có th chia thành haiề ươ ệ ứ ươ ể
nhóm chính, đó là:
- Các ch ng trình c s tr giúp vi c đi u hành các máy tính.ươ ơ ở ợ ệ ề
- Các ch ng trình ng d ng gi i quy t các bài toán trong th c ti n.ươ ứ ụ ả ế ự ễ
1. Đ nh nghĩa h đi u hànhị ệ ề
H đi u hành (HĐH) là m t ph n quan tr ng c a mõi h th ng thông tin. Mõi hệ ề ộ ầ ọ ủ ệ ố ệ
th ng thông tin g m 4 thành ph n quan tr ng: Ph n c ng, h đi u hành, ch ng trìnhố ồ ầ ọ ầ ứ ệ ề ươ
ng d ng và ng i s d ng.ứ ụ ườ ử ụ
Ph n c ng: G m CPU, b nh , thi t b vào ra cung c p các tài nguyên thông tin cầ ứ ồ ộ ớ ế ị ấ ơ
s .ở
Các ch ng trình ng d ng: G m ch ng trình d ch, h th ng c s d li u, trìnhươ ứ ụ ồ ươ ị ệ ố ơ ở ữ ệ
so n th o văn b n,… quy đ nh cách s d ng các tài nguyên đó đ gi quy t nh ng v nạ ả ả ị ử ụ ể ả ế ữ ấ
đ c a ng i s d ng.ề ủ ườ ử ụ
H đi u hành: Đi u khi n và đ ng b vi c s d ng ph n c ng c a các ch ngệ ề ề ể ồ ộ ệ ử ụ ầ ứ ủ ươ
trình ng d ng ph c v các ng i s d ng khác nhau v i các m c đích phong phú đaứ ụ ụ ụ ườ ử ụ ớ ụ
d ng.ạ
Ng i s d ng: Hi u theo nghĩa r ng bao g m nh ng ng i s d ng thu n tuý vàườ ử ụ ể ộ ồ ữ ườ ử ụ ầ
các cán b v n hành đ c bi t đ i v i các máy trung và các máy l n.ộ ậ ặ ệ ố ớ ớ
Ta có th hi u h đi u hành là h th ng các ch ng trình đ m b o các ch c năngể ể ệ ề ệ ố ươ ả ả ứ
giao ti p ng i máy và và qu n lý tài nguyên h th ng tính toán.ế ườ ả ệ ố
Tuy nhiên có nhi u ng i quan sát HĐH d i các góc đ khác nhau vì th t n t iề ườ ướ ộ ế ồ ạ
nhi u đ nh nghĩa v HĐH. ề ị ề
Đ i v i ng i s d ng : HĐH là t p h p các ch ng trình, ph c v khai thác hố ớ ườ ử ụ ậ ợ ươ ụ ụ ệ
th ng tính toán m t cách d dàng, thu n ti n.ố ộ ễ ậ ệ
Tr n Văn Trungầ, L p: 03T3 Trang :ớ4
Ch ng trình mô ph ng các gi i thu t đ nh th i ươ ỏ ả ậ ị ờ
Ng i s d ng khi th c hi n m t ch ng trình nào đó trên máy tính thì ch quan tâmườ ử ụ ự ệ ộ ươ ỉ
đ n vi c h th ng có đáp ng đ c nhu c u c a h hay không? H không quan tâmế ệ ệ ố ứ ượ ầ ủ ộ ọ
đ n vi c h đi u hành làm nh th nào, nh m m c đích gì, có c u trúc nh th nào?ế ệ ệ ề ư ế ằ ụ ấ ư ế
Đ i v i ng i làm công tác qu n lý: HĐH là m t t p các ch ng trình ph c vố ớ ườ ả ộ ậ ươ ụ ụ
qu n lý ch t ch và s d ng t i u các tài nguyên c a h th ng.ả ặ ẽ ử ụ ố ư ủ ệ ố
Đ i v i cán b k thu t: HĐH là h th ng ch ng trình bao trùm lên m t máy tínhố ớ ộ ỹ ậ ệ ố ươ ộ
v t lý c th đ t o ra m t máy logic v i nh ng tài nguyên m i và kh năng m i.ậ ụ ể ể ạ ộ ớ ữ ớ ả ớ
2. Các ch c năng chính c a h đi u hànhứ ủ ệ ề
H đi u hành là m t ch ng trình đóng vai trò trung gian trong vi c giao ti p gi aệ ề ộ ươ ệ ế ữ
ng i s d ng và ph n c ng c a máy tính. M c tiêu c a h đi u hành là cung c p m tườ ử ụ ầ ứ ủ ụ ủ ệ ề ấ ộ
môi tr ng cho phép ng i s d ng phát tri n và th c hi n các ng d ng c a h m tườ ườ ử ụ ể ự ệ ứ ụ ủ ọ ộ
cách d dàng và hi u qu . Theo nguyên t c, m t h đi u hành c n tho mãn hai ch cễ ệ ả ắ ộ ệ ề ầ ả ứ
năng sau:
a .Qu n lý, chia s tài nguyên.ả ẻ
Tài nguyên h th ng, đ c bi t các tài nguyên ph c ng nh CPU, b nh , thi t bệ ố ặ ệ ầ ứ ư ộ ớ ế ị
ngo i vi,.. h đi u hành c n có các c ch và chi n l c thích h p đ qu n lý vi cạ ệ ề ầ ơ ế ế ượ ợ ể ả ệ
phân ph i tài nguyên.ố
b. Gi l p m t máy tínhả ậ ộ
Ch c năng th hai c a h đi u hành là che d u các chi ti t ph n c ng c a máy tínhứ ứ ủ ệ ề ấ ế ầ ứ ủ
và gi i thi u v i ng i dùng m t máy tính m r ng có đ y đ các ch c năng c a máyớ ệ ớ ườ ộ ở ộ ầ ủ ứ ủ
tính.
V i đ tài ớ ề Vi t ch ng trình mô ph ng các gi i thu t đ nh th i ế ươ ỏ ả ậ ị ờ trình bày v quáề
trình ho t đ ng c a các ti n trình trong CPU, các tr ng thái c a h th ng tính toán vàạ ộ ủ ế ạ ủ ệ ố
vi c chuy n t tr ng thái này sang tr ng thái khác đ c th c hi n theo m t ch ngệ ể ừ ạ ạ ượ ự ệ ộ ươ
trình nào đó.
Đã có nhi u ch ng trình nghiên c u đ tài này và ng d ng trong cu c s ng và nóề ươ ứ ề ứ ụ ộ ố
có nh ng u và khuy t đi m c đ nhữ ư ế ể ố ị
+ u đi m : Đã đ a ra đ c cách x lý c a các ti n trình Ư ể ư ượ ử ủ ế
Ch ng trình đ n gi n, ươ ơ ả
+ Khuy t đi m : Ch a nêu rõ vi c t p h p đi u ph i gi a các ti n trìnhế ể ư ệ ậ ợ ề ố ữ ế
H ng nghiên c u gi i thi u ướ ứ ớ ệ
3. Các chi n l c đi u ph iế ượ ề ố
a. Chi n l c FIFOế ượ
Nguyên t c: CPU đ c c p phát cho ti n trình đ u tiên trong danh sách s n sàng cóắ ượ ấ ế ầ ẵ
yêu c u, là ti n trình đ c đ a vào h th ng s m nh t. Đây là m t thu t toán đi u ph iầ ế ượ ư ệ ố ớ ấ ộ ậ ề ố
theo nguyên t c đ c quy n. M t khi CPU đ c c p phát cho ti n trình, CPU ch đ cắ ộ ề ộ ượ ấ ế ỉ ượ
ti n trình t nguy n gi i phóng khi k t thúc x lí hay khi có m t yêu c u xu t/ nh p.ế ự ệ ả ế ử ộ ầ ấ ậ
Chi n l c này thì th i gian ch trung bình không đ t c c ti u và bi n đ i đáng k đ iế ượ ờ ờ ạ ự ể ế ổ ể ố
v i các giá tr v th i gian yêu c u x lí và th t khác nhau c a cácd ti n trình trongớ ị ề ờ ầ ử ứ ự ủ ế
danh sách s n sàng. Cá th x y ra hi n t ng tích lu th i gian ch , khi t t c các ti nẵ ể ả ệ ượ ỹ ờ ờ ấ ả ế
trình ph I ch đ i m t ti n trình có yêu c c th i gian dài k t thúc x lí .ả ờ ợ ộ ế ầ ờ ế ử
Tr n Văn Trungầ, L p: 03T3 Trang :ớ5