Как стать автором
Обновить

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

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

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

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

Алгоритмы планирования

Существует несколько алгоритмов как вытесняющего, так и невытесняющего планировщика. Для начала давайте разберёмся какой механизм лучше? На первый взгляд очевидным кажется, что вытесняющая многозадачность всегда лучше невытесняющей. Но это не совсем так. Невытесняющая многозадачность даёт большую фору вытесняющей там, где необходимо, чтобы процессор постоянно был занят именно решением задач, а не их переключением, подготовкой, ожиданием. Пример — системы пакетной обработки данных. А во современные пользовательские ОС трудно представить без вытесняющей многозадачности (хотя до выхода Windows NT, все вполне обходились без неё).
Итак рассмотрим основные алгоритмы невытесняющей планировки:
  • FIFO
  • Самые короткие — вперёд!
  • Самые выполнившиеся вперёд!

Насчёт первого думаю всё итак понятно: первый пришёл — первый ушёл. Самые простой но, к сожалению не самый эффективный алгоритм, так как из-за решения чьего нибудь километрового интеграла одним потоком, другой будет час ждать очереди, чтобы сложить два числа.

Очевидный способ повысить эффективность — пропускать короткие потоки вперёд в очереди. Так, сначала выполнятся все потоки которым нужно посчитать 2*2, и только потом начнёт вычисляться тот километровый интеграл. Правда тут тоже имеются свои недостатки: например, длинный поток прервавшийся на ввод/вывод снова будет помещён в конец очереди.
Третий алгоритм исключает такую ситуацию: потоки которым на данный момент нужно меньше всего времени помещаются в начало очереди.
В системах пакетной обработки данных обычно используется три уровня планирования: в начале очередь заданий формируется в дисковой памяти (планирование памяти), оттуда потоки попадают в оперативную память, где по одному из вышеперечисленных алгоритмов тоже выстраиваются в очередь. Тут, возможно ситуация, когда процессов слишком много, тогда какие-то процессы возвращаются обратно на диск (планировщик доступа). Собственно, организацией доступа потоков к управлению процессором занимается третий планировщик — планировщик процессов.
Что очевидно — невытесняющая многозадачность не пригодна для операционных систем, в которых требуется моментальный отклик на любые действия пользователя. Кроме того, такой механизм требует от программиста понимания внутреннего устройства системы, и возлагает ответственность не только за работу программы, но и за работу всей системы в целом. Ведь никто не захочет пользоваться вашим продуктом, если он вешает систему на неделю, правда?
Рассмотрим несколько алгоритмов вытесняющей планировки:
  • Циклическая
  • С приоритетом по времени
  • С приоритетом по назначению

Первый алгоритм — прямой аналог очереди, а точнее это и есть очередь: первый пришёл — первый получил свой квант времени, снова встал в конец очереди. Всего один очевидный, но очень обидный минус — поток, который использует 1/10 кванта времени будет есть столько же процессорного времени сколько поток использующий квант целиком.
Второй алгоритм решает эту проблему: каждому потоку назначается приоритет обратно пропорциональный использованной доле кванта. Поток с большем приоритетом располагается в очереди раньше.
Третий алгоритм характерен для интерактивных (серверных) ОС, в которых во главе угла стоит обработка запросов пользователя. Приоритет потокам назначается в зависимости от выполняемой ими задачи. Тут, например, наивысший приоритет будет иметь обработка http запросов, чуть меньший — обработка команд оператора и т. д. При применении такого алгоритма возможно восполнение нечастой передачи управления потоку, выделением ему большего кванта времени. Так поток, который имеет меньший приоритет и потенциально дольше всего ожидающий в очереди получит больше всего процессорного времени.
Вытесняющая многозадачность не требует от программиста понимания тонкостей работы планировщика но тоже имеет подводные камни.

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

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

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

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

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

Поток X
Занять Ресурс(А)
Занять Ресурс(Б)

Отдать Ресурс(А)
Отдать Ресурс(Б)
Поток Y
Занять Ресурс(Б)
Занять Ресурс(А)

Отдать Ресурс(Б)
Отдать Ресурс(А)

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


Сладенькое

Ну и собственно то ради чего это всё писалось. Как уже было сказано код нашего планировщика будет выполнен на языке Turbo Pascal.
Механизм критических секций реализован в процедурах 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;


Так же необходимо описать сами процедуры регистрации, включения и остановки потоков. Если кому-то интересно — можно посмотреть в исходниках процедуры RegistrThread, RunThread, StopThread.
Вот и всё! Наш планировщик готов.
Исходники вместе примером многопоточной программы написаной под этот планировщих и досовским турбиком можно скачать здесь. Можно поиграться и посмотреть как по разному будут выполняться потоки при вытесняющей и невытесняющей многозадачности (процедура ExecuteRegisterThreads(true/false)), смоделировать ситуацию взаимной блокировки и убедиться в том, что она не всегда диагностируема (я однажды минуту ждал пока возникнет дедлок).
Запускать в системах новее Win98 советую из под DOSbox.
Теги:
Хабы:
+11
Комментарии 18
Комментарии Комментарии 18

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн