Chi tiết bài học Giải pháp semaphore

Dùng spinlock và mutex lock, ta cũng có thể áp dụng semaphore để bảo vệ dữ liệu trong critical resource. Semaphore không chỉ là một kỹ thuật đồng bộ tài nguyên, mà còn được biết đến là một kỹ thuật đồng bộ hoạt động.

Semaphore là một kỹ thuật đồng bộ tài nguyên và bài học này chỉ trình bày về nó do phạm vi của khóa học.

Bạn Đang Xem: Chi tiết bài học Giải pháp semaphore

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.

Semaphore tương tự như một bộ các chìa khóa dự phòng khi được dùng với mục đích đồng bộ tài nguyên. Thread đó được phép truy cập vào tài nguyên nếu lấy được một chiếc chìa khóa. 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?

Sử dụng cấu trúc semaphore, hạt nhân Linux đại diện cho một semaphore bằng hai thành phần chính là biến đếm và danh sách chờ đợi.

Struct semaphore { raw_spinlock_t lock; unsigned int count; struct list_head wait_list;};/* Do cấu trúc semaphore cũng bị nhiều thread truy cập đồng thời,nên semaphore cũng được xem là một critical resource. Biến @lock làmột spinlock bảo vệ @count và @wait_list trong cấu trúc semaphore. *//* Biến count vừa thể hiện trạng thái của semaphore, vừa thể hiệntrạng thái của critical resource.> 0: semaphore đang ở trạng thái AVAILABLE,còn critical resource đang ở trạng thái READY.Count cũng thể hiện còn bao nhiêu thread nữa được phépsử dụng critical resource.= 0: semaphore đang ở trạng thái UNAVAILABLE,còn critical resource đang ở trạng thái BUSY. */

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 cờ tín hiệu chuyển sang trạng thái KHÔNG SẴN CÓ, nếu một luồng gọi hàm xuống, thì biến đếm bị giảm đi 1 đơn vị (nếu hiệu bằng 0 thì đếm đang lớn hơn 0). Sau đó, luồng bắt đầu sử dụng tài nguyên quan trọng. CPU bắt đầu thực thi phần mở rộng quan trọng của luồng (nói theo ngôn ngữ của hạt nhân Linux), tức là cờ tín hiệu đang ở trạng thái SẴN CÓ.

Semaphore sử dụng cơ chế chờ ngủ, do đó khi count đạt đến 0, semaphore sẽ ở trạng thái KHÔNG CÓ SẴN, nếu một luồng gọi hàm down, CPU sẽ tạm dừng luồng này và chuyển sang thực thi luồng khác (theo ngôn ngữ của CPU). Hay nói theo ngôn ngữ của Linux kernel, luồng đó sẽ được thêm vào hàng đợi wait_list và đi vào trạng thái ngủ, sau đó Linux kernel sẽ lập lịch cho luồng khác.

Khi hàng chờ vẫn còn ít nhất một luồng đang phải chờ, nếu một luồng A gọi hàm tăng, thì CPU sẽ chuyển sang thực thi luồng B đang ở vị trí đầu tiên trong danh sách chờ hàng (nói theo ngôn ngữ của CPU). Sau đó, hạt nhân Linux đánh thức luồng B dậy, luồng B bắt đầu sử dụng tài nguyên quan trọng.

Khi một luồng gọi hàm up, nếu danh sách chờ không còn luồng nào chờ đợi, thì biến đếm được tăng thêm 1 đơn vị, tức là semaphore chuyển sang trạng thái CÓ SẴN.

Semaphore bảo vệ critical resource như thế nào?

Xem Thêm : Mọi Người Cho Em Hỏi ” Bút Lục Là Gì ? Nghĩa Của Từ Bút Lục Trong Tiếng Việt

Đầu vào: Để tránh tình trạng cạnh tranh giữa các luồng, loại semaphore này thường được sử dụng để đồng bộ hóa dữ liệu, vì hoạt động của semaphore nhị phân tương tự như khóa mutex. Trong quá trình lập trình driver thiết bị, chúng ta đặt hàm giảm và tăng lần lượt trước và sau khu vực quan trọng của mỗi luồng.

Xét 2 trường hợp, hệ thống có luồng kernel A và B được thực thi riêng biệt trên 2 lõi CPU0 và CPU1. Cả 2 luồng đều có nhu cầu sử dụng tài nguyên quan trọng R và tài nguyên R được bảo vệ bằng rào cản nhị phân S.

Bảo vệ được tài nguyên quan trọng và tránh xảy ra tình huống đua điều kiện. Đua điều kiện và bảo vệ tài nguyên quan trọng được đảm bảo. Quyền của một luồng có thể chỉ định duy nhất và tối đa, không bị can thiệp tại bất kỳ điểm thời gian nào, như đã được nêu ở Input.

