text:
ĐỒNG BỘ HOÁ QUÁ TRÌNH
Chia sẻ: Nguyen Hoang Hai | Ngày: | Loại File: PDF | Số trang:24
lượt xem 74
download
ĐỒNG BỘ HOÁ QUÁ TRÌNH
Sau khi học xong chương này, người học nắm được những kiến thức sau: • Hiểu vấn đề vùng tương trục • Hiểu cơ chế hoạt động hiệu báo Semaphores để đồng bộ hóa quá trình • Hiểu cơ chế hoạt động của Monitors để đồng bộ hóa quá trình • Vận dụng các giải pháp để giải quyết các bài toán đồng bộ hóa cơ bản II Giới thiệu Một quá trình hợp tác là một quá trình có thể gây ảnh hưởng hay bị ảnh hưởng tới quá trình khác đang thực thi trong hệ thống. Các quá trình hợp...
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: ĐỒNG BỘ HOÁ QUÁ TRÌNH
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 ĐỒNG BỘ HOÁ QUÁ TRÌNH I Mục tiêu Sau khi học xong chương này, người học nắm được những kiến thức sau: • Hiểu vấn đề vùng tương trục • Hiểu cơ chế hoạt động hiệu báo Semaphores để đồng bộ hóa quá trình • Hiểu cơ chế hoạt động của Monitors để đồng bộ hóa quá trình • Vận dụng các giải pháp để giải quyết các bài toán đồng bộ hóa cơ bản II Giới thiệu Một quá trình hợp tác là một quá trình có thể gây ảnh hưởng hay bị ảnh hưởng tới quá trình khác đang thực thi trong hệ thống. Các quá trình hợp tác có thể chia sẻ trực tiếp không gian địa chỉ luận lý (mã và dữ liệu), hay được phép chia sẻ dữ liệu thông qua các tập tin. Trường hợp đầu đạt được thông qua việc sử dụng các quá trình có trọng lượng nhẹ hay luồng. Truy xuất đồng hành dữ liệu được chia sẻ có thể dẫn tới việc không đồng nhất dữ liệu. Trong chương này chúng ta sẽ thảo luận các cơ chế đảm bảo việc thực thi có thứ tự của các quá trình hợp tác chia sẻ không gian địa chỉ để tính đúng đắn của dữ liệu luôn được duy trì. III Tổng quan Trong chương trước, chúng ta phát triển một mô hình hệ thống chứa số lượng quá trình hợp tác tuần tự, tất cả chúng chạy bất đồng bộ và có thể chia sẻ dữ liệu. Chúng ta hiển thị mô hình này với cơ chế vùng đệm có kích thước giới hạn, được đại diện cho hệ điều hành. Chúng ta xét giải pháp bộ nhớ được chia sẻ cho bài toán vùng đệm có kích thước giới hạn. Giải pháp này cho phép có nhiều nhất BUFFER_SIZE –1 sản phẩm trong vùng đệm tại cùng thời điểm. Giả sử rằng chúng ta muốn hiệu chỉnh giải thuật để giải quyết sự thiếu sót này. Một khả năng là thêm một biến đếm số nguyên counter, được khởi tạo bằng 0. counter được tăng mỗi khi chúng ta thêm một sản phẩm tới vùng đệm và bị giảm mỗi khi chúng ta lấy một sản phẩm ra khỏi vùng đệm. Mã cho quá trình người sản xuất có thể được hiệu chỉnh như sau: while (1){/*tạo sản phẩm trong nextProduced*/ while (counter==BUFFER_SIZE); /*không làm gì cả*/ buffer[in] = nextProduced; in = ( in + 1 ) % BUFFER_SIZE; counter++; } Mã cho quá trình người tiêu dùng có thể được hiệu chỉnh như sau: while (1){ while (counter == 0) ; /*không làm gì cả*/ nextConsumed = buffer[out]; Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 82
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 out = ( out + 1 ) % BUFFER_SIZE; counter--; /*tiêu thụ sản phẩm trong nextConsumed*/ } Mặc dù cả hai thủ tục người sản xuất và người tiêu dùng thực thi đúng khi tách biệt nhau nhưng chúng không thực hiện đúng chức năng khi thực thi đồng hành. Như minh hoạ dưới đây, giả sử rằng giá trị của biến counter hiện tại là 5 và thủ tục người sản xuất và người tiêu dùng thực thi đồng hành câu lệnh “counter++” và “counter--”. Theo sau việc thực thi hai câu lệnh này, giá trị của biến counter có thể là 4, 5 hay 6! Kết quả chỉ đúng khi biến counter==5, được tạo ra đúng nếu quá trình người sản xuất và người tiêu dùng thực thi riêng biệt. Chúng ta có thể minh hoạ giá trị của counter có thể không đúng như sau. Chú ý, câu lệnh “counter++” có thể được cài đặt bằng ngôn ngữ máy (trên một máy điển hình) như sau: register1 = counter register1 = register1 + 1 counter = register1 Ở đây register1 là một thanh ghi CPU cục bộ. Tương tự, câu lệnh “counter--” được cài đặt như sau: register2 = counter register2 = register2 - 1 counter = register2 Ở đây register2 là thanh ghi CPU cục bộ. Dù là register1 và register2 có thể dùng cùng thanh ghi vật lý, nhưng nội dung của thanh ghi sẽ được lưu lại và lấy lại bởi bộ quản lý ngắt. Thực thi đồng hành của “counter++” và “counter--” là tương tự như thực thi tuần tự ở đây các câu lệnh cấp thấp hơn được hiện diện trước bị phủ lắp trong thứ tự bất kỳ (nhưng thứ tự bên trong mỗi câu lệnh cấp cao được lưu giữ). Một sự phủ lắp là: T0: producer thực thi register1 = counter {register1 = 5} T1: producer thực thi register1 = register1 + 1 {register1 = 6} T2: consumer thực thi register2 = counter {register2 = 5} T3: consumer thực thi register2 = register2 – 1 {register2 = 4} T4: producer thực thi counter = register1 {counter = 6} T5: consumer thực thi counter = register2 {counter = 4} Chú ý rằng, chúng ta xem xét tình trạng không đúng “counter==4” theo đó có 4 vùng đệm đầy, nhưng thực tế khi đó có 5 vùng đệm đầy. Nếu chúng đổi ngược lại thứ tự của câu lệnh T4 và T5, chúng ta sẽ có trạng thái không đúng “counter ==6”. Chúng ta đi đến trạng thái không đúng này vì chúng ta cho phép cả hai quá trình thao tác đồng thời trên biến counter. Trường hợp tương tự, ở đây nhiều quá trình truy xuất và thao tác cùng dữ liệu đồng hành và kết quả của việc thực thi phụ thuộc vào thứ tự xác định trong đó việc truy xuất xảy ra, được gọi là điều kiện cạnh tranh (race condition). Để ngăn chặn điều kiện cạnh tranh ở trên, chúng ta cần đảm bảo rằng chỉ một quá trình tại một thời điểm có thể được thao tác biến counter. Để thực hiện việc đảm bảo như thế, chúng ta yêu cầu một vài hình thức đồng bộ hoá quá trình. Những Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 83
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 trường hợp như thế xảy ra thường xuyên trong các hệ điều hành khi các phần khác nhau của hệ thống thao tác các tài nguyên và chúng ta muốn các thay đổi không gây trở ngại một sự thay đổi khác. Phần chính của chương này là tập trung vào vấn đề đồng bộ hoá và cộng tác quá trình. IV Vấn đề vùng tương trục Xét một hệ thống gồm n quá trình (P0, P1, … ,Pn-1 ). Mỗi quá trình có một phân đoạn mã, được gọi là vùng tương trục (critical section), trong đó quá trình này có thể thay đổi những biến dùng chung, cập nhật một bảng, viết đến tập tin,.. Đặc điểm quan trọng của hệ thống là ở chỗ, khi một quá trình đang thực thi trong vùng tương trục, không có quá trình nào khác được phép thực thi trong vùng tương trục của nó. Do đó, việc thực thi của các vùng tương trục bởi các quá trình là sự loại trừ hỗ tương. Vấn đề vùng tương trục là thiết kế một giao thức mà các quá trình có thể dùng để cộng tác. Mỗi quá trình phải yêu cầu quyền để đi vào vùng tương trục của nó. Vùng mã thực hiện yêu cầu này là phần đi vào (entry section). Vùng tương trục có thể được theo sau bởi một phần kết thúc (exit section). Mã còn lại là phần còn lại (remainder section). do { entry section critical section exit section remainder section } while (1); Hình 0-1 Cấu trúc chung của một quá trình điển hình Pi Một giải pháp đối với vấn đề vùng tương trục phải thoả mãn ba yêu cầu sau: • Loại trừ hỗ tương (Mutual Exclusion): Nếu quá trình Pi đang thực thi trong vùng tương trục của nó thì không quá trình nào khác đang được thực thi trong vùng tương trục đó. • Tiến trình (Progress): nếu không có quá trình nào đang thực thi trong vùng tương trục và có vài quá trình muốn vào vùng tương trục thì chỉ những quá trình không đang thực thi phần còn lại mới có thể tham gia vào việc quyết định quá trình nào sẽ đi vào vùng tương trục tiếp theo và chọn lựa này không thể trì hoãn vô hạn định. • Chờ đợi có giới hạn (bounded wait): giới hạn số lần các quá trình khác được phép đi vào miền tương trục sau khi một quá trình thực hiện yêu cầu để đi vào miền tương trục của nó và trước khi yêu cầu đó được gán. Chúng ta giả sử rằng mỗi quá trình đang thực thi với tốc độ khác 0. Tuy nhiên, chúng ta có thể thực hiện rằng không có giả thuyết nào được quan tâm về tốc tương đối của n quá trình. Trong phần tiếp theo chúng ta nghiên cứu để nắm được các giải pháp thoả ba yêu cầu này. Những giải pháp này không quan tâm đến các chỉ thị phần cứng hay số lượng bộ xử lý mà phần cứng hỗ trợ. Tuy nhiên chúng ta giả sử rằng những chỉ thị ngôn ngữ máy cơ bản (chỉ thị cơ bản như load, store và test) được thực hiện mang Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 84
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 tính nguyên tử (atomically). Nghĩa là, nếu hai chỉ thị như thế được thực thi đồng hành thì kết quả tương tự như thực thi tuần tự trong thứ tự không xác định. Do đó, nếu chỉ thị load và store được thực thi đồng hành thì load sẽ nhận giá trị cũ hay mới như không có sự kết hợp vừa cũ vừa mới. Khi trình bày một giải thuật, chúng ta định nghĩa chỉ những biến được dùng cho mục đích đồng bộ và mô tả chỉ một quá trình điển hình Pi mà cấu trúc của nó được hiển thị trong hình V.1. Phần đi vào và kết thúc được bao trong hình chữ nhật để nhấn mạnh các đoạn mã quan trọng. do { while (turn!=i) ; critical section turn = j; remainder section } while (1); Hình 0-2-Cấu trúc của quá trình Pi trong giải thuật 1 V Giải pháp Có nhiều giải pháp để thực hiện việc loại trừ hỗ tương. Các giải pháp này, tuỳ thuộc vào cách tiếp cận trong xử lý của quá trình bị khoá, được phân biệt thành hai lớp: chờ đợi bận (busy waiting) và nghẽn và đánh thức (sleep and wakeup) V.1 Giải pháp “chờ đợi bận” V.1.1 Giải pháp hai quá trình (two-Process Solution) Trong phần này, chúng ta giới hạn việc quan tâm tới những giải thuật có thể áp dụng chỉ hai quá trình cùng một lúc. Những quá trình này được đánh số P0 và P1. Để thuận lợi, khi trình bày Pi, chúng ta dùng Pj để chỉ quá trình còn lại, nghĩa là j = 1 – i .V.1.1.1 Giải thuật 1 Tiếp cận đầu tiên của chúng ta là để hai quá trình chia sẻ một biến số nguyên chung turn được khởi tạo bằng 0 (hay 1). Nếu turn == 0 thì quá trình Pi được phép thực thi trong vùng tương trục của nó. Cấu trúc của quá trình Pi được hiển thị trong Hình V.-2. Giải pháp này đảm bảo rằng chỉ một quá trình tại một thời điểm có thể ở trong vùng tương trục của nó. Tuy nhiên, nó không thoả mãn yêu cầu tiến trình vì nó yêu cầu sự thay đổi nghiêm khắc của các quá trình trong việc thực thi của vùng tương trục. Thí dụ, nếu turn == 0 và P1 sẳn sàng đi vào vùng tương trục của nó thì P1 không thể đi vào vùng tương trục thậm chí khi P0 đang ở trong phần còn lại của nó. .V.1.1.2 Giải thuật 2 Vấn đề với giải thuật 1 là nó không giữ lại đủ thông tin về trạng thái của mỗi quá trình; nó nhớ chỉ quá trình nào được phép đi vào miền tương trục. Để giải quyết vấn đề này, chúng ta có thể thay thế biến turn với mảng sau: Boolean flag[2]; Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 85
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Các phần tử của mảng được khởi tạo tới flase. Nếu flag[i] là true, giá trị này hiển thị rằng Pi sẳn sàng đi vào vùng tương trục. Cấu trúc của quá trình Pi được hiển thị trong hình V.-3 dưới đây: do{ flag[i] = true; while (flag[j]); critical section flag[i] = false; remainder section } while(1); Hình 0-3 –Cấu trúc của quá trình Pi trong giải thuật 2 Trong giải thuật này, quá trình Pi trước tiên thiết lập flag[i] tới true, hiển thị rằng nó sẳn sàng đi vào miền tương trục. Sau đó, Pi kiểm tra rằng quá trình quá trình Pj cũng không sẳn sàng đi vào miền tương trục của nó. Nếu Pj sẳn sàng thì Pi sẽ chờ cho tới khi Pj hiển thị rằng nó không còn cần ở trong vùng tương trục nữa (nghĩa là cho tới khi flag[j] là false). Tại thời điểm này, Pi sẽ đi vào miền tương trục. Thoát ra khỏi miền tương trục, Pi sẽ đặt flag[i] là false, cho phép quá trình khác (nếu nó đang chờ) đi vào miền tương trục của nó. Trong giải pháp này, yêu cầu loại trừ hỗ tương sẽ được thoả mãn. Tuy nhiên, yêu cầu tiến trình không được thoả mãn. Để minh hoạ vấn đề này, chúng ta xem xét thứ tự thực thi sau: T0: P0 thiết lập flag[0] = true; T1: P1 thiết lập flag[1] = true; Bây giờ P0 và P1 được lập mãi mãi trong câu lệnh while tương ứng của chúng. Giải thuật này phụ thuộc chủ yếu vào thời gian chính xác của hai quá trình. Thứ tự này được phát sinh trong môi trường nơi có nhiều bộ xử lý thực thi đồng hành hay nơi một ngắt (chẳng hạn như một ngắt định thời) xảy ra lập tức sau khi bước T0 được thực thi và CPU được chuyển từ một quá trình này tới một quá trình khác. Chú ý rằng chuyển đổi thứ tự của các chỉ thị lệnh để thiết lập flag[i] và kiểm tra giá trị của flag[j] sẽ không giải quyết vấn đề của chúng ta. Hơn nữa chúng ta sẽ có một trường hợp đó là hai quá trình ở trong vùng tương trục cùng một lúc, vi phạm yêu cầu loại trừ hỗ tương. .V.1.1.3 Giải thuật 3 Giải thuật 3 còn gọi là giải pháp Peterson. Bằng cách kết hợp hai ý tưởng quan trọng trong giải thuật 1 và 2, chúng ta đạt được một giải pháp đúng tới với vấn đề vùng tương trục, ở đó hai yêu cầu được thoả. Các quá trình chia sẻ hai biến: Boolean flag[2] Int turn; Khởi tạo flag[0] = flag[1] = false và giá trị của turn là không xác định (hoặc là 0 hay 1). Cấu trúc của quá trình Pi được hiển thị trong hình sau: Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 86
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 do{ flag[i] = true; turn = j; while (flag[j] &&turn ==j); critical section flag[i] = false; remainder section } while (1); Hình 0-4 Cấu trúc của quá trình Pi trong giải thuật 3 Để đi vào miền tương trục, quá trình Pi trước tiên đặt flag[i] là true sau đó đặt turn tới giá trị j, do đó xác định rằng nếu quá trình khác muốn đi vào miền tương trục nó. Nếu cả hai quá trình đi vào miền tương trục cùng một lúc turn sẽ đặt cả hai i và j tại xấp xỉ cùng một thời điểm. Chỉ một trong hai phép gán này là kết quả cuối cùng. Giá trị cuối cùng của turn quyết định quá trình nào trong hai quá trình được cho phép đi vào miền tương trục trước. Bây giờ chúng ta chứng minh rằng giải pháp này là đúng. Chúng ta cần hiển thị rằng: 1) Loại trừ hỗ tương được bảo toàn 2) Yêu cầu tiến trình được thoả 3) Yêu cầu chờ đợi có giới hạn cũng được thoả Chứng minh thuộc tính 1, chúng ta chú ý rằng mỗi Pi đi vào miền tương trục của nó chỉ nếu flag[j] ==false hay turn ==i. Cũng chú ý rằng, nếu cả hai quá trình có thể đang thực thi trong vùng tương trục của chúng tại cùng thời điểm thì flag[0] == flag[1] ==true. Hai nhận xét này ngụ ý rằng P0 và P1 không thể thực thi thành công trong vòng lặp while của chúng tại cùng một thời điểm vì giá trị turn có thể là 0 hay 1. Do đó, một trong các quá trình-Pj phải được thực thi thành công câu lệnh while, ngược lại Pi phải thực thi ít nhất câu lệnh bổ sung (“turn==j”). Tuy nhiên, vì tại thời điểm đó, flag[j] ==true và turn ==j, và điều kiện này sẽ không đổi với điều kiện là Pj ở trong vùng miền tương trục của nó, kết quả sau việc loại trừ hỗ tương được bảo vệ do { flag[i] = true; turn = j; while (flag[j] && turn ==j); critical section flag[i] = false; Remainder section }while (1); Hình 0-5-Cấu trúc của quá trình Pi trong giải thuật 3 Để chứng minh thuộc tính 2 và 3, chúng ta chú ý rằng một quá trình Pi có thể được ngăn chặn từ việc đi vào miền tương truc chỉ nếu nó bị kẹt trong vòng lặp while với điều kiện flag[j] == true và turn == j. Nếu Pj không sẳn sàng đi vào miền tương trục thì flag[j] == false và Pi có thể đi vào miền tương trục của nó. Nếu Pj đặt flag[j] là true và nó cũng đang thực thi trong câu lệnh while của nó thì turn == i hay turn == j. Nếu turn == i thì Pi sẽ đi vào miền tương trục. Nếu turn ==j thì Pj sẽ đi vào miền tương trục. Tuy nhiên, một khi Pj ở trong vùng tương trục của nó thì nó sẽ đặt lại Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 87
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 flag[j] tới false, cho phép Pi đi vào miền tương trục của nó. Nếu Pj đặt lại flag[j] tới true, nó cũng phải đặt turn tới i. Do đó, vì Pi không thay đổi giá trị của biến turn trong khi thực thi câu lệnh while, nên Pi sẽ đi vào miền tương trục (tiến trình) sau khi nhiều nhất chỉ Pj đi vào (chờ có giới hạn). V.1.2 Giải pháp nhiều quá trình Giải thuật 3 giải quyết vấn đề miền tương trục cho hai quá trình. Bây giờ chúng ta phát triển một giải thuật để giải quyết vấn đề miền tương trục cho n quá trình. Giải thuật này được gọi là giải thuật Bakery và nó dựa trên cơ sở của giải thuật định thời thường được dùng trong cửa hiệu bánh mì, cửa hàng kem,..nơi mà thứ tự rất hỗn độn. Giải thuật này được phát triển cho môi trường phân tán, nhưng tại thời điểm này chúng ta tập trung chỉ những khía cạnh của giải thuật liên quan tới môi trường tập trung. Đi vào một cửa hàng, mỗi khách hàng nhận một số. Khách hàng với số thấp nhất được phục vụ tiếp theo. Tuy nhiên, giải thuật Bakery không thể đảm bảo hai quá trình (khách hàng) không nhận cùng số. Trong trường hợp ràng buộc, một quá trình với tên thấp được phục vụ trước. Nghĩa là, nếu Pi và Pj nhận cùng một số và nếu (i < j) thì Pi được phục vụ trước. Vì tên quá trình là duy nhất và được xếp thứ tự nên giải thuật là hoàn toàn mang tính “may rủi” (deterministic). Cấu trúc dữ liệu chung là boolean choosing[n]; int number[n]; Đầu tiên, các cấu trúc dữ liệu này được khởi tạo tới false và 0 tương ứng. Để tiện dụng, chúng ta định nghĩa các ký hiệu sau: • (a, b) < (c, d) nếu a< c hay nếu a==c và b< d • max(a0,…,an-1) là số k ≥ ai với i = 0,…,n-1 Cấu trúc của quá trình Pi được dùng trong giải thuật Bakery, được hiển thị trong hình dưới đây. do { choosing[i] = true; number[i] = max(number[0], number[i],…,number[n-1]) + 1; choosing[i] = false; for (j=0; j < n; j++){ while (choosing[j]); while ((number[j]!=0)&&((number[ j ], j )
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Do đó, nó tiếp tục vòng lặp trong câu lệnh while cho đến khi Pi rời khỏi vùng tương trục Pi. Giải thuật trên đảm bảo rằng yêu cầu về tiến trình, chờ đợi có giới hạn và đảm bảo sự công bằng, vì các quá trình đi vào miền tương trục dựa trên cơ sở tới trước được phục vụ trước. V.1.3 Phần cứng đồng bộ hoá Như các khía cạnh khác của phần mềm, các đặc điểm phần cứng có thể làm các tác vụ lập trình dễ hơn và cải tiến tính hiệu quả của hệ thống. Trong phần này, chúng ta trình bày một số chỉ thị phần cứng đơn giản sẳn dùng trên nhiều hệ thống và trình bày cách chúng được dùng hiệu quả trong việc giải quyết vấn đề miền tương trục. boolean TestAndSet( boolean &target){ boolean rv = target; target = true; return rv; } Hình 0-7 Định nghĩa của chỉ thị TestAndSet Vấn đề miền tương trục có thể được giải quyết đơn giản trong môi trường chỉ có một bộ xử lý nếu chúng ta cấm các ngắt xảy ra khi một biến chia sẻ đang được thay đổi. Trong cách này, chúng ta đảm bảo rằng chuỗi chỉ thị hiện hành có thể được cho phép thực thi trong thứ tự không trưng dụng. Không có chỉ thị nào khác có thể chạy vì thế không có bất cứ sự thay đổi nào có thể được thực hiện trên các biến được chia sẻ. Tuy nhiên, giải pháp này là không khả thi trong một môi trường có nhiều bộ xử lý. Vô hiệu hoá các ngắt trên đa bộ xử lý có thể mất nhiều thời gian khi một thông điệp muốn truyền qua tất cả bộ xử lý. Việc truyền thông điệp này bị trì hoãn khi đi vào miền tương trục và tính hiệu quả của hệ thống bị giảm. Do đó nhiều máy cung cấp các chỉ thị phần cứng cho phép chúng ta kiểm tra hay thay đổi nội dung của một từ (word) hay để thay đổi nội dung của hai từ tuân theo tính nguyên tử (atomically)-như là một đơn vị không thể ngắt. Chúng ta có thể sử dụng các chỉ thị đặc biệt này để giải quyết vấn đề miền tương trục trong một cách tương đối đơn giản. Chỉ thị TestAndSet có thể được định nghĩa như trong hình V.-7. Đặc điểm quan trọng của chỉ thị này là việc thực thi có tính nguyên tử. Do đó, nếu hai chỉ thị TestAndSet được thực thi cùng một lúc (mỗi chỉ thị trên một CPU khác nhau), thì chúng sẽ được thực thi tuần tự trong thứ tự bất kỳ. do{ while (TestAndSet(lock)); Critical section lock:= false remainder section } while (1); Hình 0-8: Cài đặt loại trừ hỗ tương với TestAndSet Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 89
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Nếu một máy hỗ trợ chỉ thị TestAndSet thì chúng ta có thể loại trừ hỗ tương bằng cách khai báo một biến khoá kiểu luận lý và được khởi tạo tới false. Cấu trúc của quá trình Pi được hiển thị trong hình V.-9 ở trên. Chỉ thị Swap được định như hình V.-9 dưới đây, thao tác trên nội dung của hai từ; như chỉ thị TestAndSet, nó được thực thi theo tính nguyên tử. void Swap(boolean &a, boolean &b){ boolean temp = a; a = b; b = temp; } Hình 0-9: Định nghĩa chỉ thị Swap Nếu một máy hỗ trợ chỉ thị Swap, thì việc loại trừ hỗ tương có thể được cung cấp như sau. Một biến luận lý toàn cục lock được khai báo và được khởi tạo tới false. Ngoài ra, mỗi quá trình cũng có một biến luận lý cục bộ key. Cấu trúc của quá trình Pi được hiển thị trong hình V.-10 dưới đây. do{ key = true; while (key == true) Swap(lock, key); Critical section lock = false; Remainder section } while(1); Hình 0-10: Cài đặt loại trừ hỗ tương với chỉ thị Swap Các giải thuật này không thoả mãn yêu cầu chờ đợi có giới hạn. Chúng ta hiển thị giải thuật sử dụng chỉ thị TestAndSet trong hình V.-11 dưới đây. Giải thuật này thoả mãn tất cả các yêu cầu miền tương trục. do{ Waiting[i] = true; key = true; while (waiting[i] && key) key = TestAndSet(lock); waiting[i] = false; Critical section j = (i + 1) % n; while ((j != i ) && !waiting[j]) j = (j + 1 ) % n; if (j == i) lock = false; else waiting[j] = false; Remainder section } while(1); Hình 0-11 Loại trừ hỗ tương chờ đợi có giới hạn với TestAndSet Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 90
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Cấu trúc dữ liệu thông thường là: boolean waiting[n]; boolean lock; Cấu trúc dữ liệu này được khởi tạo tới false. Để chứng minh rằng loại trừ hỗ tương được thoả, chúng ta chú ý rằng quá trình Pi có thể đưa vào miền tương trục chỉ nếu hoặc waiting[i] ==false hay key == false. Giá trị của key có thể trở thành false chỉ nếu TestAndSet được thực thi. Đối với quá trình đầu tiên, để thực thi TestAndSet sẽ tìm key == false; tất cả quá trình khác phải chờ. Biến waiting[i] có thể trở thành false chỉ nếu quá trình khác rời khởi miền tương trục của nó; chỉ một waiting[i] được đặt false, duy trì yêu cầu loại trừ hỗ tương. Để chứng minh yêu cầu tiến trình được thoả, chúng ta chú ý rằng các đối số được hiện diện cho việc loại trừ hỗ tương cũng áp dụng được ở đây, vì thế một quá trình thoát khỏi miền tương trục hoặc đặt lock bằng false hay đặt waiting[j] bằng false. Cả hai trường hợp đều cho phép một quá trình đang chờ để đi vào miền tương trục được xử lý. Để chứng minh yêu cầu chờ đợi được giới hạn được thoả, chúng ta chú ý rằng khi một quá trình rời miền tương trục của nó, nó duyệt qua mảng waiting trong thứ tự tuần hoàn (i + 1, i + 2, …, n – 1, 0, …, i - 1). Nó định rõ quá trình đầu tiên trong thứ tự này mà thứ tự đó ở trong phần đi vào (waiting[j] == true) khi quá trình tiếp theo đi vào miền tương trục. Bất cứ quá trình nào đang chờ để đi vào miền tương trục sẽ thực hiện n – 1 lần. Tuy nhiên, đối với người thiết kế phần cứng, cài đặt các chỉ thị nguyên tử TestAndSet trên bộ đa xử lý không là tác vụ thử nghiệm. Những giải pháp trên đều phải thực hiện một vòng lặp để kiểm tra liệu nó có được phép vào miền tương trục hay không. Nếu điều kiện chưa thoả, quá trình phải chờ tiếp tục trong vòng lặp kiểm tra này. Các giải pháp buộc quá trình phải liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào miền tương trục như thế được gọi là các giải pháp chờ đợi bận “busy waiting”. Lưu ý, việc kiểm tra như thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy quá trình đang chờ vẫn chiếm dụng CPU. Xu hướng giải quyết vấn đề đồng bộ hoá là nên tránh các giải pháp chờ đợi bận. V.2 Các giải pháp “SLEEP and WAKEUP” Để loại bỏ các bất tiện của của giải pháp chờ đợi bận, chúng ta có thể tiếp cận theo hướng cho một quá trình chưa đủ điều kiện vào miền tương trục chuyển sang trạng thái nghẽn, từ bỏ quyền sử dụng CPU. Để thực hiện điều này, cần phải sử dụng các thủ tục do hệ điều hành cung cấp để thay đổi trạng thái quá trình. Hai thủ tục cơ bản SLEEP và WAKEUP thường được sử dụng cho mục đích này. SLEEP là một lời gọi hệ thống có tác dụng làm “nghẽn” (blocked) hoạt động của quá trình gọi nó và chờ đến khi được một tiến trình khác “đánh thức”. Lời gọi hệ thống WAKEUP nhận một tham số duy nhất: quá trình sẽ được kích hoạt trở lại (đặt về trạng thái sẳn sàng). Ý tưởng sử dụng SLEEP và WAKEUP như sau: khi một quá trình chưa đủ điều kiện vào miền tương trục, nó gọi SLEEP để tự khoá đến khi có một quá trình khác gọi WAKEUP để giải phóng nó. Một quá trình gọi WAKEUP khi ra khỏi miền tương trục để đánh thức một quá trình đang chờ, tạo cơ hội cho quá trình này vào miền tương trục. int busy; // 1 nếu miền tương trục đang bị chiếm int blocked; // đếm số lượng quá trình đang bị khoá Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 91
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 do{ if (busy) { blocked = blocked + 1; sleep(); } else busy = 1; }while (1); Critical section busy = 0; if (blocked){ wakeup(process); blocked = blocked -1; } Remainder section Hình 0-12 Cấu trúc chương trình trong giải pháp SLEEP and WAKEUP Khi sử dụng SLEEP và WAKEUP cần hết sức cẩn thận, nếu không muốn xảy ra tình trạng mâu thuẩn truy xuất trong một vài tình huống như sau: giả sử quá trình A vào miền tương trục, và trước khi nó rời miền tương trục thì quá trình B được kích hoạt. Quá trình B thử vào miền tương trục nhưng nó nhận thấy A đang ở trong đó, do vậy B tăng giá trị biến blocked lên 1 và chuẩn bị gọi SLEEP để tự nghẽn. Tuy nhiên, trước khi B có thể thực hiện SLEEP, quá trình A được kích hoạt trở lại và ra khỏi miền tương trục. Khi ra khỏi miền tương trục, quá trình A nhận thấy có một quá trình đang chờ (blocked=1) nên gọi WAKEUP và giảm giá trị blocked xuống 1. Khi đó tín hiệu WAKEUP sẽ lạc mất do quá trình B chưa thật sự “ngủ” để nhận tín hiệu đánh thức! Khi quá trình B được tiếp tục xử lý, nó mới gọi SLEEP và tự nghẽn vĩnh viễn! Vấn đề ghi nhận được là tình trạng lỗi này xảy ra do việc kiểm tra trạng thái miền tương trục và việc gọi SLEEP hay WAKEUP là những hành động tách biệt, có thể bị ngắt nửa chừng trong quá trình xử lý, do đó có khi tín hiệu WAKEUP gởi đến một quá trình chưa bị nghẽn sẽ lạc mất. Để tránh những tình huống tương tự, hệ điều hành cung cấp những cơ chế đồng bộ hoá dựa trên ý tưởng của chiến lược “SLEEP and WAKEUP” nhưng chưa được xây dựng bao gồm cả phương tiện kiểm tra điều kiện vào miền tương trục giúp sử dụng an toàn. V.2.1 Semaphore Tiếp cận Semaphore được. Dijkstra đề xuất vào năm 1965. Một semaphore S là một biến số nguyên (integer) được truy xuất chỉ thông qua hai thao tác nguyên tử: wait và signal. Các thao tác này được đặt tên P (cho wait - chờ để kiểm tra) và V (cho signal- báo hiệu để tăng). Định nghĩa cơ bản của wait trong mã giả là: wait(S){ while (S≤0) ;//no-op S--; } Định nghĩa cơ bản của signal trong mã giả là signal(S){ S++; } Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 92
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Những sửa đổi đối với giá trị integer của semaphore trong các thao tác wait và signal phải được thực thi không bị phân chia. Nghĩa là khi một quá trình sửa đổi giá trị semaphore, không có quá trình nào cùng một lúc có thể sửa đổi cùng biến semaphore đó. Ngoài ra, trong trường hợp của biến wait(S), kiểm tra giá trị integer của S (S ≤ 0) và sửa đổi có thể của nó (S--) cũng phải được thực thi mà không bị ngắt. .V.2.1.1 Cách dùng Chúng ta có thể sử dụng semaphores để giải quyết vấn đề miền tương trục với n quá trình. N quá trình chia sẻ một biến semaphore, mutex (viết tắt từ mutual exclusion) được khởi tạo 1. Mỗi quá trình Pi được tổ chức như được hiển thị trong hình dưới đây. do{ wait(mutex) critical section Signal(mutex) remainder section }while(1); Hình 0-13 Cài đặt loại trừ hỗ tương với semaphores Chúng ta cũng sử dụng semaphores để giải quyết các vấn đề đồng bộ khác nhau. Thí dụ, để xem xét hai quá trình đang thực thi đồng hành: P1 với câu lệnh S1 và P2 với câu lệnh S2. Giả sử chúng ta yêu cầu rằng S2 được thực thi chỉ sau khi S1 hoàn thành. Chúng ta có thể hoàn thành cơ chế này một cách dễ dàng bằng cách P1 và P2 chia sẻ một semaphore chung synch, được khởi tạo 0 và bằng cách chèn các câu lệnh: S1; signal(sync); vào quá trình P1 và các câu lệnh: wait(synch); S2; vào trong quá trình P2. Vì synch được khởi tạo 0. P2 sẽ thực thi S2 chỉ sau khi P1 nạp signal(synch) mà sau đó là S1; .V.2.1.2 Cài đặt Nhược điểm chính của các giải pháp loại trừ hỗ tương trong phần V.-5.1 và của semaphore được cho ở đây là tất cả chúng đều đòi hỏi sự chờ đợi bận.Để giải quyết yêu cầu cho việc chờ đợi bận, chúng ta có thể hiệu chỉnh định nghĩa của các thao tác wait và signal của semaphore. Khi một quá trình thực thi thao tác wait và nhận thấy rằng nếu giá trị của semaphore không dương, nó phải chờ. Tuy nhiên, thay vì chờ đợi bận, quá trình có thể nghẽn chính nó. Thao tác nghẽn đặt quá trình vào một hàng đợi gắn liền với semaphore và trạng thái quá trình được chuyển tới trạng thái chờ. Sau đó, điều khiển được chuyển tới bộ định thời biểu và bộ định thời biểu chọn một quá trình khác để thực thi. Một quá trình bị nghẽn chờ trên biến semaphore nên được khởi động lại khi quá trình khác thực thi thao tác signal. Quá trình được khởi động lại bởi thao tác wakeup và chuyển quá trình từ trạng thái chờ sang trạng thái sẳn sàng. Sau đó, quá trình này được đặt vào hàng đợi sẳn sàng. (CPU có thể hay không thể được chuyển từ quá trình đang chạy tới quá trình sẳn sàng mới nhất phụ thuộc vào giải thuật định thời biểu CPU). Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 93
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Để cài đặt semaphore dưới định nghĩa này, chúng ta định nghĩa một semaphore như một cấu trúc được viết bằng C như sau: typedef struct{ int value; struct process *L; } semaphore; Mỗi semaphore có một số integer value và một danh sách các quá trình L. Khi một quá trình phải chờ trên một semaphore, nó được thêm vào danh sách các quá trình L. Một thao tác signal xoá một quá trình ra khỏi danh sách các quá trình đang chờ và đánh thức quá trình đó. Thao tác semaphore wait bây giờ được định nghĩa như sau: void wait(semaphore S){ S.value--; If (S.value < 0){ Thêm quá trình này tới danh sách các quá trình S.L; block(); } } Thao tác semaphore signal bây giờ có thể được định nghĩa như sau: void signal(semaphore S){ S.value++; if(S.value
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Trong môi trường đa xử lý, ngăn chặn ngắt không thể thực hiện được. Các chỉ thị từ các quá trình khác nhau (chạy trên các bộ xử lý khác nhau) có thể được chen vào trong cách bất kỳ. Nếu phần cứng không cung cấp bất cứ các chỉ thị đặc biệt nào, chúng ta có thể tận dụng các giải pháp phần cứng phù hợp cho vấn đề vùng tương trục (phần V.-4), ở đó các vùng tương trục chứa cá thủ tục wait và signal. Vấn đề quan trọng là chúng ta không xoá hoàn toàn chờ đợi bận, với định nghĩa này cho các thao tác wait và signal. Dĩ nhiên là chúng ta xoá chờ đợi bận từ việc đi vào vùng tương trục của chương trình ứng dụng. Ngoài ra, chúng ta hạn chế việc chờ đợi bận chỉ các miền tương trục với thao tác wait và signal và các vùng này là ngắn (nếu được mã hợp lý, chúng nên không quá 10 chỉ thị). Do đó, miền tương trục hầu như không bao giờ bị chiếm và sự chờ đợi bận rất hiếm khi xảy ra và sau đó chỉ cho thời gian ngắn. Một trường hợp hoàn toàn khác xảy ra với những chương trình ứng dụng có miền tương trục dài (vài phút hay thậm chí vài giờ) hay có thể hầu như luôn bị chiếm. Trong trường hợp này, chờ đợi bận là cực kỳ kém hiệu quả. .V.2.1.3 Sự khoá chết (deadlocks) và đói tài nguyên Cài đặt semaphore với một hàng đợi có thể dẫn đến trường hợp hai hay nhiều quá trình đang chờ không hạn định một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Sự kiện đặt ra là sự thực thi của thao tác signal. Khi một trạng thái như thế xảy ra, những quá trình này được nói là bị khoá chết. Để hiển thị điều này, chúng ta xét một hệ thống chứa hai quá trình P0 và P1, mỗi truy xuất hai semaphore, S và Q, được đặt giá trị 1. P0 P1 wait(S); wait(Q); wait(Q); wait(S); . . . . signal(S); signal(Q); Signal(Q); signal(S); Giả sử rằng P0 thực thi wait(S) và sau đó P1 thực thi wait(Q). Khi P0 thực thi wait(Q), nó phải chờ cho đến khi P1 thực thi signal(Q). Tương tự, khi P1 thực thi wait(S), nó phải chờ cho tới khi P0 thực thi signal(S). Vì các thao tác signal này không thể được thực thi nên P0 và P1 bị khoá chết. Chúng ta nói rằng một tập hợp các quá trình trong trạng thái khoá chết khi mọi quá trình trong tập hợp đang chờ một sự kiện được gây ra chỉ bởi một quá trình khác trong tập hợp. Những sự kiện mà chúng ta quan tâm chủ yếu ở đây là việc chiếm tài nguyên và giải phóng tài nguyên. Tuy nhiên, các loại sự kiện khác cũng có thể dẫn đến việc khoá chết. Chúng ta sẽ xem trong chương VI. Trong chương đó, chúng ta sẽ mô tả các cơ chế khác nhau để giải quyết vấn đề khoá chết. Một vấn đề khoá chết liên quan tới khoá chết là nghẽn hay đói tài nguyên không hạn định (indefinite blocking or starvation), ở đó các quá trình chờ đợi không hạn định trong semaphore. Nghẽn không hạn định có thể xảy ra nếu chúng ta thêm vào và lấy ra các quá trình từ danh sách được nối kết với một semaphore trong thứ tự vào sau ra trước (LIFO). Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 95
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 .V.2.1.4 Semaphore nhị phân Xây dựng semaphore được mô tả trong phần trước được gọi là semaphore đếm (counting semaphore) vì giá trị nguyên có thể trãi dài một phạm vi không giới hạn. Một semaphore nhị phân (binary semaphore) là một semaphore với một giá trị nguyên mà trải dài từ 0 và 1. Semaphore nhị phân có thể đơn giản hơn trong cài đặt so với semaphore đếm và phụ thuộc vào kiến trúc phần cứng nằm bên dưới. Chúng sẽ hiển thị cách một semaphore đếm có thể được cài đặt sử dụng semaphore nhị phân dưới đây: Giả sử S là một semaphore đếm. Để cài đặt nó trong dạng semaphore nhị phân chúng ta cần các cấu trúc dữ liệu như sau: Binary-semaphore S1, S2; int C; Khởi tạo S1 = 1, S2 = 0 và giá trị nguyên C được đặt tới giá trị khởi tạo của semaphore đếm S. Thao tác wait trên semaphore đếm S có thể được cài đặt như sau: wait(S); C--; If (C
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 } . . . procedure Pn (…){ … } { mã khởi tạo } } Hình 0-14 Cú pháp của monỉtor Biểu diễn kiểu monitor không thể được dùng trực tiếp bởi các quá trình khác nhau. Do đó, một thủ tục được định nghĩa bên trong một monitor chỉ có thể truy xuất những biến được khai báo cục bộ bên trong monitor đó và các tham số chính thức của nó. Tương tự, những biến cục bộ của monitor có thể được truy xuất chỉ bởi những thủ tục cục bộ. Xây dựng monitor đảm bảo rằng chỉ một quá trình tại một thời điểm có thể được kích hoạt trong monitor. Do đó, người lập trình không cần viết mã ràng buộc đồng bộ hoá như hình V-15 dưới đây: Hình 0-15 Hình ảnh dưới dạng biểu đồ của monitor Tuy nhiên, xây dựng monitor như được định nghĩa là không đủ mạnh để mô hình hoá các cơ chế đồng bộ. Cho mục đích này, chúng ta cần định nghĩa các cơ chế đồng bộ hoá bổ sung. Những cơ chế này được cung cấp bởi construct condition. Người lập trình có thể định nghĩa một hay nhiều biến của kiểu condition: condition x, y; Chỉ những thao tác có thể gọi lên trên các biến điều kiện là wait và signal. Thao tác Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 97
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 x.wait(); có nghĩa là quá trình gọi trên thao tác này được tạm dừng cho đến khi quá trình khác gọi x.signal(); thao tác x.signal() thực thi tiếp một cách chính xác một quá trình tạm dừng. Nếu không có quá trình tạm dừng thì thao tác signal không bị ảnh hưởng gì cả; nghĩa là trạng thái x như thể thao tác chưa bao giờ được thực thi (như hình V.-16). Ngược lại, với thao tác signal được gán cùng với semaphores luôn ảnh hưởng tới trạng thái của semaphore. Bây giờ giả sử rằng, khi thao tác x.signal() được gọi bởi một quá trình P thì có một quá trình Q gán với biến điều kiện x bị tạm dừng. Rõ ràng, nếu quá trình Q được phép thực thi tiếp thì quá trình P phải dừng. Nếu không thì cả hai quá trình P và Q hoạt động cùng một lúc trong monitor. Tuy nhiên, về khái niệm hai quá trình có thể tiếp tục việc thực thi của chúng. Hai khả năng có thể xảy ra: P chờ cho đến khi Q rời khỏi monitor hoặc chờ điều kiện khác. Q chờ cho đến khi P rời monitor hoặc chờ điều kiện khác. Hình 0-16 Monitor với các biến điều kiện Có các luận cứ hợp lý trong việc chấp nhận khả năng 1 hay 2. Vì P đã thực thi trong monitor rồi, nên chọn khả năng 2 có vẻ hợp lý hơn. Tuy nhiên, nếu chúng ta cho phép quá trình P tiếp tục, biến điều kiện “luận lý” mà Q đang chờ có thể không còn quản lý thời gian Q được tiếp tục. Chọn khả năng 1 được tán thành bởi Hoare vì tham số đầu tiên của nó chuyển trực tiếp tới các qui tắc chứng minh đơn giản hơn. Thoả hiệp giữa hai khả năng này được chấp nhận trong ngôn ngữ đồng hành C. Khi quá trình P thực thi thao tác signal thì quá trình Q lập tức được tiếp tục. Mô hình này không mạnh hơn mô hình của Hoare vì một quá trình không thể báo hiệu nhiều lần trong một lời gọi thủ tục đơn. Bây giờ chúng ta xem xét cài đặt cơ chế monitor dùng semaphores. Đối với mỗi monitor, một biến semaphore mutex (được khởi tạo 1) được cung cấp. Một quá Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 98
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 trình phải thực thi wait(mutex) trước khi đi vào monitor và phải thực thi signal(mutex) sau khi rời monitor. Vì quá trình đang báo hiệu phải chờ cho đến khi quá trình được bắt đầu lại rời hay chờ, một biến semaphore bổ sung next được giới thiệu, được khởi tạo 0 trên quá trình báo hiệu có thể tự tạm dừng. Một biến số nguyên next_count cũng sẽ được cung cấp để đếm số lượng quá trình bị tạm dừng trên next. Do đó, mỗi thủ tục bên ngoài F sẽ được thay thế bởi wait(mutex); ... thân của F if (next_count > 0) signal(next); else signal(mutex); Loại trừ hỗ tương trong monitor được đảm bảo. Bây giờ chúng ta mô tả các biến điều kiện được cài đặt như thế nào. Đối với mỗi biến điều kiện x, chúng ta giới thiệu một biến semaphore x_sem và biến số nguyên x_count, cả hai được khởi tạo tới 0. Thao tác x.wait có thể được cài đặt như sau: x_count++; if ( next_count > 0) signal(next); else signal(mutex); wait(x_sem); x_count--; Thao tác x.signal() có thể được cài đặt như sau: if ( x_count > 0){ next_count++; signal(x_sem); wait(next); next_count--; } Cài đặt này có thể áp dụng để định nghĩa của monitor được cho bởi cả hai Hoare và Brinch Hansen. Tuy nhiên, trong một số trường hợp tính tổng quát của việc cài đặt là không cần thiết và yêu cầu có một cải tiến hiệu quả hơn. Bây giờ chúng ta sẽ trở lại chủ đề thứ tự bắt đầu lại của quá trình trong monitor. Nếu nhiều quá trình bị trì hoãn trên biến điều kiện x và thao tác x.signal được thực thi bởi một vài quá trình thì thứ tự các quá trình bị trì hoãn được thực thi trở lại như thế nào? Một giải pháp đơn giản là dùng thứ tự FCFS vì thế quá trình chờ lâu nhất sẽ được thực thi tiếp trước. Tuy nhiên, trong nhiều trường hợp, cơ chế định thời biểu như thế là không đủ. Cho mục đích này cấu trúc conditional-wait có thể được dùng; nó có dạng x.wait(c); ở đây c là một biểu thức số nguyên được định giá khi thao tác wait được thực thi. Giá trị c, được gọi là số ưu tiên, được lưu với tên quá trình được tạm dừng. Khi x.signal được thực thi, quá trình với số ưu tiên nhỏ nhất được thực thi tiếp. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 99
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Để hiển thị cơ chế mới này, chúng ta xem xét monitor được hiển thị như hình dưới đây, điều khiển việc cấp phát của một tài nguyên đơn giữa các quá trình cạnh tranh. Mỗi quá trình khi yêu cầu cấp phát tài nguyên của nó, xác định thời gian tối đa nó hoạch định để sử dụng tài nguyên. Monitor cấp phát tài nguyên tới quá trình có yêu cầu thời gian cấp phát ngắn nhất. Monitor ResourceAllocation { boolean busy; condition x; void acquire(int time){ if (busy) x.wait(time); busy = true; } void release(){ busy = false; x.signal(); } void init(){ busy = false; } } Hình 0-17 Một monitor cấp phát tới một tài nguyên Một quá trình cần truy xuất tài nguyên phải chú ý thứ tự sau: R.acquire(t); … truy xuất tài nguyên ... R.release(); ở đây R là thể hiện của kiểu ResourceAllocation. Tuy nhiên, khái niệm monitor không đảm bảo rằng các thứ tự truy xuất trước sẽ được chú ý. Đặc biệt, • Một quá trình có thể truy xuất tài nguyên mà không đạt được quyền truy xuất trước đó. • Một quá trình sẽ không bao giờ giải phóng tài nguyên một khi nó được gán truy xuất tới tài nguyên đó. • Một quá trình có thể cố gắng giải phóng tài nguyên mà nó không bao giờ yêu cầu. • Một quá trình có thể yêu cầu cùng tài nguyên hai lần (không giải phóng tài nguyên đó trong lần đầu) Việc sử dụng monitor cũng gặp cùng những khó khăn như xây dựng miền tương trục. Trong phần trước, chúng ta lo lắng về việc sử dụng đúng semaphore. Bây giờ, chúng ta lo lắng về việc sử dụng đúng các thao tác được định nghĩa của người lập trình cấp cao mà các trình biên dịch không còn hỗ trợ chúng ta. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 100
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Một giải pháp có thể đối với vấn đề trên là chứa các thao tác truy xuất tài nguyên trong monitor ResourceAllocation. Tuy nhiên, giải pháp này sẽ dẫn đến việc định thời được thực hiện dựa theo giải thuật định thời monitor được xây dựng sẳn hơn là được viết bởi người lập trình. Để đảm bảo rằng các quá trình chú ý đến thứ tự hợp lý, chúng ta phải xem xét kỹ tất cả chương trình thực hiện việc dùng monitor ResourceAllocation và những tài nguyên được quản lý của chúng. Có hai điều kiện mà chúng ta phải kiểm tra để thiết lập tính đúng đắn của hệ thống. Đầu tiên, các quá trình người dùng phải luôn luôn thực hiện các lời gọi của chúng trên monitor trong thứ tự đúng. Thứ hai, chúng ta phải đảm bảo rằng một quá trình không hợp tác không đơn giản bỏ qua cổng (gateway) loại trừ hỗ tương được cung cấp bởi monitor và cố gắng truy xuất trực tiếp tài nguyên được chia sẻ mà không sử dụng giao thức truy xuất. Chỉ nếu hai điều kiện này có thể được đảm bảo có thể chúng ta đảm bảo rằng không có lỗi ràng buộc thời gian nào xảy ra và giải thuật định thời sẽ không bị thất bại. Mặc dù việc xem xét này có thể cho hệ thống nhỏ, tĩnh nhưng nó không phù hợp cho một hệ thống lớn hay động. Vấn đề kiểm soát truy xuất có thể được giải quyết chỉ bởi một cơ chế bổ sung khác. VI Các bài toán đồng bộ hoá nguyên thuỷ Trong phần này, chúng ta trình bày một số bài toán đồng bộ hoá như những thí dụ về sự phân cấp lớn các vấn đề điều khiển đồng hành. Các vấn đề này được dùng cho việc kiểm tra mọi cơ chế đồng bộ hoá được đề nghị gần đây. Semaphore được dùng cho việc đồng bộ hoá trong các giải pháp dưới đây. VI.1 Bài toán người sản xuất-người tiêu thụ Bài toán người sản xuất-người tiêu thụ (Producer-Consumer) thường được dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hoá. Hai quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ hỗ tương để truy xuất vùng đệm và được khởi tạo với giá trị 1. Các biến semaphore empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo tới giá trị n; biến semaphore full được khởi tạo tới giá trị 0. Mã cho người quá trình sản xuất được hiển thị trong hình V.-18: do{ … sản xuất sản phẩm trong nextp … wait(empty); wait(mutex); … thêm nextp tới vùng đệm … signal(mutex); signal(full); } while (1); Hình 0-18 Cấu trúc của quá trình người sản xuất Mã cho quá trình người tiêu thụ được hiển thị trong hình dưới đây: Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 101
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Chương 7: Đồng bộ hóa tiến trình
55 p | 220 | 62
-
Giáo Trình Hệ Điều Hành – Đồng bộ hóa quá trình
24 p | 155 | 57
-
Bài giảng Hệ điều hành - Chương 4: Đồng bộ hóa tiến trình
85 p | 155 | 56
-
Giáo Trình Hệ Điều Hành - Chương 5: ĐỒNG BỘ HOÁ QUÁ TRÌNH
24 p | 111 | 45
-
Đồng bộ hóa tiến trình
10 p | 139 | 30
-
Chương 5: Đồng bộ hóa tiến trình
0 p | 44 | 16
-
Bài giảng Bài ôn tập: Đồng bộ hóa tiến trình
29 p | 32 | 9
-
Bài giảng Nguyên lý hệ điều hành - Chương 2: Tiến trình
54 p | 26 | 9
-
Bài giảng Hệ điều hành: Chương 5 - Phan Xuân Huy
235 p | 17 | 5
-
Bài giảng Hệ điều hành (Operating Systems) - Hà Lê Hoài Trung
322 p | 27 | 5
-
Bài giảng Hệ điều hành nâng cao - Chapter 6: Process Synchronization
72 p | 40 | 4
-
Bài giảng Nguyên lý hệ điều hành: Chương 2 - ĐH Bách khoa Đà Nẵng
54 p | 20 | 3
-
Bài giảng Nguyên lý hệ điều hành (Bài giảng tuần 4) - Nguyễn Hải Châu
10 p | 18 | 3
-
Bài giảng Hệ điều hành: Chương 5 - Trần Công Án (ĐH Cần Thơ)
56 p | 10 | 2
-
.Cấu hình Nokia E71 đồng bộ hóa với Exchange Server 2007 (Phần 2)
8 p | 21 | 1
-
.Cấu hình Nokia E71 đồng bộ hóa với Exchange Server 2007 (Phần 1)
8 p | 25 | 1
-
Bài giảng Hệ điều hành - Chương 5: Đồng bộ hóa tiến trình
88 p | 8 | 1

markdown:
# ĐỒNG BỘ HOÁ QUÁ TRÌNH
Chia sẻ: Nguyen Hoang Hai | Ngày: | Loại File: PDF | Số trang:24
lượt xem 74
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091208/haimenpro/80x100/chuong5_dong_bo_hoa_2584.jpg)
##
ĐỒNG BỘ HOÁ QUÁ TRÌNH
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Sau khi học xong chương này, người học nắm được những kiến thức sau: • Hiểu vấn đề vùng tương trục • Hiểu cơ chế hoạt động hiệu báo Semaphores để đồng bộ hóa quá trình • Hiểu cơ chế hoạt động của Monitors để đồng bộ hóa quá trình • Vận dụng các giải pháp để giải quyết các bài toán đồng bộ hóa cơ bản II Giới thiệu Một quá trình hợp tác là một quá trình có thể gây ảnh hưởng hay bị ảnh hưởng tới quá trình khác đang thực thi trong hệ thống. Các quá trình hợp...
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: ĐỒNG BỘ HOÁ QUÁ TRÌNH
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 ĐỒNG BỘ HOÁ QUÁ TRÌNH I Mục tiêu Sau khi học xong chương này, người học nắm được những kiến thức sau: • Hiểu vấn đề vùng tương trục • Hiểu cơ chế hoạt động hiệu báo Semaphores để đồng bộ hóa quá trình • Hiểu cơ chế hoạt động của Monitors để đồng bộ hóa quá trình • Vận dụng các giải pháp để giải quyết các bài toán đồng bộ hóa cơ bản II Giới thiệu Một quá trình hợp tác là một quá trình có thể gây ảnh hưởng hay bị ảnh hưởng tới quá trình khác đang thực thi trong hệ thống. Các quá trình hợp tác có thể chia sẻ trực tiếp không gian địa chỉ luận lý (mã và dữ liệu), hay được phép chia sẻ dữ liệu thông qua các tập tin. Trường hợp đầu đạt được thông qua việc sử dụng các quá trình có trọng lượng nhẹ hay luồng. Truy xuất đồng hành dữ liệu được chia sẻ có thể dẫn tới việc không đồng nhất dữ liệu. Trong chương này chúng ta sẽ thảo luận các cơ chế đảm bảo việc thực thi có thứ tự của các quá trình hợp tác chia sẻ không gian địa chỉ để tính đúng đắn của dữ liệu luôn được duy trì. III Tổng quan Trong chương trước, chúng ta phát triển một mô hình hệ thống chứa số lượng quá trình hợp tác tuần tự, tất cả chúng chạy bất đồng bộ và có thể chia sẻ dữ liệu. Chúng ta hiển thị mô hình này với cơ chế vùng đệm có kích thước giới hạn, được đại diện cho hệ điều hành. Chúng ta xét giải pháp bộ nhớ được chia sẻ cho bài toán vùng đệm có kích thước giới hạn. Giải pháp này cho phép có nhiều nhất BUFFER_SIZE –1 sản phẩm trong vùng đệm tại cùng thời điểm. Giả sử rằng chúng ta muốn hiệu chỉnh giải thuật để giải quyết sự thiếu sót này. Một khả năng là thêm một biến đếm số nguyên counter, được khởi tạo bằng 0. counter được tăng mỗi khi chúng ta thêm một sản phẩm tới vùng đệm và bị giảm mỗi khi chúng ta lấy một sản phẩm ra khỏi vùng đệm. Mã cho quá trình người sản xuất có thể được hiệu chỉnh như sau: while (1){/*tạo sản phẩm trong nextProduced*/ while (counter==BUFFER_SIZE); /*không làm gì cả*/ buffer[in] = nextProduced; in = ( in + 1 ) % BUFFER_SIZE; counter++; } Mã cho quá trình người tiêu dùng có thể được hiệu chỉnh như sau: while (1){ while (counter == 0) ; /*không làm gì cả*/ nextConsumed = buffer[out]; Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 82
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 out = ( out + 1 ) % BUFFER_SIZE; counter--; /*tiêu thụ sản phẩm trong nextConsumed*/ } Mặc dù cả hai thủ tục người sản xuất và người tiêu dùng thực thi đúng khi tách biệt nhau nhưng chúng không thực hiện đúng chức năng khi thực thi đồng hành. Như minh hoạ dưới đây, giả sử rằng giá trị của biến counter hiện tại là 5 và thủ tục người sản xuất và người tiêu dùng thực thi đồng hành câu lệnh “counter++” và “counter--”. Theo sau việc thực thi hai câu lệnh này, giá trị của biến counter có thể là 4, 5 hay 6! Kết quả chỉ đúng khi biến counter==5, được tạo ra đúng nếu quá trình người sản xuất và người tiêu dùng thực thi riêng biệt. Chúng ta có thể minh hoạ giá trị của counter có thể không đúng như sau. Chú ý, câu lệnh “counter++” có thể được cài đặt bằng ngôn ngữ máy (trên một máy điển hình) như sau: register1 = counter register1 = register1 + 1 counter = register1 Ở đây register1 là một thanh ghi CPU cục bộ. Tương tự, câu lệnh “counter--” được cài đặt như sau: register2 = counter register2 = register2 - 1 counter = register2 Ở đây register2 là thanh ghi CPU cục bộ. Dù là register1 và register2 có thể dùng cùng thanh ghi vật lý, nhưng nội dung của thanh ghi sẽ được lưu lại và lấy lại bởi bộ quản lý ngắt. Thực thi đồng hành của “counter++” và “counter--” là tương tự như thực thi tuần tự ở đây các câu lệnh cấp thấp hơn được hiện diện trước bị phủ lắp trong thứ tự bất kỳ (nhưng thứ tự bên trong mỗi câu lệnh cấp cao được lưu giữ). Một sự phủ lắp là: T0: producer thực thi register1 = counter {register1 = 5} T1: producer thực thi register1 = register1 + 1 {register1 = 6} T2: consumer thực thi register2 = counter {register2 = 5} T3: consumer thực thi register2 = register2 – 1 {register2 = 4} T4: producer thực thi counter = register1 {counter = 6} T5: consumer thực thi counter = register2 {counter = 4} Chú ý rằng, chúng ta xem xét tình trạng không đúng “counter==4” theo đó có 4 vùng đệm đầy, nhưng thực tế khi đó có 5 vùng đệm đầy. Nếu chúng đổi ngược lại thứ tự của câu lệnh T4 và T5, chúng ta sẽ có trạng thái không đúng “counter ==6”. Chúng ta đi đến trạng thái không đúng này vì chúng ta cho phép cả hai quá trình thao tác đồng thời trên biến counter. Trường hợp tương tự, ở đây nhiều quá trình truy xuất và thao tác cùng dữ liệu đồng hành và kết quả của việc thực thi phụ thuộc vào thứ tự xác định trong đó việc truy xuất xảy ra, được gọi là điều kiện cạnh tranh (race condition). Để ngăn chặn điều kiện cạnh tranh ở trên, chúng ta cần đảm bảo rằng chỉ một quá trình tại một thời điểm có thể được thao tác biến counter. Để thực hiện việc đảm bảo như thế, chúng ta yêu cầu một vài hình thức đồng bộ hoá quá trình. Những Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 83
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 trường hợp như thế xảy ra thường xuyên trong các hệ điều hành khi các phần khác nhau của hệ thống thao tác các tài nguyên và chúng ta muốn các thay đổi không gây trở ngại một sự thay đổi khác. Phần chính của chương này là tập trung vào vấn đề đồng bộ hoá và cộng tác quá trình. IV Vấn đề vùng tương trục Xét một hệ thống gồm n quá trình (P0, P1, … ,Pn-1 ). Mỗi quá trình có một phân đoạn mã, được gọi là vùng tương trục (critical section), trong đó quá trình này có thể thay đổi những biến dùng chung, cập nhật một bảng, viết đến tập tin,.. Đặc điểm quan trọng của hệ thống là ở chỗ, khi một quá trình đang thực thi trong vùng tương trục, không có quá trình nào khác được phép thực thi trong vùng tương trục của nó. Do đó, việc thực thi của các vùng tương trục bởi các quá trình là sự loại trừ hỗ tương. Vấn đề vùng tương trục là thiết kế một giao thức mà các quá trình có thể dùng để cộng tác. Mỗi quá trình phải yêu cầu quyền để đi vào vùng tương trục của nó. Vùng mã thực hiện yêu cầu này là phần đi vào (entry section). Vùng tương trục có thể được theo sau bởi một phần kết thúc (exit section). Mã còn lại là phần còn lại (remainder section). do { entry section critical section exit section remainder section } while (1); Hình 0-1 Cấu trúc chung của một quá trình điển hình Pi Một giải pháp đối với vấn đề vùng tương trục phải thoả mãn ba yêu cầu sau: • Loại trừ hỗ tương (Mutual Exclusion): Nếu quá trình Pi đang thực thi trong vùng tương trục của nó thì không quá trình nào khác đang được thực thi trong vùng tương trục đó. • Tiến trình (Progress): nếu không có quá trình nào đang thực thi trong vùng tương trục và có vài quá trình muốn vào vùng tương trục thì chỉ những quá trình không đang thực thi phần còn lại mới có thể tham gia vào việc quyết định quá trình nào sẽ đi vào vùng tương trục tiếp theo và chọn lựa này không thể trì hoãn vô hạn định. • Chờ đợi có giới hạn (bounded wait): giới hạn số lần các quá trình khác được phép đi vào miền tương trục sau khi một quá trình thực hiện yêu cầu để đi vào miền tương trục của nó và trước khi yêu cầu đó được gán. Chúng ta giả sử rằng mỗi quá trình đang thực thi với tốc độ khác 0. Tuy nhiên, chúng ta có thể thực hiện rằng không có giả thuyết nào được quan tâm về tốc tương đối của n quá trình. Trong phần tiếp theo chúng ta nghiên cứu để nắm được các giải pháp thoả ba yêu cầu này. Những giải pháp này không quan tâm đến các chỉ thị phần cứng hay số lượng bộ xử lý mà phần cứng hỗ trợ. Tuy nhiên chúng ta giả sử rằng những chỉ thị ngôn ngữ máy cơ bản (chỉ thị cơ bản như load, store và test) được thực hiện mang Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 84
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 tính nguyên tử (atomically). Nghĩa là, nếu hai chỉ thị như thế được thực thi đồng hành thì kết quả tương tự như thực thi tuần tự trong thứ tự không xác định. Do đó, nếu chỉ thị load và store được thực thi đồng hành thì load sẽ nhận giá trị cũ hay mới như không có sự kết hợp vừa cũ vừa mới. Khi trình bày một giải thuật, chúng ta định nghĩa chỉ những biến được dùng cho mục đích đồng bộ và mô tả chỉ một quá trình điển hình Pi mà cấu trúc của nó được hiển thị trong hình V.1. Phần đi vào và kết thúc được bao trong hình chữ nhật để nhấn mạnh các đoạn mã quan trọng. do { while (turn!=i) ; critical section turn = j; remainder section } while (1); Hình 0-2-Cấu trúc của quá trình Pi trong giải thuật 1 V Giải pháp Có nhiều giải pháp để thực hiện việc loại trừ hỗ tương. Các giải pháp này, tuỳ thuộc vào cách tiếp cận trong xử lý của quá trình bị khoá, được phân biệt thành hai lớp: chờ đợi bận (busy waiting) và nghẽn và đánh thức (sleep and wakeup) V.1 Giải pháp “chờ đợi bận” V.1.1 Giải pháp hai quá trình (two-Process Solution) Trong phần này, chúng ta giới hạn việc quan tâm tới những giải thuật có thể áp dụng chỉ hai quá trình cùng một lúc. Những quá trình này được đánh số P0 và P1. Để thuận lợi, khi trình bày Pi, chúng ta dùng Pj để chỉ quá trình còn lại, nghĩa là j = 1 – i .V.1.1.1 Giải thuật 1 Tiếp cận đầu tiên của chúng ta là để hai quá trình chia sẻ một biến số nguyên chung turn được khởi tạo bằng 0 (hay 1). Nếu turn == 0 thì quá trình Pi được phép thực thi trong vùng tương trục của nó. Cấu trúc của quá trình Pi được hiển thị trong Hình V.-2. Giải pháp này đảm bảo rằng chỉ một quá trình tại một thời điểm có thể ở trong vùng tương trục của nó. Tuy nhiên, nó không thoả mãn yêu cầu tiến trình vì nó yêu cầu sự thay đổi nghiêm khắc của các quá trình trong việc thực thi của vùng tương trục. Thí dụ, nếu turn == 0 và P1 sẳn sàng đi vào vùng tương trục của nó thì P1 không thể đi vào vùng tương trục thậm chí khi P0 đang ở trong phần còn lại của nó. .V.1.1.2 Giải thuật 2 Vấn đề với giải thuật 1 là nó không giữ lại đủ thông tin về trạng thái của mỗi quá trình; nó nhớ chỉ quá trình nào được phép đi vào miền tương trục. Để giải quyết vấn đề này, chúng ta có thể thay thế biến turn với mảng sau: Boolean flag[2]; Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 85
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Các phần tử của mảng được khởi tạo tới flase. Nếu flag[i] là true, giá trị này hiển thị rằng Pi sẳn sàng đi vào vùng tương trục. Cấu trúc của quá trình Pi được hiển thị trong hình V.-3 dưới đây: do{ flag[i] = true; while (flag[j]); critical section flag[i] = false; remainder section } while(1); Hình 0-3 –Cấu trúc của quá trình Pi trong giải thuật 2 Trong giải thuật này, quá trình Pi trước tiên thiết lập flag[i] tới true, hiển thị rằng nó sẳn sàng đi vào miền tương trục. Sau đó, Pi kiểm tra rằng quá trình quá trình Pj cũng không sẳn sàng đi vào miền tương trục của nó. Nếu Pj sẳn sàng thì Pi sẽ chờ cho tới khi Pj hiển thị rằng nó không còn cần ở trong vùng tương trục nữa (nghĩa là cho tới khi flag[j] là false). Tại thời điểm này, Pi sẽ đi vào miền tương trục. Thoát ra khỏi miền tương trục, Pi sẽ đặt flag[i] là false, cho phép quá trình khác (nếu nó đang chờ) đi vào miền tương trục của nó. Trong giải pháp này, yêu cầu loại trừ hỗ tương sẽ được thoả mãn. Tuy nhiên, yêu cầu tiến trình không được thoả mãn. Để minh hoạ vấn đề này, chúng ta xem xét thứ tự thực thi sau: T0: P0 thiết lập flag[0] = true; T1: P1 thiết lập flag[1] = true; Bây giờ P0 và P1 được lập mãi mãi trong câu lệnh while tương ứng của chúng. Giải thuật này phụ thuộc chủ yếu vào thời gian chính xác của hai quá trình. Thứ tự này được phát sinh trong môi trường nơi có nhiều bộ xử lý thực thi đồng hành hay nơi một ngắt (chẳng hạn như một ngắt định thời) xảy ra lập tức sau khi bước T0 được thực thi và CPU được chuyển từ một quá trình này tới một quá trình khác. Chú ý rằng chuyển đổi thứ tự của các chỉ thị lệnh để thiết lập flag[i] và kiểm tra giá trị của flag[j] sẽ không giải quyết vấn đề của chúng ta. Hơn nữa chúng ta sẽ có một trường hợp đó là hai quá trình ở trong vùng tương trục cùng một lúc, vi phạm yêu cầu loại trừ hỗ tương. .V.1.1.3 Giải thuật 3 Giải thuật 3 còn gọi là giải pháp Peterson. Bằng cách kết hợp hai ý tưởng quan trọng trong giải thuật 1 và 2, chúng ta đạt được một giải pháp đúng tới với vấn đề vùng tương trục, ở đó hai yêu cầu được thoả. Các quá trình chia sẻ hai biến: Boolean flag[2] Int turn; Khởi tạo flag[0] = flag[1] = false và giá trị của turn là không xác định (hoặc là 0 hay 1). Cấu trúc của quá trình Pi được hiển thị trong hình sau: Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 86
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 do{ flag[i] = true; turn = j; while (flag[j] &&turn ==j); critical section flag[i] = false; remainder section } while (1); Hình 0-4 Cấu trúc của quá trình Pi trong giải thuật 3 Để đi vào miền tương trục, quá trình Pi trước tiên đặt flag[i] là true sau đó đặt turn tới giá trị j, do đó xác định rằng nếu quá trình khác muốn đi vào miền tương trục nó. Nếu cả hai quá trình đi vào miền tương trục cùng một lúc turn sẽ đặt cả hai i và j tại xấp xỉ cùng một thời điểm. Chỉ một trong hai phép gán này là kết quả cuối cùng. Giá trị cuối cùng của turn quyết định quá trình nào trong hai quá trình được cho phép đi vào miền tương trục trước. Bây giờ chúng ta chứng minh rằng giải pháp này là đúng. Chúng ta cần hiển thị rằng: 1) Loại trừ hỗ tương được bảo toàn 2) Yêu cầu tiến trình được thoả 3) Yêu cầu chờ đợi có giới hạn cũng được thoả Chứng minh thuộc tính 1, chúng ta chú ý rằng mỗi Pi đi vào miền tương trục của nó chỉ nếu flag[j] ==false hay turn ==i. Cũng chú ý rằng, nếu cả hai quá trình có thể đang thực thi trong vùng tương trục của chúng tại cùng thời điểm thì flag[0] == flag[1] ==true. Hai nhận xét này ngụ ý rằng P0 và P1 không thể thực thi thành công trong vòng lặp while của chúng tại cùng một thời điểm vì giá trị turn có thể là 0 hay 1. Do đó, một trong các quá trình-Pj phải được thực thi thành công câu lệnh while, ngược lại Pi phải thực thi ít nhất câu lệnh bổ sung (“turn==j”). Tuy nhiên, vì tại thời điểm đó, flag[j] ==true và turn ==j, và điều kiện này sẽ không đổi với điều kiện là Pj ở trong vùng miền tương trục của nó, kết quả sau việc loại trừ hỗ tương được bảo vệ do { flag[i] = true; turn = j; while (flag[j] && turn ==j); critical section flag[i] = false; Remainder section }while (1); Hình 0-5-Cấu trúc của quá trình Pi trong giải thuật 3 Để chứng minh thuộc tính 2 và 3, chúng ta chú ý rằng một quá trình Pi có thể được ngăn chặn từ việc đi vào miền tương truc chỉ nếu nó bị kẹt trong vòng lặp while với điều kiện flag[j] == true và turn == j. Nếu Pj không sẳn sàng đi vào miền tương trục thì flag[j] == false và Pi có thể đi vào miền tương trục của nó. Nếu Pj đặt flag[j] là true và nó cũng đang thực thi trong câu lệnh while của nó thì turn == i hay turn == j. Nếu turn == i thì Pi sẽ đi vào miền tương trục. Nếu turn ==j thì Pj sẽ đi vào miền tương trục. Tuy nhiên, một khi Pj ở trong vùng tương trục của nó thì nó sẽ đặt lại Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 87
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 flag[j] tới false, cho phép Pi đi vào miền tương trục của nó. Nếu Pj đặt lại flag[j] tới true, nó cũng phải đặt turn tới i. Do đó, vì Pi không thay đổi giá trị của biến turn trong khi thực thi câu lệnh while, nên Pi sẽ đi vào miền tương trục (tiến trình) sau khi nhiều nhất chỉ Pj đi vào (chờ có giới hạn). V.1.2 Giải pháp nhiều quá trình Giải thuật 3 giải quyết vấn đề miền tương trục cho hai quá trình. Bây giờ chúng ta phát triển một giải thuật để giải quyết vấn đề miền tương trục cho n quá trình. Giải thuật này được gọi là giải thuật Bakery và nó dựa trên cơ sở của giải thuật định thời thường được dùng trong cửa hiệu bánh mì, cửa hàng kem,..nơi mà thứ tự rất hỗn độn. Giải thuật này được phát triển cho môi trường phân tán, nhưng tại thời điểm này chúng ta tập trung chỉ những khía cạnh của giải thuật liên quan tới môi trường tập trung. Đi vào một cửa hàng, mỗi khách hàng nhận một số. Khách hàng với số thấp nhất được phục vụ tiếp theo. Tuy nhiên, giải thuật Bakery không thể đảm bảo hai quá trình (khách hàng) không nhận cùng số. Trong trường hợp ràng buộc, một quá trình với tên thấp được phục vụ trước. Nghĩa là, nếu Pi và Pj nhận cùng một số và nếu (i < j) thì Pi được phục vụ trước. Vì tên quá trình là duy nhất và được xếp thứ tự nên giải thuật là hoàn toàn mang tính “may rủi” (deterministic). Cấu trúc dữ liệu chung là boolean choosing[n]; int number[n]; Đầu tiên, các cấu trúc dữ liệu này được khởi tạo tới false và 0 tương ứng. Để tiện dụng, chúng ta định nghĩa các ký hiệu sau: • (a, b) < (c, d) nếu a< c hay nếu a==c và b< d • max(a0,…,an-1) là số k ≥ ai với i = 0,…,n-1 Cấu trúc của quá trình Pi được dùng trong giải thuật Bakery, được hiển thị trong hình dưới đây. do { choosing[i] = true; number[i] = max(number[0], number[i],…,number[n-1]) + 1; choosing[i] = false; for (j=0; j < n; j++){ while (choosing[j]); while ((number[j]!=0)&&((number[ j ], j )
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Do đó, nó tiếp tục vòng lặp trong câu lệnh while cho đến khi Pi rời khỏi vùng tương trục Pi. Giải thuật trên đảm bảo rằng yêu cầu về tiến trình, chờ đợi có giới hạn và đảm bảo sự công bằng, vì các quá trình đi vào miền tương trục dựa trên cơ sở tới trước được phục vụ trước. V.1.3 Phần cứng đồng bộ hoá Như các khía cạnh khác của phần mềm, các đặc điểm phần cứng có thể làm các tác vụ lập trình dễ hơn và cải tiến tính hiệu quả của hệ thống. Trong phần này, chúng ta trình bày một số chỉ thị phần cứng đơn giản sẳn dùng trên nhiều hệ thống và trình bày cách chúng được dùng hiệu quả trong việc giải quyết vấn đề miền tương trục. boolean TestAndSet( boolean &target){ boolean rv = target; target = true; return rv; } Hình 0-7 Định nghĩa của chỉ thị TestAndSet Vấn đề miền tương trục có thể được giải quyết đơn giản trong môi trường chỉ có một bộ xử lý nếu chúng ta cấm các ngắt xảy ra khi một biến chia sẻ đang được thay đổi. Trong cách này, chúng ta đảm bảo rằng chuỗi chỉ thị hiện hành có thể được cho phép thực thi trong thứ tự không trưng dụng. Không có chỉ thị nào khác có thể chạy vì thế không có bất cứ sự thay đổi nào có thể được thực hiện trên các biến được chia sẻ. Tuy nhiên, giải pháp này là không khả thi trong một môi trường có nhiều bộ xử lý. Vô hiệu hoá các ngắt trên đa bộ xử lý có thể mất nhiều thời gian khi một thông điệp muốn truyền qua tất cả bộ xử lý. Việc truyền thông điệp này bị trì hoãn khi đi vào miền tương trục và tính hiệu quả của hệ thống bị giảm. Do đó nhiều máy cung cấp các chỉ thị phần cứng cho phép chúng ta kiểm tra hay thay đổi nội dung của một từ (word) hay để thay đổi nội dung của hai từ tuân theo tính nguyên tử (atomically)-như là một đơn vị không thể ngắt. Chúng ta có thể sử dụng các chỉ thị đặc biệt này để giải quyết vấn đề miền tương trục trong một cách tương đối đơn giản. Chỉ thị TestAndSet có thể được định nghĩa như trong hình V.-7. Đặc điểm quan trọng của chỉ thị này là việc thực thi có tính nguyên tử. Do đó, nếu hai chỉ thị TestAndSet được thực thi cùng một lúc (mỗi chỉ thị trên một CPU khác nhau), thì chúng sẽ được thực thi tuần tự trong thứ tự bất kỳ. do{ while (TestAndSet(lock)); Critical section lock:= false remainder section } while (1); Hình 0-8: Cài đặt loại trừ hỗ tương với TestAndSet Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 89
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Nếu một máy hỗ trợ chỉ thị TestAndSet thì chúng ta có thể loại trừ hỗ tương bằng cách khai báo một biến khoá kiểu luận lý và được khởi tạo tới false. Cấu trúc của quá trình Pi được hiển thị trong hình V.-9 ở trên. Chỉ thị Swap được định như hình V.-9 dưới đây, thao tác trên nội dung của hai từ; như chỉ thị TestAndSet, nó được thực thi theo tính nguyên tử. void Swap(boolean &a, boolean &b){ boolean temp = a; a = b; b = temp; } Hình 0-9: Định nghĩa chỉ thị Swap Nếu một máy hỗ trợ chỉ thị Swap, thì việc loại trừ hỗ tương có thể được cung cấp như sau. Một biến luận lý toàn cục lock được khai báo và được khởi tạo tới false. Ngoài ra, mỗi quá trình cũng có một biến luận lý cục bộ key. Cấu trúc của quá trình Pi được hiển thị trong hình V.-10 dưới đây. do{ key = true; while (key == true) Swap(lock, key); Critical section lock = false; Remainder section } while(1); Hình 0-10: Cài đặt loại trừ hỗ tương với chỉ thị Swap Các giải thuật này không thoả mãn yêu cầu chờ đợi có giới hạn. Chúng ta hiển thị giải thuật sử dụng chỉ thị TestAndSet trong hình V.-11 dưới đây. Giải thuật này thoả mãn tất cả các yêu cầu miền tương trục. do{ Waiting[i] = true; key = true; while (waiting[i] && key) key = TestAndSet(lock); waiting[i] = false; Critical section j = (i + 1) % n; while ((j != i ) && !waiting[j]) j = (j + 1 ) % n; if (j == i) lock = false; else waiting[j] = false; Remainder section } while(1); Hình 0-11 Loại trừ hỗ tương chờ đợi có giới hạn với TestAndSet Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 90
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Cấu trúc dữ liệu thông thường là: boolean waiting[n]; boolean lock; Cấu trúc dữ liệu này được khởi tạo tới false. Để chứng minh rằng loại trừ hỗ tương được thoả, chúng ta chú ý rằng quá trình Pi có thể đưa vào miền tương trục chỉ nếu hoặc waiting[i] ==false hay key == false. Giá trị của key có thể trở thành false chỉ nếu TestAndSet được thực thi. Đối với quá trình đầu tiên, để thực thi TestAndSet sẽ tìm key == false; tất cả quá trình khác phải chờ. Biến waiting[i] có thể trở thành false chỉ nếu quá trình khác rời khởi miền tương trục của nó; chỉ một waiting[i] được đặt false, duy trì yêu cầu loại trừ hỗ tương. Để chứng minh yêu cầu tiến trình được thoả, chúng ta chú ý rằng các đối số được hiện diện cho việc loại trừ hỗ tương cũng áp dụng được ở đây, vì thế một quá trình thoát khỏi miền tương trục hoặc đặt lock bằng false hay đặt waiting[j] bằng false. Cả hai trường hợp đều cho phép một quá trình đang chờ để đi vào miền tương trục được xử lý. Để chứng minh yêu cầu chờ đợi được giới hạn được thoả, chúng ta chú ý rằng khi một quá trình rời miền tương trục của nó, nó duyệt qua mảng waiting trong thứ tự tuần hoàn (i + 1, i + 2, …, n – 1, 0, …, i - 1). Nó định rõ quá trình đầu tiên trong thứ tự này mà thứ tự đó ở trong phần đi vào (waiting[j] == true) khi quá trình tiếp theo đi vào miền tương trục. Bất cứ quá trình nào đang chờ để đi vào miền tương trục sẽ thực hiện n – 1 lần. Tuy nhiên, đối với người thiết kế phần cứng, cài đặt các chỉ thị nguyên tử TestAndSet trên bộ đa xử lý không là tác vụ thử nghiệm. Những giải pháp trên đều phải thực hiện một vòng lặp để kiểm tra liệu nó có được phép vào miền tương trục hay không. Nếu điều kiện chưa thoả, quá trình phải chờ tiếp tục trong vòng lặp kiểm tra này. Các giải pháp buộc quá trình phải liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào miền tương trục như thế được gọi là các giải pháp chờ đợi bận “busy waiting”. Lưu ý, việc kiểm tra như thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy quá trình đang chờ vẫn chiếm dụng CPU. Xu hướng giải quyết vấn đề đồng bộ hoá là nên tránh các giải pháp chờ đợi bận. V.2 Các giải pháp “SLEEP and WAKEUP” Để loại bỏ các bất tiện của của giải pháp chờ đợi bận, chúng ta có thể tiếp cận theo hướng cho một quá trình chưa đủ điều kiện vào miền tương trục chuyển sang trạng thái nghẽn, từ bỏ quyền sử dụng CPU. Để thực hiện điều này, cần phải sử dụng các thủ tục do hệ điều hành cung cấp để thay đổi trạng thái quá trình. Hai thủ tục cơ bản SLEEP và WAKEUP thường được sử dụng cho mục đích này. SLEEP là một lời gọi hệ thống có tác dụng làm “nghẽn” (blocked) hoạt động của quá trình gọi nó và chờ đến khi được một tiến trình khác “đánh thức”. Lời gọi hệ thống WAKEUP nhận một tham số duy nhất: quá trình sẽ được kích hoạt trở lại (đặt về trạng thái sẳn sàng). Ý tưởng sử dụng SLEEP và WAKEUP như sau: khi một quá trình chưa đủ điều kiện vào miền tương trục, nó gọi SLEEP để tự khoá đến khi có một quá trình khác gọi WAKEUP để giải phóng nó. Một quá trình gọi WAKEUP khi ra khỏi miền tương trục để đánh thức một quá trình đang chờ, tạo cơ hội cho quá trình này vào miền tương trục. int busy; // 1 nếu miền tương trục đang bị chiếm int blocked; // đếm số lượng quá trình đang bị khoá Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 91
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 do{ if (busy) { blocked = blocked + 1; sleep(); } else busy = 1; }while (1); Critical section busy = 0; if (blocked){ wakeup(process); blocked = blocked -1; } Remainder section Hình 0-12 Cấu trúc chương trình trong giải pháp SLEEP and WAKEUP Khi sử dụng SLEEP và WAKEUP cần hết sức cẩn thận, nếu không muốn xảy ra tình trạng mâu thuẩn truy xuất trong một vài tình huống như sau: giả sử quá trình A vào miền tương trục, và trước khi nó rời miền tương trục thì quá trình B được kích hoạt. Quá trình B thử vào miền tương trục nhưng nó nhận thấy A đang ở trong đó, do vậy B tăng giá trị biến blocked lên 1 và chuẩn bị gọi SLEEP để tự nghẽn. Tuy nhiên, trước khi B có thể thực hiện SLEEP, quá trình A được kích hoạt trở lại và ra khỏi miền tương trục. Khi ra khỏi miền tương trục, quá trình A nhận thấy có một quá trình đang chờ (blocked=1) nên gọi WAKEUP và giảm giá trị blocked xuống 1. Khi đó tín hiệu WAKEUP sẽ lạc mất do quá trình B chưa thật sự “ngủ” để nhận tín hiệu đánh thức! Khi quá trình B được tiếp tục xử lý, nó mới gọi SLEEP và tự nghẽn vĩnh viễn! Vấn đề ghi nhận được là tình trạng lỗi này xảy ra do việc kiểm tra trạng thái miền tương trục và việc gọi SLEEP hay WAKEUP là những hành động tách biệt, có thể bị ngắt nửa chừng trong quá trình xử lý, do đó có khi tín hiệu WAKEUP gởi đến một quá trình chưa bị nghẽn sẽ lạc mất. Để tránh những tình huống tương tự, hệ điều hành cung cấp những cơ chế đồng bộ hoá dựa trên ý tưởng của chiến lược “SLEEP and WAKEUP” nhưng chưa được xây dựng bao gồm cả phương tiện kiểm tra điều kiện vào miền tương trục giúp sử dụng an toàn. V.2.1 Semaphore Tiếp cận Semaphore được. Dijkstra đề xuất vào năm 1965. Một semaphore S là một biến số nguyên (integer) được truy xuất chỉ thông qua hai thao tác nguyên tử: wait và signal. Các thao tác này được đặt tên P (cho wait - chờ để kiểm tra) và V (cho signal- báo hiệu để tăng). Định nghĩa cơ bản của wait trong mã giả là: wait(S){ while (S≤0) ;//no-op S--; } Định nghĩa cơ bản của signal trong mã giả là signal(S){ S++; } Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 92
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Những sửa đổi đối với giá trị integer của semaphore trong các thao tác wait và signal phải được thực thi không bị phân chia. Nghĩa là khi một quá trình sửa đổi giá trị semaphore, không có quá trình nào cùng một lúc có thể sửa đổi cùng biến semaphore đó. Ngoài ra, trong trường hợp của biến wait(S), kiểm tra giá trị integer của S (S ≤ 0) và sửa đổi có thể của nó (S--) cũng phải được thực thi mà không bị ngắt. .V.2.1.1 Cách dùng Chúng ta có thể sử dụng semaphores để giải quyết vấn đề miền tương trục với n quá trình. N quá trình chia sẻ một biến semaphore, mutex (viết tắt từ mutual exclusion) được khởi tạo 1. Mỗi quá trình Pi được tổ chức như được hiển thị trong hình dưới đây. do{ wait(mutex) critical section Signal(mutex) remainder section }while(1); Hình 0-13 Cài đặt loại trừ hỗ tương với semaphores Chúng ta cũng sử dụng semaphores để giải quyết các vấn đề đồng bộ khác nhau. Thí dụ, để xem xét hai quá trình đang thực thi đồng hành: P1 với câu lệnh S1 và P2 với câu lệnh S2. Giả sử chúng ta yêu cầu rằng S2 được thực thi chỉ sau khi S1 hoàn thành. Chúng ta có thể hoàn thành cơ chế này một cách dễ dàng bằng cách P1 và P2 chia sẻ một semaphore chung synch, được khởi tạo 0 và bằng cách chèn các câu lệnh: S1; signal(sync); vào quá trình P1 và các câu lệnh: wait(synch); S2; vào trong quá trình P2. Vì synch được khởi tạo 0. P2 sẽ thực thi S2 chỉ sau khi P1 nạp signal(synch) mà sau đó là S1; .V.2.1.2 Cài đặt Nhược điểm chính của các giải pháp loại trừ hỗ tương trong phần V.-5.1 và của semaphore được cho ở đây là tất cả chúng đều đòi hỏi sự chờ đợi bận.Để giải quyết yêu cầu cho việc chờ đợi bận, chúng ta có thể hiệu chỉnh định nghĩa của các thao tác wait và signal của semaphore. Khi một quá trình thực thi thao tác wait và nhận thấy rằng nếu giá trị của semaphore không dương, nó phải chờ. Tuy nhiên, thay vì chờ đợi bận, quá trình có thể nghẽn chính nó. Thao tác nghẽn đặt quá trình vào một hàng đợi gắn liền với semaphore và trạng thái quá trình được chuyển tới trạng thái chờ. Sau đó, điều khiển được chuyển tới bộ định thời biểu và bộ định thời biểu chọn một quá trình khác để thực thi. Một quá trình bị nghẽn chờ trên biến semaphore nên được khởi động lại khi quá trình khác thực thi thao tác signal. Quá trình được khởi động lại bởi thao tác wakeup và chuyển quá trình từ trạng thái chờ sang trạng thái sẳn sàng. Sau đó, quá trình này được đặt vào hàng đợi sẳn sàng. (CPU có thể hay không thể được chuyển từ quá trình đang chạy tới quá trình sẳn sàng mới nhất phụ thuộc vào giải thuật định thời biểu CPU). Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 93
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Để cài đặt semaphore dưới định nghĩa này, chúng ta định nghĩa một semaphore như một cấu trúc được viết bằng C như sau: typedef struct{ int value; struct process *L; } semaphore; Mỗi semaphore có một số integer value và một danh sách các quá trình L. Khi một quá trình phải chờ trên một semaphore, nó được thêm vào danh sách các quá trình L. Một thao tác signal xoá một quá trình ra khỏi danh sách các quá trình đang chờ và đánh thức quá trình đó. Thao tác semaphore wait bây giờ được định nghĩa như sau: void wait(semaphore S){ S.value--; If (S.value < 0){ Thêm quá trình này tới danh sách các quá trình S.L; block(); } } Thao tác semaphore signal bây giờ có thể được định nghĩa như sau: void signal(semaphore S){ S.value++; if(S.value
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Trong môi trường đa xử lý, ngăn chặn ngắt không thể thực hiện được. Các chỉ thị từ các quá trình khác nhau (chạy trên các bộ xử lý khác nhau) có thể được chen vào trong cách bất kỳ. Nếu phần cứng không cung cấp bất cứ các chỉ thị đặc biệt nào, chúng ta có thể tận dụng các giải pháp phần cứng phù hợp cho vấn đề vùng tương trục (phần V.-4), ở đó các vùng tương trục chứa cá thủ tục wait và signal. Vấn đề quan trọng là chúng ta không xoá hoàn toàn chờ đợi bận, với định nghĩa này cho các thao tác wait và signal. Dĩ nhiên là chúng ta xoá chờ đợi bận từ việc đi vào vùng tương trục của chương trình ứng dụng. Ngoài ra, chúng ta hạn chế việc chờ đợi bận chỉ các miền tương trục với thao tác wait và signal và các vùng này là ngắn (nếu được mã hợp lý, chúng nên không quá 10 chỉ thị). Do đó, miền tương trục hầu như không bao giờ bị chiếm và sự chờ đợi bận rất hiếm khi xảy ra và sau đó chỉ cho thời gian ngắn. Một trường hợp hoàn toàn khác xảy ra với những chương trình ứng dụng có miền tương trục dài (vài phút hay thậm chí vài giờ) hay có thể hầu như luôn bị chiếm. Trong trường hợp này, chờ đợi bận là cực kỳ kém hiệu quả. .V.2.1.3 Sự khoá chết (deadlocks) và đói tài nguyên Cài đặt semaphore với một hàng đợi có thể dẫn đến trường hợp hai hay nhiều quá trình đang chờ không hạn định một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Sự kiện đặt ra là sự thực thi của thao tác signal. Khi một trạng thái như thế xảy ra, những quá trình này được nói là bị khoá chết. Để hiển thị điều này, chúng ta xét một hệ thống chứa hai quá trình P0 và P1, mỗi truy xuất hai semaphore, S và Q, được đặt giá trị 1. P0 P1 wait(S); wait(Q); wait(Q); wait(S); . . . . signal(S); signal(Q); Signal(Q); signal(S); Giả sử rằng P0 thực thi wait(S) và sau đó P1 thực thi wait(Q). Khi P0 thực thi wait(Q), nó phải chờ cho đến khi P1 thực thi signal(Q). Tương tự, khi P1 thực thi wait(S), nó phải chờ cho tới khi P0 thực thi signal(S). Vì các thao tác signal này không thể được thực thi nên P0 và P1 bị khoá chết. Chúng ta nói rằng một tập hợp các quá trình trong trạng thái khoá chết khi mọi quá trình trong tập hợp đang chờ một sự kiện được gây ra chỉ bởi một quá trình khác trong tập hợp. Những sự kiện mà chúng ta quan tâm chủ yếu ở đây là việc chiếm tài nguyên và giải phóng tài nguyên. Tuy nhiên, các loại sự kiện khác cũng có thể dẫn đến việc khoá chết. Chúng ta sẽ xem trong chương VI. Trong chương đó, chúng ta sẽ mô tả các cơ chế khác nhau để giải quyết vấn đề khoá chết. Một vấn đề khoá chết liên quan tới khoá chết là nghẽn hay đói tài nguyên không hạn định (indefinite blocking or starvation), ở đó các quá trình chờ đợi không hạn định trong semaphore. Nghẽn không hạn định có thể xảy ra nếu chúng ta thêm vào và lấy ra các quá trình từ danh sách được nối kết với một semaphore trong thứ tự vào sau ra trước (LIFO). Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 95
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 .V.2.1.4 Semaphore nhị phân Xây dựng semaphore được mô tả trong phần trước được gọi là semaphore đếm (counting semaphore) vì giá trị nguyên có thể trãi dài một phạm vi không giới hạn. Một semaphore nhị phân (binary semaphore) là một semaphore với một giá trị nguyên mà trải dài từ 0 và 1. Semaphore nhị phân có thể đơn giản hơn trong cài đặt so với semaphore đếm và phụ thuộc vào kiến trúc phần cứng nằm bên dưới. Chúng sẽ hiển thị cách một semaphore đếm có thể được cài đặt sử dụng semaphore nhị phân dưới đây: Giả sử S là một semaphore đếm. Để cài đặt nó trong dạng semaphore nhị phân chúng ta cần các cấu trúc dữ liệu như sau: Binary-semaphore S1, S2; int C; Khởi tạo S1 = 1, S2 = 0 và giá trị nguyên C được đặt tới giá trị khởi tạo của semaphore đếm S. Thao tác wait trên semaphore đếm S có thể được cài đặt như sau: wait(S); C--; If (C
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 } . . . procedure Pn (…){ … } { mã khởi tạo } } Hình 0-14 Cú pháp của monỉtor Biểu diễn kiểu monitor không thể được dùng trực tiếp bởi các quá trình khác nhau. Do đó, một thủ tục được định nghĩa bên trong một monitor chỉ có thể truy xuất những biến được khai báo cục bộ bên trong monitor đó và các tham số chính thức của nó. Tương tự, những biến cục bộ của monitor có thể được truy xuất chỉ bởi những thủ tục cục bộ. Xây dựng monitor đảm bảo rằng chỉ một quá trình tại một thời điểm có thể được kích hoạt trong monitor. Do đó, người lập trình không cần viết mã ràng buộc đồng bộ hoá như hình V-15 dưới đây: Hình 0-15 Hình ảnh dưới dạng biểu đồ của monitor Tuy nhiên, xây dựng monitor như được định nghĩa là không đủ mạnh để mô hình hoá các cơ chế đồng bộ. Cho mục đích này, chúng ta cần định nghĩa các cơ chế đồng bộ hoá bổ sung. Những cơ chế này được cung cấp bởi construct condition. Người lập trình có thể định nghĩa một hay nhiều biến của kiểu condition: condition x, y; Chỉ những thao tác có thể gọi lên trên các biến điều kiện là wait và signal. Thao tác Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 97
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 x.wait(); có nghĩa là quá trình gọi trên thao tác này được tạm dừng cho đến khi quá trình khác gọi x.signal(); thao tác x.signal() thực thi tiếp một cách chính xác một quá trình tạm dừng. Nếu không có quá trình tạm dừng thì thao tác signal không bị ảnh hưởng gì cả; nghĩa là trạng thái x như thể thao tác chưa bao giờ được thực thi (như hình V.-16). Ngược lại, với thao tác signal được gán cùng với semaphores luôn ảnh hưởng tới trạng thái của semaphore. Bây giờ giả sử rằng, khi thao tác x.signal() được gọi bởi một quá trình P thì có một quá trình Q gán với biến điều kiện x bị tạm dừng. Rõ ràng, nếu quá trình Q được phép thực thi tiếp thì quá trình P phải dừng. Nếu không thì cả hai quá trình P và Q hoạt động cùng một lúc trong monitor. Tuy nhiên, về khái niệm hai quá trình có thể tiếp tục việc thực thi của chúng. Hai khả năng có thể xảy ra: P chờ cho đến khi Q rời khỏi monitor hoặc chờ điều kiện khác. Q chờ cho đến khi P rời monitor hoặc chờ điều kiện khác. Hình 0-16 Monitor với các biến điều kiện Có các luận cứ hợp lý trong việc chấp nhận khả năng 1 hay 2. Vì P đã thực thi trong monitor rồi, nên chọn khả năng 2 có vẻ hợp lý hơn. Tuy nhiên, nếu chúng ta cho phép quá trình P tiếp tục, biến điều kiện “luận lý” mà Q đang chờ có thể không còn quản lý thời gian Q được tiếp tục. Chọn khả năng 1 được tán thành bởi Hoare vì tham số đầu tiên của nó chuyển trực tiếp tới các qui tắc chứng minh đơn giản hơn. Thoả hiệp giữa hai khả năng này được chấp nhận trong ngôn ngữ đồng hành C. Khi quá trình P thực thi thao tác signal thì quá trình Q lập tức được tiếp tục. Mô hình này không mạnh hơn mô hình của Hoare vì một quá trình không thể báo hiệu nhiều lần trong một lời gọi thủ tục đơn. Bây giờ chúng ta xem xét cài đặt cơ chế monitor dùng semaphores. Đối với mỗi monitor, một biến semaphore mutex (được khởi tạo 1) được cung cấp. Một quá Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 98
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 trình phải thực thi wait(mutex) trước khi đi vào monitor và phải thực thi signal(mutex) sau khi rời monitor. Vì quá trình đang báo hiệu phải chờ cho đến khi quá trình được bắt đầu lại rời hay chờ, một biến semaphore bổ sung next được giới thiệu, được khởi tạo 0 trên quá trình báo hiệu có thể tự tạm dừng. Một biến số nguyên next_count cũng sẽ được cung cấp để đếm số lượng quá trình bị tạm dừng trên next. Do đó, mỗi thủ tục bên ngoài F sẽ được thay thế bởi wait(mutex); ... thân của F if (next_count > 0) signal(next); else signal(mutex); Loại trừ hỗ tương trong monitor được đảm bảo. Bây giờ chúng ta mô tả các biến điều kiện được cài đặt như thế nào. Đối với mỗi biến điều kiện x, chúng ta giới thiệu một biến semaphore x_sem và biến số nguyên x_count, cả hai được khởi tạo tới 0. Thao tác x.wait có thể được cài đặt như sau: x_count++; if ( next_count > 0) signal(next); else signal(mutex); wait(x_sem); x_count--; Thao tác x.signal() có thể được cài đặt như sau: if ( x_count > 0){ next_count++; signal(x_sem); wait(next); next_count--; } Cài đặt này có thể áp dụng để định nghĩa của monitor được cho bởi cả hai Hoare và Brinch Hansen. Tuy nhiên, trong một số trường hợp tính tổng quát của việc cài đặt là không cần thiết và yêu cầu có một cải tiến hiệu quả hơn. Bây giờ chúng ta sẽ trở lại chủ đề thứ tự bắt đầu lại của quá trình trong monitor. Nếu nhiều quá trình bị trì hoãn trên biến điều kiện x và thao tác x.signal được thực thi bởi một vài quá trình thì thứ tự các quá trình bị trì hoãn được thực thi trở lại như thế nào? Một giải pháp đơn giản là dùng thứ tự FCFS vì thế quá trình chờ lâu nhất sẽ được thực thi tiếp trước. Tuy nhiên, trong nhiều trường hợp, cơ chế định thời biểu như thế là không đủ. Cho mục đích này cấu trúc conditional-wait có thể được dùng; nó có dạng x.wait(c); ở đây c là một biểu thức số nguyên được định giá khi thao tác wait được thực thi. Giá trị c, được gọi là số ưu tiên, được lưu với tên quá trình được tạm dừng. Khi x.signal được thực thi, quá trình với số ưu tiên nhỏ nhất được thực thi tiếp. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 99
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Để hiển thị cơ chế mới này, chúng ta xem xét monitor được hiển thị như hình dưới đây, điều khiển việc cấp phát của một tài nguyên đơn giữa các quá trình cạnh tranh. Mỗi quá trình khi yêu cầu cấp phát tài nguyên của nó, xác định thời gian tối đa nó hoạch định để sử dụng tài nguyên. Monitor cấp phát tài nguyên tới quá trình có yêu cầu thời gian cấp phát ngắn nhất. Monitor ResourceAllocation { boolean busy; condition x; void acquire(int time){ if (busy) x.wait(time); busy = true; } void release(){ busy = false; x.signal(); } void init(){ busy = false; } } Hình 0-17 Một monitor cấp phát tới một tài nguyên Một quá trình cần truy xuất tài nguyên phải chú ý thứ tự sau: R.acquire(t); … truy xuất tài nguyên ... R.release(); ở đây R là thể hiện của kiểu ResourceAllocation. Tuy nhiên, khái niệm monitor không đảm bảo rằng các thứ tự truy xuất trước sẽ được chú ý. Đặc biệt, • Một quá trình có thể truy xuất tài nguyên mà không đạt được quyền truy xuất trước đó. • Một quá trình sẽ không bao giờ giải phóng tài nguyên một khi nó được gán truy xuất tới tài nguyên đó. • Một quá trình có thể cố gắng giải phóng tài nguyên mà nó không bao giờ yêu cầu. • Một quá trình có thể yêu cầu cùng tài nguyên hai lần (không giải phóng tài nguyên đó trong lần đầu) Việc sử dụng monitor cũng gặp cùng những khó khăn như xây dựng miền tương trục. Trong phần trước, chúng ta lo lắng về việc sử dụng đúng semaphore. Bây giờ, chúng ta lo lắng về việc sử dụng đúng các thao tác được định nghĩa của người lập trình cấp cao mà các trình biên dịch không còn hỗ trợ chúng ta. Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 100
- Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 Một giải pháp có thể đối với vấn đề trên là chứa các thao tác truy xuất tài nguyên trong monitor ResourceAllocation. Tuy nhiên, giải pháp này sẽ dẫn đến việc định thời được thực hiện dựa theo giải thuật định thời monitor được xây dựng sẳn hơn là được viết bởi người lập trình. Để đảm bảo rằng các quá trình chú ý đến thứ tự hợp lý, chúng ta phải xem xét kỹ tất cả chương trình thực hiện việc dùng monitor ResourceAllocation và những tài nguyên được quản lý của chúng. Có hai điều kiện mà chúng ta phải kiểm tra để thiết lập tính đúng đắn của hệ thống. Đầu tiên, các quá trình người dùng phải luôn luôn thực hiện các lời gọi của chúng trên monitor trong thứ tự đúng. Thứ hai, chúng ta phải đảm bảo rằng một quá trình không hợp tác không đơn giản bỏ qua cổng (gateway) loại trừ hỗ tương được cung cấp bởi monitor và cố gắng truy xuất trực tiếp tài nguyên được chia sẻ mà không sử dụng giao thức truy xuất. Chỉ nếu hai điều kiện này có thể được đảm bảo có thể chúng ta đảm bảo rằng không có lỗi ràng buộc thời gian nào xảy ra và giải thuật định thời sẽ không bị thất bại. Mặc dù việc xem xét này có thể cho hệ thống nhỏ, tĩnh nhưng nó không phù hợp cho một hệ thống lớn hay động. Vấn đề kiểm soát truy xuất có thể được giải quyết chỉ bởi một cơ chế bổ sung khác. VI Các bài toán đồng bộ hoá nguyên thuỷ Trong phần này, chúng ta trình bày một số bài toán đồng bộ hoá như những thí dụ về sự phân cấp lớn các vấn đề điều khiển đồng hành. Các vấn đề này được dùng cho việc kiểm tra mọi cơ chế đồng bộ hoá được đề nghị gần đây. Semaphore được dùng cho việc đồng bộ hoá trong các giải pháp dưới đây. VI.1 Bài toán người sản xuất-người tiêu thụ Bài toán người sản xuất-người tiêu thụ (Producer-Consumer) thường được dùng để hiển thị sức mạnh của các hàm cơ sở đồng bộ hoá. Hai quá trình cùng chia sẻ một vùng đệm có kích thước giới hạn n. Biến semaphore mutex cung cấp sự loại trừ hỗ tương để truy xuất vùng đệm và được khởi tạo với giá trị 1. Các biến semaphore empty và full đếm số khe trống và đầy tương ứng. Biến semaphore empty được khởi tạo tới giá trị n; biến semaphore full được khởi tạo tới giá trị 0. Mã cho người quá trình sản xuất được hiển thị trong hình V.-18: do{ … sản xuất sản phẩm trong nextp … wait(empty); wait(mutex); … thêm nextp tới vùng đệm … signal(mutex); signal(full); } while (1); Hình 0-18 Cấu trúc của quá trình người sản xuất Mã cho quá trình người tiêu thụ được hiển thị trong hình dưới đây: Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 101
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Chương 7: Đồng bộ hóa tiến trình
55 p |
220 |
62
-
Giáo Trình Hệ Điều Hành – Đồng bộ hóa quá trình
24 p |
155 |
57
-
Bài giảng Hệ điều hành - Chương 4: Đồng bộ hóa tiến trình
85 p |
155 |
56
-
Giáo Trình Hệ Điều Hành - Chương 5: ĐỒNG BỘ HOÁ QUÁ TRÌNH
24 p |
111 |
45
-
Đồng bộ hóa tiến trình
10 p |
139 |
30
-
Chương 5: Đồng bộ hóa tiến trình
0 p |
44 |
16
-
Bài giảng Bài ôn tập: Đồng bộ hóa tiến trình
29 p |
32 |
9
-
Bài giảng Nguyên lý hệ điều hành - Chương 2: Tiến trình
54 p |
26 |
9
-
Bài giảng Hệ điều hành: Chương 5 - Phan Xuân Huy
235 p |
17 |
5
-
Bài giảng Hệ điều hành (Operating Systems) - Hà Lê Hoài Trung
322 p |
27 |
5
-
Bài giảng Hệ điều hành nâng cao - Chapter 6: Process Synchronization
72 p |
40 |
4
-
Bài giảng Nguyên lý hệ điều hành: Chương 2 - ĐH Bách khoa Đà Nẵng
54 p |
20 |
3
-
Bài giảng Nguyên lý hệ điều hành (Bài giảng tuần 4) - Nguyễn Hải Châu
10 p |
18 |
3
-
Bài giảng Hệ điều hành: Chương 5 - Trần Công Án (ĐH Cần Thơ)
56 p |
10 |
2
-
.Cấu hình Nokia E71 đồng bộ hóa với Exchange Server 2007 (Phần 2)
8 p |
21 |
1
-
.Cấu hình Nokia E71 đồng bộ hóa với Exchange Server 2007 (Phần 1)
8 p |
25 |
1
-
Bài giảng Hệ điều hành - Chương 5: Đồng bộ hóa tiến trình
88 p |
8 |
1

Server: Apache/2.2.31 (CentOS)

Set-Cookie: TLDEVNamespace=ommkh9n7rli0a55d5f7oq8hai7; path=/; domain=.tailieu.vn; HttpOnly


text:
Đưa số liệu vào dạng thức vật lý mang qui luật Pythagore
Chia sẻ: Pt1506 Pt1506 | Ngày: | Loại File: PDF | Số trang:3
103
lượt xem 12
download
lượt xem 12
download
Đưa số liệu vào dạng thức vật lý mang qui luật Pythagore
Mô tả tài liệu
Download Vui lòng tải xuống để xem tài liệu đầy đủ
Trong quá trình giảng dạy Vật lý, chúng tôi nhận thấy có rất nhiều biểu thức tuân theo qui luật Pythagore. Và trong tài liệu này chúng tôi xin liên hệ cụ thể một số dạng thức sau đây.
Chủ đề:
Bình luận(0) Đăng nhập để gửi bình luận!
CÓ THỂ BẠN MUỐN DOWNLOAD

markdown:
# Đưa số liệu vào dạng thức vật lý mang qui luật Pythagore
Chia sẻ: Pt1506 Pt1506 | Ngày: | Loại File: PDF | Số trang:3
103
lượt xem 12
download
lượt xem 12
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20090317/pt1506/80x100/6865_dua_so_lieu_vao_dang_thuc.jpg)
##
Đưa số liệu vào dạng thức vật lý mang qui luật Pythagore
Mô tả tài liệu
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Trong quá trình giảng dạy Vật lý, chúng tôi nhận thấy có rất nhiều biểu thức tuân theo qui luật Pythagore. Và trong tài liệu này chúng tôi xin liên hệ cụ thể một số dạng thức sau đây.
Chủ đề:
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
CÓ THỂ BẠN MUỐN DOWNLOAD

WARC-Type: response

Content-Type: application/http; msgtype=response

WARC-Identified-Payload-Type: application/xhtml+xml

Connection: close

Pragma: no-cache

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Set-Cookie: TLDEVNamespace=1041tuini4vl99qveeq8dqqpv5; path=/; domain=.tailieu.vn; HttpOnly

Vary: Accept-Encoding

Content-Type: text/html; charset=UTF-8


text:
Đừng xem nhẹ bộ máy kế toán doanh nghiệp
Chia sẻ: Nguyễn Thanh Triều | Ngày: | Loại File: PDF | Số trang:3
lượt xem 67
download
Đừng xem nhẹ bộ máy kế toán doanh nghiệp
Đừng xem nhẹ bộ máy kế toán doanh nghiệp Nhiều hãng lớn của châu Âu như Orcale, Vodaphone đã quy định những nhà quản lý nếu chư¬a am hiểu về kế toán thì phải bổ sung kiến thức chuyên môn bằng cách tham dự các khóa học ngắn hạn do trư¬ờng đại học hoặc trung học kinh tế tổ chức. Thời gian học khoáng từ hai đến sáu tháng, sau đó có thể học tiếp lớp nâng cao hoặc tham khảo sách chuyên ngành. Tai các công ty của Mỹ, giờ đây người ta coi rằng nhà quản lý doanh nghiệp hiểu...
Bình luận(0) Đăng nhập để gửi bình luận!
CÓ THỂ BẠN MUỐN DOWNLOAD

markdown:
# Đừng xem nhẹ bộ máy kế toán doanh nghiệp
Chia sẻ: Nguyễn Thanh Triều | Ngày: | Loại File: PDF | Số trang:3
lượt xem 67
download
![](http://image1.tailieu.vn/document/thumbnail/2009/20091229/thanh_trieu/80x100/dung_xem_nhe_bo_may_ke_toan_doanh_nghiep_9188.jpg)
##
Đừng xem nhẹ bộ máy kế toán doanh nghiệp
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static1.tailieu.vn/b2013az/templates/version1/default/images/down16x21.png)
Đừng xem nhẹ bộ máy kế toán doanh nghiệp Nhiều hãng lớn của châu Âu như Orcale, Vodaphone đã quy định những nhà quản lý nếu chư¬a am hiểu về kế toán thì phải bổ sung kiến thức chuyên môn bằng cách tham dự các khóa học ngắn hạn do trư¬ờng đại học hoặc trung học kinh tế tổ chức. Thời gian học khoáng từ hai đến sáu tháng, sau đó có thể học tiếp lớp nâng cao hoặc tham khảo sách chuyên ngành. Tai các công ty của Mỹ, giờ đây người ta coi rằng nhà quản lý doanh nghiệp hiểu...
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
CÓ THỂ BẠN MUỐN DOWNLOAD

Set-Cookie: TLDEVNamespace=4ef28becaorl7pbppkk6oj5j22; path=/; domain=.tailieu.vn; HttpOnly