Tại sao phải đồng bộ quá trình
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. 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
II. Các Cơ Chế Thông Tin Liên lạc II.1. Tín hiệu (Signal)
II.2. Pipe
II.3. Vùng nhớ chia sẻ
II.4. Trao đổi th�ng điệp (Message)
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 destination 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
Hình 3.4 Các socket và port trong mối nối TCP.
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 : truyền dữ liệu không cấu trúcVù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.
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: // Mỗi tiến trình MakeH tạo 1 nguyên tử H { Make-Hydro(); } MakeO() // Mỗi tiến trình MakeO tạo 1 nguyên tử O 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 đ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.*/{
} 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.
{ 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<4; i++) // tiếp nhận các hành khách ngồi xe lăn { ArrangeSeat(); // đưa 1 khách vào chỗ } for (int i=0; i<6; i++) // tiếp nhận các hành khách bình thường{ ArrangeSeat(); // đưa 1 khách vào chỗ } CloseDoor(); // đ�ng cửa xe, thủ tục này xem như đã cóDepartTerminal(); // cho một xe rời bến} WheelPassenger() { ArriveTerminal(); // đến bếnGetOnBus(); // lên xe } NonWheelPassenger() { ArriveTerminal(); // đến bếnGetOnBus(); // lên xe } B�i 5. Bài toán sản xuất thiết bị xe hơi động song song : - Bộ phận sản xuất 1 khung xe : MakeChassis() { // tạo khung xeProduce_chassis(); } - Bộ phận sản xuất 1 bánh xe : MakeTires() { // tạo bánh xe và gắn vào khung xeProduce_tire(); Put_tire_to_Chassis(); } đồng bộ hoạt động trong việc sản xuất xe hơi theo nguyên tắc sau : o Sản xuất một khung xe,o cần có đủ 4 b�nh xe cho 1 khung xe được sản xuất ra, sau đ� mới tiếp tục sản xuất khung xe kh�c� |