Простая модель планировщика ОС

Не так давно пытался найти здесь какую-нибудь информацию о планировщике Windows и к своему удивлению не нашёл ничего конкретного о планировщиках вообще, поэтому решил запостить вот этот пример планировщика, надеюсь кому-то он окажется полезен. Код написан на Turbo Pascal со вставками ассемблера 8086.

Что собственно планирует планировщик?

Планировщик — часть операционной системы, которая отвечает за (псевдо)параллельное выполнения задач, потоков, процессов. Планировщик выделяет потокам процессорное время, память, стек и прочие ресурсы. Планировщик может принудительно забирать управление у потока (например по таймеру или при появлении потока с большим приоритетом), либо просто ожидать пока поток сам явно(вызовом некой системной процедуры) или неявно(по завершении) отдаст управление планировщику.
Первый вариант работы планировщика называется реальным или вытесняющим(preemptive), второй, соответственно, не вытесняющим (non-preemptive).

Критические секции

C процессорным временем или стеком вроде бы всё просто, а что если потоку требуется например напечатать на принтере котёнка? А что если таких потоков два? При невытесняющей многозадачности всё пройдёт как по маслу: один поток отпечатает котёнка, завершится и отдаст управление планировщику, который позволит печатать второму потоку. Но если многозадачность вытесняющая, планировщик может переключить потоки в момент, когда те ещё не завершили печать и получится что-то вроде этого:

Чтобы такого не происходило вводится механизм критических секций. Поток, которой хочет занять некий неразделяемый ресурс, сообщает об этом планировщику. Если ресурс уже не занят другим потоком — планировщик разрешает потоку продолжить работу, а сам помечает ресурс, как занятый. Если же ресурс занят — поток помещается в очередь, где он ожидает, когда тот освободится. По завершении работы с таким ресурсом поток должен сообщить планировщику о том что ресурс теперь могут использовать другие потоки. Эти два действия: попытка захватить ресурс и сообщение о прекращении работы с ним называются критическими скобками. Кстати при неумелой их расстановке может возникнуть ситуация взаимной блокировки потоков, которая не всегда хорошо и быстро диагностируется и может вызвать неиллюзорный батхёрт у разработчика и пользователя уже после релиза продукта.

Взаимная блокировка

Допустим у нас есть неразделяемые ресурсы А и Б и потоки Х, Y, которые хотят задействовать эти ресурсы. Если некий криворукий недостаточно компетентный программист расставит критические скобки вот так:
…
Поток X
Занять Ресурс(А)
Занять Ресурс(Б)
…
Отдать Ресурс(А)
Отдать Ресурс(Б)
Поток Y
Занять Ресурс(Б)
Занять Ресурс(А)
…
Отдать Ресурс(Б)
Отдать Ресурс(А)

через некоторое время возникнет вот такая ситуация:

Сладенькое

Ну и собственно то ради чего это всё писалось. Как уже было сказано код нашего планировщика будет выполнен на языке Turbo Pascal.

interface

  const MaxThread=10;
        maxCritical=10;
  type TCriticalNum=0..maxCritical;

  function RegisterThread( ThreadAddr:pointer;
                          StackSize:word):integer;
  {Регистрация задачи - занесение в очередь. Возвращается хэндл задачи}

  procedure ExecuteRegisteredThreads(UseTimer:boolean);
  {Выполняет зарегистрированные задачи.
   Задачи  регистрируются активными, т.е. каждая способна получить
   управление. Выполнение прекращается, когда все задачи будут
   прекращены с помощью StopThread. UseTimer указывает, будут ли
   переключаться задачи по таймеру (вытесняющая многозадачность) или
   "добровольно", т.е. путем вызова SwitchThreads внутри себя}

  procedure StopThread(ThreadNumber:byte);{Запрещает передачу управления задаче}
  procedure RunThread(ThreadNumber:byte); {Разрешает передачу управления задаче}
  procedure SwitchThreads; {Досрочно отдать управление диспетчеру задач}

  procedure EnterCritical(num:TCriticalNum); {Войти в критическую секцию}
  procedure LeaveCritical(num:TCriticalNum); {Покинуть критическую секцию}

  procedure LoopBack; {Бесконечный цикл, используется в конце задачи
                       вместо команды RET}

  procedure ClearThreads;

Кроме того нам понадобятся: структура для хранения состояния регистров и стека

type TThreadStateWord=record
       BP_reg, ES_reg, DS_reg, DI_reg, SI_reg, DX_reg,
       CX_reg, BX_reg, AX_reg, IP_reg, CS_reg, Flags:  word;
       Stack:pointer;
       Active:boolean;
     end;