Ví dụ: Để định nghĩa và khởi tạo giá trị cho binary semaphore ngay từ khi biên dịch (compile time), chúng ta có thể sử dụng macro DEFINE_SEMAPHORE.

DEFINE_SEMAPHORE(my_semaphore); //khởi tạo trạng thái AVAILABLE cho my_semaphore.

Trong hàm khởi tạo của driver, ta thường gọi hàm sema_init để thiết lập giá trị cho semaphore. Vì vậy, 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). Ví dụ, ta sẽ sử dụng hàm sema_init. Tuy nhiên,

Cấu trúc my_struct { cấu trúc my_semaphore;} my_struct_t;int khởi_tạo_hàm_điều_khien() { khởi_tạo_sema(&my_struct_t.My_semaphore, 1); …} /* Khi ta muốn bảo vệ dữ liệu trong cấu trúc my_struct, ta sẽ nhúng biến cấu trúc kiểu semaphore vào trong cấu trúc my_struct. Biến cấu trúc my_struct_t đại diện cho tài nguyên quan trọng, còn my_semaphore đại diện cho tập hợp các khóa bảo vệ tài nguyên quan trọng. */

Có thể dùng hàm down và up tuần tự trước và sau phần quan trọng của luồng, sau khi đã khai báo và khởi tạo semaphore, để tránh xảy ra tình trạng cạnh tranh.

Down(&my_semaphore); /* critical section của kernel thread */ up(&my_semaphore);.

Đôi khi, ta có thể sử dụng hàm down_interruptible thay cho hàm down. Cách sử dụng như sau:.

Nếu nắm được semaphore, hàm down_interruptible sẽ trả về 0. Đối với trường hợp tiến trình P yêu cầu đọc/ghi dữ liệu trong tài nguyên quan trọng R, khi kernel thread T’ đang truy cập R, thread T sẽ bị tạm dừng tại hàm down_interruptible. Nếu có một tín hiệu được tạo ra, ví dụ nhấn tổ hợp CTRL + C để hủy tiến trình P, thì hàm down_interruptible sẽ ngay lập tức trả về -EINTR mà không chặn thread T nữa. Điều này giúp hủy tiến trình P ngay lập tức mà không cần chờ thread T’ giải phóng semaphore. Nếu không nắm được semaphore, thread sẽ bị tạm dừng hoạt động. Khi sử dụng down_interruptible, thread sẽ nhận các tín hiệu trong quá trình chờ semaphore.

Ngoài ra, Linux kernel hỗ trợ hàm down_trylock.

Int down_trylock(struct semaphore *sem){ /* hàm: trylock */ /* chức năng: yêu cầu giữ semaphore. Nếu không thể giữ được, trả ngay về cho thread gọi hàm này. Thread gọi hàm này sẽ không chờ đợi semaphore nữa (non-blocking). */ /* Tham số đầu vào: *sem [IO]: là địa chỉ của vùng nhớ chứa cấu trúc semaphore. */ /* Giá trị trả về: Nếu giữ được semaphore, trả về 0. Nếu không giữ được semaphore (do thread khác đã giữ rồi), trả về 1. */}

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:.

Xem Thêm : Cách Nuôi Gà Chọi Chiến Chuẩn C1 – Mê Gà Chọi

Hôm nay, chúng ta tạo thư mục cho bài học như sau: Trong ví dụ này, chúng ta sẽ sử dụng kỹ thuật semaphore để cải thiện driver vchar trong bài hôm trước. Đầu tiên, chúng ta tạo thư mục cho bài học ngày hôm nay.

Cd /home/ubuntu/ldd/phan_6 cp -r bai_6_1 bai_6_5.

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 .

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.

Thời gian để hoàn thành bài toán mất nhiều thời gian hơn so với phương pháp spinlock và mutex lock, có thể thấy rằng, nếu sử dụng phương pháp semaphore. Sau khi 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 chính xác là 3,145,728. Bây giờ, ta nhập lệnh make để dịch lại vchar driver.

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.

Đèn báo gồm 2 thành phần chủ yếu là biến đếm và hàng đợi danh sách chờ. Biến đếm giúp điều khiển số lượng luồng còn lại được phép truy cập vào tài nguyên quan trọng. Còn hàng đợi danh sách chờ chứa danh sách các luồng đang phải chờ đợi trước khi có thể truy cập tài nguyên quan trọng. Đèn báo là một cấu trúc, vừa được sử dụng để đồng bộ tài nguyên, vừa được sử dụng để đồng bộ hoạt động.

Semaphore bao gồm 2 loại là semaphore nhị phân và semaphore đếm. Hoạt động của semaphore nhị phân tương tự như khóa mutex, vì vậy thường được sử dụng để tránh tình trạng cạnh tranh. Một luồng có thể giải phóng semaphore mà không cần chiếm giữ semaphore đó. Điểm khác biệt đáng chú ý so với khóa mutex là.

Nguồn: https://domainente.com
Danh mục: Chia sẻ