基于Test&Set实现无中断禁用的计数信号量：死锁解决及可行性问询

Alright, let's break this down step by step. You're trying to implement a counting semaphore using the Test&Set atomic instruction without disabling interrupts, and you're stuck on deadlock issues—totally understandable, since Test&Set is a low-level hardware primitive that needs careful wrapping to avoid common pitfalls.

The main deadlock risks here come from two common mistakes when using Test&Set for synchronization:

1. Holding a spinlock while blocking: If your thread grabs the spinlock (via Test&Set) and then goes to sleep (e.g., when the semaphore count hits 0), it'll hold the lock indefinitely. Other threads will spin forever trying to acquire it, leading to deadlock.
2. Uncontrolled spinning + priority inversion: Without disabling interrupts, a higher-priority thread can preempt the thread holding your spinlock. The high-priority thread will spin trying to get the lock, but the low-priority thread (holding the lock) can't run to release it—this is priority inversion that spirals into deadlock.

The key is to use Test&Set to protect the semaphore's internal state (count and wait queue) without holding the lock during blocking. Here's a practical implementation outline with pseudocode:

Semaphore Structure #

typedef struct {
    int count;                  // Semaphore value
    int lock;                   // Spinlock protected by Test&Set
    ThreadQueue* wait_queue;    // Queue of blocked threads waiting for the semaphore
} CountingSemaphore;

Wait Operation (P) #

void sem_wait(CountingSemaphore* sem) {
    // Acquire the spinlock with Test&Set—yield CPU instead of spinning endlessly
    while (__atomic_test_and_set(&sem->lock, __ATOMIC_SEQ_CST)) {
        sched_yield(); // Let other threads run, reducing priority inversion risk
    }

    if (sem->count > 0) {
        // Semaphore is available: decrement count and release lock
        sem->count--;
        __atomic_clear(&sem->lock, __ATOMIC_SEQ_CST);
    } else {
        // No slots left: add self to wait queue, RELEASE LOCK, then block
        add_thread_to_queue(sem->wait_queue, current_thread);
        __atomic_clear(&sem->lock, __ATOMIC_SEQ_CST); // Critical: unlock BEFORE blocking
        block_current_thread(); // Yield CPU until woken
    }
}

Post Operation (V) #

void sem_post(CountingSemaphore* sem) {
    // Acquire spinlock
    while (__atomic_test_and_set(&sem->lock, __ATOMIC_SEQ_CST)) {
        sched_yield();
    }

    if (!is_queue_empty(sem->wait_queue)) {
        // Wake a waiting thread instead of incrementing count
        Thread* waiting_thread = remove_thread_from_queue(sem->wait_queue);
        wake_thread(waiting_thread);
    } else {
        // No waiting threads: increment semaphore count
        sem->count++;
    }

    // Release spinlock
    __atomic_clear(&sem->lock, __ATOMIC_SEQ_CST);
}

Critical Fixes for Deadlock: #

• Never hold the spinlock while blocking: We explicitly release the lock before calling block_current_thread(). This lets other threads access the semaphore state instead of spinning forever.
• Yield during spin: Using sched_yield() instead of empty spinning gives the lock-holding thread a chance to run and release the lock, mitigating priority inversion.
• Atomic lock operations: We use the atomic variants of Test&Set and clear to ensure no race conditions on the spinlock itself—no interrupt disabling needed here, since the hardware guarantees atomicity.

Absolutely! Test&Set is just one atomic primitive—you have several alternatives that might be more efficient or easier to work with:

• Compare-and-Swap (CAS): A more flexible atomic operation that lets you atomically update a value only if it matches an expected state. You can use CAS to directly modify the semaphore count without a separate spinlock, reducing overhead.
• Fetch-and-Add (FAA): An atomic instruction that adds a value to a variable and returns the old value. Perfect for counting semaphores: sem_post can atomically increment the count, and sem_wait can atomically decrement it and check if the result is negative (indicating a need to block).
• Ticket Locks: A fairer spinlock implementation built on Test&Set/CAS that eliminates starvation (a common cause of deadlock-like behavior). Each thread takes a ticket and waits for its turn, ensuring no thread spins forever.
• User-Space Condition Variables + Mutexes: If you're working in user space, you can build semaphores using higher-level primitives (which themselves use atomic instructions like Test&Set under the hood). This abstracts away low-level details and reduces deadlock risks.

Disabling interrupts is only necessary if you're dealing with interrupt handlers accessing the semaphore. For thread-only synchronization, hardware atomic primitives like Test&Set are sufficient to avoid race conditions without disabling interrupts—you just need to avoid holding locks during blocking and handle spin logic thoughtfully.

内容的提问来源于stack exchange，提问作者Phoenix47