Разработка планировщика процессов в ОС MS-DOS
Содержание
Введение
. Анализ проставленной задачи
. Разработка процедур, реализующих
процессы
. Разработка процедур планировщика
. Разработка процедур анализа клавиш
. Организация интерфейса
пользователя
. Руководство пользователя
Заключение
Список литературы
Приложение
планировщик клавиша
программа интерфейс
Введение
В данной курсовой работе разрабатывается
планировщик процессов в ОС MS-DOS.
Количество моделируемых процессов - 6. Планировщик вызывается добровольно.
Переключение между процессами осуществляется по алгоритму "очередь с
накапливаемыми приоритетами". Для отображения работы планировщика каждый
процесс рисует линии. Выход из приложения выполняется комбинацией клавиш "Ctrl+D".
В ходе работы должен быть произведен анализ
поставленной задачи, составлен алгоритм работы программы, разработаны
процедуры, реализующие процессы, разработаны процедуры планировщика,
разработаны процедуры анализа клавиш.
. Анализ поставленной задачи
В соответствии с задание программа должна
выполнять следующие действия:
) Добровольный вызов планировщика
2) Переключение между процессами
) Анализ нажатия клавиш Ctrl-D
Добровольный вызов планировщика базируется на
идее перехвата прерывания 60h
(пользовательское прерывание). Для этого в таблицу векторов прерываний
записывается адрес процедуры планировщика процессов в формате сегмент:смещение.
Вызов планировщика происходит после того как процесс полностью истратит
отведенный ему квант времени. Т.е. процесс добровольно освободит машинный
ресурс для следующего процесса и перейдет в режим ожидания.
Переключения между процессами выполняется по
алгоритму "очередь с накапливаемыми приоритетами". Суть данного
алгоритма в том, что каждый процесс имеет свой приоритет и переключение на него
будет происходить с определенной вероятностью P.
Чем ниже число приоритета, тем выше вероятность P.
Данный алгоритм может быть реализован генератором случайных чисел (ГСЧ). Пусть An
- массив размерностью n,
где n - кол-во выборок
случайной величины. Также пусть ГСЧ генерирует числа от 1 до n
с вероятностью P=1/n.
Тогда каждый элемент массива может быть выбран случайно с одинаковой
вероятностью 1/n. Если
массив А заполнить числами от 1 до 6 так, что число m
повторяется (7-m) раз то
вероятность выборки случайного числа m
из массива А будет равна P=m/n.
Т.е. чем чаще повторяется число, тем выше вероятность выборки этого числа с
помощью ГСЧ. Для накопления приоритета через каждые K
выборок приоритет каждого процесса увеличивается. А именно A[i]:=A[i]+1.
Если A[i]
будет равен максимальному числу приоритета, то ему присваивается минимальное
число приоритета.
Для анализа нажатия клавиши необходимо проверить
тот факт, что клавиша была нажата. Если была нажата какая-либо клавиша, то
проводится анализ и проверка нажатых комбинаций. В случае если была нажата
комбинация Ctrl+D,
то программа завершает свою работу и передает управление MS-DOS.
Учитывая особенность функций ввода с клавиатуры в языке ассемблер проверка
нажатия клавиш будет производится 2 раза. Первый раз - проверка клавиши Ctrl,
второй - клавиши D. Для завершения
работы программы используется прерывание 20h.
Кроме того, планировщик должен:
)сохранять параметры процесса;
)загружать параметры процесса
После того как процесс приостановится, но не
завершится, его параметры изменятся и их необходимо сохранить. Для хранения
параметров используется специальным образом организованная область памяти,
такая как стек. Под каждый процесс выделяется некоторый объем памяти (кол-во
адресного пространства). Таким образом стек условно делится на несколько
стеков. Для того чтобы сохранить данные в стек, необходимо переместить
указатель стека на дно стека текущего процесса. Затем занести в стек параметры
и сохранить адрес вершины стека. Для загрузки параметров в указатель стека
записывается сохраненный адрес вершины стека. Т.е. для стека каждого процесса
необходимо минимум две переменные: 1 - хранит адрес дна стека, 2 - адрес
вершины стека.
Кроме того для того чтобы загружать или
сохранять словосостояние процессов необходимо в самом начале загрузить в стеки
каждый из процессов.
2. Разработка процедур, реализующих процессы
Каждый процесс представляет собой процедуру (proc_1,
proc_2, proc_3,
proc_4, proc_5,
proc_6), состоящую из
адреса начала процедуры, команд процесса и команды возврата. Для визуального
отображения работы планировщика каждый процесс должен закрасить 3200 пикселей в
виде прямоугольника. Закрашивание пикселя выполняется с помощью функции 0ch
прерывания 10h. Входные параметры:
) Цвет линии (регистр AL);
2) Координата Y
(регистр DX);
) Координата Х (регистр СХ);
) Видеостраница (регистр BH);
Если данная функция будет вызываться циклически,
то кол-во итераций - квант времени. Изменяемыми параметрами являются значения
регистров CX, AL,
DX. После того как
процесс завершится и передаст управление основной программе значения этих
регистров должны быть сохранены в стек данного процесса.
Так как метка на каждый процесс содержит адрес,
то для того чтобы вызвать нужную процедуру достаточно записать этот адрес в
переменную proc_p.
А для вызова процесса будет использоваться команда call
[cs:proc_p].
Такой подход позволит избежать ветвлений из условных операторов для проверки
некоторого параметра содержащего номер процесса.
Алгоритм работы процесса
)Рг.BL:=50
)Рг.AH:=0ch
)Рг.BH:=1
)выполнить прерывание 10h
)Рг.СХ:=Рг.СХ-1
) Рг.BL:=Рг.BL-1
7)сравнить BL
c 0.
)Если не равно 0, то перейти на метку 2
)сравнить СХ с 0
)если не равно 0, то перейти на метку 13
)Рг.AL:=Рг.AL+1
)Рг.СХ:=3200
. Разработка процедур планировщика
Основными процедурами планировщика являются:
сохранение словосостояния текущего процесса, загрузка выбранного процесса,
переключение между процессами.
Для сохранения словосостояний процесса
используется процедура save_.
Входным параметром данной процедуры является переменная р. Данная переменная
хранит адрес по которому в памяти записан номер приостановленного процесса.
Используя команды cmp
и jСС значение по
адресу p сравнивается с
числами 1h, 2h,
3h, 4h,
5h, 6h.
При совпадении с одним из чисел выполняется переход на метку ms1,
ms2, ms3,
ms4, ms5
или ms6. После
каждой из меток выполняются команды сохранения регистров CX,
AX, DX
в стек. После записи в стек адрес вершины стека записывается как значение по
адресу на который указывает одна из переменных sp1,
sp2, sp3,
sp4, sp5,
sp6. Данные
переменные содержат адрес по которому записан адрес вершины каждого из стеков
после записи.
Алгоритм процедуры save_
)Загрузить номер процесса в BX
)Сравнить BX с 1h
)Если BX
= 1h, то переход на
метку 14
)Сравнить BX с 2h
)Если BX
= 2h, то переход на
метку 15
)Сравнить BX с 3h
)Если BX
=
3h, то переход на
метку 16
)Сравнить BX с 4h
)Если BX
= 4h, то переход на
метку 17
10)Сравнить BX с 5h
)Если BX
= 5h, то переход на
метку 18
)Сравнить BX с 6h
)Если BX
= 6h, то переход на
метку 19
14)Загрузить параметры в стек ss1
и перейти на метку 20
) Загрузить параметры в стек ss2
и перейти на метку 20
) Загрузить параметры в стек ss3
и перейти на метку 20
) Загрузить параметры в стек ss4
и перейти на метку 20
) Загрузить параметры в стек ss6
и перейти на метку 20
)Передать управление основной программе и
переключиться на её стек
После каждой сохранения словосостояния адрес
вершины стека записывается по адресу соответствующей переменной.
Для загрузки словосостояния процесса
используется процедура load_.
Работа данной процедуры идентична процедуре save_.
Отличием будет то, что для работы со стеком переменные sp1,
sp2, sp3,
sp4, sp5,
sp6 не нужны.
Процедура load_
вызывается перед вызовом процедуры по адресу proc_p.
После завершения работы вызванной процедуры вызывается процедура save_.
Планировщик реализуется процедурой proc.
Для записи адреса данной процедуры в таблицу векторов прерываний используются
команды запрета и разрешения прерываний и каманды пересылки mov.
При вызове прерывания 60h
происходит переход на процедуру proc
по адресу [cs:proc].
Данная процедура выполняет следующие действия
) Инициализация генератора случайных
чисел;
2) Генерация случайной величены;
) Выборка из массива процессов по
сгенерированному случайному индексу;
) Запись адреса выбранного процесса;
) Запись номера выбранного процесса.
В языке ассемблер отсутствует встроенный
генератор случайных чисел. Поэтому он должен быть описан в виде процедуры. Для
данной программы можно выбрать минимальный генератор Парка-Миллера. Данный генератор
состоит из процедуры WIrandom,
Wrandom и WIRandomInit.
Полученное случайное число записывается в регистр EAX.
Так как диапозон генерируемых чисел от 0 до 20 то можно будь использовать
регистр AX.
Полученное число используется как индекс
элемента массива. Используя индексную адресацию со смещением, значение из
массива mass
записывается в регистр DX.
Необходимое значение хранится в младшем байте регистра.
Сравнивая значение в регистре DL
выполняется переход по определенной метке, в которой в переменную proc_p
записывается адрес процедуры процесса, а в переменную p
номер процесса.
Метка main
указывает на адрес начала основного кода программы в котором происходит вызов
планировщика, загрузка и сохранение процесса. Вызов процедуры процесса, смена
приоритетов, проверка нажатия Ctrl+D.
. Разработка процедур анализа клавиш
Процедура анализа клавиш расположена в основном
коде программы после метки main.
Проверка нажатия клавиш происходит поэтапно:
)проверка факта нажатия клавиши
)проверка нажатия клавиши Ctrl
)проверка нажатия клавиши D
Для проверки факта нажатия клавиши используется
функция 0bh прерывания
21h. Данная функция
проверяет кольцевой буфер клавиатуры. Если он содержит код нажатой/отжатой
клавиши, то флаг Z=1 иначе Z=0.
Поэтому использование данной функции позволит выполнять следующие, после
проверки, команды без ожидания нажатия клавиш. Если была нажата какая-либо
клавиша, то вызывается функция 02h
прерывания 16h. При нажатии на
клавишу Ctrl в регистр AL
помещается байт. Наличие 1 в третьем бите говорит о том, что была нажата
клавиша Ctrl. Если
нажата Ctrl, то
командой in из порта 60h
в регистр AL будет
помещен код следующей нажатой клавиши. При этом, независимо от того как долго
прошло времени между нажатием клавиши Ctrl
и следующей клавишей, в регистр AL
при считывании из порта 60h
будет помещен скан-код последней нажатой клавиши. Т.е. в случае комбинации D+Ctrl
программа не завершит свою работу и не передаст управление MS-DOS.
5. Организация интерфейса пользователя
Программа работает в графическом режиме 320х200,
256 цветов. Моделирование процессов происходит сразу после запуска программы. В
левом верхнем углу выводится текст "DLya
vihoda iz
programmi
nazhmite
Ctrl+D".
На рисунке 1 представлен интерфейс пользователя.
Рисунок 1 - интерфейс пользователя
6. Руководство пользователя
Программа является исполняемым com
файлом. Предназначена для моделирования работы планировщика, управляющего 6-ю
процессами с заранее заданными параметрами. Процессы переключаются добровольно.
Выбор следующего процесса осуществляется по алгоритму "очередь с
накапливаемыми приоритетами". Каждые 100 вызовов процессов их приоритеты
изменяются.
Системные требования:
IBM-PC
совместимый компьютер с процессором 80368,
4мб памяти,
видеоадаптер EGA,
ОС MS-DOS
3.3.
Для каждого процесса выделяется одинаковое
кол-во кванта времени и измеряется в циклах. Каждый процесс рисует 5 точек.
Каждая точка рисуется с задержкой в 2000 циклов.
После запуска программы ввод данных не
требуется.
Выход осуществляется нажатием комбинации клавиш Ctrl+D.
Заключение
В курсовой работе разработана программа
планировщика для 6 процессов. Каждый процесс выполняется с заданным
приоритетом. Визуально можно заметить что те процессы которые имеют более
низкий приоритет выполняются менее часто. Однако не смотря на то, что процесс
имеет самый низкий приоритет, ему гарантированно будет выделен квант времени.
Загрузка и сохранение словосостояние каждого
процесса выполняется не в самом прерывании 60h
а перед вызовом процесса и после. После того как процесс истратил свой квант
времени он не вызывает прерывание 60h.
Прерывание вызывается после проверки комбинации клавиш.
Одной из основных задач, решаемых в данной
курсовой работе, является переключение стеков и загрузка/сохранение параметров
процессов, так как вызов процедур сохранения и загрузки приводит к потере
данных если они были записаны в регистры. Для решения данной проблемы процедуры
загрузки и сохранения были помещены перед и после вызова процесса. Однако эти
процедуры должны выполняться непосредственно в процедуре планировщика. Для того
чтобы загрузка и сохранение выполнялись внутри планировщика можно
продублировать параметры в память. А после выполнения процесса обновить эти
параметры. Вызов процедур и остальные команды не затронут параметры.
Список литературы
1. Олифер В., Олифер Н. Сетевые
операционные системы: учебник для вузов. 2-е изд. - СПб.: Питер, 2009. -
669с.:ил.
. Гордеев А.В. Операционные
системы: учебник для вузов. 2-е изд. - СПб.: Питер, 2006. - 420с.:ил.
3. Таненбаум Э. Современные
операционные системы. 3-е издание. - СПб.: Питер, 2010,
1120 с.
Приложение А
100hstartdw 100h dup (?)dw 100h dup
(?)dw 100h dup (?)dw 100h dup (?)dw 100h dup (?)dw 100h dup (?)dw ?dw ?dw ?dw
?dw ?dw ?_sp dw ?_p dw ?dw ?db 'Dlya vihoda nazhmite Ctrl+D','$'db
1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,5,5,6_seed dd
?:ax,csds,axax,0es,axax,proc[es:60h*4],ax[es:60h*4+2],csah,00hal,13h10hah,09hDX,str121h[main_sp],spsp,ss1ax,1dx,20cx,3200axdxcx[sp1],spsp,ss2ax,1dx,40cx,3200axdxcx[sp2],spsp,ss3ax,1dx,60cx,3200axdxcx[sp3],spsp,ss4ax,1dx,80cx,3200axdxcx[sp4],spsp,ss5ax,1dx,100cx,3200di,pbl,5[di],blaxdxcx[sp5],spsp,ss6ax,1dx,120cx,3200axdxcx[sp6],spsp,[main_sp]cx,cx:cx60hload_[cs:proc_p]save_cxcxcx,100main1di,masscx,21:al,[di]al,6main2al,1[di],almain3:al[di],al:dimain4:ah,0bh21hal,0mainah,02h16hal,00000100bmainal,60hal,20hmain20h:WRandomInitWIRandomdi,massdi,axdx,[di]dl,1m11dl,2m22dl,3m33dl,4m44dl,5m55dl,6m66m77:dx,proc1[proc_p],dx[p],1hm77:dx,proc2[proc_p],dx[p],2hm77:dx,proc3[proc_p],dx[p],3hm77:dx,proc4[proc_p],dx[p],4hm77:dx,proc5[proc_p],dx[p],5hm77:dx,proc6[proc_p],dx[p],6h:iret:edx
ecxeax,
[random_seed]edx,edxecx,12773ecxecx,eaxeax,16807edxedx,ecxecx,eaxeax,2836edxecx,eaxedx,edxeax,ecx[random_seed],ecxecx,100000ecxeax,edxecx
edx:eax edxeax,edx[random_seed],eaxedx eax:edx
ecxecx,20ecx,0ecxWRandomedx,edxecxeax,edxeax,0ecx
edx:bl,5_3:ah,0Chbh,1_1:10hcxcx,2000_2:cxcx,0mproc1_2cxcxblbl,0mproc1_3cx,0mproc1_4alcx,3200_4::bl,5_3:ah,0Chbh,1_1:10hcxcx,2000_2:cxcx,0mproc2_2cxcxblbl,0mproc2_3cx,0mproc2_4alcx,3200_4::bl,5_3:ah,0Chbh,1_1:10hcxcx,2000_2:cxcx,0mproc3_2cxcxblbl,0mproc3_3cx,0mproc3_4alcx,3200_4::bl,5_3:ah,0Chbh,1_1:10hcxcx,2000_2:cxcx,0mproc4_2cxcxblbl,0mproc4_3cx,0mproc4_4alcx,3200_4::bl,5_3:ah,0Chbh,1_1:10hcxcx,2000_2:cxcx,0mproc5_2cxcxblbl,0mproc5_3cx,0mproc5_4alcx,3200_4::bl,5_3:ah,0Chbh,1_1:10hcxcx,2000_2:cxcx,0mproc6_2cxcxblbl,0mproc6_3cx,0mproc6_4alcx,3200_4:_:[main_sp],spbx,[p]bx,1hml1bx,2hml2bx,3hml3bx,4hml4bx,5hml5bx,6hml6ml7:sp,[sp1]cxdxaxml7:sp,[sp2]cxdxaxml7:sp,[sp3]cxdxaxml7:sp,[sp4]cxdxaxml7:sp,[sp5]cxdxaxml7:sp,[sp6]cxdxax:mov
sp,[main_sp]_:[main_sp],spbx,[p]bx,1hms1bx,2hms2bx,3hms3bx,4hms4bx,5hms5bx,6hms6ms7:sp,ss1axdxcx[sp1],spms7:sp,ss2axdxcx[sp2],spms7:sp,ss3axdxcx[sp3],spms7:sp,ss4axdxcx[sp4],spms7:sp,ss5axdxcx[sp5],spms7:sp,ss6axdxcx[sp6],sp:mov
sp,[main_sp]
ret
Приложение Б
Рисунок 1 - приоритет "1" у процесса 1
Рисунок 2 - приоритет "1" у процесса 4
Рисунок 3 - изменение приоритетов процесса.
Первый процесс имеет больший приоритет чем второй.
Рисунок 4 - результат завершения работы
программы
Приложение В
Блок-схема алгоритма работы программы
Блок-схема алгоритма планировщика
Блок-схема алгоритма загрузки параметров
Блок-схема алгоритма загрузки параметров
