Hỏi đáp

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

Ngoài spinlock , 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.

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 chính là một kỹ thuật đồng bộ tài nguyên:

Bạn đang xem: Semaphore là gì

Giới thiệu semaphore là gì, có cấu tạo như thế nào, hoạt động ra sao, bảo vệ critical resource như thế nào?Sử dụng kỹ thuật semaphore trong lập trình device driver như thế nào?Cần chú ý các gì khi sử dụng kỹ thuật semaphore?

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

Semaphore là gì vậy?

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 cũng sẽ bị ngăn chặn.

rWblTvBGdHeRsX9_V5vN2LhDGVCnd_6RY3zn0J2qHdot16rg4buQEwYEWQAD-ePWucnZKaOXEvI2epCgxj5CgJp_J9B_xsfE3F5TK3HEV97qFgASXdFZL4uIn9IxjYjEZMPB5NPk

Tìm hiểu thêm: Mẹ đơn thân là gì mà nhiều phụ nữ đang lựa 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.

struct semaphore /* * 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. */ raw_spinlock_t lock; /* * Biến count vừa thể hiện trạng thái của semaphore, vừa thể hiện * trạ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ép * sử dụng critical resource. * = 0: semaphore đang ở trạng thái UNAVAILABLE, * còn critical resource đang ở trạng thái BUSY. */ unsigned int count; // wait_list chính là danh sách các thread đang chờ đợi để có đã được semaphore struct list_head wait_list; ;

Căn cứ vào giá trị của biến count, semaphore đã được chia làm 2 các loại chính là counting semaphore , binary semaphore.

Nếu giá trị cực đại của biến count lớn hơn 1, thì semaphore được gọi chính là counting semaphore. Giá trị cực đại của biến count thể hiện số lượng thread tối đa đã được phép sử dụng critical resource tại cùng một thời điểm.Nếu biến count chỉ có hai giá trị 0 , 1, thì semaphore được gọi là binary semaphore. Binary semaphore có một vài nét tương đồng với mutex lock.

Semaphore hoạt động ra sao?

SwEnQVMvhM2rHmCe2zXrRrqwlVK3NPzzhEd1hIf_hgArt1FwRDnbfJCB_QaswKBskPNSUl4MZkyPXAaGP3fb6OTHKAraIPcgfhNva4mpB2x4ySjlTz6YWsiNrf-jYz1dbfcu2q1Y

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 chỉ 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 là 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 cũng sẽ lập lịch cho thread khác. Do đó, ta nói rằng, semaphore áp dụng cơ chế sleep-waiting.

Tham khảo thêm: Xét nghiệm NIPT là gì vậy? Phát hiện các bệnh nào?

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 chính 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 hạn chế race condition. Trong khi lập trình device driver, ta đặt hàm downup 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:

Trường hợp 1: A muốn truy cập R trong khi B đang truy cập R. Trước khi thực thi các lệnh trong critical section của thread A, CPU0 sẽ thực thi hàm down và thấy rằng S đang ở trạng thái UNAVAILABLE. Khi đó, CPU0 sẽ tạm dừng thực thi thread A rồi chuyển sang thực thi một thread C nào đó.Sau khi thực thi xong critical section của thread B, CPU1 thực thi tiếp hàm up để đánh thức thread A dậy , CPU0 tiếp tục thực thi thread A.Trường hợp 2: cả A , và B đồng thời muốn truy cập R. Khi đó, cả 2 thread đồng thời thực thi hàm down. Tuy nhiên, do semaphore được bảo vệ chỉ bằng một spinlock, nên chỉ có một trong hai thread chiếm được S.Thread nào chiếm được S trước thì sẽ sử dụng R trước. Thread nào chưa chiếm đã được S thì cũng sẽ đi ngủ cho đến khi thread đầu tiên sử dụng xong R.

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 cũng sẽ chưa xảy ra , critical resource đã được bảo vệ.

Để khai báo , khởi tạo giá trị cho binary semaphore ngay đến từ lúc biên dịch (compile time), ta có thể sử dụng macro DEFINE_SEMAPHORE. thí dụ:

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

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 quy 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. thí dụ:

/* * Khi ta muốn bảo vệ dữ liệu trong cấu trúc my_struct, ta cũng 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 critical resource, * còn my_semaphore đại diện cho bộ các chìa khóa bảo vệ critical resource. */ struct my_struct … struct semaphore my_semaphore; … my_struct_t; int init_driver_func() … //Giá trị khởi tạo lớn hơn hoặc bằng 0 sema_init(&my_struct_t.my_semaphore, 1); …

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 , sau critical section của thread để ngăn không cho race condition xảy ra.

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. Phương Pháp sử dụng như sau:

