Разработка планировщика процессов в ОС MS-DOS

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Анализ проставленной задачи

2. Разработка процедур, реализующих процессы

3. Разработка процедур планировщика

4. Разработка процедур анализа клавиш

5. Организация интерфейса пользователя

6. Руководство пользователя

Заключение

Список литературы

Приложение

планировщик клавиша программа интерфейс



Введение

В данной курсовой работе разрабатывается планировщик процессов в ОС MS-DOS. Количество моделируемых процессов - 6. Планировщик вызывается добровольно. Переключение между процессами осуществляется по алгоритму "очередь с накапливаемыми приоритетами". Для отображения работы планировщика каждый процесс рисует линии. Выход из приложения выполняется комбинацией клавиш "Ctrl+D".

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



1. Анализ поставленной задачи

В соответствии с задание программа должна выполнять следующие действия:

1) Добровольный вызов планировщика

2) Переключение между процессами

3) Анализ нажатия клавиш Ctrl-D

Добровольный вызов планировщика базируется на идее перехвата прерывания 60h (пользовательское прерывание). Для этого в таблицу векторов прерываний записывается адрес процедуры планировщика процессов в формате сегмент:смещение. Вызов планировщика происходит после того как процесс полностью истратит отведенный ему квант времени. Т.е. процесс добровольно освободит машинный ресурс для следующего процесса и перейдет в режим ожидания.

Переключения между процессами выполняется по алгоритму "очередь с накапливаемыми приоритетами". Суть данного алгоритма в том, что каждый процесс имеет свой приоритет и переключение на него будет происходить с определенной вероятностью P. Чем ниже число приоритета, тем выше вероятность P. Данный алгоритм может быть реализован генератором случайных чисел (ГСЧ). Пусть A_n - массив размерностью 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)загружать параметры процесса

После того как процесс приостановится, но не завершится, его параметры изменятся и их необходимо сохранить. Для хранения параметров используется специальным образом организованная область памяти, такая как стек. Под каждый процесс выделяется некоторый объем памяти (кол-во адресного пространства). Таким образом стек условно делится на несколько стеков. Для того чтобы сохранить данные в стек, необходимо переместить указатель стека на дно стека текущего процесса. Затем занести в стек параметры и сохранить адрес вершины стека. Для загрузки параметров в указатель стека записывается сохраненный адрес вершины стека. Т.е. для стека каждого процесса необходимо минимум две переменные: 1 - хранит адрес дна стека, 2 - адрес вершины стека.

Кроме того для того чтобы загружать или сохранять словосостояние процессов необходимо в самом начале загрузить в стеки каждый из процессов.



2. Разработка процедур, реализующих процессы

Каждый процесс представляет собой процедуру (proc_1, proc_2, proc_3, proc_4, proc_5, proc_6), состоящую из адреса начала процедуры, команд процесса и команды возврата. Для визуального отображения работы планировщика каждый процесс должен закрасить 3200 пикселей в виде прямоугольника. Закрашивание пикселя выполняется с помощью функции 0ch прерывания 10h. Входные параметры:

1) Цвет линии (регистр AL);

2) Координата Y (регистр DX);

3) Координата Х (регистр СХ);

4) Видеостраница (регистр BH);

Если данная функция будет вызываться циклически, то кол-во итераций - квант времени. Изменяемыми параметрами являются значения регистров CX, AL, DX. После того как процесс завершится и передаст управление основной программе значения этих регистров должны быть сохранены в стек данного процесса.

Так как метка на каждый процесс содержит адрес, то для того чтобы вызвать нужную процедуру достаточно записать этот адрес в переменную proc_p. А для вызова процесса будет использоваться команда call [cs:proc_p]. Такой подход позволит избежать ветвлений из условных операторов для проверки некоторого параметра содержащего номер процесса.

Алгоритм работы процесса

1)Рг.BL:=50

2)Рг.AH:=0ch

3)Рг.BH:=1

4)выполнить прерывание 10h

5)Рг.СХ:=Рг.СХ-1

6) Рг.BL:=Рг.BL-1

7)сравнить BL c 0.

8)Если не равно 0, то перейти на метку 2

9)сравнить СХ с 0

10)если не равно 0, то перейти на метку 13

