Bài giảng Hệ điều hành - Chương 2: Tiến trình

gữ lập trình song song OCCAM (1988). Tiến trình 
trọng lƣợng nhẹ để trao đổi thông tin có thể bao gồm vài lệnh trên một dòng. Thí 
dụ, kiểu sản sinh- tác dụng ở trong OCCAM đƣợc coi nhƣ một công việc gởi tới 
một tiến trình đệm, mà ngƣời sử dụng nhận lại từ đó. 
Hình 2.37------------------- 
Bộ đệm là kiểu bộ đệm hình xuyến với 10 phần tử trong một tiến trình 
BufferProc đƣợc bao bọc bởi mã: 
CHAN OF item producer, consumer: 
INT in, out: 
SEQ 
 in := 0 
 out :=0 
 WHILE TRUE 
 ALT 
 IF (in < out +10) AND (producer? buffer(in REM 10)) 
 in :=in +1 
 IF (out < in )AND (cosumer?more) 
 out := out+1 
Theo đó, chỉ số thích hợp của bộ đệm xuyến đƣợc chuyển cho việc vào –ra 
trong khoảng tác vụ REM (remmainder). Ký hiệu ALT để chỉ dãy tuần tự bất kỳ, 
còn ký hiệu SEQ để chỉ một dãy tuần tự xác định, mà nó xác định việc thực hiện 
của các dòng lệnh. Vì chỉ có việc nhập vào các điều kiện mới mới đƣợc kiểm tra, 
do đó, một tín hiệu bổ sung more của ngƣời sử dụng thì rất cần thiết để gọi thông 
tin tiếp từ bộ đệm. 
2.4.5 Trao đổi thông tin ẩn và hiện 
Trong thí dụ kiểu sản sinh- sử dụng ở mục 2.3.5, các dữ liệu của một tiến trình 
đƣợc chuyển tới một tiến trình khác nhờ khoảng nhớ cơ bản của bộ nhớ, tiến trình 
này sẽ xử lý các dữ liệu vừa chuyển tới. Sự chuyển giao thông tin này gọi là trao 
đổi thông tin ẩn, nếu nhƣ sử dụng putInBuffer(item); còn đƣợc gọi là trao đổi 
thông tin hiển thị sử dụng send(consumer, item) và receive(procedure, item). 
Theo hình 2.38, ngƣời ta rút ra những nhận xét sau đây: 
+ Lệnh send(consumer, item) để chuyển item tới một bộ đệm hệ thống, mà 
nó đƣợc làm đầy nhờ một trong hai tác vụ P() và V(). Nếu bộ đệm đầy, tiến trình 
bị làm chậm lại cho tới khi không gian cho item tồn tại trở lại. 
+ Lệnh receive(procedure, item) để đọc một item từ bộ đệm và đƣợc bảo 
vệ nhờ các tác vụ P() và V(). Nếu không có item nào đƣợc sử dụng, thì tiến trình 
sẽ bị làm chậm cho tới khi một item xuất hiện. 
Dạng trao đổi thông tin kiểu sản sinh- sử dụng có ƣu điểm: Cơ cấu đồng bộ 
của kiểu này có thể đƣợc thực thi với cơ cấu đồng bộ của sự trao đổi thông tin và 
hoạt động bỏ qua giới hạn các kiểu máy tính. 
Chúng ta đã tiết kiệm đƣợc số tác vụ cờ hiệu, mà ở đây, chúng ta giả thiết mục 
đích xác định thích hợp của các thủ tục trao đổi thông tin send(Msg) và 
receive(Msg). Cụ thể, điều này cũng đƣợc thực thi trên hệ thống đơn vi xử lý nhờ 
các tác vụ cờ hiệu cục bộ. Trong trƣờng hợp này, phạm vi bộ đệm là một hộp thoại 
(mainbox), mà ở đó thông tin đƣợc treo vào. 
Nói chung, hầu hết các cơ cấu trao đổi thông tin hoạt động giữa các tiến trình 
với sự trợ giúp của các vùng nhớ, chúng đƣợc trình bày tốt hơn nhờ sự trao đổi 
thông tin hiển. Tiêu phí sẽ giảm đi đáng kể, nếu phần mềm đƣợc tạo lập chạy đƣợc 
không chỉ trên hệ thống đơn vi xử lý, mà cả trong hệ phân bổ. Ở đây, ngƣời ta có 
thể chuyển đổi một cách dễ dàng từ sự trao đổi thông tin giữa các tiến trình này 
với sự trao đổi thông tin giữa các tiến trình khác, vì ở cùng một giao diện, việc 
thực thi các chức năng send() và receive() đƣợc sử dụng nhƣ là một thƣ viện. 
2.5 Các bài tập của chương 2 
2.5.1.Các bài tập về các trạng thái của tiến trình 
Bài tập 2.1 Về các dạng điều hành (operating-typs) 
Bạn hãy kể một vài dạng điều hành của một hệ điều hành (operating-
system) mà bạn nhận thức đƣợc qua chƣơng này. 
Bài tập 2.2 Về các tiến trình 
a) Bạn hãy giải thích sự khác nhau thực chất giữa các khái niệm chƣơng trình, 
tiến trình và thread (xâu) 
b) Trong hệ điều hành Unix của một máy tính, một khối điều khiển tiến trình 
(PCB) và các cấu trúc ngƣời sử dụng đƣợc xem xét nhƣ thế nào? Bạn hãy kiểm tra 
các tệp tin /include/sys/proc.h và /include/sys/user.h, đồng thời bạn hãy biểu thị 
các sự điền vào trong đó theo nhận thức của mình. 
Bài tập 2.3 Về các tiến trình 
a). Một tiến trình dẫn qua những trạng thái tiến trình nào? 
b). Điều kiện chờ đợi và biến cố là gì? 
c). Bạn hãy thay đổi những quá độ trạng thái ở sơ đồ trạng thái của hình 2.2 
bằng một sơ đồ khác tƣơng tự. Bạn hãy lý giải các sự thay đổi của bạn. 
Bài tập 2.4. Về các tiến trình ở hệ điều hành Unix 
Ở hệ điều hành Unix, với ngôn ngữ C, một gọi hệ thống 
ExecuteProgramm(prg) đƣợc thực hiện nhƣ thế nào? Khi đó nhƣ là một thủ tục với 
sự trợ giúp của các gọi hệ thống fork() và waitpid(). 
Bài tập 2.5. Về các tiến trình threads 
Bạn hãy thực hiện hai thủ tục nhƣ là các tiến trình trọng lƣợng nhẹ khi chúng 
đƣợc chuyển giao sự điều khiển một cách đồng thời. 
2.5.2. Các bài tập về định thời tiến trình 
Bài tập 2.6. Về định thời 
a). Sự khác nhau giữa thời gian thực hiện và thời gian của một Job là gì? 
b). Bạn hãy lý giải sự khác nhau giữa giải thuật định thời kiểu phản hồi đa mức 
(multilevel- feedback) và giải thuật định thời kiểu tiền cảnh hậu cảnh (foreground- 
background). 
Bài tập 2.7. Về định thời 
Có 5 xấp nhiệm vụ cùng tới một máy tính gần nhƣ đồng thời; chúng có thời 
gian thực hiện phỏng chừng 10, 6,4,2 và 8 phút; theo đó, chúng có quyền ƣu tiên 
theo thứ tự 3, 5, 2, 1 và 4; ở đây, số 5 là có quyền ƣu tiên cao nhất và số 1 là có 
quyền ƣu tiên thấp nhất. Bạn hãy cho biết thời gian thực thi trung bình cho mỗi 
giải thuật định thời dƣới đây (bỏ qua tổn thất thời gian khi chuyển đổi một tiến 
trình.): 
a). Kiểu định thời quay vòng Robin; 
b). Kiểu định thời có ƣu tiên; 
c). Kiểu định thời đến trƣớc dịch vụ trƣớc; 
d). Kiểu định thời Job ngắn nhất - trƣớc nhất. 
 Ghi chú: Đối với kiểu (a), bạn thấy rằng, hệ thống sử dụng kiểu điều hành đa 
