Tìm hiểu phương pháp đồng bộ hóa tiến trình Semaphores

Tóm tắt nội dung tài liệu

1. Chương 7: Đồng bộ hóa tiến trình s 3.1. Giải pháp « busy waiting » q 3.1.1. Các giải pháp phần mềm q 3.1.2. Các giải pháp phần cứng s 3.2. Các giải pháp « SLEEP and WAKEUP » q 3.2.1. Semaphore q 3.2.2. Monitors q 3.2.3. Trao đổi thông điệp s 3.3. Các vấn đề đồng bộ hóa q 3.3.1. Vấn đề Người sản xuất – Người tiêu thụ [Producer-Consumer] q 3.3.2. Phần tự lực - mô hình Readers-Writers Nguyên lý hệ điều hành 1 Nguyễn Văn Huy – KTMT - 2008
2. Chương 7: Đồng bộ hóa tiến trình Mục tiêu của chương s Giới thiệu các giải pháp cụ thể để xử lý bài toán đồng bộ hoá. q Giải pháp « busy waiting » q Giải pháp « sleep and wakeup » Nguyên lý hệ điều hành 2 Nguyễn Văn Huy – KTMT - 2008
3. Chương 7: Đồng bộ hóa tiến trình Kiến thức sinh viên phải nắm dược sau chương này s Nhiệm vụ của việc đồng bộ hóa tiến trình. s Hiểu và áp dụng được các giải pháp đồng bộ, đặc biệt với các giải pháp “sleep and wakeup”. Nguyên lý hệ điều hành 3 Nguyễn Văn Huy – KTMT - 2008
4. Chương 7: Đồng bộ hóa tiến trình Đưa ra bài toán s Tại sao cần đồng bộ hóa tiến trình? s Đối tượng tác động? s Thuật ngữ miền găng? Nguyên lý hệ điều hành 4 Nguyễn Văn Huy – KTMT - 2008
5. Chương 7: Đồng bộ hóa tiến trình Bốn điều kiện phải thỏa mãn: s Không có hai tiến trình cùng ở trong miền găng. s Không có giả thiết nào đặt ra cho sự liên hệ về tốc độ của các tiến trình, cũng như về số lượng bộ xử lý trong hệ thống. s Một tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng. s Không có tiến trình nào phải chờ vô hạn để được vào miền găng Nguyên lý hệ điều hành 5 Nguyễn Văn Huy – KTMT - 2008
6. Chương 7: Đồng bộ hóa tiến trình 3.1. Giải pháp « busy waiting » s Các giải pháp phần mềm s Các giải pháp phần cứng Nguyên lý hệ điều hành 6 Nguyễn Văn Huy – KTMT - 2008
7. Chương 7: Đồng bộ hóa tiến trình 3.1.1. Các giải pháp phần mềm a] Sử dụng các biến cờ hiệu: s Tiếp cân: Các tiến trình chia sẻ một biến chung đóng vai trò lock , được khởi động=0. s Một tiến trình muốn vào miền găng trước tiên phải kiểm tra giá trị của biến lock. Nếu lock = 0, tiến trình đặt lock = 1 và đi vào miền găng. s Nếu lock đang nhận giá trị 1, tiến trình phải chờ bên ngoài miền găng cho đến khi lock có giá trị 0. Nguyên lý hệ điều hành 7 Nguyễn Văn Huy – KTMT - 2008
8. Chương 7: Đồng bộ hóa tiến trình 3.1.1. Các giải pháp phần mềm a] Sử dụng các biến cờ hiệu: s Cấu trúc của 1 tiến trình while [TRUE] { while [lock == 1]; // wait lock = 1; critical-section []; lock = 0; Noncritical-section [];} Nguyên lý hệ điều hành 8 Nguyễn Văn Huy – KTMT - 2008
9. Chương 7: Đồng bộ hóa tiến trình 3.1.1. Các giải pháp phần mềm Thảo luận về biện pháp sử dụng biến “Lock” s Có thể vi phạm điều kiện hai tiến trình cùng ở trong miền găng tại một thời điểm. s P1 s P2 while [TRUE] { while [TRUE] { while [lock == 1]; // wait while [lock == 1]; // wait lock = 1; lock = 1; critical-section []; critical-section []; lock = 0; lock = 0; Noncritical-section [];} Noncritical-section [];} Nguyên lý hệ điều hành 9 Nguyễn Văn Huy – KTMT - 2008
10. Chương 7: Đồng bộ hóa tiến trình 3.1.1. Các giải pháp phần mềm b] Sử dụng việc kiểm tra luân phiên s Tiếp cận : Đây là một giải pháp đề nghị cho hai tiến trình. s Hai tiến trình này sử dụng chung biến turn [phản ánh phiên tiến trình nào được vào miền găng], được khởi động với giá trị 0. Nếu turn = 0, chỉ có tiến trình A được vào miền găng. Nếu turn = 1, chỉ có tiến trình B được đi vào miền găng. Nguyên lý hệ điều hành 10 Nguyễn Văn Huy – KTMT - 2008
11. Chương 7: Đồng bộ hóa tiến trình 3.1.1. Các giải pháp phần mềm b] Sử dụng việc kiểm tra luân phiên Nguyên lý hệ điều hành 11 Nguyễn Văn Huy – KTMT - 2008
12. Chương 7: Đồng bộ hóa tiến trình Thảo luận về biện pháp kiểm tra luân phiên s Ngăn chặn được tình trạng hai tiến trình cùng vào miền găng. [?] s Có thể vi phạm điều kiện một tiến trình có thể bị ngăn chặn vào miền găng bởi một tiến trình khác không ở trong miền găng. [?] Nguyên lý hệ điều hành 12 Nguyễn Văn Huy – KTMT - 2008
13. Chương 7: Đồng bộ hóa tiến trình 3.1.1. Các giải pháp phần mềm c] Giải pháp của Peterson s Tiếp cận : Petson đưa ra một giải pháp kết hợp ý tưởng của cả hai giải pháp kể trên. Các tiến trình chia sẻ hai biến chung : s int turn; // đến phiên ai s int interesse[2]; // khởi động là FALSE Nguyên lý hệ điều hành 13 Nguyễn Văn Huy – KTMT - 2008
14. Chương 7: Đồng bộ hóa tiến trình 3.1.1. Các giải pháp phần mềm c] Giải pháp của Peterson while [TRUE] { int j = 1-i; // j là tiến trình còn lại interesse[i]= TRUE; turn = j; while [turn == j && interesse[j]==TRUE]; critical-section []; interesse[i] = FALSE; Noncritical-section [];}//Cấu trúc tiến trình Pi trong giải pháp Peterson Nguyên lý hệ điều hành 14 Nguyễn Văn Huy – KTMT - 2008
15. Chương 7: Đồng bộ hóa tiến trình Thảo luận về giải pháp của Peterson s Giải pháp này ngăn chặn được tình trạng mâu thuẫn truy xuất. s Vẫn vi phạm điều kiện một tiến trình ngoài miền “găng” ngăn cản tiến trình trong “găng” Nguyên lý hệ điều hành 15 Nguyễn Văn Huy – KTMT - 2008
16. Chương 7: Đồng bộ hóa tiến trình 3.1.2. Các giải pháp phần cứng a] Cấm ngắt s Tiếp cân: Cho phép tiến trình cấm tất cả các ngắt trước khi vào miền găng, và phục hồi ngắt khi ra khỏi miền găng. s Khi đó, ngắt đồng hồ cũng không xảy ra, do vậy hệ thống không thể tạm dừng hoạt động của tiến trình đang xử lý để cấp phát CPU cho tiến trình khác. Nguyên lý hệ điều hành 16 Nguyễn Văn Huy – KTMT - 2008
17. Chương 7: Đồng bộ hóa tiến trình Thảo luận về phương pháp cấm ngắt s Giải pháp này không được ưa chuộng vì rất thiếu thận trọng khi cho phép tiến trình người dùng được phép thực hiện lệnh cấm ngắt. s Nếu hệ thống có nhiều bộ xử lý, lệnh cấm ngắt chỉ có tác dụng trên bộ xử lý đang xử lý tiến trình, còn các tiến trình hoạt động trên các bộ xử lý khác vẫn có thể truy xuất đến miền găng ! s Có thể một tiến trình sẽ phải chờ vô hạn. Nguyên lý hệ điều hành 17 Nguyễn Văn Huy – KTMT - 2008
18. Chương 7: Đồng bộ hóa tiến trình 3.1.2. Các giải pháp phần cứng b] Chỉ thị TSL [Test-and-Set] s Tiếp cận: Nhiều máy tính cung cấp một chỉ thị đặc biệt cho phép kiểm tra và cập nhật nội dung một vùng nhớ trong một thao tác không thể phân chia, gọi là chỉ thị Test-and-Set Lock [TSL] và được định nghĩa như sau: Test-and-Setlock[boolean target] {Test-and-Setlock = target; target = TRUE;} Nguyên lý hệ điều hành 18 Nguyễn Văn Huy – KTMT - 2008
19. Chương 7: Đồng bộ hóa tiến trình 3.1.2. Các giải pháp phần cứng b] Chỉ thị TSL [Test-and-Set] while [TRUE] { while [Test-and-Setlock[lock]]; critical-section []; lock = FALSE; Noncritical-section [];// Cấu trúc một chương trình trong giải pháp TSL Nguyên lý hệ điều hành 19 Nguyễn Văn Huy – KTMT - 2008
20. Chương 7: Đồng bộ hóa tiến trình Thảo luận về TSL [Test-and-Set] s TSL giảm nhẹ công việc lập trình, nhưng lại không dễ dàng để cài đặt chỉ thị TSL sao cho được xử lý một cách không thể phân chia, nhất là trên máy với cấu hình nhiều bộ xử lý. s Vi phạm một số điều kiện… Nguyên lý hệ điều hành 20 Nguyễn Văn Huy – KTMT - 2008

Page 2

YOMEDIA

Mục tiêu của chương: Giới thiệu các giải pháp cụ thể để xử lý bài toán đồng bộ hoá. lGiải pháp « busy waiting ». lGiải pháp « sleep and wakeup ». Kiến thức sinh viên phải nắm dược sau chương này: Nhiệm vụ của việc đồng bộ hóa tiến trình. Hiểu và áp dụng được các giải pháp đồng bộ, đặc biệt với các giải pháp “sleep and wakeup”.

26-11-2010 841 68

Download

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.

TÌM HIỂU CÁC PHƯƠNG PHÁP ĐỒNG BỘ HOÁ TIẾN TRÌNH - VIẾT ỨNG DỤNG MINH HOẠ BÀI TOÁN BỮA ĂN TỐI CỦA CÁC TRIẾT GIA, SỬ DỤNG PHƯƠNG PHÁP SEMAPHORE

Bài toán “Bữa ăn tối của các triết gia” được đưa ra bởi Dijkstra là một bài toán kinh điển về đồng bộ hoá trong môi trường đa luồng và minh hoạ các kỹ thuật để giải quyết chúng.

• Phải đặt ra thuật toán sao cho khi một triết gia bị đói thì ông ta sẽ được ăn và đảm bảo không có triết gia nào bị chết đói.
• Thuật toán được đưa ra là thuật toán Semaphore.
• Ngôn ngữ thực hiện thuật toán: Java.