3

我正在使用一个简单的系统，它没有互斥体，而是有限的硬件二进制信号量数组。通常，所有多线程都是使用繁重的信号量技术完成的，这使得代码性能很差，而且很难在没有死锁的情况下正确编写。

一种简单的实现是全局使用一个信号量，以确保对关键部分的原子访问。但是，这意味着如果访问任何关键部分，不相关的对象（即使是不同类型的对象）也会阻塞。

我目前对这个问题的解决方案是使用单个全局信号量来确保对保护字节的原子访问，然后确保对特定关键部分的原子访问。到目前为止，我目前有这个：

while (true) {
    while (mutexLock == Mutex::Locked) {
    } //wait on mutex
    Semaphore semaLock(SemaphoreIndex::Mutex); //RAII semaphore object
    if (mutexLock == Mutex::Unlocked) {
        mutexLock = Mutex::Locked;
        break;
    }
} //Semaphore is released by destructor here
// ... atomically safe code
mutexLock = Mutex::Unlocked;

我有几个问题：这是解决这个问题的最佳方法吗？这段代码是线程安全的吗？这和“双重检查锁”一样吗？如果是这样，它是否会遇到同样的问题并因此需要内存屏障？

编辑：关于正在实施的系统的一些注意事项......

它是具有 32kB RAM 的 RISC 16 位处理器。虽然它具有强大的多线程功能，但它的内存模型非常原始。加载和存储是原子的，没有缓存，没有分支预测或分支目标预测，一个核心多线程。内存屏障主要是让编译器知道它应该将内存重新加载到通用寄存器中，而不是出于任何硬件原因（无缓存）

4

2 回答 2

1

即使处理器具有强大的多线程功能（不知道你的意思是什么），但它是一个单核处理器，它仍然意味着任何时候只能执行一个线程。

必须使用任务切换系统（通常以特权模式运行）使用该系统，您必须能够定义关键部分以原子地执行（软件实现）互斥锁/解锁。

当您说“一个内核，许多线程”时，这是否意味着您的处理器上运行了某种内核？任务切换系统将由该内核实现。查看内核文档或向供应商询问任何提示可能会有所帮助。

祝你好运。

于 2013-11-27T11:35:18.737 回答
1

现在我们仍然没有关于您的系统的那么多信息（例如，并行中的每条指令都有哪些类型的寄存器可用？您使用银行架构吗？，您实际上可以同时执行多少条指令？）但希望是什么我建议会帮助你

如果我了解您的情况，您的硬件没有真正的内核，而只是通过矢量化操作（基于您的回复）实现的 MIMD 能力。它是“具有 32kB RAM 的 RISC 16 位处理器”，其中：

加载和存储是原子的，没有缓存，没有分支预测或分支目标预测，一核多线程

这里的关键是加载和存储是原子的。请注意，您将无法以原子方式执行大于 16 位的加载和存储，因为它们将被编译为两个单独的原子指令（因此本身不是原子指令）。

这是互斥锁的功能：

  • 尝试锁定
  • 开锁

要锁定，如果每个资源都尝试锁定，您可能会遇到问题。例如，在您的硬件中说 N = 4（并行运行的进程数）。如果指令 1 (I1) 和 I2 尝试锁定，它们都将成功锁定。由于您的加载和存储是原子的，因此两个进程同时看到“解锁”，并且都获得了锁。

这意味着您不能执行以下操作：

 if mutex_1 unlocked:
      lock mutex_1

在任意汇编语言中可能看起来像这样：

 load arithmetic mutex_addr
 or arithmetic immediate(1)  // unlocked = 0000 or 1 = 0001, locked = 0001 or 1 = 0001 
 store mutex_addr arithmetic // not putting in conditional label to provide better synchronization. 
 jumpifzero MUTEXLABEL arithmetic

为了解决这个问题，您需要让每个“线程”知道它当前是否获得了其他人的锁，或者完全避免同时锁定访问。