chƣơng trình và mỗi nhiệm vụ nhận một phần xác định thời gian bộ vi xử lý. Đối 
với các kiểu (b), (c) và (d), bạn thấy đấy, các nhiệm vụ lần lƣợt kế nhau đƣợc thực 
hiện. 
Bài tập 2.8. Về định thời song song 
a). Nếu một chƣơng trình đƣợc dẫn tới 40% mã tuần tự (không thể dẫn tới mã 
song song). Khi đó, độ tăng tốc (speedup) đạt đƣợc bao nhiêu? 
b). Giả sử có một phƣơng tiện điều hành A đƣợc tiếp tục sử dụng. Ngƣời ta có 
thể thay đổi sơ đồ Gantt trong hình 2.12 nhƣ thế nào để thời gian sử dụng là ít 
hơn? 
2.5.1 Các bài tập về đồng bộ tiến trình 
Bài tập 2.9. 
Cái gì sẽ xảy ra, nếu ở mục 2.3.1, một tiến trình A nhận đƣợc sự điều khiển và 
sau bƣớc 2 xảy ra sự đổi chiều? Có còn các khả năng tạo ra lỗi không? 
Bài tập 2.10. Về sự ngăn hãm lẫn nhau 
Bạn hãy diễn giải các thủ tục: 
Entering_area(Process: INTEGER) và leaving_area(Process: INTEGER), 
mà chúng chứa đựng giải pháp của Peterson đối với vấn đề ngăn hãm lẫn nhau. 
Cho cái đó, hạn hãy định nghĩa hai biến toàn cục cơ bản Interesse[1..2] và dran. 
Một sự khái quát có thể tồn tại trên n tiến trình không? Nếu có, thì nhƣ thế nào? 
Bài tập 2.11. Về cờ hiệu 
a). Các tác vụ cờ hiệu P và V đƣợc diễn đạt nhƣ thế nào, nếu s chứa đựng một 
số lƣợng các tiến trình chờ đợi? 
b) Giải pháp mô tả quan hệ nhà sản xuất và ngƣời tiêu dùng đƣợc thay đổi nhƣ 
thế nào? 
c). Ngƣời ta phải thay đổi s nhƣ thế nào, nếu có nhiều phƣơng tiện điều hành 
tồn tại? 
Bài tập 2.12. Về đồng bộ tiến trình 
Việc đồng bộ các phƣơng tiện điều hành theo hình 2.11 đƣợc dẫn ra nhƣ thế 
nào với sự trợ giúp của cờ hiệu? 
Bài tập 2.13. Về một vài khái niệm 
a). Sự khác nhau giữa các khái niệm về khoá tử, sự ngăn hãm và sự làm đói 
của các tiến trình là gì? 
b). Sự khác nhau giữa hai khái niệm chờ đợi tích cực và chờ đợi thụ động là ở 
chỗ nào? 
c). Bạn hãy dẫn ra một ví dụ thực tế về khái niệm khoá tử. 
Bài tập 2.14. Về khoá tử và sự ngăn hãm 
Một sinh viên s1 có mƣợn một quyển sách A ở thƣ viện; trong quyển sách, anh 
ta tìm thấy một tài liệu hƣớng dẫn ở quyển sách B; do đó, anh ta muốn mƣợn 
quyển sách này. Quyển sách B hiện tại sinh viên s2 đã mƣợn, anh này tìm thấy ở 
trong sách B một hƣớng dẫn nằm trong sách A; vì thế, anh ta thử đi mƣợn quyển 
sách A. Tình huống này cần phải thiết đặt một khoá tử,một sự ngăn hãm hay 
không có cả hai? Bạn hãy lý giải ý kiến của bạn. 
Bài tập 2.15. Về vấn đề kiểm tra 
a). Bạn hãy thực thi vấn đề đọc/ viết nhƣ là một giải pháp kiểm tra. 
b). Ƣu nhƣợc điểm của giải pháp kiểm tra là gì? 
Bài tập 2.16. Về giải thuật nhà băng(ngân hàng) 
a). Dãy tuần tự nào trong hai dãy tuần tự là có khả năng trong ví dụ nêu ở hình 
2.29 đối với giải thuật nhà băng của 5 tiến trình (P1…P5). 
b). Giả sử tiến trình P1 nhận đƣợc một ổ đĩa băng từ (một loại ổ đĩa mềm dùng 
trong bƣu điện hay ngân hàng) bổ sung. Có phải khi đó hệ thống bị khoá tử đe dọa 
không? 
Bài tập 2.17. Về bảo vệ hệ thống 
a). Một hệ thống máy tính có 6 ổ đĩa và n tiến trình; khi đó mỗi tiến trình cần 
dùng hai ổ đĩa. Hỏi n phải bằng bao nhiêu để đảm bảo một hệ thống an toàn? 
b). Nhằm để phân cấp trạng thái bảo vệ, nếu có m phƣơng tiện điều hành và n 
tiến trình thì số lƣợng các tác vụ tỷ lệ với biểu thức manb. Hỏi a và b bằng bao 
nhiêu thì đạt yêu cầu? 
2.5.4. Các bài tập về trao đổi thông tin 
Bài tập 2.18. 
 a). Bạn hãy mô tả một cách chi tiết dòng lệnh sau đây tác động lên cái gì ở 
