Bên cạnh spinlock và mutex lock, ta cũng có thể vận dụng kỹ thuật semaphore để bảo vệ dữ liệu trong crucial useful resource. Ko chỉ là 1 kỹ thuật đồng bộ tài nguyên, semaphore cũng được biết tới là 1 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 có tư bí quyết là 1 kỹ thuật đồng bộ tài nguyên:
- Giới thiệu semaphore là gì, có cấu tạo như thế nào, hoạt động ra sao, bảo vệ crucial useful resource như thế nào?
- Dùng kỹ thuật semaphore trong lập trình system driver như thế nào?
- Cần chú ý những gì lúc dùng kỹ thuật semaphore?
Semaphore là gì?
Semaphore là 1 cấu trúc dữ liệu, được dùng để đồng bộ tài nguyên và đồng bộ hoạt động.
Lúc được dùng có phần đích đồng bộ tài nguyên, semaphore tương tự động như 1 bộ những chìa khóa dự phòng. Giả dụ 1 thread lấy được 1 cái chìa khóa, thread đấy được phép truy cập vào tài nguyên. Nhưng trường hợp ko còn cái chìa khóa nào, thread đấy nên đợi cho tới lúc 1 thread khác trả lại chìa khóa dự phòng. Nhờ có vậy, race situation sẽ bị ngăn chặn.
Hình 1. 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 rely và hàng đợi wait_list. Linux kernel dùng cấu trúc semaphore để biểu diễn 1 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à 1 crucial useful resource. Biến @lock là * 1 spinlock bảo vệ @rely và @wait_list trong cấu trúc semaphore. */ raw_spinlock_t lock; /* * Biến rely vừa mô tả trạng thái của semaphore, vừa mô tả * trạng thái của crucial useful resource. * > 0: semaphore đang tại trạng thái AVAILABLE, * còn crucial useful resource đang tại trạng thái READY. * rely cũng mô tả còn bao nhiêu thread nữa được phép * dùng crucial useful resource. * = 0: semaphore đang tại trạng thái UNAVAILABLE, * còn crucial useful resource đang tại trạng thái BUSY. */ unsigned int rely; // wait_list là danh sách những thread đang chờ đợi để có được semaphore struct list_head wait_list; };
Căn cứ vào giá trị của biến rely, semaphore được chia khiến 2 loại là counting semaphore và binary semaphore.
- Giả dụ giá trị cực đại của biến rely lớn hơn 1, thì semaphore được gọi là counting semaphore. Giá trị cực đại của biến rely mô tả số lượng thread cao nhất} được phép dùng crucial useful resource tại cùng 1 thời điểm.
- Giả dụ biến rely chỉ có 2 giá trị 0 và 1, thì semaphore được gọi là binary semaphore. Binary semaphore có 1 số nét tương đồng có mutex lock.
Semaphore hoạt động ra sao?
Hình 2. Sơ đồ biểu diễn những trạng thái hoạt của 1 semaphore
Lúc rely đang lớn hơn 0, tức là semaphore đang tại trạng thái AVAILABLE, trường hợp 1 thread gọi hàm down, thì biến rely bị giảm đi 1 đơn vị (trường hợp hiệu bằng 0 thì semaphore chuyển sang trạng thái UNAVAILABLE). Tiếp theo, CPU khởi đầu thực thi crucial part của thread (nói theo ngôn ngữ của CPU), hay thread khởi đầu dùng crucial useful resource (nói theo ngôn ngữ của Linux kernel).
Lúc rely đang bằng 0, tức là semaphore đang tại trạng thái UNAVAILABLE, trường hợp 1 thread gọi hàm down, thì CPU tạm ngừ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 đấy được thêm vào hàng đợi wait_list và đi ngủ, tiếp theo Linux kernel sẽ lập lịch cho thread khác. Do đấy, ta bảo rằng, semaphore vận dụng cơ chế sleep-waiting.
Lúc wait_list vẫn còn ít nhất 1 thread đang nên đợi, trường hợp 1 thread A gọi hàm up, thì CPU sẽ chuyển sang thực thi thread B nằm tại vùng vị trí trước 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, tiếp theo thread B khởi đầu dùng crucial useful resource.
Lúc wait_list ko còn thread nào chờ đợi, trường hợp 1 thread gọi hàm up, thì biến rely được nâng cao thêm 1 đơn vị, tức là semaphore chuyển sang trạng thái AVAILABLE.
Semaphore bảo vệ crucial useful resource như thế nào?
Vì hoạt động của binary semaphore tương tự động như mutex lock, nên loại semaphore này thường được dùng để đồng bộ dữ liệu, phòng giảm thiểu race situation. Trong lúc lập trình system driver, ta đặt hàm down và up lần lượt vào trước và sau crucial part của từng thread.
Giả sử, hệ thống có kernel thread A và B được thực thi biệt lập trên 2 lõi CPU0 và CPU1. Cả 2 thread đều có nhu cầu dùng crucial useful 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 lúc B đang truy cập R.
- Trước lúc thực thi những lệnh trong crucial part của thread A, CPU0 sẽ thực thi hàm down và thấy rằng S đang tại trạng thái UNAVAILABLE. Lúc đấy, CPU0 sẽ tạm ngừng thực thi thread A rồi chuyển sang thực thi 1 thread C nào đấy.
- Sau khoản thời gian thực thi xong crucial part của thread B, CPU1 thực thi tiếp hàm up để đánh thức thread A dậy và 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.
- Lúc đấy, cả 2 thread đồng thời thực thi hàm down. Tuy nhiên, do semaphore được bảo vệ bằng 1 spinlock, nên chỉ có 1 trong 2 thread chiếm được S.
- Thread nào chiếm được S trước thì sẽ dùng R trước. Thread nào ko chiếm được S thì sẽ đi ngủ cho tới lúc thread trước tiên dùng xong R.
Như vậy, tại bất cứ thời điểm nào, cao nhất} chỉ có 1 thread được phép chiếm dụng binary semaphore, đồng nghĩa có việc, cao nhất} chỉ có 1 thread được phép dùng crucial useful resource. Do đấy, race situation sẽ ko xảy ra và crucial useful resource được bảo vệ.
Để 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ể 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 thuộc diện 1 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 đấy, 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ụ:
/* * Lúc 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 crucial useful resource, * còn my_semaphore đại diện cho bộ những chìa khóa bảo vệ crucial useful 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 khoản thời gian đã khai báo và khởi tạo semaphore, ta có thể dùng cặp hàm down và up lần lượt vào trước và sau crucial part của thread để ngăn ko cho race situation xảy ra.
down(&my_semaphore); /* crucial part của kernel thread */ up(&my_semaphore);
Đôi lúc, ta có thể dùng hàm down_interruptible thay thế cho hàm down. Phương pháp dùng như sau:
/* * Ta có thể dùng “int down_interruptible(struct semaphore *sem)” * thay thế cho hàm “void down(struct semaphore *sem)”. * Giả dụ chiếm được semaphore, hàm này sẽ trả về 0. * Giả dụ chưa chiếm được, thread (gọi hàm này) sẽ bị tạm ngừng hoạt động. * Giả dụ thread đang tạm ngừng hoạt động mà có 1 tín hiệu, hàm này trả về -EINTR. * * Lúc nào dùng down_interruptible thay thế cho down? * Ấy là lúc ta muốn thread tiếp nhận những tín hiệu (sign) trong lúc * đang chờ semaphore. * * Xét trường hợp tiến trình P trên consumer house đề nghị system driver * đọc/ghi dữ liệu trong crucial useful resource R. Lúc đấy, tương ứng có P, * sẽ có 1 kernel thread T định truy cập vào R. Giả dụ kernel thread T’ * đang truy cập R, thread T sẽ bị tạm ngừng tại hàm down_interruptible. * Ta nói, thread T đang bị blocking bởi hàm down_interruptible. * Giả dụ lúc này người mua tạo 1 tín hiệu (sign), thí dụ nhấn tổ hợp * CTRL + C để hủy tiến trình P, thì hàm down_interruptible * sẽ trả luôn về -EINTR mà ko blocking thread T nữa. Điều này giúp hủy * tiến trình P luôn mà ko nên chờ đợi thread T’ giải phóng semaphore. */ if (down_interruptible(&my_semaphore)) return -ERESTARTSYS; /* crucial part của kernel thread */ up(&my_semaphore);
Bên cạnh ra, Linux kernel tương trợ hàm down_trylock.
/* * hàm: down_trylock * chức năng: đề nghị chiếm giữ semaphore. Giả dụ ko thể chiếm được, * trả luôn về cho thread gọi hàm này. Thread gọi hàm này * sẽ ko chờ đợi semaphore nữa (non-blocking). * tham số đầu vào: * *sem [IO]: là liên hệ của vùng nhớ chứa cấu trúc semaphore. * giá trị trả về: * Giả dụ chiếm được semaphore, trả về 0. * Giả dụ ko chiếm được semaphore (do thread khác đã chiếm rồi), trả về 1. */ int down_trylock(struct semaphore *sem);
Chú ý lúc dùng semaphore
Lúc triển khai giải pháp này, ta cần chú ý mấy điểm sau:
- Do semaphore vận dụng cơ chế chờ đợi sleep-waiting, nên ta chỉ dùng kỹ thuật này lúc khoảng thời kì chờ đợi dài. Thông thường, trường hợp crucial part chứa lời gọi hàm sleep/schedule hoặc gồm nhiều câu lệnh, thì có thể vận dụng semaphore.
- Kỹ thuật này hoàn toàn yêu thích để vận dụng trong những thread được phép đi ngủ, thí dụ như những kernel thread thông thường, hoặc bottom-half được triển khai bằng workqueue.
- Ta ko đượ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 và up vẫn có thể được gọi từ ISR.
- 1 thread có thể giải phóng semaphore dù rằng nó ko nên là người đã chiếm dụng. Điều này khác so có kỹ thuật spinlock và mutex lock.
- Trong lúc đang chiếm dụng 1 spinlock, ta ko được gọi hàm down_interruptible hoặc down để lấy 1 semaphore.
Trong thí dụ này, chúng ta sẽ vận dụng kỹ thuật semaphore để cải thiện vchar driver trong bài hôm trước. Trước tiên, ta tạo thư phần cho bài học ngày hôm nay như sau:
cd /dwelling/ubuntu/ldd/phan_6 cp -r bai_6_1 bai_6_5
Thời điểm này}, ta tiến hành sửa file vchar_driver.c. Trước 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.
Tiếp theo, 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 crucial part.
Thời điểm này}, ta gõ lệnh make để biên dịch lại vchar driver. Sau khoản thời gian biên dịch thành công, ta thực hành đánh giá 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, trường hợp vận dụng kỹ thuật semaphore, thời kì để hoàn thành bài toán thời gian dài hơn siêu nhiều so có kỹ thuật spinlock và mutex lock.
Hình 3. Dùng kỹ thuật binary semaphore giúp ngăn ngừa race situation trên biến critical_resource
Semaphore là 1 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 rely và hàng đợi wait_list. Biến rely giúp kiểm soát số lượng thread còn lại được phép truy cập vào crucial useful resource. Còn hàng đợi wait_list chứa danh sách những thread đang nên chờ đợi trước lúc có thể truy cập crucial useful resource.
Semaphore gồm 2 loại là binary semaphore và counting semaphore. Hoạt động của binary semaphore tương tự động như mutex lock, do đấy thường được dùng để phòng giảm thiểu race situation. Điểm khác biệt nổi bật so có mutex lock đấy là: 1 thread có thể giải phóng semaphore dù rằng thread đấy chưa hề chiếm dụng semphore.
