Giới thiệuNgoài spinlock và mutex lock, ta cũng có thể áp dụng kỹ thuật semaphore để bảo vệ dữ liệu trong critical resource. Không chỉ là một kỹ thuật đồng bộ tài nguyên, semaphore cũng được biết đến là một kỹ thuật đồng bộ hoạt động. Show Do phạm vi của khóa học, bài học này chỉ trình bày về semaphore với tư cách là một kỹ thuật đồng bộ tài nguyên:
Giới thiệu về semaphoreSemaphore là gì?Semaphore là một cấu trúc dữ liệu, được dùng để đồng bộ tài nguyên và đồng bộ hoạt động. Khi được dùng với mục đích đồng bộ tài nguyên, semaphore tương tự như một bộ các chìa khóa dự phòng. Nếu một thread lấy được một chiếc chìa khóa, thread đó được phép truy cập vào tài nguyên. Nhưng nếu không còn chiếc chìa khóa nào, thread đó phải đợi cho tới khi một thread khác trả lại chìa khóa dự phòng. Nhờ vậy, race condition sẽ bị ngăn chặn. Hình 1. Sử dụng semaphore để đồng bộ tài nguyên Semaphore có cấu tạo như thế nào?Semaphore gồm 2 thành phần chính: biến count và hàng đợi wait_list. Linux kernel sử dụng cấu trúc semaphore để biểu diễn một semaphore.
Căn cứ vào giá trị của biến count, semaphore được chia làm 2 loại là counting semaphore và binary semaphore.
Semaphore hoạt động ra sao?Hình 2. Sơ đồ biểu diễn các trạng thái hoạt của một semaphore Khi count đang lớn hơn 0, tức là semaphore đang ở trạng thái AVAILABLE, nếu một thread gọi hàm down, thì biến count bị giảm đi 1 đơn vị (nếu hiệu bằng 0 thì semaphore chuyển sang trạng thái UNAVAILABLE). Sau đó, CPU bắt đầu thực thi critical section của thread (nói theo ngôn ngữ của CPU), hay thread bắt đầu sử dụng critical resource (nói theo ngôn ngữ của Linux kernel). Khi count đang bằng 0, tức là semaphore đang ở trạng thái UNAVAILABLE, nếu một thread gọi hàm down, thì CPU tạm dừng thực thi thread này rồi chuyển sang thực thi thread khác (nói theo ngôn ngữ của CPU). Hay nói theo ngôn ngữ của Linux kernel, thread đó được thêm vào hàng đợi wait_list và đi ngủ, sau đó Linux kernel sẽ lập lịch cho thread khác. Do đó, ta nói rằng, semaphore áp dụng cơ chế sleep-waiting. Khi wait_list vẫn còn ít nhất một thread đang phải đợi, nếu một thread A gọi hàm up, thì CPU sẽ chuyển sang thực thi thread B nằm ở vị trí đầu tiên trong hàng đợi wait_list (nói theo ngôn ngữ của CPU). Hay nói theo ngôn ngữ của Linux kernel, Linux kernel đánh thức thread B dậy, sau đó thread B bắt đầu sử dụng critical resource. Khi wait_list không còn thread nào chờ đợi, nếu một thread gọi hàm up, thì biến count được tăng thêm 1 đơn vị, tức là semaphore chuyển sang trạng thái AVAILABLE. Semaphore bảo vệ critical resource như thế nào?Vì hoạt động của binary semaphore tương tự như mutex lock, nên loại semaphore này thường được sử dụng để đồng bộ dữ liệu, phòng tránh race condition. Trong khi lập trình device driver, ta đặt hàm down và up lần lượt vào trước và sau critical section của mỗi thread. Giả sử, hệ thống có kernel thread A và B được thực thi riêng biệt trên 2 lõi CPU0 và CPU1. Cả 2 thread đều có nhu cầu sử dụng critical resource R, và tài nguyên R được bảo vệ bằng binary semaphore S. Xét 2 trường hợp:
Như vậy, tại bất cứ thời điểm nào, tối đa chỉ có một thread được phép chiếm dụng binary semaphore, đồng nghĩa với việc, tối đa chỉ có một thread được phép sử dụng critical resource. Do đó, race condition sẽ không xảy ra và critical resource được bảo vệ. Sử dụng các semaphore kernel API trong lập trình device driverĐể khai báo và khởi tạo giá trị cho binary semaphore ngay từ lúc biên dịch (compile time), ta có thể sử dụng macro DEFINE_SEMAPHORE. Ví dụ:
Tuy nhiên, semaphore thường nằm trong một cấu trúc lớn hơn và được cấp phát bộ nhớ trong quá trình chạy (run time). Do đó, ta sẽ dùng hàm sema_init để khởi tạo giá trị cho semaphore. Ta thường gọi hàm sema_init trong hàm khởi tạo của driver. Ví dụ:
Sau khi đã khai báo và khởi tạo semaphore, ta có thể sử dụng cặp hàm down và up lần lượt vào trước và sau critical section của thread để ngăn không cho race condition xảy ra.
Đôi khi, ta có thể sử dụng hàm down_interruptible thay cho hàm down. Cách sử dụng như sau:
Ngoài ra, Linux kernel hỗ trợ hàm down_trylock.
Chú ý khi sử dụng semaphore Khi triển khai giải pháp này, ta cần chú ý mấy điểm sau:
Case studyTrong ví dụ này, chúng ta sẽ áp dụng kỹ thuật semaphore để cải thiện vchar driver trong bài hôm trước. Đầu tiên, ta tạo thư mục cho bài học ngày hôm nay như sau:
Bây giờ, ta tiến hành sửa file vchar_driver.c. Đầu tiên, để triển khai semaphore, ta cần tham chiếu tới thư viện <linux/semaphore.h>. Tiếp theo, ta thêm biến vchar_semaphore trong cấu trúc _vchar_drv. Semaphore này giúp bảo vệ dữ liệu trong biến critical_resource. Sau đó, trong hàm vchar_driver_init, ta khởi tạo semaphore này để tạo ra binary semaphore: Cuối cùng, ta thêm hàm down và up lần lượt vào trước vào sau vùng critical section. Bây giờ, ta gõ lệnh makeđể biên dịch lại vchar driver. Sau khi biên dịch thành công, ta thực hiện kiểm tra như hình 3 dưới đây và thấy rằng, kết quả cuối cùng của biến critical_resource đúng bằng 3,145,728. Tuy nhiên, có thể thấy rằng, nếu áp dụng kỹ thuật semaphore, thời gian để hoàn thành bài toán lâu hơn rất nhiều so với kỹ thuật spinlock và mutex lock. Hình 3. Sử dụng kỹ thuật binary semaphore giúp ngăn ngừa race condition trên biến critical_resource Kết luậnSemaphore là một cấu trúc, vừa dùng để đồng bộ tài nguyên, vừa dùng để đồng bộ hoạt động. Semaphore gồm 2 thành phần chính là biến count và hàng đợi wait_list. Biến count giúp kiểm soát số lượng thread còn lại được phép truy cập vào critical resource. Còn hàng đợi wait_list chứa danh sách các thread đang phải chờ đợi trước khi có thể truy cập critical resource. Semaphore gồm 2 loại là binary semaphore và counting semaphore. Hoạt động của binary semaphore tương tự như mutex lock, do đó thường được sử dụng để phòng tránh race condition. Điểm khác biệt nổi bật so với mutex lock đó là: một thread có thể giải phóng semaphore mặc dù thread đó chưa hề chiếm dụng semphore. |