11)Рг.AL:=Рг.AL+1

12)Рг.СХ:=3200

3. Разработка процедур планировщика

Основными процедурами планировщика являются: сохранение словосостояния текущего процесса, загрузка выбранного процесса, переключение между процессами.

Для сохранения словосостояний процесса используется процедура 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_

1)Загрузить номер процесса в BX

2)Сравнить BX с 1h

3)Если BX = 1h, то переход на метку 14

4)Сравнить BX с 2h

5)Если BX = 2h, то переход на метку 15

6)Сравнить BX с 3h

7)Если BX = 3h, то переход на метку 16

8)Сравнить BX с 4h

9)Если BX = 4h, то переход на метку 17

10)Сравнить BX с 5h

11)Если BX = 5h, то переход на метку 18

12)Сравнить BX с 6h

13)Если BX = 6h, то переход на метку 19

14)Загрузить параметры в стек ss1 и перейти на метку 20

15) Загрузить параметры в стек ss2 и перейти на метку 20

16) Загрузить параметры в стек ss3 и перейти на метку 20

17) Загрузить параметры в стек ss4 и перейти на метку 20

18) Загрузить параметры в стек ss5 и перейти на метку 20

19) Загрузить параметры в стек ss6 и перейти на метку 20

20)Передать управление основной программе и переключиться на её стек

После каждой сохранения словосостояния адрес вершины стека записывается по адресу соответствующей переменной.

Для загрузки словосостояния процесса используется процедура load_. Работа данной процедуры идентична процедуре save_. Отличием будет то, что для работы со стеком переменные sp1, sp2, sp3, sp4, sp5, sp6 не нужны.

Процедура load_ вызывается перед вызовом процедуры по адресу proc_p. После завершения работы вызванной процедуры вызывается процедура save_.

Планировщик реализуется процедурой proc. Для записи адреса данной процедуры в таблицу векторов прерываний используются команды запрета и разрешения прерываний и каманды пересылки mov. При вызове прерывания 60h происходит переход на процедуру proc по адресу [cs:proc]. Данная процедура выполняет следующие действия

1) Инициализация генератора случайных чисел;

2) Генерация случайной величены;

3) Выборка из массива процессов по сгенерированному случайному индексу;

4) Запись адреса выбранного процесса;

5) Запись номера выбранного процесса.

В языке ассемблер отсутствует встроенный генератор случайных чисел. Поэтому он должен быть описан в виде процедуры. Для данной программы можно выбрать минимальный генератор Парка-Миллера. Данный генератор состоит из процедуры WIrandom, Wrandom и WIRandomInit. Полученное случайное число записывается в регистр EAX. Так как диапозон генерируемых чисел от 0 до 20 то можно будь использовать регистр AX.

Полученное число используется как индекс элемента массива. Используя индексную адресацию со смещением, значение из массива mass записывается в регистр DX. Необходимое значение хранится в младшем байте регистра.

Сравнивая значение в регистре DL выполняется переход по определенной метке, в которой в переменную proc_p записывается адрес процедуры процесса, а в переменную p номер процесса.

Метка main указывает на адрес начала основного кода программы в котором происходит вызов планировщика, загрузка и сохранение процесса. Вызов процедуры процесса, смена приоритетов, проверка нажатия Ctrl+D.

4. Разработка процедур анализа клавиш

Процедура анализа клавиш расположена в основном коде программы после метки main. Проверка нажатия клавиш происходит поэтапно:

1)проверка факта нажатия клавиши

2)проверка нажатия клавиши Ctrl

3)проверка нажатия клавиши 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. Гордеев А.В. Операционные системы: учебник для вузов. 2-е изд. - СПб.: Питер, 2006. - 420с.:ил.

3. Таненбаум Э. Современные операционные системы. 3-е издание. - СПб.: Питер, 2010, 1120 с.



Приложение А

use16

org 100h

jmp start

ss1 dw 100h dup (?)

ss2 dw 100h dup (?)

ss3 dw 100h dup (?)

ss4 dw 100h dup (?)

ss5 dw 100h dup (?)

ss6 dw 100h dup (?)

sp1 dw ?

sp2 dw ?

sp3 dw ?

sp4 dw ?

sp5 dw ?

sp6 dw ?

