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

Ngoài spin lock và mutexes, chúng ta cũng có thể áp dụng công nghệ semaphore để bảo vệ dữ liệu trong các tài nguyên chính. Semaphore không chỉ là công nghệ đồng bộ hóa tài nguyên mà còn được gọi là công nghệ đồng bộ hóa tích cực.

Do phạm vi của khóa học, bài học này chỉ giới thiệu cờ hiệu như một kỹ thuật đồng bộ hóa tài nguyên:

• Giới thiệu semaphore là gì, cấu tạo, nguyên lý hoạt động và cách bảo vệ các tài nguyên chính?
• Làm cách nào để sử dụng semaphore trong lập trình trình điều khiển thiết bị?
• Tôi nên chú ý điều gì khi sử dụng công nghệ semaphore?

Semaphore là gì?

Một semaphore là một cấu trúc dữ liệu được sử dụng để đồng bộ hóa tài nguyên và đồng bộ hóa các hoạt động.

Khi được sử dụng cho mục đích đồng bộ hóa tài nguyên, semaphore giống như một bộ khóa dự phòng. Nếu một luồng lấy được khóa, thì luồng đó được phép truy cập tài nguyên. Nhưng nếu không còn khóa nào, chuỗi phải đợi cho đến khi chuỗi khác trả về khóa thay thế. Nhờ đó, tình trạng đua đòi sẽ được ngăn chặn.



Hình 1. Sử dụng semaphore để đồng bộ tài nguyên

Cấu trúc semaphore?

Một semaphore bao gồm 2 phần chính: biến count và hàng đợi wait_list. Nhân linux sử dụng cấu trúc semaphore để biểu diễn một semaphore.

Theo giá trị của biến count, semaphore được chia thành hai loại: semaphore đếm và semaphore nhị phân.

• Nếu giá trị lớn nhất của biến count lớn hơn 1, semaphore được gọi là semaphore đếm. Giá trị tối đa của biến count cho biết số luồng tối đa được phép sử dụng các tài nguyên chính cùng một lúc.
• Nếu biến count chỉ có hai giá trị là 0 và 1 thì semaphore này được gọi là semaphore nhị phân. Semaphores nhị phân có một số điểm tương đồng với mutexes.

Semaphores hoạt động như thế nào?



Hình 2. Sơ đồ hiển thị hoạt động semaphore

Khi count lớn hơn 0, nghĩa là semaphore ở trạng thái sẵn sàng. Nếu một luồng gọi hàm down, count Strong> biến sẽ bị giảm đi 1 (nếu If chênh lệch bằng 0, semaphore trở thành không khả dụng). Sau đó, cpu bắt đầu thực thi phần quan trọng của luồng (trong ngôn ngữ cpu) hoặc luồng bắt đầu sử dụng các tài nguyên quan trọng (trong ngôn ngữ nhân linux).

Khi count bằng 0, nghĩa là semaphore ở trạng thái không khả dụng, nếu một luồng gọi xuống, CPU sẽ tạm dừng việc thực thi luồng, sau đó Chuyển sang luồng thực thi khác (bằng ngôn ngữ của cpu). Hoặc trong ngôn ngữ nhân linux, luồng được thêm vào hàng đợi wait_list và chuyển sang chế độ ngủ, sau đó nhân linux sẽ lên lịch cho một luồng khác. Do đó, chúng tôi nói rằng semaphore áp dụng cơ chế sleep-waiting.

.

Khi có ít nhất một luồng đang chờ trong wait_list, nếu có luồng a đang gọi, cpu sẽ chuyển sang luồng b ở vị trí đầu tiên trong hàng đợi thực thi wait_list mạnh> (trong ngôn ngữ cpu). Hoặc trong ngôn ngữ nhân linux, nhân linux đánh thức luồng B, sau đó luồng B bắt đầu sử dụng các tài nguyên quan trọng.

Khi không có chuỗi nào đang chờ trong wait_list, nếu có một chuỗi đang gọi hàm up, thì biến count sẽ thêm 1 , tức là đèn hiệu sẽ chuyển đến lên mạnh>Có sẵn.

. tiểu bang

Làm cách nào để semaphores bảo vệ các tài nguyên quan trọng?

Do hoạt động của semaphore nhị phân tương tự như một mutex, nên semaphore này thường được sử dụng để đồng bộ hóa dữ liệu và tránh các điều kiện tương tranh. Khi viết trình điều khiển thiết bị, chúng tôi đặt các chức năng xuống và lên trước và sau phần quan trọng của từng luồng tương ứng.

Ví dụ, hệ thống có các luồng hạt nhân a và b, được thực thi tương ứng trên hai lõi cpu0 và cpu1. Cả hai luồng đều có nhu cầu sử dụng tài nguyên quan trọng r, được bảo vệ bởi một semaphore nhị phân. Hãy xem xét hai trường hợp:

