Giáo trình Hệ điều hành - Chương 2: Tiến trình

xuyên qua việc chọn lệnh cho tới khi không còn điều kiện nào thoả mãn. Sau đó, tiếp tục việc thực hiện các lệnh của chương trình tiếp theo khác.
Cấu trúc này được E.W.Dijktra phát mình để cảnh giới các lệnh, nó được đảm bảo một phần là nhờ ngôn ngữ 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?
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 (P1P5).
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!