Ngoài spinlock và mutex lock, ta cũng sẽ có thể ứng dụng kỹ thuật semaphore để bảo vệ tài liệu trong critical resource. Không chỉ là một kỹ thuật đồng bộ tài nguyên, semaphore cũng được nghe biết là một kỹ thuật đồng bộ hoạt động.

Bạn Đang Xem: Chào mừng bạn đến với Vimentor!

Do phạm vi của khóa học, bài học kinh nghiệm 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 semaphore là gì, có cấu trúc thế nào, hoạt động ra sao, bảo vệ critical resource thế nào?
• Sử dụng kỹ thuật semaphore trong lập trình device driver thế nào?
• Cần lưu ý những gì khi sử dụng kỹ thuật semaphore?

Semaphore là gì?

Semaphore là một cấu trúc tài liệu, được dùng để làm đồng bộ tài nguyên và đồng bộ hoạt động.

Khi được sử dụng với mục tiêu đồ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 này đượ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 trúc 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 để trình diễn một semaphore.

struct semaphore { /* * Do cấu trúc semaphore cũng trở thành nhiều thread truy cập song song, * 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 là list các thread đang mong chờ để đạt được semaphore struct list_head wait_list; };

Địa thế 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.

• Nếu giá trị cực to của biến count to ra hơn 1, thì semaphore được gọi là counting semaphore. Giá trị cực to 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 khắc.
• Nếu biến count chỉ có hai giá trị 0 và 1, thì semaphore được gọi là binary semaphore. Binary semaphore có một số nét tương đồng với mutex lock.

Semaphore hoạt động ra sao?

Hình 2. Sơ đồ trình diễn các trạng thái hoạt của một semaphore

Khi count đang to ra 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 khai mạc thực thi critical section của thread (nói theo tiếng nói của CPU), hay thread khai mạc sử dụng critical resource (nói theo tiếng nói 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 tiếng nói của CPU). Hay nói theo tiếng nói của Linux kernel, thread này đượ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 ứng 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í trước tiên trong hàng đợi wait_list (nói theo tiếng nói của CPU). Hay nói theo tiếng nói của Linux kernel, Linux kernel thức tỉnh thread B dậy, sau đó thread B khai mạc sử dụng critical resource.

Xem Thêm : General Manager là gì? Sự khác biệt giữa General Manager và General Director

Khi wait_list không còn thread nào mong chờ, nếu một thread gọi hàm up, thì biến count được tăng thêm một đơn vị, tức là semaphore chuyển sang trạng thái AVAILABLE.

Semaphore bảo vệ critical resource 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ộ tài liệu, phòng tránh race condition. Trong lúc lập trình device driver, ta đặt hàm down và up tuần tự vào trước và sau critical section của mỗi thread.

Giả sử, mạng lưới 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ả hai thread đều phải sở hữu 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 những lúc B đang truy cập R.
  • Trước lúc 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 lúc thực thi xong critical section của thread B, CPU1 thực thi tiếp hàm up để thức tỉnh thread A dậy và CPU0 tiếp tục thực thi thread A.
• Trường hợp 2: cả A và B song song muốn truy cập R.
  • Khi đó, cả hai thread song song thực thi hàm down. Tuy nhiên, do semaphore được bảo vệ bằng một spinlock, nên chỉ có thể có một trong hai thread chiếm hữu được S.
  • Thread nào chiếm hữu được S trước thì sẽ sử dụng R trước. Thread nào không chiếm hữu được S thì sẽ đi ngủ cho đến lúc thread trước tiên sử dụng xong R.

Như vậy, tại bất kỳ thời khắc 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 còn xẩy ra và critical 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ể sử dụng macro DEFINE_SEMAPHORE. Ví 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 to ra hơn và được cấp phép 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ụ:

/* * Khi ta muốn bảo vệ tài 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 thay mặt cho critical resource, * còn my_semaphore đại diện thay mặt 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 to ra hơn hoặc bằng 0 sema_init(&my_struct_t.my_semaphore, 1); … }

Sau lúc đã khai báo và khởi tạo semaphore, ta có thể sử dụng cặp hàm down và up tuần tự vào trước và 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);

Thỉnh thoảng, ta có thể sử dụng hàm down_interruptible thay cho hàm down. Cách 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 hữu được semaphore, hàm này sẽ trả về 0. * Nếu chưa chiếm hữu được, thread (gọi hàm này) 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? * Đó là lúc ta muốn thread tiếp nhận thêm các tín hiệu (signal) trong lúc * đang chờ semaphore. * * Xét trường hợp tiến trình Phường trên user space yêu cầu device driver * đọc/ghi tài liệu trong critical resource R. Khi đó, tương ứng với Phường, * sẽ có đượ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 sẽ bị tạm dừng tại hàm down_interruptible. * Ta nói, thread T hiện nay đ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), ví dụ nhấn tổng hợp * CTRL + C để hủy tiến trình Phường, thì hàm down_interruptible * sẽ trả luôn về -EINTR mà không blocking thread T nữa. Điều này giúp hủy * tiến trình Phường luôn mà không phải mong chờ thread T’ phóng thích semaphore. */ if (down_interruptible(&my_semaphore)) return -ERESTARTSYS; /* critical section của kernel thread */ up(&my_semaphore);

Ngoài ra, Linux kernel tương trợ hàm down_trylock.

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

Lưu ý khi sử dụng semaphore

Xem Thêm : Kerning là gì? Phân biệt Kerning, Leading và Tracking 

Khi triển khai giải pháp này, ta cần lưu ý mấy điểm sau:

• Do semaphore ứng dụng cơ chế mong chờ sleep-waiting, nên ta chỉ sử dụng kỹ thuật này khi khoảng chừng thời kì mong chờ 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ể ứng dụng semaphore.
• Kỹ thuật này hoàn toàn phù hợp để ứng dụng trong các thread được phép đi ngủ, ví dụ như các kernel thread thông thường, hoặc bottom-half được triển khai bằng workqueue.
• Ta không đượ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.
• Một thread có thể phóng thích semaphore mặc dù nó không 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 lúc đ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 ví dụ này, tất cả chúng ta sẽ ứng dụng kỹ thuật semaphore để cải thiện vchar driver trong bài ngày hôm trước. Trước nhất, ta tạo thư mục cho bài học kinh nghiệm ngày hôm nay như sau:

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

Lúc này, ta tiến hành sửa file vchar_driver.c. Trước nhất, để triển khai semaphore, ta cần tham chiếu tới thư viện <linux/semaphore.hvàgt;.

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ệ tài 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 tuần tự vào trước vào sau vùng critical section.

Lúc này, ta gõ lệnh make để biên dịch lại vchar driver. Sau lúc biên dịch thành công, ta thực hiện kiểm tra như hình 3 về sau 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 ứng dụng kỹ thuật semaphore, thời kì để 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

Semaphore là một cấu trúc, vừa dùng để làm đồng bộ tài nguyên, vừa dùng để làm đồng bộ hoạt động. Semaphore gồm 2 thành phần đây 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 sót lại được phép truy cập vào critical resource. Còn hàng đợi wait_list chứa list các thread đang phải mong chờ trước lúc 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 này thường được sử dụng để phòng tránh race condition. Điểm khác biệt nổi trội so với mutex lock đó là: một thread có thể phóng thích semaphore mặc dù thread đó chưa hề chiếm dụng semphore.