main_sp dw ?

proc_p dw ?

p dw ?

str1 db 'Dlya vihoda nazhmite Ctrl+D','$'

mass db 1,1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,5,5,6

random_seed dd ?

start:

mov ax,cs

mov ds,ax

mov ax,0

mov es,ax

cli

mov ax,proc

mov [es:60h*4],ax

mov [es:60h*4+2],cs

sti

mov ah,00h

mov al,13h

int 10h

mov ah,09h

mov DX,str1

int 21h

mov [main_sp],sp

mov sp,ss1

mov ax,1

mov dx,20

mov cx,3200

push ax

push dx

push cx

mov [sp1],sp

mov sp,ss2

mov ax,1

mov dx,40

mov cx,3200

push ax

push dx

push cx

mov [sp2],sp

mov sp,ss3

mov ax,1

mov dx,60

mov cx,3200

push ax

push dx

push cx

mov [sp3],sp

mov sp,ss4

mov ax,1

mov dx,80

mov cx,3200

push ax

push dx

push cx

mov [sp4],sp

mov sp,ss5

mov ax,1

mov dx,100

mov cx,3200

mov di,p

mov bl,5

mov [di],bl

push ax

push dx

push cx

mov [sp5],sp

mov sp,ss6

mov ax,1

mov dx,120

mov cx,3200

push ax

push dx

push cx

mov [sp6],sp

mov sp,[main_sp]

xor cx,cx

main:

push cx

int 60h

call load_

call [cs:proc_p]

call save_

pop cx

inc cx

cmp cx,100

jne main1

mov di,mass

mov cx,21

main4:

mov al,[di]

cmp al,6

jne main2

mov al,1

mov [di],al

jmp main3

main2:

inc al

mov [di],al

main3:

inc di

loop main4

main1:

mov ah,0bh

int 21h

cmp al,0

je main

mov ah,02h

int 16h

test al,00000100b

jz main

in al,60h

cmp al,20h

jne main

int 20h

proc:

call WRandomInit

call WIRandom

mov di,mass

add di,ax

mov dx,[di]

cmp dl,1

je m11

cmp dl,2

je m22

cmp dl,3

je m33

cmp dl,4

je m44

cmp dl,5

je m55

cmp dl,6

je m66

jmp m77

m11:

mov dx,proc1

mov [proc_p],dx

mov [p],1h

jmp m77

m22:

mov dx,proc2

mov [proc_p],dx

mov [p],2h

jmp m77

m33:

mov dx,proc3

mov [proc_p],dx

mov [p],3h

jmp m77

m44:

mov dx,proc4

mov [proc_p],dx

mov [p],4h

jmp m77

m55:

mov dx,proc5

mov [proc_p],dx

mov [p],5h

jmp m77

m66:

mov dx,proc6

mov [proc_p],dx

mov [p],6h

m77:iret

WRandom:

push edx ecx

mov eax, [random_seed]

xor edx,edx

mov ecx,12773

div ecx

mov ecx,eax

mov eax,16807

mul edx

mov edx,ecx

mov ecx,eax

mov eax,2836

mul edx

sub ecx,eax

xor edx,edx

mov eax,ecx

mov [random_seed],ecx

mov ecx,100000

div ecx

mov eax,edx

pop ecx edx

ret

WRandomInit:

push eax edx

rdtsc

xor eax,edx

mov [random_seed],eax

pop edx eax

ret

WIRandom:

push edx ecx

mov ecx,20

sub ecx,0

inc ecx

call WRandom

xor edx,edx

div ecx

mov eax,edx

add eax,0

pop ecx edx

ret

proc1:

mov bl,5

mproc1_3:

mov ah,0Ch

mov bh,1

mproc1_1:

int 10h

push cx

mov cx,2000

mproc1_2:

dec cx

cmp cx,0

jne mproc1_2

pop cx

dec cx

dec bl

cmp bl,0

jne mproc1_3

cmp cx,0

jne mproc1_4

inc al

mov cx,3200

mproc1_4:

ret

proc2:

mov bl,5

mproc2_3:

mov ah,0Ch

mov bh,1

mproc2_1:

int 10h

push cx

mov cx,2000

mproc2_2:

dec cx

cmp cx,0