我只看到可以在您的系统上完成的一种方式（通过标志/互斥体 ID 检查）。对于当前正在检查的每个互斥锁，都有一个与每个线程关联的互斥锁 ID，并检查所有其他线程以查看您是否真的可以获得锁。您的二进制信号量在这里并没有真正的帮助，因为如果您要使用它，您需要将单个互斥锁与信号量相关联（并且仍然必须从 ram 加载互斥锁）。

检查每个线程解锁和锁定的简单实现，基本上每个互斥锁都有一个 ID 和一个状态，为了避免每条指令的竞争条件，当前正在处理的互斥锁在实际获取之前就被识别出来。让“确定您要使用哪个锁”和“实际尝试获取锁”分两个步骤来阻止同时访问时意外获取。使用这种方法，您可以拥有 2^16-1（因为 0 表示未找到锁）互斥锁，并且您的“线程”可以存在于任何指令管道上。

// init to zero
volatile uint16_t CURRENT_LOCK_ATTEMPT[NUM_THREADS]{0};
// make thread id associated with priority
bool tryAcqureLock(uint16_t mutex_id, bool& mutex_lock_state){
    if(mutex_lock_state == false){
        // do not actually attempt to take the lock until checked everything.  
        // No race condition can happen now, you won't have actually set the lock
        // if two attempt to acquire the same lock at the same time, you'll both 
        // be able to see some one else is as well. 
        CURRENT_LOCK_ATTEMPT[MY_THREAD_ID] = mutex_id;
        //checking all lower threads, need some sort of priority 
        //predetermined to figure out locking. 
        for( int i = 0; i < MY_THREAD_ID; i++ ){
            if((CURRENT_LOCK_ATTEMPT[i] == mutex_id){
                //clearing bit. 
                CURRENT_LOCK_ATTEMPT[MY_THREAD_ID] = 0;
                return false;
            }
        }
        // make sure to lock mutex before clearing which mutex you are currently handling
        mutex_lock_state = true;
        CURRENT_LOCK_ATTEMPT[MY_THREAD_ID] = 0;
        return true;
    }
    return false;
}

// its your fault if you didn't make sure you owned the lock in the first place
// if you did own it, theres no race condition, because of atomic store load. 
// if you happen to set the state while another instruction is attempting to 
// acquire the lock they simply wont get the lock and no race condition occurs
bool unlock(bool& mutex_lock_state){
    mutex_lock_state = false;
}

如果您想要更平等地访问资源，您可以更改索引而不是基于i = 0to i < MY_THREAD_ID，您可以随机选择一个“起点”以使用模算术绕回 MY_THREAD_ID 。IE：

bool tryAcqureLock(uint16_t mutex_id, bool& mutex_lock_state, uint16_t per_mutex_random_seed){
    if(mutex_lock_state == false){

        CURRENT_LOCK_ATTEMPT[MY_THREAD_ID] = mutex_id;    
        //need a per thread linear congruence generator for speed and consistency
        std::minstd_rand0 random(per_mutex_random_seed)
        for(int i = random() % TOTAL_NUM_THREADS; i != MY_THREAD_ID i = (i + 1) % TOTAL_NUM_THREADS)
        {
        //same as before
        }
        // if we actually acquired the lock
        GLOBAL_SEED = global_random() // use another generator to set the next seed to be used
        mutex_lock_state = true;
        CURRENT_LOCK_ATTEMPT[MY_THREAD_ID] = 0;
        return true;
    }
    return false;
}

一般来说，您缺乏测试和设置能力确实会给所有事情带来麻烦，这意味着您被迫使用其他算法来实现互斥锁。有关可用于非测试和设置架构的其他算法的更多信息，请查看此 SO 帖子，以及这些仅依赖于原子加载和存储的维基百科算法：

所有这些算法基本上都分解为检查一组标志，看看您是否可以通过检查每个其他标志来安全地访问资源。

于 2017-07-05T17:07:43.637 回答