Bài t p l n h đi u hànhậ ớ ệ ề L p MT2000ớ
BÀI T P L N H ĐI U HÀNHẬ Ớ Ệ Ề
Quy đ nh :ị
• Ngôn ng l p trình s d ng trong các bài t p là C, C++ ho c Java.ữ ậ ử ụ ậ ặ
• Các bài t p vi t trên UNIX ph i vi t trên n n Linux. ậ ế ả ế ề
• Sinh viên chia nhóm t 3-4 ng i. M i nhóm ch n 2 bài t p thu c 2 ch đ l p trình vàừ ườ ỗ ọ ậ ộ ủ ề ậ
1 bài t p ph n tìm hi u h th ng. ậ ầ ể ệ ố
• Các nhóm sinh viên có th đăng ký đ trình bày tr c l p v đ tài c a nhóm mình. Các nhómể ể ướ ớ ề ề ủ
đăng ký ph i chu n b slide ho c bài vi t đ trình bày tr c l p trong các bu i h c cu i cùngả ẩ ị ặ ế ể ướ ớ ổ ọ ố
c a môn h c.ủ ọ
• Sinh viên có tham gia thuy t trình s đ c c ng thêm đi m vào bài t p l nế ẽ ượ ộ ể ậ ớ
• L p tr ng đánh máy và in ra danh sách các nhóm (h tên, mã s sinh viên), tên bài t p vàớ ưở ọ ố ậ
thông tin đăng ký thuy t trình c a các sinh viên và g i cho GVHD qua email.ế ủ ở
BÀI T P L P TRÌNH Ậ Ậ
Ch đ 1:ủ ề Mô ph ngỏ
1. Tài li u tham kh o ệ ả
-Bài gi ng H đi u hànhả ệ ề , Vũ Lê Hùng
-An Introduction To Operating System, H.M. Deitel
2. Ngôn ng l p trình s d ng: C, C++, Java trên UNIX ho c Windowsữ ậ ử ụ ặ
Bài 1.1: Vi t ch ng trình mô ph ng gi i thu t nhà băng c a Dijsktra đ tránh deadlock. Sế ươ ỏ ả ậ ủ ể ố
l ng các ngu n tài nguyên, các yêu c u c a h th ng đ c t o ng u nhiên. Hãy hi n th c cáchượ ồ ầ ủ ệ ố ượ ạ ẫ ệ ự
xét tr ng thái hi n th i c a h th ng là an toàn hay không an toàn. N u tr ng thái là an toàn,ạ ệ ờ ủ ệ ố ế ạ
ch ng trình ph i ch ra cách đ thu h i tài nguyên h th ng. V i m i yêu c u cung c p tàiươ ả ỉ ể ồ ệ ố ớ ỗ ầ ấ
nguyên, hãy hi n th ra màn hình cách c p phát, thu h i t ng ng.ể ị ấ ồ ươ ứ
Bài 1.2: Vi t ch ng trình mô ph ng các gi i thu t đ nh th i đã h c: FIFO, SJF, SRT, RR,ế ươ ỏ ả ậ ị ờ ọ
HRRN, MLFQ. Đ u vào c a gi i thu t: s quá trình, đ dài các CPU burst, I/O burst… đ c t oầ ủ ả ậ ố ộ ượ ạ
ng u nhiên. Tính toán các thông s và đánh giá đ hi u qu c a t ng gi i thu t.ẫ ố ộ ệ ả ủ ừ ả ậ
Bài 1.3: Vi t ch ng trình mô ph ng các gi i thu t thay th trang đã h c: OPT, FIFO, LRU,ế ươ ỏ ả ậ ế ọ
LFU, NUR, Second Chance. Đ u vào c a gi i thu t: s khung trang, chu i tham kh o trang, yêuầ ủ ả ậ ố ỗ ả
c u thay th trang…đ c t o ng u nhiên. Đánh giá đ hi u qu (so sánh s page fault) c a t ngầ ế ượ ạ ẫ ộ ệ ả ố ủ ừ
gi i thu t. ả ậ
Ch đ 2:ủ ề Đ ng b gi a các quá trìnhồ ộ ữ
1. Tài li u tham kh o ệ ả
-UNIX network programming.
-Tài li u h ng d n th c hành H đi u hànhệ ướ ẫ ự ệ ề , H Qu c Thu n.ồ ố ầ
2. Tìm hi u cách t o quá trình trong UNIX: hàm fork( ).ể ạ
3. Tìm hi u các cách đ ng b gi a các quá trình trong UNIX: semaphore, lock file.ể ồ ộ ữ
4. Ngôn ng l p trình s d ng: C trên UNIX ữ ậ ử ụ
Bài 2.1 : (Semaphore)
Vi t ch ng trình t o ra m t quá trình con. Quá trình cha s nh n chu i s nguyên t bànế ươ ạ ộ ẽ ậ ỗ ố ừ
phím do ng i dùng nh p và ghi vào file tên input. Quá trình con s đ c d li u t file này, s pườ ậ ẽ ọ ữ ệ ừ ắ
x p chúng theo th t tăng d n và ghi vào m t file khác tên là sorted. ế ứ ự ầ ộ
Bài 2.2 : (Semaphore)
Vi t ch ng trình producer-consumer v i bounded buffer. ế ươ ớ
Bài 2.3 : (Semaphore)
Trang 1/6
Bài t p l n h đi u hànhậ ớ ệ ề L p MT2000ớ
Vi t ch ng trình gi i quy t bài toán 5 tri t gia ăn t i. Ch ng trình ph i t o ra 5 quá trìnhế ươ ả ế ế ố ươ ả ạ
con mô ph ng ho t đ ng c a 5 tri t gia. Dùng semaphore đ đ ng b ho t đ ng c a 5 tri t giaỏ ạ ộ ủ ế ể ồ ộ ạ ộ ủ ế
này.
Bài 2.4 : (Lock file)
Vi t ch ng trình gi i quy t bài toán reader/writer d ng t ng quát. Ch ng trình ph i t o raế ươ ả ế ạ ổ ươ ả ạ
5 quá trình đ ng th i v i ho t đ ng đ c/ghi file b t kỳ đ th nghi m gi i thu t. ồ ờ ớ ạ ộ ọ ấ ể ử ệ ả ậ
Ch đ 3:ủ ề Qu n lý b nh ả ộ ớ
1. Tài li u tham kh o ệ ả
-The Design of the UNIX Operating System- Andrew S. Tanenbaum, Ch ng 7ươ
-Interprocess Communications in UNIX-The Nooks and Crannies.
-Tài li u h ng d n th c hành H đi u hànhệ ướ ẫ ự ệ ề , H Qu c Thu n.ồ ố ầ
2. Tìm hi u các hàm truy c p b nh :ể ậ ộ ớ
- Tìm hi u cách t o quá trình trong UNIX dùng hàm fork( ).ể ạ
- Tìm hi u cách c p phát b nh cho quá trình trong h đi u hành UNIX. ể ấ ộ ớ ệ ề
- Tìm hi u các hàm cho phép l y các thông tin v vùng nh c p cho quá trình cũng nhể ấ ề ớ ấ ư
cho phép thay đ i các vùng nh đó.ổ ớ
3. Ngôn ng l p trình s d ng: C trên UNIXữ ậ ử ụ
Bài 3.1 :
Vi t ch ng trình có khai báo 4 bi n nh sau:ế ươ ế ư
-global là bi n nguyên toàn c c không kh i đ ng tr .ế ụ ở ộ ị
-local là bi n nguyên khai báo c c b trong hàm ế ụ ộ doNoth( ) (hàm này không làm gì c ) ả
-intarray là m t con tr đ n bi n ki u nguyên.ộ ỏ ế ế ể
Trong hàm main(), hãy gán global=1, sau đó in đ a ch các segment c a quá trình ra màn hình. Choị ỉ ủ
bi t đ a ch các bi n ế ị ỉ ế global, local và intarray (1). Ti p theo, hãy dùng hàm ếfork() t o ra m t quáạ ộ
trình con. Cho bi t giá tr các đ a ch trên trong quá trình con (2). Hãy gán ế ị ị ỉ ở global=2 trong quá
trình con và cho bi t giá tr m i c a bi n global trong quá trình con và quá trình cha.ế ị ớ ủ ế
Trong quá trình cha, sau khi dùng fork(), hãy g i hàm ọdoNoth(), sau đó dùng malloc() đ xin m tể ộ
vùng nh cho m t m ng 10 s nguyên và gán đ a ch đ u m ng vào bi n ớ ộ ả ố ị ỉ ầ ả ế intarray.
Tr l i các câu h i sau:ả ờ ỏ
-Bi n ếglobal là bi n chung hay bi n riêng c a t ng quá trình?ế ế ủ ừ
-Bi n ếintarray c a quá trình cha ủn m trên stack hay trên heap? ằ
-Bi n ếlocal c a quá trình cha n m trên stack hay trên heap? ủ ằ
- Các đ a ch (1) và (2) có khác nhau không? Gi i thích?ị ỉ ở ả
Bài 3.2 :
Vi t các hàm ếmymalloc() và myfree() d a trên các hàm cung c p s n là ự ấ ẵ brk() và sbrk().
Ch đ 4:ủ ề Thread
1. Tài li u tham kh o ệ ả
-UNIX Internal, ph n ầThread and Lightweight Processes
-Multithread Programming Guide.
-Interprocess Communications in UNIX.
-MSDN CDROM
-Java How to Program, ph n Threadsầ
2. Tìm hi u thread :ể
- Tìm hi u khái ni m thread.ể ệ
- Phân bi t gi a mô hình x lý dùng multithread và dùng nhi u process.ệ ứ ử ề
- Tìm hi u cách đ ng b gi a các thread trong Java và trong Linux.ể ồ ộ ữ
3. Ngôn ng l p trình s d ng có th là C, C++, Java trên UNIX ho c Windows.ữ ậ ử ụ ể ặ
Bài 4.1 :
Trang 2/6
Bài t p l n h đi u hànhậ ớ ệ ề L p MT2000ớ
ng d ng multithread trong bài toán nhân ma tr n. Đ c vào 2 ma tr n A & B t file, sau đóỨ ụ ậ ọ ậ ừ
dùng nhi u thread đ th c hi n vi c nhân 2 ma tr n này. Ghi ma tr n k t qu ra m t file khác. ề ể ự ệ ệ ậ ậ ế ả ộ
Bài 4.2 :
ng d ng multithread trong bài toán x lý nh. Đ c vào m t ma tr n A t file, sau đó dùngỨ ụ ử ả ọ ộ ậ ừ
nhi u thread đ th c hi n x lý trên ma tr n này nh sau : m t ph n t trên ma tr n là trung bìnhề ể ự ệ ử ậ ư ộ ầ ử ậ
c ng c a các ph n t chung quanh nó. Ghi ma tr n k t qu ra m t file khác. ộ ủ ầ ử ậ ế ả ộ
Bài 4.3 :
ng d ng multithread trong bài toán sau : Đ c vào m t ma tr n A t file và nh p vào m t sỨ ụ ọ ộ ậ ừ ậ ộ ố
k, sau đó dùng n thread đ th c hi n tìm ki m trên các ma tr n này xem có bao nhiêu ph n tể ự ệ ế ậ ầ ử
gi ng k. M i l n tìm th y ph n t gi ng k thì tăng bi n chung ố ỗ ầ ấ ầ ử ố ế number (kh i đ ng là 0) lên 1.ở ộ
Bài 4.4 :
ng d ng multithread trong bài toán sau : Đ c vào m t dãy A t file, dùng n thread đ s pỨ ụ ọ ộ ừ ể ắ
x p dãy theo th t tăng d n nh sau:ế ứ ự ầ ư
M i thread l y m t ph n dãy a và s p theo th t tăng d nỗ ấ ộ ầ ắ ứ ự ầ
Sau đó, 1 thread tr n các dãy do n thread v a r i đã s p x p thành dãy k t qu .ộ ừ ồ ắ ế ế ả
Bài 4.5 :
Cho ng i dùng nh p vào 2 s nguyên d ng a và b, sau đó dùng n thread đ tìm ki m cácườ ậ ố ươ ể ế
s nguyên t n m trong kho ng 2 s đã nh p. M i l n tìm đ c m t s thì s tăng bi n chungố ố ằ ả ố ậ ỗ ầ ượ ộ ố ẽ ế
number (kh i đ ng là 0)ở ộ lên 1.
Bài 4.6 :
Cho ng i dùng nh p vào 2 s nguyên d ng a và b, sau đó dùng n thread đ tìm ki m cácườ ậ ố ươ ể ế
s nguyên t n m trong kho ng 2 s đã nh p và ghi các s này ra file.ố ố ằ ả ố ậ ố
Bài 4.7:
Đ c vào m t ma tr n (kích th c N*N) t file, sau đó dùng n thread đ tính t ng c a t ngọ ộ ậ ướ ừ ể ổ ủ ừ
hàng trên ma tr n (1 thread n u tính t ng m t hàng xong có th tính t ng c a m t hàng khác).ậ ế ổ ộ ể ổ ủ ộ
Dùng m t thread đ thu th p các k t qu c a các thread kia và ghi vào m t file k t qu .ộ ể ậ ế ả ủ ộ ế ả
Bài 4.8:
S d ng thread và các ph ng th c đ ng b trên thread đ vi t ch ng trình producers-ử ụ ươ ứ ồ ộ ể ế ươ
consumers v i 1 bounded buffer trong tr ng h p có nhi u producer và nhi u consumer. ớ ườ ợ ề ề
Bài 4.9:
S d ng thread và các ph ng th c đ ng b trên thread đ gi i quy t bài toán N tri t gia ănử ụ ươ ứ ồ ộ ể ả ế ế
t i. ố
Bài 4.10 :
S d ng thread và các ph ng th c đ ng b trên thread đ vi t gi i quy t bài toánử ụ ươ ứ ồ ộ ể ế ả ế
reader/writer d ng t ng quát. ạ ổ
Ch đ 5:ủ ề Giao ti p gi a các quá trìnhế ữ
1. Tài li u tham kh o ệ ả
-UNIX network programming, ph n ầInterprocess Communications
-Interprocess Communication in UNIX
-Tài li u h ng d n th c hành H đi u hànhệ ướ ẫ ự ệ ề , H Qu c Thu n.ồ ố ầ
2. Tìm hi u các c ch giao ti p gi a các quá trình trong UNIXể ơ ế ế ữ
- Tìm hi u các c ch giao ti p gi a các quá trình trong UNIX dùng pipe, messageể ơ ế ế ữ
queue, shared memory.
- u nh c đi m c a t ng ph ng pháp.Ư ượ ể ủ ừ ươ
3. Ngôn ng l p trình s d ng: C trên UNIX ữ ậ ử ụ
Bài 5.1 :
T o ra 2 quá trình. Quá trình th nh t đ c t file nhi u chu i liên ti p, m i chu i g m cácạ ứ ấ ọ ừ ề ỗ ế ỗ ỗ ồ
phép toán +, -, *, / và hai toán h ng. ạ
Ví d trong file s l u các chu i d ng nh sau :ụ ẽ ư ỗ ạ ư
2 + 3
1 - 2
4 * 6
Trang 3/6
Bài t p l n h đi u hànhậ ớ ệ ề L p MT2000ớ
15 / 3
Sau đó quá trình th nh t truy n các chu i d li u này cho quá trình th hai. Quá trình thứ ấ ề ỗ ữ ệ ứ ứ
hai th c hi n tính toán và tr chu i k t qu v l i cho quá trình đ u tiên đ ghi l i vào file nhự ệ ả ỗ ế ả ề ạ ầ ể ạ ư
sau:
2 + 3 = 5
1 - 2 = -1
4 * 6 = 24
15 / 3 =5
Th c hi n bài toán dùng message queue đ giao ti p gi a 2 quá trình.ự ệ ể ế ứ
Bài 5.2 :
Vi t ch ng trình t ng t bài 5.1 nh ng dùng pipe đ giao ti p.ế ươ ươ ự ư ể ế
Bài 5.3 :
Vi t ch ng trình t ng t bài 5.1 nh ng dùng shared memory đ giao ti p.ế ươ ươ ự ư ể ế
Bài 5.4 :
Vi t ch ng trình g m có 2 quá trình. Quá trình th nh t cho ng i dùng nh p vào t bànế ươ ồ ứ ấ ườ ậ ừ
phím m t chu i bi u di n m t phép tính g m các ph n t +, -, (, ). Đ u tiên c a các phép tínhộ ỗ ễ ễ ộ ồ ầ ử ộ ư ủ
trong ngo c (c p d u ( & )) là cao nh t, phép + và – cùng đ u tiên. Ví d :ặ ặ ấ ấ ộ ư ụ
1+2+(2-3-4) –((3+4)-5)
(1+(-2)–((3+4)-5))
Sau đó truy n chu i d li u này cho quá trình th hai. Quá trình th hai th c hi n tính toánề ỗ ữ ệ ứ ứ ự ệ
trên và tr k t qu v cho quá trình th nh t đ hi n th cho ng i s d ng bi t.ả ế ả ề ứ ấ ể ể ị ườ ử ụ ế
Th c hi n bài toán dùng message queue đ giao ti p gi a 2 quá trình.ự ệ ể ế ứ
Bài 5.5 :
Vi t ch ng trình t ng t bài 5.4 nh ng dùng pipe đ giao ti p.ế ươ ươ ự ư ể ế
Bài 5.6 :
Vi t ch ng trình t ng t bài 5.4 nh ng dùng shared memory đ giao ti p.ế ươ ươ ự ư ể ế
Bài 5.7 :
T o ra 2 quá trình P0 và P1. Quá trình P0 đ c t file nhi u dãy s nguyên liên ti p (m i dãyạ ọ ừ ề ố ế ỗ
có th có s ph n t khác nhau). Sau đó quá trình này g i l n l t các dãy này cho quá trình P1.ể ố ầ ử ở ầ ượ
P1 th c hi n s p x p m i dãy theo th t tăng d n, đ ng th i tính t ng c a dãy đó và g i dãyự ệ ắ ế ỗ ứ ự ầ ồ ờ ổ ủ ở
k t qu cùng v i t ng tính đ c t ng ng cho m i dãy v l i quá trình P0. Khi này, P0 th cế ả ớ ổ ượ ươ ứ ỗ ề ạ ự
hi n ghi các dãy k t qu vào l i file sao cho: dãy có t ng nh nh t s đ c ghi đ u tiên, dãy cóệ ế ả ạ ổ ỏ ấ ẽ ượ ầ
t ng l n h n s đ c ghi sau. Th c hi n bài toán dùng message queue đ giao ti p gi a 2 quáổ ớ ơ ẽ ượ ự ệ ể ế ứ
trình.
Bài 5.8 :
Vi t ch ng trình t ng t bài 5.7 nh ng dùng pipe đ giao ti p.ế ươ ươ ự ư ể ế
Bài 5.9 :
Vi t ch ng trình t ng t bài 5.7 nh ng dùng shared memory đ giao ti p.ế ươ ươ ự ư ể ế
Bài 5.10 :
T o ra 2 quá trình P0 và P1. Quá trình P0 đ c t file m t ma tr n vuông c p N*N, sau đó g iạ ọ ừ ộ ậ ấ ở
ma tr n này cho P1. Quá trình P1 s th c hi n ngh ch đ o ma tr n này và ghi k t qu xu ng m tậ ẽ ự ệ ị ả ậ ế ả ố ộ
file khác. N u ma tr n không th ngh ch đ o đ c, P1 ghi vào file k t qu dòng thông báo t ngế ậ ể ị ả ượ ế ả ươ
ng.ứ
Th c hi n bài toán dùng message queue đ giao ti p gi a 2 quá trình.ự ệ ể ế ứ
Bài 5.11 :
Vi t ch ng trình t ng t bài 5.10 nh ng dùng pipe đ giao ti p.ế ươ ươ ự ư ể ế
Bài 5.12 :
Vi t ch ng trình t ng t bài 5.10 nh ng dùng shared memory đ giao ti p.ế ươ ươ ự ư ể ế
Ch đ 6:ủ ề Socket
1. Tài li u tham kh o ệ ả
-UNIX network programming, ph n ầBerkeley Sockets
-Interprocess Communication in UNIX
-Internetworking with TCP/IP volume III, ph n ầmô hình Client/Server.
Trang 4/6
Bài t p l n h đi u hànhậ ớ ệ ề L p MT2000ớ
-Internetworking with TCP/IP volume II (cho các bài v broadcast và multicast).ề
-MSDN CDROM
2. Tìm hi u socket và mô hình client/serverể
-Tìm hi u c ch làm vi c c a socket, ể ơ ế ệ ủ
-Các b c c n thi t trong vi c t o socket dùng TCP và UDP.ướ ầ ế ệ ạ
- Mô hình client/server.
3. Ngôn ng l p trình s d ng: C trên UNIX, C++ trên Windowsữ ậ ử ụ
Bài 6.1:
T o hai quá trình server và client hai máy khác nhau. Client nh n m t dãy s t ng i sạ ở ậ ộ ố ừ ườ ử
d ng và g i cho quá trình server. Server s p x p chu i này theo th t tăng d n và g i tr l iụ ở ắ ế ỗ ứ ự ầ ở ả ạ
client đ hi n th cho ng i dùng bi t.ể ể ị ườ ế
Bài 6.2:
T o hai quá trình server và client hai máy khác nhau. Client nh n m t s nguyên d ng tạ ở ậ ộ ố ươ ừ
ng i s d ng và g i cho quá trình server. Server phân tích s này thành th a s nguyên t vàườ ử ụ ở ố ừ ố ố
g i tr l i client đ hi n th cho ng i dùng bi t.ở ả ạ ể ể ị ườ ế
Bài 6.3:
Dùng socket đ vi t ch ng trình chat gi a hai quá trình trên hai máy khác nhau. ể ế ươ ữ
G i ý : vi t 1 ch ng trình chat client (đ ng i dùng s d ng) và dùng m t ch ng trìnhợ ế ươ ể ườ ử ụ ộ ươ
chat server đ qu n lý các chat client đó.ể ả
Bài 6.4 :
T o hai quá trình server và client hai máy khác nhau. Client nh n m t chu i ký t do ng iạ ở ậ ộ ỗ ự ườ
s d ng nh p theo d ng m t s l nh thông d ng và thông s , ví d nh chu i “mkdirử ụ ậ ạ ộ ố ệ ụ ố ụ ư ỗ
/temp/new” và g i cho quá trình server. Server th c hi n l nh này và g i thông báo thành côngở ự ệ ệ ở
hay không cho client đ hi n th cho ng i dùng bi t.ể ể ị ườ ế
Bài 6.5 :
Vi t 2 ch ng trình là server và admin. Cho th c thi ch ng trình server trên nhi u máy khácế ươ ự ươ ề
nhau. Sau đó s th c thi ch ng trình admin đ bi t đ c có bao nhiêu ch ng trình server đangẽ ự ươ ể ế ượ ươ
ch y trên m ng đó. Dùng c ch broadcast.ạ ạ ơ ế
Bài 6.6 :
T ng t bài 5.5 nh ng dùng c ch multicast.ươ ự ư ơ ế
Bài 6.7 :
Vi t 2 ch ng trình listen và send. Ch ng trình listen dùng đ nh n thông tin t các ng iế ươ ươ ể ậ ừ ườ
khác g i đ n và hi n th lên màn hình.Ch ng trình send cho phép g i thông tin đ n t t c cácở ế ể ị ươ ở ế ấ ả
ng i ch y ch ng trình listen trên m ng. Dùng c ch broadcast.ườ ạ ươ ạ ơ ế
Bài 6.8 :
T ng t bài 5.7 nh ng dùng c ch multicast.ươ ự ư ơ ế
BÀI T P V TÌM HI U H TH NGẬ Ề Ể Ệ Ố
Tài li u tham kh o ệ ả
-ftp.dit.hcmut.edu.vn/pub/OS/books
- Sinh viên t tìm ki m trên Internetự ế
Bài 1: Tìm hi u c ch boot và cách cài đ t multiboot cho nhi u h đi u hành trên m t máyể ơ ế ặ ề ệ ề ộ
đ n.ơ
Bài 2: Tìm hi u ph n m m VMWare và cách ch y nhi u h đi u hành trên cùng m t máy t iể ầ ề ạ ề ệ ề ộ ạ
m t th i đi m.ộ ờ ể
Bài 3: Tìm hi u và phân tích ki n trúc t ng quát c a h đi u hành Linux.ể ế ổ ủ ệ ề
Bài 4: Tìm hi u và phân tích ki n trúc t ng quát c a h đi u hành WinNT/2000.ể ế ổ ủ ệ ề
Bài 5: Tìm hi u c ch đ nh th i c a h đi u hành Solaris/Linux.ể ơ ế ị ờ ủ ệ ề
Bài 6: Tìm hi u c ch đ nh th i c a h đi u hành WinNT /2000.ể ơ ế ị ờ ủ ệ ề
Trang 5/6