Wikipedia

Đèn báo (lập trình)

Trong khoa học máy tính, đèn báo là một biến được bảo vệ hoặc một kiểu dữ liệu trừu tượng tạo ra sự trừu tượng hoá đơn giản nhưng hữu dụng để kiểm soát truy cập của nhiều tiến trình đến một tài nguyên chung trong môi trường lập trình song song.

Một cách nhìn về đèn báo là một bản ghi có bao nhiêu đơn vị của một tài nguyên có thể sử dụng, gắn với các tác vụ điều chỉnh bản ghi đó một cách an toàn (nghĩa là không tạo ra race condition) khi yêu cầu hoặc giải phóng các đơn vị và đợi đến khi một đơn vị rảnh rỗi nếu cần. Đèn báo là một công cụ hữu ích để chống race condition và khoá chết, tuy nhiên việc sử dụng nó không đảm bảo rằng chương trình không gặp phải các vấn đề trên. Đèn báo cho phép một số lượng tuỳ ý tài nguyên gọi là đèn báo đếm (counting semaphore) trong khi đèn báo bị giới hạn trong giá trị 0 và 1 được gọi là đèn báo nhị phân (binary semaphores).

Khái niệm đèn báo được phát minh bởi nhà nghiên cứu người Hà Lan Edsger Dijkstra,[1] and the concept has found widespread use in a variety of operating systems.

Ý nghĩa và cài đặt sửa

Đèn báo đếm được trang bị hai thao tác, ký hiệu là V và P. Thao tác V tăng đèn báo S và thao tác P giảm nó. Ý nghĩa của chúng được giải thích bên dưới. Ngoặc vuông chỉ ra các thao tác nguyên tử, nghĩa là các thao tác không thể chia nhỏ dưới góc nhìn của các tiến trình khác. 

function V(semaphore S):
Atomically increment S
[S ← S + 1]

function P(semaphore S):
repeat:
Between repetitions of the loop other processes may operate on the semaphore
[if S > 0:
Atomically decrement S - note that S cannot become negative
S ← S - 1
break]

Giá trị của đèn báo S là số đơn vị của tài nguyên còn rỗi. Thao tác P chờ đợi tích cực hoặc ngủ cho đến khi tài nguyên được bảo vệ trở nên rảnh rỗi, khi đó nó ngay lập tức yêu cầu. Thao tác V ngược lại: làm cho tài nguyên rảnh rỗi trở lại sau khi một tiến trình đã sử dụng xong.

Ví dụ: Bài toán người sản xuất/người tiêu dùng sửa

Cho emptyCount và fullCount là các đèn báo đém, và emptyCount được khởi tạo bằng N trong khi fullCount bằng 0, người sản xuất thực hiện lặp lại công việc sau: 

produce:
P(emptyCount)
putItemIntoQueue(item)
V(fullCount)

Người sử dụng lặp đi lặp lại công việc sau: 

consume:
P(fullCount)
item ← getItemFromQueue()
V(emptyCount)

Lưu ý rằng thứ tự các phép toán là quan trọng. Ví dụ, nếu người sản xuất đặt hàng vào hàng đợi sau khi tăng fullCount, người sử dụng có thể cố lấy hàng trước khi nó được ghi. Nếu người sản xuất đặt hàng vào trước khi giảm emptyCount, nó có thể vượt quá giới hạn của hàng đợi.

Nguồn gốc tên hàm sửa

Các tên chuẩn P và V xuất phát từ chữ cái đầu của từ tiếng Hà Lan. V là viết tắt của verhogen ("tăng lên"). Có nhiều giải thích cho P, bao gồm proberen - "kiểm tra"[2], passeer - "vượt qua", probeer - "thử", and pakken for "bắt". Tuy nhiên, Dijkstra viết rằng ông định sử dụng từ ghép prolaag[3], viết tắt cho probeer te verlagen, nghĩa là "thử giảm",[4]

Trong ALGOL 68, nhân Linux,[5] và một số sách giáo khoa tiếng Anh, các thao tác P and V thường được gọi lần lượt là down và up. Trong thực hành, chúng thường được gọi là wait và signal, acquire và release (thư viên chuẩn của Java sử dụng cách này[6]), hoặc pend và post. Một vài cuốn sách sử dụng procure và vacate để phù hợp với viết tắt ban đầu bằng tiếng Hà Lan.

Đèn báo và mutex sửa

Mutex về căn bản giống như đèn báo nhị phân và đôi khi sử dụng cùng một cách cài đặt. Tuy nhiên khái niệm "mutex" thường được sử dụng để mô tả một cấu trúc ngăn cản hai tiến trình cũng thực hiện một đoạn mã hoặc truy cập một dữ liệu cùng lúc. Khái niệm đèn báo nhị phân thường mô tả cấu trúc dùng để hạn chế truy cập vào một tài nguyên.

Trong nhiều trường hợp một mutex có khái niệm "chủ": duy nhất tiến trình khoá mutex được quyền mở nó. Ngược lại đèn báo nói chung không đặt ra ràng buộc này, điều mà ví dụ người sản xuất - người tiêu dùng ở trên dựa vào.

Sử dụng sửa

Đèn báo được nhiều hệ điều hành cung cấp như là một mẫu đồng bộ hoá và được sử dụng ở nhiều nơi. Tuy nhiên xu hướng phát triển các ngôn ngữ lập trình là các cách đồng bộ hoá có cấu trúc hơn, như là monitor. Những sự trừu tượng hoá này thường chứa đèn báo hoặc mutex bên trong những không thể hiện giao diện của đèn báo ra đối với lập trình viên. Xu hướng này được khuyến khích mở những vấn đề nghiêm trọng và khó chẩn đoán khi đèn báo bị sử dụng không đúng cách, một nguy cơ được giảm thiểu rất nhiều khi sự đồng bộ hoá được gắn chặt với tài nguyên mà nó điều khiển một cách tự động bởi ngôn ngữ thay vì bằng tay bởi người lập trình.

Xem thêm sửa

Ghi chú sửa

  1. ^ “E.W.Dijkstra Archive: Cooperating sequential processes (EWD 123)”.
  2. ^ Silberschatz, Galvin & Gagne 2008, tr. 234
  3. ^ http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF
  4. ^ http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD51.html MULTIPROGAMMERING EN DE X8 from the E.W. Dijkstra Archive (in Tiếng Hà Lan)
  5. ^ “Kernel hacking howto on linuxgrill.com”. Bản gốc lưu trữ ngày 28 tháng 5 năm 2010. Truy cập ngày 25 tháng 5 năm 2011.
  6. ^ java.util.concurrent.Semaphore
  • Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (ấn bản 8), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5

Liên kết ngoài sửa

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Đèn_báo_(lập_trình)&oldid=69468702”