Реализация блокировки с использованием спин-блокировок в принципах и на практике операционных систем Anderson

Question

Учитывая следующий псевдокод в многопроцессорной системе:

class SpinLock {
   private:
     int value = 0; // 0 = FREE; 1 = BUSY
 
   public:
     void acquire() {
         while (test_and_set(&value)) // while BUSY
             ; // spin
     }
 
     void release() {
         value = 0;
         memory_barrier();
     }
 }

, где инструкция test-and-set атомарно считывает значение из памяти в регистр и записывает значение 1 в эту ячейку памяти.

Теперь они реализуют блокировки следующим образом:

class Lock {
    private:
      int value = FREE;
      SpinLock spinLock;
      Queue waiting;
    public:
      void acquire();
      void release();
 }
 
 Lock::acquire() {
     spinLock.acquire();
     if (value != FREE) {
         waiting.add(runningThread);
         scheduler.suspend(&spinLock);
        // scheduler releases spinLock
     } else {
         value = BUSY;
         spinLock.release();
     }
 }
 
 void Lock::release() {
     TCB *next;
 
     spinLock.acquire();
     if (waiting.notEmpty()) {
         next = waiting.remove();
         scheduler.makeReady(next);
     } else {
         value = FREE;
     }
     spinLock.release();
 }
 class Scheduler {
   private:
     Queue readyList;
     SpinLock schedulerSpinLock;
   public:
     void suspend(SpinLock *lock);”
     void makeReady(Thread *thread);
 }
 
 void
 Scheduler::suspend(SpinLock *lock) {
     TCB *chosenTCB;
 
     disableInterrupts();
     schedulerSpinLock.acquire();
     lock->release();
     runningThread->state = WAITING;
     chosenTCB = readyList.getNextThread();
     thread_switch(runningThread,
                   chosenTCB);
     runningThread->state = RUNNING;
     schedulerSpinLock.release();
     enableInterrupts();
 }
 
 void
 Scheduler::makeReady(TCB *thread) {
     disableInterrupts();
     schedulerSpinLock.acquire();
     readyList.add(thread);
     thread->state = READY;
     schedulerSpinLock.release();
     enableInterrupts();
 }

Я не понимаю, как это работает.Предположим, что мы находимся в потоке A, когда мы вызываем acqu (), а Lock принадлежит другому потоку B.

Мы получаем спин-блокировку объекта Lock, добавляем поток в список ожидания и вызываем scheduler.suspend.с прядом блокировки в качестве аргумента.В методе suspend мы получим спин-блокировку планировщика, предполагая, что она свободна, затем мы снимаем спин-блокировку блокировки, меняем состояние работающего потока A на ожидание, получаем поток C из очереди готовности и затем выполняемпереключение контекста.

Я не понимаю, как теперь выпускается спин-блокировка планировщика.При переключении контекста указатель стека изменяется на указатель нового потока C, также обмениваются регистры, в частности, также указатель инструкции, поэтому оператор после thread_switch не выполняется до тех пор, пока старому потоку C снова не будет выделено время ЦП, верно?Итак, давайте предположим, что спин-блокировка планировщика не свободна, а удерживается потоком A.

Предположим, что поток B снимает блокировку.Он получает спин-блокировку Lock, которая является бесплатной, и в очереди ожидания есть по крайней мере один поток, а именно A. Предположим, что A выбран следующим, поэтому мы вызываем scheduler.makeReady с потоком A в качестве аргумента.Но теперь внутри makeReady есть вызов для получения спин-блокировки планировщика, которая не была освобождена, потому что мы произвели переключение контекста до того, как schedulerSpinlock.release () был вызван внутри Scheduler :: suspend (), когда мы выполняли поток A. Так как можноthread A отпустите спин-блокировку планировщика сейчас, если мы не сможем запустить ее снова?

Answer 1

[предостережение: я не читал Андерсона].

Thread_switch () останавливает выполнение одного потока и возобновляет выполнение другого. Этот другой сразу же вернется в своем стеке к инструкции после вызова , который он сделал для thread_switch (), который остановил ее.

Если мы предположим, что каждый не работающий поток стал не запущенным из-за вызова suspend, то только что пробудившийся поток освободит спин-блокировку планировщика, полученную тем, который приостановил сам. Если мы не можем сделать это предположение, но можем предположить, что каждый вызов thread_switch имеет вид:

 schedulerSpinLock.acquire();
 ...
 thread_switch(cur, new);
 ...
 schedulerSpinLock.release();

Тогда достаточно убедиться, что предполагаемый сценарий не будет реализован - schedulerSpinLock будет освобожден C либо потому, что C выходит из режима ожидания, либо какой-либо другой функцией, которая повторяет шаблон приостановки.

Совершенство этой конструкции может быть спорным. Должны ли вы выпускать spinlock () в одном потоке, который был выделен в другом, вероятно, является предметом горячих споров в некоторых кругах. Будьте уверены, большинство ядер имеют некоторую жонглирование чистой семантикой для обработки перехода, когда что-то технически приостановлено, но все еще выполняется или технически выполняется, но все еще приостановлено.