структура для хранения состояния потоков

var TS:array [0..MaxThread-1] of TThreadStateWord;
      Stacks: array [0..MaxThread-1] of record
                sze:word; {размеры стеков}
                ptr:pointer; {указатель на блок, выделенный под стек}
              end;

а так же массивы, в которых будет храниться состояние критических секций и очередей на вход в критические секции.

criticalTable:array [TCriticalNum] of byte=(0,0,0,0,0,0,0,0,0,0,0);
 criticalTableWait:array [TCriticalNum] of byte=(0,0,0,0,0,0,0,0,0,0,0);

Механизм критических секций реализован в процедурах EnterCritical(), LeaveCritical(). Вспомним ещё раз: чтобы войти в критическую секцию — нужно проверить не занята ли она, и по результату — либо занять её и разрешить потоку ей пользоваться, либо поставить поток в очередь и передать управление кому-то другому.

procedure EnterCritical(num:TCriticalNum); {Войти в критическую секцию}
begin
  asm cli end;
  if num<=maxCritical then begin
    if criticalTable[num]<>0 then begin
      inc(criticalTableWait[num]); {запрос на вход в КС}
      while criticalTable[num]>0 do begin {Пока КС занята кем-то}
        {отдать управление другому процессу и ждать освобождения КС}
        asm sti end;
        SwitchThreads;
        asm cli end;
      end;
      dec(criticalTableWait[num]);
    end;
    criticalTable[num]:=1;
  end;
  asm sti end;
end;

C LeaveCritical() вроде бы и так всё ясно:

procedure LeaveCritical(num:TCriticalNum); {Покинуть критическую секцию}
begin
  asm cli end;
  if num<=maxCritical then
    criticalTable[num]:=0;
  asm sti end;

  if criticalTableWait[num]>0 then {Если кто-то ждет КС}
    switchThreads;
end;

Сама процедура переключения потоков написана с использованием ассемблерных вставок, поэтому можно увидеть момент переключения потоков от одного к другому с точностью до машинной команды:

procedure TimerHandler(flags,cs,ip,ax,bx,cx,dx,si,di,ds,es,bp:word); interrupt;
  {Следующие типизированные константы являются на самом деле
   статическими локальными переменными, которые размещаются в сегменте
   данных и сохраняют свои значения между вызовами процедуры}
  const ThreadNumber:byte=0;
  const NumPrev:byte=0;
  const tsoffset:word=0;
        mainSP:word=0;
        mainSS:word=0;
begin
  if not DisableHardwareEvents then begin
    asm pushf end;
    oldvec8;
    {Вызван старый обработчик прерывания от таймера. Он сбросил
     контроллер прерываний.}
  end;

  if preemptiveSwitch or DisableHardwareEvents then
    if (ThreadsRegistered>1) or (parallelStart) then begin
      {Зарегистрировано более одной задачи}
      asm cli end;

      if ParallelStart then begin
        {Если идет запуск процесса параллельных вычислений}
        StepCount:=0;
        asm
          mov       ParallelFinished,false {Сброс флага завершения}
          mov       mainsp,bp {Стек главного потока для возврата по окончании}
          mov       mainss,ss {исполнения параллельных потоков}
        end;
      end;

      inc(StepCount);

      if {ts[ThreadNumber].active and} not ParallelStart then begin
        {Сохранение состояния текущего (прерванного) потока.
        Не производится при взведенном флаге ParallelStart, т.к.
        предполагается, что в этом случае была прервана основная программа}

        {Смещение текущнго потока в таблице зарегистрированных потоков}
        tsoffset:=ThreadNumber*sizeof(TThreadStateWord);
        asm
          push      ds
             {нет гарантий, что при прерывании DS указывает
              на сегмент данных программы!}
          mov       ax,seg ts
          mov       es,ax
          mov       di,offset ts
          add       di,tsoffset

          mov       ax,ss
          mov       ds,ax
          mov       si,bp {ds:si указывает на регистры, сохраненные в стеке}

          cld
          mov       cx,12
      rep movsw     {сохранение состояния прерванного потока (кроме стека)}
          pop       ds

          {es:di продвинулось на 24 байта вперед и указывает на место
          для сохранения состояния стека}
          mov       ax,bp  {BP содержит состояние стека после 12 сохранений регистров}
          add       ax,12*2
          stosw  {SP задачи}
          mov       ax,ss
          stosw  {SS задачи}
        end;
      end;

      {Поиск следующей активной задачи}
      NumPrev:=ThreadNumber;
      repeat
        ThreadNumber:=(ThreadNumber+1) mod ThreadsRegistered;
      until (ThreadNumber=NumPrev) or TS[ThreadNumber].active;

      if ts[ThreadNumber].active and ((ThreadNumber<>NumPrev) or parallelStart)
      then begin
        {Восстановление новой задачи, если она отлична от прежней.
        Производится при взведенном флаге ParallelStart, даже если
        задача совпадает с якобы прежней, т.к. может
        оказаться, что единственной активной задачей в очереди является
        задача номер 0}
        tsOffset:=(ThreadNumber+1)*sizeof(TThreadStateWord) - 3;
        asm
          mov       dx,ds

          mov       ax,seg TS
          mov       ds,ax
          mov       si,offset TS
          add       si,tsOffset  {ds:si указывает на состояние активизируемого потока}
          std

          lodsw
          mov       ss,ax
          lodsw
          mov       sp,ax
          mov       bp,ax    {Переключение на стек нового потока}
          sub       bp,12*2

          {Подмена регистров в стеке на сосотояние нового потока. После
           возврата из процедуры будет исполняться код с той точки,
           где он был прерван при деактивации активизируемого сейчас
           потока}
          mov       cx,12
      @m1:
          lodsw
          push      ax
          loop      @m1
          cld

          mov       ds,dx
        end;
      end
      else if (not ts[Threadnumber].active) and (Threadnumber=NumPrev) then begin
        {Все задачи завершены}
        setintvec($8,@oldvec8);
        asm
          mov   parallelfinished,true
          mov   ax,mainss
          mov   ss,ax
          mov   bp,mainsp
          mov   sp,bp
        end;
      end;
      parallelstart:=false;
    end;

  DisableHardwareEvents:=false;