• Trường hợp 1: a muốn truy cập r, và b đang truy cập r.
  • Trước khi thực hiện các lệnh trong phần quan trọng của chuỗi a, cpu0 sẽ thực thi ngừng và thấy rằng s ở trạng thái không khả dụng. Khi đó cpu0 sẽ tạm ngưng thực thi luồng a, rồi chuyển sang thực thi luồng c nào đó.
  • Sau khi thực hiện phần quan trọng của luồng b, cpu1 thực thi chức năng up để đánh thức luồng a và cpu0 tiếp tục thực thi luồng a.
  • Trường hợp 2: Cả a và b đều muốn truy cập r cùng một lúc.
    • Sau đó, cả hai luồng thực thi chức năng xuống đồng thời. Tuy nhiên, vì semaphore được bảo vệ bởi một spinlock, nên chỉ một trong hai luồng có thể chụp s.
    • Chuỗi lấy s trước sẽ dùng r trước. Các luồng không thu được s sẽ ngủ cho đến khi luồng đầu tiên tiêu thụ hết r.

    Do đó, tại bất kỳ thời điểm nào, nhiều nhất một luồng được phép chiếm semaphore nhị phân, nghĩa là, nhiều nhất một luồng được phép sử dụng tài nguyên quan trọng. Do đó, điều kiện chạy đua không xảy ra và các tài nguyên quan trọng được bảo vệ.

    Để khai báo và khởi tạo một semaphore nhị phân tại thời điểm biên dịch, chúng ta có thể sử dụng macrodefine_semaphore. Ví dụ:

    Tuy nhiên, các semaphores thường có cấu trúc lớn hơn và bộ nhớ được phân bổ trong thời gian chạy. Vì vậy chúng ta sẽ sử dụng hàm sema_init để khởi tạo semaphore. Chúng tôi thường gọi hàm sema_init trong hàm tạo trình điều khiển. Ví dụ:

    Sau khi khai báo và khởi tạo semaphore, chúng ta có thể sử dụng các cặp hàm down và up trước và sau phần quan trọng của luồng để ngăn tình trạng tranh đua xảy ra.

    Đôi khi chúng 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, nhân linux hỗ trợ chức năng down_trylock.

    Hãy cẩn thận khi sử dụng semaphores

    Khi triển khai chương trình này, bạn cần chú ý một số điểm sau:

    • Vì semaphore sử dụng trạng thái ngủ chờ nên chúng tôi chỉ sử dụng kỹ thuật này khi thời gian chờ lâu. Thông thường, một semaphore có thể được áp dụng nếu phần quan trọng chứa lệnh gọi hàm sleep/schedule hoặc chứa nhiều câu lệnh.
    • Kỹ thuật này hoạt động hiệu quả đối với các luồng được phép ngủ, chẳng hạn như luồng nhân thông thường hoặc nửa dưới được triển khai bằng cách sử dụng hàng đợi công việc.
    • Chúng tôi không cho phép gọi các hàm down hoặc down_interruptible trong isr hoặc nửa dưới do tasklet/softirq triển khai. Tuy nhiên, hàm down_trylock và up vẫn có thể được gọi từ isr.
    • Một luồng có thể giải phóng semaphore, ngay cả khi nó không phải là luồng chiếm semaphore. Điều này khác với các kỹ thuật spinlock và mutex.
    • Bạn không được gọi down_interruptible hoặc down để lấy semaphore khi đang giữ spinlock.

    Trong ví dụ này, chúng tôi sẽ áp dụng các kỹ thuật semaphore để cải thiện trình điều khiển vchar từ bài viết trước. Đầu tiên chúng ta tạo một thư mục cho bài học hôm nay như sau:

    Bây giờ chúng ta tiến hành chỉnh sửa file vchar_driver.c. Đầu tiên, để triển khai semaphore, chúng ta cần tham khảo thư viện .

    

    Tiếp theo, chúng tôi thêm biến vchar_semaphore vào 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, chúng ta khởi tạo semaphore để tạo semaphore nhị phân:

    

    Cuối cùng, chúng tôi thêm các hàm xuống và lên trước và sau phần quan trọng tương ứng.

    

    Bây giờ, chúng ta nhập lệnh make để biên dịch lại trình điều khiển vchar. Sau khi biên dịch thành công, ta kiểm tra hình 3 sau, ta thấy kết quả cuối cùng của biến critical_resource chính xác bằng 3.145.728. Tuy nhiên, có thể thấy nếu áp dụng công nghệ semaphore thì thời gian hoàn thành bài toán sẽ lâu hơn nhiều so với công nghệ spin lock và mutex.

    

    Điểm 3. Sử dụng các kỹ thuật semaphore nhị phân để giúp ngăn chặn các điều kiện tương tranh trên các biến critical_resource

    Một semaphore là một cấu trúc có thể đồng bộ hóa tài nguyên và hoạt động. Một semaphore bao gồm hai phần chính, biến count và hàng đợi wait_list. Biến count giúp kiểm soát số lượng luồng còn lại được phép truy cập vào các tài nguyên quan trọng. Và hàng đợi wait_list chứa danh sách các luồng đang đợi cho đến khi chúng có thể truy cập các tài nguyên quan trọng.

    Semaphore bao gồm semaphore nhị phân và semaphore đếm. Semaphores nhị phân hoạt động tương tự như mutexes và do đó thường được sử dụng để tránh điều kiện chủng tộc. Sự khác biệt chính so với một mutex là một luồng có thể giải phóng một semaphore ngay cả khi luồng đó chưa bao giờ sở hữu semaphore.