BÀI 4 : LIÊN LẠC GIỮA CÁC TIẾN TRÌNH & VẤN ĐỀ ĐỒNG BỘ HOÁ
Các tiến trình trên nguyên tắc là hoàn toàn độc lập, nhưng thực tế có thể như thế không? Trong bài này chúng ta sẽ tìm hiểu lý do các tiến trình có nhu cầu liên lạc, các cơ chế hỗ trợ việc liên lạc này cũng như những vấn đề đặt ra khi c�c tiến trình trao đổi th�ng tin với nhau.
I. LIÊN LẠC GIỮA CÁC TIẾN TRÌNH
I.1. Nhu cầu liên lạc giữa các tiến trình
Trong môi trường đa chương, một tiến trình không đơn độc trong hệ thống , mà có thể ảnh hưởng đến c�c tiến trình khác , hoặc bị các tiến trình khác tác động. N�i c�ch kh�c, c�c tiến trình là những thực thể độc lập , nhưng chúng vẫn có nhu cầu liên lạc với nhau để :
: nhiều tiến trình có thể cùng quan tâm đến những dữ liệu nào đ�, do vậy hệ điều hành cần cung cấp một môi trường cho phép sự truy cập đồng thời đến c�c dữ liệu chung.Chia sẻ thông tin
Hợp tác hoàn thành tác vụ
: đ�i khi để đạt được một sự xử lý nhanh chóng, người ta phân chia một tác vụ thành các công việc nhỏ có thể tiến hành song song. Thường thì các công việc nhỏ này cần hợp tác với nhau để cùng hoàn thành tác vụ ban đầu, v� dụ dữ liệu kết xuất của tiến trình này lại là dữ liệu nhập cho tiến trình khác �Trong các trường hợp đ�, hệ điều hành cần cung cấp cơ chế để c�c tiến trình có thể trao đổi th�ng tin với nhau.I.2. Các vấn đề nảy sinh trong việc liên lạc giữa các tiến trình
Do mỗi tiến trình sỡ hữu một không gian địa chỉ riêng biệt, nên các tiến trình không thể liên lạc trực tiếp dễ dàng mà phải nhờ vào các cơ chế do hệ điều hành cung cấp. Khi cung cấp cơ chế liên lạc cho các tiến trình, hệ điều hành thường phải tìm giải pháp cho các vấn đề ch�nh yếu sau:
Liên kết tường minh hay tiềm ẩn [explicit naming/implicit naming]
: tiến trình có cần phải biết tiến trình nào đang trao đổi hay chia sẻ th�ng tin với n�? Mối liên kết được gọi là tường minh khi được thiết lập rõ ràng , trực tiếp giữa các tiến trình, và là tiềm ẩn khi các tiến trình liên lạc với nhau thông qua một qui ước ngầm nào đ�.Liên lạc theo chế độ đồng bộ hay kh�ng đồng bộ [blocking / non-blocking]
: khi một tiến trình trao đổi th�ng tin với một tiến trình khác, các tiến trình có cần phải đợi cho thao t�c liên lạc hoàn tất rồi mới tiếp tục các xử lý khác? Các tiến trình liên lạc theo cơ chế đồng bộ sẽ chờ nhau hoàn tất việc liên lạc, còn các tiến trình liên lạc theo cơ chế nonblocking thì không.Liên lạc giữa các tiến trình trong hệ thống tập trung và hệ thống phân tán
: cơ chế liên lạc giữa các tiến trình trong cùng một máy tính có sự khác biệt với việc liên lạc giữa các tiến trình giữa những máy tính khác nhau?Hầu hết các hệ điều hành đưa ra nhiều cơ chế liên lạc khác nhau, mỗi cơ chế có những đặc t�nh riêng, và thích hợp trong một hoàn cảnh chuyên biệt.
II. Các Cơ Chế Thông Tin Liên lạc
II.1. Tín hiệu [Signal]
Giới thiệu: Tín hiệu là một cơ chế phần mềm tương tự như các ngắt cứng tác động đến c�c tiến trình. Một tín hiệu được sử dụng để th�ng b�o cho tiến trình về một sự kiện nào đ� xảy ra. C� nhiều t�n hiệu được định nghĩa, mỗi một t�n hiệu c� một � nghĩa tương ứng với một sự kiện đặc trưng.
Ví dụ: Một số tín hiệu của UNIX
Tín hiệu | Mô tả |
| Người dùng nhấn phím DEL để ngắt xử lý tiến trình |
SIGQUIT | Yêu cầu thoát xử lý |
SIGILL | Tiến trình xử lý một chỉ thị bất hợp lệ |
| Yêu cầu kết thúc một tiến trình |
SIGFPT | Lỗi floating � point xảy ra [ chia cho 0] |
SIGPIPE | Tiến trình ghi dữ liệu vào pipe mà không có reader |
SIGSEGV | Tiến trình truy xuất đến một địa chỉ bất hợp lệ |
| Tiến trình con kết thúc |
SIGUSR1 | Tín hiệu 1 do người dùng định nghĩa |
SIGUSR2 | Tín hiệu 2 do người dùng định nghĩa |
Mỗi tiến trình sỡ hữu một bảng biễu diễn các tín hiệu khác nhau. Với mỗi tín hiệu sẽ có tương ứng một trình xử lý tín hiệu [signal handler] qui định c�c xử l� của tiến trình khi nhận được tín hiệu tương ứng.
Các tín hiệu được gởi đi bởi:
Phần cứng [ví dụ lỗi do các phép tính số học]
Hạt nhân hệ điều hành gởi đến một tiến trình [ ví dụ lưu ý tiến trình khi có một thiết bị nhập/xuất tự do].
Một tiến trình gởi đến một tiến trình khác [ ví dụ tiến trình cha yêu cầu một tiến trình con kết thúc]
Người dùng [ ví dụ nhấn phím Ctl-C để ngắt xử l� của tiến trình]
Khi một tiến trình nhận một tín hiệu, nó có thể xử sự theo một trong các cách sau:
Bỏ qua tín hiệu
Xử lý tín hiệu theo kiểu mặc định
Tiếp nhận tín hiệu và xử lý theo cách đặc biệt của tiến trình.
H�nh 3.1 Li�n lạc bằng t�n hiệu
Thảo luận:
Liên lạc bằng tín hiệu mang tính chất không đồng bộ, nghĩa là một tiến trình nhận tín hiệu không thể xác định trước thời điểm nhận t�nh hiệu. Hơn nữa các tiến trình không thể kiểm tra được sự kiện tương ứng với tín hiệu có thật sự xảy ra? Cuối cùng, các tiến trình chỉ có thể thông báo cho nhau về một biến cố nào đ�, mà không trao đổi dữ liệu theo cơ chế này được.
II.2. Pipe
Giới thiệu:
Một pipe là một kênh liên lạc trực tiếp giữa hai tiến trình: dữ liệu xuất của tiến trình này được chuyển đến làm dữ liệu nhập cho tiến trình kia dưới dạng một dòng các byte.Khi một pipe được thiết lập giữa hai tiến trình, một trong chúng sẽ ghi dữ liệu vào pipe và tiến trình kia sẽ đọc dữ liệu từ pipe. Thứ tự dữ liệu truyền qua pipe được bảo toàn theo nguyên tắc FIFO. Một pipe có kích thước giới hạn [thường là 4096 ký tự]
H�nh 3.2 Li�n lạc qua pipe
Một tiến trình chỉ có thể sử dụng một pipe do nó tạo ra hay kế thừa từ tiến trình cha. Hệ điều hành cung cấp các lời gọi hệ thống read/write cho các tiến trình thực hiện thao tác đọc/ghi dữ liệu trong pipe. Hệ điều hành cũng chịu trách nhiệm đồng bộ h�a việc truy xuất pipe trong c�c tình huống:
Tiến trình đọc pipe sẽ bị kh�a nếu pipe trống, n� sẽ phải đợi đến khi pipe c� dữ liệu để truy xuất.
Tiến trình ghi pipe sẽ bị khóa nếu pipe đầy, n� sẽ phải đợi đến khi pipe c� chỗ trống để chứa dữ liệu.
Thảo luận:
Liên lạc bằng pipe là một cơ chế liên lạc một chiều [unidirectional], nghĩa là một tiến trình kết nối với một pipe chỉ có thể thực hiện một trong hai thao tác đọc hoặc ghi, nhưng không thể thực hiện cả hai. Một số hệ điều hành cho phép thiết lập hai pipe giữa một cặp tiến trình để tạo liên lạc hai chiều. Trong những hệ thống đ�, c� nguy cơ xảy ra tình trạng tắc nghẽn [deadlock]: một pipe bị giới hạn về kích thước, do vậy nếu cả hai pipe nối kết hai tiến trình đều đầy[hoặc đều trống] và cả hai tiến trình đều muốn ghi [hay đọc] dữ liệu vào pipe[mỗi tiến trình ghi dữ liệu vào một pipe], chúng sẽ cùng bị khóa và chờ lẫn nhau mãi mãi!Cơ chế này cho phép truyền dữ liệu với cách thức không cấu trúc.
Ngoài ra, một giới hạn của hình thức liên lạc này là chỉ cho phép kết nối hai tiến trình có quan hệ cha-con, và trên cùng một máy tính.
II.3. Vùng nhớ chia sẻ
Giới thiệu:
Cách tiếp cận của cơ chế này là cho nhiều tiến trình cùng truy xuất đến một vùng nhớ chung gọi là vùng nhớ chia sẻ [shared memory].Không có bất kỳ hành vi truyền dữ liệu nào cần phải thực hiện ở đ�y, dữ liệu chỉ đơn giản được đặt vào một vùng nhớ mà nhiều tiến trình có thể cùng truy cập được.Với phương thức này, các tiến trình chia sẻ một vùng nhớ vật lý thông qua trung gian không gian địa chỉ của ch�ng. Một vùng nhớ chia sẻ tồn tại độc lập với c�c tiến trình, và khi một tiến trình muốn truy xuất đến vùng nhớ này, tiến trình phải kết gắn vùng nhớ chung đ� vào không gian địa chỉ riêng của từng tiến trình, và thao tác trên đ� như một vùng nhớ riêng của mình.
H�nh 3.3 Li�n lạc qua v�ng nhớ chia sẻ
Thảo luận:
. Đ�y là phương pháp nhanh nhất để trao đổi dữ liệu giữa c�c tiến trình. Nhưng phương thức này cũng làm phát sinh các khó khăn trong việc bảo đảm sự toàn vẹn dữ liệu [coherence] , ví dụ: làm sao biết được dữ liệu mà một tiến trình truy xuất là dữ liệu mới nhất mà tiến trình khác đã ghi? Làm thế nào ngăn cản hai tiến trình cùng đồng thờighi dữ liệu vào vùng nhớ chung?�Rõ ràng vùng nhớ chia sẻ cần được bảo vệ bằng những cơ chế đồng bộ h�a th�ch hợp..Một khuyết điểm của phương pháp liên lạc này là không thể áp dụng hiệu quả trong các hệ phân tán , để trao đổi th�ng tin giữa c�c m�y t�nh kh�c nhau.
II.4. Trao đổi th�ng điệp [Message]
Giới thiệu:
Hệ điều hành còn cung cấp một cơ chế liên lạc giữa các tiến trình không thông qua việc chia sẻ một tài nguyên chung , mà thông qua việc gởi thông điệp. Để hỗ trợ cơ chế liên lạc bằng thông điệp, hệ điều hành cung cấp các hàm IPC chuẩn [Interprocess communication], cơ bản là hai hàm:[message] : gởi một thông điệpSend
Receive
[message] : nhận một thông điệp
Nếu hai tiến trình P và Q muốn liên lạc với nhau, cần phải thiết lập một mối liên kết giữa hai tiến trình, sau đ� P, Q sử dụng c�c hàm IPC thích hợp để trao đổi th�ng điệp, cuối cùng khi sự liên lạc chấm dứt mối liên kết giữa hai tiến trình sẽ bị hủy. Có nhiều cách thức để thực hiện sự liên kết giữa hai tiến trình và cài đặt c�c theo t�c send/receive tương ứng : liên lạc trực tiếp hay gián tiếp, liên lạc đồng bộ hoặc kh�ng đồng bộ, k�ch thước thông điệp là cố định hay kh�ng � Nếu c�c tiến trình liên lạc theo kiểu liên kết tường minh, các hàm Send và Receive sẽ được cài đặt với tham số:
[destination, message] : gởi một thông điệp đến destinationSend
Receive
[source,message] : nhận một thông điệp từ sourceThảo luận:
Đơn vị truyền thông tin trong cơ chế trao đổi th�ng điệp là một thông điệp, do đ� c�c tiến trình có thể trao đổi dữ liệu ở dạng c� cấu tr�c.II.5. Sockets
Giới thiệu:
Một socket là một thiết bị truyền thông hai chiều tương tự như tập tin, chúng ta có thể đọc hay ghi lên nó, tuy nhiên mỗi socket là một thành phần trong một mối nối nào đ� giữa c�c m�y trên mạng máy tính và các thao tác đọc/ghi ch�nh là sự trao đổi dữ liệu giữa c�c ứng dụng trên nhiều máy khác nhau.Sử dụng socket có thể mô phỏng hai phương thức liên lạc trong thực tế: liên lạc thư tín [socket đ�ng vai trò bưu cục] và liên lạc điện thoại [socket đ�ng vai trò tổng đài] .
Các thuộc tính của socket:
Domaine:
định nghĩa dạng thức địa chỉ và các nghi thức sử dụng. Có nhiều domaines, ví dụ UNIX, INTERNET, XEROX_NS, ...Type: định nghĩa c�c đặc điểm liên lạc:
a] Sự tin cậy
b] Sự bảo toàn thứ tự dữ liệu
c] Lặp lại dữ liệu
d] Chế độ nối kết
e] Bảo toàn giới hạn thông điệp
f] Khả năng gởi th�ng điệp khẩn
Để thực hiện liên lạc bằng socket, cần tiến hành các thao tác::
Ví dụ:Tạo lập hay mở một socket
Gắn kết một socket với một địa chỉ
Liên lạc : có hai kiểu liên lạc tùy thuộc vào chế độ nối kết:
a] Liên lạc trong chế độ kh�ng liên kết
: liên lạc theo hình thức hộp thư:hai tiến trình liên lạc với nhau không kết nối trực tiếp
mỗi thông điệp phải kèm theo địa chỉ người nhận.
Hình thức liên lạc này có đặc điểm được:
người gởi không chắc chắn thông điệp của học được gởi đến người nhận,
một thông điệp c� thể được gởi nhiều lần,
hai thông điệp đượ gởi theo một thứ tự nào đ� c� thể đến tay người nhận theo một thứ tự khác.
Một tiến trình sau khi đã mở một socket có thể sử dụng nó để liên lạc với nhiều tiến trình khác nhau nhờ sử hai primitive send và receive.
b] Liên lạc trong chế độ nối kết:
Một liên kết được thành lập giữa hai tiến trình. Trước khi mối liên kết này được thiết lập, một trong hai tiến trình phải đợi c� một tiến trình khác yêu cầu kết nối.Có thể sử dụng socket để liên lạc theo mô hình client-serveur. Trong mô hình này, server sử dụng lời gọi hệ thống listen và accept để nối kết với client, sau đ� , client và server có thể trao đổi th�ng tin bằng c�ch sử dụng c�c primitive send và receive.
Hủy một socket
Trong nghi thức truyền thông TCP, mỗi mối nối giữa hai máy tính được xác định bởi một port, kh�i niệm port ở đ�y kh�ng phải là một cổng giao tiếp trên thiết bị vật lý mà chỉ là một khái niệm logic trong cách nhìn của người lập trình, mỗi port được tương ứng với một số nguyên dương.
Hình 3.4
Các socket và port trong mối nối TCP.Hình 3.4 minh họa một cách giao tiếp giữa hai máy tính trong nghi thức truyền thông TCP. Máy A tạo ra một socket và kết buộc [bind] socket nầy với một port X [tức là một số nguyên dương có ý nghĩa cục bộ trong máy A], trong khi đ� m�y B tạo một socket kh�c và móc vào [connect] port X trong máy A.
Thảo luận:
Cơ chế socket có thể sử dụng để chuẩn ho� mối liên lạc giữa các tiến trình vốn không liên hệ với nhau, và có thể hoạt động trong những hệ thống kh�c nhau.
III. Nhu cầu đồng bộ h�a [synchronisation]
Trong một hệ thống cho phép các tiến trình liên lạc với nhau, bao giờ hệ điều hành cũng cần cung cấp kèm theo những cơ chế đồng bộ h�a để bảo đảm hoạt động của c�c tiến trình đồng hành không tác động sai lệch đến nhau vì các lý do sau đ�y:
III.1. Yêu cầu độc quyền truy xuất [Mutual exclusion]
Các tài nguyên trong hệ thống được phân thành hai loại: tài nguyên có thể chia sẻ cho phép nhiều tiến trình đồng thời truy xuất, và tài nguyên không thể chia sẻ chỉ chấp nhận một [ hay một số lượng hạn chế ] tiến trình sử dụng tại một thời điểm. T�nh kh�ng thể chia sẻ của tài nguyên thường có nguồn gốc từ một trong hai nguyên nhân sau đ�y:
Đặc t�nh cấu tạo phần cứng của tài nguyên không cho phép chia sẻ.
Nếu nhiều tiến trình sử dụng tài nguyên đồng thời, c� nguy cơ xảy ra các kết quả không dự đo�n được do hoạt động của c�c tiến trình trên tài nguyên ảnh hưởng lẫn nhau.
Để giải quyết vấn đề, cần bảo đảm tiến tr
ình độc quyền truy xuất tài nguyên, nghĩa là hệ thống phải kiểm soát sao cho tại một thời điểm, chỉ c� một tiến trình được quyền truy xuất một tài nguyên không thể chia sẻ.III.2. Yêu cầu phối hợp [Synchronization]
Nhìn chung, mối tương quan về tốc độ thực hiện của hai tiến trình trong hệ thống là không thể biết trước, vì điều này phụ thuộc vào nhiều yếu tố động như tần suất xảy ra các ngắt của từng tiến trình, thời gian tiến trình được cấp phát bộ xử lý� Có thể nói rằng các tiến trình hoạt động kh�ng đồng bộ với nhau. Như ng có những tình huống các tiến trình cần hợp tác trong việc hoàn thành tác vụ, khi đ� cần phải đồng bộ h�a hoạt động của c�c tiến trình , ví dụ một tiến trình chỉ có thể xử lý nếu một tiến trình khác đã kết thúc một công việc nào đ� �
III.3. Bài toán đồng bộ ho�
III.3.1. Vấn đề tranh đoạt điều khiển [race condition]
Giả sử có hai tiến trình P1 và P2 thực hiện công việc của các kế toán, và cùng chia sẻ một vùng nhớ chung lưu trữ biến taikhoan phản ánh thông tin về tài khoản. Mỗi tiến trình muốn rút một khoản tiền tienrut từ tài khoản:
if [taikhoan - tienrut >=0]
taikhoan = taikhoan - tienrut;
else
error[�khong the rut tien!�];
Giả sử trong tài khoản hiện còn 800, P1 muốn rút 500 và P2 muốn rút 400. Nếu xảy ra tình huống như sau:
Sau khi đã kiểm tra điều kiện [taikhoan - tienrut >=0] và nhận kết quả là 300, P1 hết thời gian xử lý mà hệ thống cho phép, hệ điều hành cấp phát CPU cho P2.
P2 kiểm tra cùng điều kiện trên, nhận được kết quả là 400 [do P1 vẫn chưa rút tiền] và rút 400. Giá trị của taikhoan được cập nhật lại là 400.
Khi P1 được tái kích hoạt và tiếp tục xử lý, nó sẽ không kiểm tra lại điều kiện [taikhoan - tienrut >=0]-vì đã kiểm tra trong lượt xử lý trước- mà thực hiện rút tiền. Giá trị của taikhoan sẽ lại được cập nhật thành -100. Tình huống lỗi xảy ra!
Các tình huống tương tự như thế - có thể xảy ra khi có nhiều hơn hai tiến trình đọc và ghi dữ liệu trên cùng một vùng nhớ chung, và kết quả phụ thuộc vào sự điều phối tiến trình của hệ thống- được gọi là các tình huống tranh đoạt điều khiển [race condition] .
III.3.2. Miền găng [critical section]
Để ngăn chặn c�c t
ình huống lỗi có thể nảy sinh khi các tiến trình truy xuất đồng thời một tài nguyên không thể chia sẻ, cần phải áp đặt một sự truy xuất độc quyền trên tài nguyên đ�: khi một tiến trình đang sử dụng tài nguyên, thì những tiến trình khác không được truy xuất đến tài nguyên.Đoạn ch
ương trình trong đ� c� khả năng xảy ra c�c m�u thuẫn truy xuất trên tài nguyên chung được gọi là miền găng [critical section]. Trong ví dụ trên, đoạn mã:if [taikhoan - tienrut >=0]
taikhoan = taikhoan - tienrut;
của mỗi tiến trình tạo thành một miền găng.
Có thể giải quyết vấn đề m�u thuẫn truy xuất nếu c� thể bảo đảm tại một thời điểm chỉ c� duy nhất một tiến trình được xử lý lệnh trong miền găng.
Một phương pháp giải quyết tốt bài toán miền găng cần thõa mãn 4 điều kiện sau:
Không có hai tiến trình cùng ở trong miền găng cùng lúc.
Không có giả thiết nào đặt ra cho sự liên hệ về tốc độ của c�c tiến trình, cũng như về số lượng bộ xử lý trong hệ thống.
Một tiến trình tạm dừng bên ngoài miền găng kh�ng được ngăn cản c�c tiến trình khác vào miền găng.
Không có tiến trình nào phải chờ vô hạn để được vào miền găng.
IV. Tóm tắt
Một số tiến trình trong hệ thống có nhu cầu trao đổi th�ng tin để phối hợp hoạt động, do mỗi tiến trình có một không gian địa chỉ độc lập nên viêc liên lạc chỉ có thể thực hiện thông qua các cơ chế do hệ điều hành cung cấp.
Một số cơ chế trao đổi th�ng tin giữa c�c tiến trình:
Tín hiệu
: thông báo sự xảy ra của một sự kiệnPipe
Vùng nhớ chia sẻ
: cho phép nhiều tiến trình truy cập đến cùng một vùng nhớTrao đổi th�ng điệp
: truyền dữ liệu có cấu trúc, có thể vận dụng trong cáchệ phân tán
Socket
: chuẩn hoán việc liên lạc giữa các hệ thống khác biệtKhi các tiến trình trao đổi th�ng tin, chia sẻ tài nguyên chung, cần phải đồng bộ ho� hoạt động của ch�ng chủ yếu do yêu cầu độc quyền truy xuất hoặc phối hợp hoạt động.
Miền găng là đoạn lệnh trong chương trình có khả năng ph�t sinh m�u thuẫn truy xuất. Để kh�ng xảy ra m�u thuẫn truy xuất, cần đảm bảo tại một thời điểm chỉ c� một tiến trình được vào miền găng.
Củng cố b�i học
Các câu hỏi cần trả lời được sau bài học này :
1. Các cơ chế trao đổi th�ng tin: tình huống sử dụng, ưu, khuyết?
2. Các yêu cầu đồng bộ ho�?
B�i tập
Phân tích các bài toán sau đ�y và xác định những yêu cầu đồng bộ ho�, miền găng:
B�i 1.Bài toán Tạo phân tử H2O
òng thí nghiệm sử dụng nhiều tiến trình đồng hành sau để tạo c�c ph�n tử H2O:Đồng bộ hoạt động của một ph
// Mỗi tiến trình MakeH tạo 1 nguyên tử HMakeH[]
{
Make-Hydro[];
}
MakeO[] // Mỗi tiến trình MakeO tạo 1 nguyên tử O
{
Make-Oxy[];
}
MakeWater[]
/* Tiến trình MakeWater hoạt động đồng hànhvới các tiến trình MakeH, MakeO, chờ có đủ 2 H và 1 O để tạo H2O */
{
while [T]
Make-Water[]; //Tạo 1 phân tử H2O
}
B�i 2.Bài toán Cây cầu cũ
Để tr�nh sụp đổ, ng
ười ta chỉ có cho phép tối đa 3 xe lưu thông đồng thời qua một c�y cầu rất cũ. Hãy xây dựng thủ tục ArriveBridge[int direction] và ExitBridge[] kiểm soát giao thông trên cầu sao cho :điểm, chỉ cho ph�p tối đa 3 xe lưu thông trên cầu.Tại mỗi thời
Tại mỗi thời
điểm, chỉ cho ph�p tối đa 3 xe lưuthông cùng hướngtrên cầu.
Mỗi chiếc xe khi
đến đầu cầu sẽ gọi ArriveBridge[direction] để kiểm tra điều kiện lên cầu, và khi đã qua cầu được sẽ gọi ExitBridge[] để b�o hiệu kết th�c.Giả sử hoạt
động của mỗi chiếc xe được mô tả bằng một tiến trình Car[] sau đ�y:Car[int direction]
/* direction xác định hướng di chuyển của mỗi chiếc xe.*/{
RuntoBridge[]; // Đi về ph�a cầu
ArriveBridge[direction];
PassBridge[]; // Qua cầu
Exit Bridge[];
RunfromBridge[]; // Đã qua cầu
}
B�i 3. Bài toán Qua sông
Để v
ượt qua sông, các nhân viên Microsof và các Linux hacker cùng sử dụng một bến sông và phải chia sẻ một số thuyền đặc biệt. Mỗi chiếc thuyền này chỉ cho phép chở 1 lần 4 người, và phải có đủ 4 người mới khởi hành được. Để bảo đảm an toàn cho cả 2 phía, cần tuân thủ các luật sau :a. Không chấp nhận 3 nhân viên Microsoft và 1 Linux hacker trên cùng một chiếc thuyền.
b. Ngược lại, không chấp nhận 3 Linux hacker và 1 nhân viên Microsoft trên cùng một chiếc thuyền.
c. Tất cả các trường hợp kết hợp khác
đều hợp ph�p.d. Thuyền chỉ khởihành khi
đã có đủ 4 hành khách.Cần xây dựng 2 thủ tục HackerArrives[] và EmployeeArrives[]
được gọi tương ứng bởi 1 hacker hoặc 1 nhân viên khi họ đến bờ s�ng để kiểm tra điều kiện c� cho ph�p họ xuống thuyền kh�ng ? C�c thủ tục này sẽ sắp xếp những người thích hợp có thể lên thuyền. Những người đã được lên thuyền khi thuyền chưa đầy sẽ phải chờ đến khi người thứ 4 xuống thuyền mới có thể khởi hành qua sông. [Không quan tâm đến số lương thuyền hay việc thuyền qua sông rồi trở lại�Xem như luôn có thuyền để sắp xếp theo c�c yêu cầu hợp lệ]Giả sử hoạt
động của mỗi hacker được mô tả bằng một tiến trình Hacker[] sau đ�y:Hacker[]
{
RuntoRiver[];
// Đi đến bờ s�ngHackerArrives []; // Kiểm tra điều kiện xuống thuyền
CrossRiver[]; // Khởi hành qua sông
}
và hoạt
động của mỗi nh�n viên được mô tả bằng một tiến trình Employee[] sau đ�y:Employee[]
{
RuntoRiver[];
// Đi đến bờ s�ngEmployeeArrives []; // Kiểm tra điều kiện xuống thuyền
CrossRiver[]; // Khởi hành qua sông
}
B�i 4. Bài toán
Điều phối hành khách xe busHãy tưởng tượng bạn chịu trách nhiệm kiểm soát hành khách lên xe bus tại một trạm dừng.
Mỗi xe bus có
đủ chỗ cho 10 hành khách. Trong đ� 4 chỗ chỉ dành cho khách ngồi xe lăn, 6 chỗ còn lại chỉ dành cho khách bình thường.Công việc của bạn là cho khách lên xe theo
đ�ng qui định chỗ, khi xe đầy kh�ch sẽ khởi hành. Có thể có nhiều xe và nhiều hành khách vào bến cùng lúc, nguyên tắc điều phối sẽ xếp kh�ch vào đầy một xe, cho xe này khởi hành rồi mới điều phối cho xe kh�c.Giả sử hoạt
động điều phối kh�ch của bạn cho 1 chiếc xe bus được mô tả qua tiến trình GetPassengers[]; hoạt động của mỗi hành khách tùy loại được mô tả lần lượt bằng tiến trình WheelPassenger[] và NonWheelPassenger[] sau đ�y , hãy sửa chữa các đoạn code, sử dụng cơ chế semaphore để thực hiện c�c nguyên tắc đồng bộ ho� cần thiết.GetPassenger[]
{
ArriveTerminal[];
// tiếp nhận một xe vào bếnOpenDoor[]; // mở cửa xe, thủ tục này xem như đã có
for [int i=0; i