trong hệ điều hành Unix? 
 grep deb xyz | wc-1 
b). Ở Unix, việc trao đổi thông tin bị bó hẹp bởi các thông tin trên nhóm tiến 
trình cha/ con. Tại sao việc thực thi gặp phải sự thu hẹp này? 
c). Bạn hãy trình bày sự quá độ giữa các trạng thái tiến trình ở mục 2.1 với sự 
trợ giúp của các thông tin và các hộp thƣ. Ai gởi cho ai các thông tin này? 
Bài tập 2.19. Về trao đổi thông tin kiểu đƣờng kênh (còn gọi kiểu pip) 
Bạn hãy quan sát một hệ thống tiến trình, hệ thống này chỉ trao đổi thông tin 
kiểu các đƣờng kênh (pips) của hệ điều hành Unix, mà bộ đệm của chúng đƣợc 
cấp phát một không gian bộ nhớ nói chung và mỗi đƣờng kênh có đúng một tiến 
trình gởi và một tiến trình nhận. 
a). Dƣới hoàn cảnh nào, một tiến trình đƣợc chen vào để đợi chờ? 
b). Bạn hãy sơ đồ hoá một cơ chế thích hợp để khẳng định hay để phòng tránh 
các khoá tử (deadlocks) cho hệ thống. 
c). Với hệ thống này có một quy tắc để lựa chọn một tiến trình nhƣ là vật hy 
sinh, khi một khoá tử còn tồn tại. Nếu đúng, bạn hãy thiết lập quy tắc này!