jne mproc2_2

pop cx

dec cx

dec bl

cmp bl,0

jne mproc2_3

cmp cx,0

jne mproc2_4

inc al

mov cx,3200

mproc2_4:

ret

proc3:

mov bl,5

mproc3_3:

mov ah,0Ch

mov bh,1

mproc3_1:

int 10h

push cx

mov cx,2000

mproc3_2:

dec cx

cmp cx,0

jne mproc3_2

pop cx

dec cx

dec bl

cmp bl,0

jne mproc3_3

cmp cx,0

jne mproc3_4

inc al

mov cx,3200

mproc3_4:

ret

proc4:

mov bl,5

mproc4_3:

mov ah,0Ch

mov bh,1

mproc4_1:

int 10h

push cx

mov cx,2000

mproc4_2:

dec cx

cmp cx,0

jne mproc4_2

pop cx

dec cx

dec bl

cmp bl,0

jne mproc4_3

cmp cx,0

jne mproc4_4

inc al

mov cx,3200

mproc4_4:

ret

proc5:

mov bl,5

mproc5_3:

mov ah,0Ch

mov bh,1

mproc5_1:

int 10h

push cx

mov cx,2000

mproc5_2:

dec cx

cmp cx,0

jne mproc5_2

pop cx

dec cx

dec bl

cmp bl,0

jne mproc5_3

cmp cx,0

jne mproc5_4

inc al

mov cx,3200

mproc5_4:

ret

proc6:

mov bl,5

mproc6_3:

mov ah,0Ch

mov bh,1

mproc6_1:

int 10h

push cx

mov cx,2000

mproc6_2:

dec cx

cmp cx,0

jne mproc6_2

pop cx

dec cx

dec bl

cmp bl,0

jne mproc6_3

cmp cx,0

jne mproc6_4

inc al

mov cx,3200

mproc6_4:

ret

load_:

mov [main_sp],sp

mov bx,[p]

cmp bx,1h

je ml1

cmp bx,2h

je ml2

cmp bx,3h

je ml3

cmp bx,4h

je ml4

cmp bx,5h

je ml5

cmp bx,6h

je ml6

jmp ml7

ml1:

mov sp,[sp1]

pop cx

pop dx

pop ax

jmp ml7

ml2:

mov sp,[sp2]

pop cx

pop dx

pop ax

jmp ml7

ml3:

mov sp,[sp3]

pop cx

pop dx

pop ax

jmp ml7

ml4:

mov sp,[sp4]

pop cx

pop dx

pop ax

jmp ml7

ml5:

mov sp,[sp5]

pop cx

pop dx

pop ax

jmp ml7

ml6:

mov sp,[sp6]

pop cx

pop dx

pop ax

ml7:mov sp,[main_sp]

ret

save_:

mov [main_sp],sp

mov bx,[p]

cmp bx,1h

je ms1

cmp bx,2h

je ms2

cmp bx,3h

je ms3

cmp bx,4h

je ms4

cmp bx,5h

je ms5

cmp bx,6h

je ms6

jmp ms7

ms1:

mov sp,ss1

push ax

push dx

push cx

mov [sp1],sp

jmp ms7

ms2:

mov sp,ss2

push ax

push dx

push cx

mov [sp2],sp

jmp ms7

ms3:

mov sp,ss3

push ax

push dx

push cx

mov [sp3],sp

jmp ms7

ms4:

mov sp,ss4

push ax

push dx

push cx

mov [sp4],sp

jmp ms7

ms5:

mov sp,ss5

push ax

push dx

push cx

mov [sp5],sp

jmp ms7

ms6:

mov sp,ss6

push ax

push dx

push cx

mov [sp6],sp

ms7:mov sp,[main_sp]

ret



Приложение Б

Рисунок 1 - приоритет "1" у процесса 1

Рисунок 2 - приоритет "1" у процесса 4



Рисунок 3 - изменение приоритетов процесса. Первый процесс имеет больший приоритет чем второй.

Рисунок 4 - результат завершения работы программы



Приложение В

Блок-схема алгоритма работы программы



Блок-схема алгоритма планировщика



Блок-схема алгоритма загрузки параметров



Блок-схема алгоритма загрузки параметров

Размещено на Allbest.ru