/* * Ta có thể sử dụng “int down_interruptible(struct semaphore *sem)” * thay cho hàm “void down(struct semaphore *sem)”. * Nếu chiếm đã được semaphore, hàm này cũng sẽ trả về 0. * Nếu chưa chiếm được, thread (gọi hàm này) cũng sẽ bị tạm ngừng hoạt động. * Nếu thread đang tạm ngừng hoạt động mà có một tín hiệu, hàm này trả về -EINTR. * * Khi nào sử dụng down_interruptible thay cho down? * Đó chính là khi ta muốn thread tiếp nhận các tín hiệu (signal) trong lúc * đang chờ semaphore. * * Xét trường hợp tiến trình P ở trên user space yêu cầu device driver * đọc/ghi dữ liệu trong critical resource R. Khi đó, tương ứng với P, * sẽ có một kernel thread T định truy cập vào R. Nếu kernel thread T’ * đang truy cập R, thread T cũng sẽ bị tạm dừng tại hàm down_interruptible. * Ta nói, thread T đang bị blocking bởi hàm down_interruptible. * Nếu lúc này người dùng tạo một tín hiệu (signal), thí dụ nhấn tổ hợp * CTRL + C để hủy tiến trình P, thì hàm down_interruptible * cũng sẽ trả luôn về -EINTR mà không blocking thread T nữa. Điều này giúp cho hủy * tiến trình P luôn mà chưa phải chờ đợi thread T’ giải phóng semaphore. */ if (down_interruptible(&my_semaphore)) return -ERESTARTSYS; /* critical section của kernel thread */ up(&my_semaphore);

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

/* * hàm: down_trylock * chức năng: yêu cầu chiếm giữ semaphore. Nếu chưa thể chiếm được, * trả luôn về cho thread gọi hàm này. Thread gọi hàm này * cũng 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 chiếm đã được semaphore, trả về 0. * Nếu chưa chiếm đã được semaphore (do thread khác đã chiếm rồi), trả về 1. */ int down_trylock(struct semaphore *sem);

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:

Do semaphore áp dụng cơ chế chờ đợi sleep-waiting, nên ta chỉ sử dụng kỹ thuật này khi khoảng thời gian chờ đợi dài. Thông thường, nếu critical section chứa lời gọi hàm sleep/schedule hoặc gồm nhiều câu lệnh, thì có thể áp dụng semaphore.Kỹ thuật này hoàn toàn phù hợp để áp dụng trong các thread được phép đi ngủ, thí dụ như các kernel thread thông thường, hoặc bottom-half được triển khai chỉ bằng workqueue.Ta chưa được phép gọi hàm down hoặc down_interruptible trong ISR, hoặc bottom-half được triển khai bằng tasklet/softirq. Tuy vậy, hàm down_trylock , up vẫn có thể được gọi từ ISR.Một thread có thể giải phóng semaphore mặc dù nó chưa phải là người đã chiếm dụng. Điều này khác so với kỹ thuật spinlock và mutex lock.Trong khi đang chiếm dụng một spinlock, ta không được gọi hàm down_interruptible hoặc down để lấy một semaphore.

Trong thí 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:

cd /home/ubuntu/ldd/phan_6 cp -r bai_6_1 bai_6_5

Tham khảo thêm: Tinder Gold là gì , và nó có đáng đồng tiền bát gạo không?

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

Aj_hqsbXcamB8ry29VQsoHjSdt0T-y7nUespQRcZ-AliDGU62t9gcKa707r79tRtclmPj04dhbbJ_P5lvto6ZQZFbYifozSWZUoMTxfAXer8G83o-jY0iBg4S1ho4o2giXknzZkk

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.

1MlvAVsQ8ETiDqIzTp0OjGtgCJ_ACQm1_dEu1BPP4s_cWdruzOqaWruRLxkWZhpkvB2o4hliVAoYWya-ITpQGMTGjzwQ8aeTY51fI9BOWHL8H3ULYlgRQofdpnSfz9VuVhimK8h8

Sau đó, trong hàm vchar_driver_init, ta khởi tạo semaphore này để gây nên binary semaphore:

WqevTXQJRCos8TGYm88KWoUBR0Z4XgrZGDHHQQC-H2pTRS8mQ-SVHH_ewovxIaMoF5YXeg0zk7z4ZNnDHmKYyYyNbmOPinl1hA_zYYu1qvUiK05UnqxD-KH25hNprrZxo5M-FHfa

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.

h_wtck9oLL7USwd1O6cLH5DBawmrHGxHm6cHx1LSXo39clZ4pxngQoq17qoWuKJ1IUCCGDlb-nK20vy6fkXxcln6AVT6n18r5S02gRhWaWGKnsXVR2NrKY0Id-qTOdf5CwJjezlQ

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 chỉ 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 , mutex lock.

Cq2twV3gIAeoEJyW4xy1PMwesqVb1kpkTg3f7xB3Y4aeuVM83ZIZY-0SQPIaH_4iOysnBUqJPV7SOACkXS2VjXzDyrj66qPmlYNzjiKdNsqN1hmMHvOqmRzkGwKEcsljhE1KTd0g

Hình 3. Dùng kỹ thuật binary semaphore giúp ngăn ngừa race condition ở trên biến critical_resource

Semaphore chính 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 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.

Xem thêm: SO FAR là gì vậy? Giải Nghĩa , Phương Pháp Dùng Cấu Trúc So far, So Good

Bạn thấy bài viết thế nào?

Tìm hiểu thêm: &quotDụng Cụ&quot trong Tiếng Anh là gì: Định Nghĩa, thí dụ Anh Việt