end;

Сама процедура скомпилирована с директивой interrupt, то есть является обработчиком прерывания. Которое может быть спровоцировано как аппаратно, так и программно вызовом int 08h, вот так:

procedure SwitchThreads;
begin
  if not parallelFinished then
    asm
      cli
      mov DisableHardwareEvents,1
      int 08h
      sti
    end;
end;

Добавим возможность выбора между вытесняющей и невытесняющей многозадачностью:

procedure ExecuteRegisteredThreads(useTimer:boolean);
begin
  parallelfinished:=false;
  parallelstart:=true;
  fillchar(criticalTable,sizeof(criticaltable),0);
  fillchar(criticalTableWait,sizeof(criticaltable),0);
  PreemptiveSwitch:=useTimer;
  getintvec($08,@oldvec8);
  setintvec($08,@TimerHandler);
  if not useTimer then SwitchThreads;
  repeat until parallelFinished;
  setintvec($08,@oldvec8);
end;

Ну и, собственно, работа с потоками:

procedure StopThread(ThreadNumber:byte);
begin
  ts[ThreadNumber].active:=false;
  SwitchThreads;
end;

procedure RunThread(ThreadNumber:byte);
begin
  ts[ThreadNumber].active:=true;
end;

procedure LoopBack;
begin
  repeat
    SwitchThreads; {Отдать управление другому}
  until false;
end;

function RegisterThread(ThreadAddr:pointer; StackSize:word):integer;
begin
  asm
    sti
    pushf
    cli
    pop  ax  {разрешить прерывания в запоминаемом состоянии флагов}
    mov  curflags,ax
  end;
  ts[ThreadsRegistered].ip_reg:=word(ThreadAddr);
  ts[ThreadsRegistered].cs_reg:=word(longint(ThreadAddr) shr 16);
  ts[ThreadsRegistered].ds_reg:=dseg;
  ts[ThreadsRegistered].flags:=curflags;

  getmem(ts[ThreadsRegistered].stack,StackSize);    {Стек задачи}
  stacks[ThreadsRegistered].sze:=StackSize;
  stacks[ThreadsRegistered].ptr:=ts[ThreadsRegistered].stack;
  inc(word(ts[ThreadsRegistered].stack),StackSize and $FFFE-2);
  {Стек нарастает "вниз", адресуется словами!}

  ts[ThreadsRegistered].active:=true;
  registerThread:=ThreadsRegistered;
  inc(ThreadsRegistered);
  if Threadsregistered>maxThread then runerror(0);
  asm
    sti
  end;
end;

procedure ClearThreads;
  var i:integer;
begin
  for i:=0 to threadsregistered-1 do
    freemem(stacks[i].ptr,stacks[i].sze);
  ThreadsRegistered:=0;
  fillchar(ts,sizeof(ts),0);
end;

Вот и всё! Наш планировщик готов.

Автор: AvrGavr