1. Процессы: взаимодействие параллельных процессов – монопольный доступ и взаимоисключение; программная реализация взаимоисключения – флаги, алгоритм Деккера, алгоритм Лампорта.
2. Защищенный режим: перевод компьютера в защищенный режим – реализация – пример кода из лабораторной работы.
Процессы: взаимодействие параллельных процессов – монопольный доступ и взаимоисключение
Необходимость монопольного доступа к разделяемым переменным при взаимодействии параллельных процессов обусловлена тем, что при немонопольном доступе возможно возникновение потерянного обновления (ситуация, когда при одновременном изменении одной переменной разными процессами теряются все изменения, кроме последнего). Рассмотрим данную ситуацию на примере:
Пусть есть 2 процесса: P1, P2.
Пусть у них имеются следующие участки кодов (myvar - разделяемая переменная):
| P1 | P2 |
|---|---|
| mov eax, myvar | mov eax, myvar |
| inc eax | inc eax |
| mov myvar, eax | mov myvar, eax |
При выполнении этих 2 процессов параллельно (или квазипараллельно) возможен следующий порядок команд:
| Команды P1 | eax | myvar | eax | Команды P2 |
|---|---|---|---|---|
| 0 | ||||
| mov eax, myvar | 0 | 0 | ||
| 0 | 0 | 0 | mov eax, myvar | |
| 0 | 0 | 1 | inc eax | |
| 0 | 1 | 1 | mov myvar, eax | |
| inc eax | 1 | 1 | 1 | |
| mov myvar, eax | 1 | 1 | 1 |
(myvar должен был стать 2, но стал 1)
Действия, подобные описанным, называются критическими. Секции кода - критическими секциями. Необходимо обеспечить монопольное использование разделяемых параллельными процессами ресурсов. Монопольный доступ к разделяемому ресурсу обеспечивается методами взаимоисключения, то есть если одни процесс находится в критической секции по некоторой разделяемой переменной, другой процесс не может войти в критическую секцию по той же переменной, пока 1 не освободит её.
Способы взаимоисключения:
- Программный
- Аппаратный
- Семафоры
- Мониторы
Программная реализация взаимоисключения – флаги
P1:
while (1)
begin
while (flagp2); //цикл активного ожидания
flagp1 = 1;
CR1; // критическая секция
flagp1 = 0;
PR1;
end;
P2:
while (1)
begin
while (flagp1);
flagp2 = 1;
CR2;
flagp2 = 0;
PR2;
end;
//объявления
flagp1, flagp2: logical;
//начальные установки
flagp1 = 0;
flagp2 = 0;
parbegin;
P1; P2;
parend;
Способ не работает, также теряются единицы. Пусть процесс устанавливает флаг до проверки.
P1:
while (1)
begin
flagp1 = 1;
while (flagp2); //бесконечный цикл, так как в паузу устанавливается флаг
CR1;
flagp1 = 0;
PR1;
end; //Dead lock - каждый процесс будет находиться в цикле
//Никто не продолжит свое выполнение
P2:
while (1)
begin
flagp2 = 1;
while (flagp1);
CR2;
flagp2 = 0;
PR2;
end;
//объявления
flagp1, flagp2: logical;
//начальные установки
flagp1 = 0;
flagp2 = 0;
parbegin;
P1; P2;
parend;
Не могут выполняться, оба ждут освобождения (тупиковая ситуация). Проблемы:
- Бесконечное откладывание.
- Можно попасть в тупиковую ситуацию, каждый процесс ждёт освобождения флага другого процесса и ни один из них не может продолжить свою работу (dead lock).
- Захват и освобождение одних и тех же ресурсов (trashing - процесс не может загрузить в память все рабочее множество и все время подгружает одни и те же страницы).
Алгоритм Деккера
Эту проблему удалось решить голландскому математику Деккеру, алгоритм был назван алгоритм Деккера. Решение разработано только для двух параллельных процессов. Деккер ввёл флаги и дополнительную переменную que, которую назвал «чья очередь».
flagp1 , flagp2: logical;
que:int;
P1:
while (1)
begin
flagp1 = 1;
while(flagp2)
begin
if (que == 2) then
begin
flagp1 = 0;
while(que == 2);
flagp1 = 1;
end
end
CR1;
flagp1 = 0;
que = 2;
PR1;
end; //Флаг сбрасывается. и указывается, что в критич.секцию
//заходит другой процесс
P2:
while (1)
begin
flagp2 = 1;
while(flagp1)
begin
if (que == 1) then
begin
flagp2 = 0;
while(que == 1);
flagp2 = 1;
end
end
CR2;
flagp2 = 0;
que = 1;
PR2;
end;
//объявления
flagp1, flagp2: logical;
que: int;
//начальные установки
flagp1 = 0;
flagp2 = 0;
que = 1;
parbegin;
P1; P2;
parend;
Такое решение избавляет от dead lock, потому что процессы сбрасывают свои флаги. Так как процесс передает активность другому процессу (с помощью переменной que), исключается вечное откладывание.
Алгоритм Лампорта
Алгоритм bakery(булочная). Решает проблему критической секции N потоков. Каждому клиенту выдается листок с номером, новому – с большим номером. Когда продавец освобождается, то обслуживает клиента с меньшим номером. Бывает, что одновременно приходят 2 клиента, в этом случае им выдаются одинаковые номера, но первым будет обслужен клиент с меньшим номером паспорта, к примеру. Два процесса получат одинаковые номера, но учитываться будет их идентификатор => возникает необходимость в дополнительных данных.
1. var choosing: shared array [0 .. n - 1] of boolean;
2. number: shared array [0 .. n - 1] of integer;
3. repeat
4. choosing[i] := true;
5. number[i] := max(number[0], .., number[n - 1]) + 1;
6. choosing[i] := false;
7. for j := 0 to n - 1 do begin
8. while choosing[j] do /*nothing*/;
9. while(number[j] <> 0) and
10. (number[j], j) < (number[i], i) do
11. /*nothing*/;
12. end;
13. /*critical section*/
14. number[i] := 0;
15. /*remainder section*/
16. until false;
1 и 2 определяет массивы флагов и целых чисел.
choosing позволяет нам определять критическую секцию choosing[i]=true, если процесс p[i] выбирает номер.
Номер, которые использует p[i] для входа в критический участок, это number[i]. number[i]=0, если p[i] не пытается войти в свой критический участок.
4,5,6 строки показывают, что процесс выбирает номер и устанавливает свой флаг choosing[i] в true. После этого он пытается получить уникальный номер, максимальный среди выданных +1, если это возможно. Получив номер, он сбрасывает свой флаг (строчка 6).
7-12 определяет какой процесс входит в критический участок. Процесс p[i] ждет пока имеется процесс, у которого меньший номер, для того чтобы войти в критический участок. Если 2 процесса имеют одинаковые номера, то выбирается процесс с меньшим идентификатором.
Запись 10 – лексикографический порядок ((a,b) < (c,d), если (a<c) или (a=c, b<d) ) Также необходимо обратить внимание на то, когда 2 процесса выбирают номер, то 2 процесс будет ждать, пока 1 не сделает (строчка 8).
14 строка – процесс p[i] больше не заинтересован во входе в критический участок.
Защищенный режим. Перевод компьютера в защищенный режим - реализация - пример кода из лабораторной работы
Защищенный - 32-разрядный режим => 32-разрядный регистр, 32-разрядная шина адреса. В отличие от реального режима, здесь доступно 4 Гб памяти. В защищенном режиме 4 уровня защиты (4 кольца привилегий). Ядро ОС находится на 0‐м уровне. Пользовательские приложения находятся на 3-ем уровне. Используется страничная организация памяти (повышает уровень защиты задач друг от друга и эффективность их выполнения). Объем адресуемой памяти – 4 Гб.
Защищенный режим (protected mode) - режим процессора, в котором действуют механизмы защиты, сегментная адресация с дескрипторами и селекторами и страничная адресация (Зубков, стр. 599).
- Специальный режим V86 - это задача, исполняющаяся в защищенном режиме, в которой флаг VM регистра EFLAGS равен единице. Внутри задачи процессор ведет себя так, как если бы он находился в реальном режиме, за исключением того, что пре- рывания и исключения передаются обработчикам защищенного режима вне ее (кроме случая, когда используется карта перенаправления прерываний) (Зубков, стр. 527). В этом режиме просиходит дизассемблирование.
- Многозадачный режим с поддержкой виртуальной памяти = выполняется много задач.
В защищенном режиме используется сегментная адресация, поэтому, чтобы обращаться к сегментам памяти и обработчикам прерываний, необходимо хранить информацию о сегменте памяти/обработчике прерываний в дескрипторе, формат которого соответствует структуре (в примере descr/idescr).
Структура дескриптора сегмента памяти
descr struc
limit dw 0
base_l dw 0
base_m db 0
attr_1 db 0
attr_2 db 0
base_h db 0
descr ends
Структура дескриптора прерывания (шлюза)
idescr struc
offs_l dw 0
sel dw 0
cntr db 0
attr db 0
offs_h dw 0
idescr ends
GDT (глобальная таблица дескрипторов сегментов памяти)
gdt_null descr <>
gdt_code16 descr <code16_size-1,0,0,98h>
gdt_code32 descr <code32_size-1,0,0,98h,40h>
gdt_data32 descr <data_size-1,0,0,92h,40h>
gdt_stack32 descr <stack_size-1,0,0,92h,40h>
gdt_size = $ - gdt_null
Получение и запись линейных адресов в дескрипторы сегментов (остальные аналогично)
; Записываем линейные адреса в дескрипторы сегментов
mov ax, code16
shl eax, 4
mov word ptr gdt_code16.base_l, ax
shr eax, 16
mov byte ptr gdt_code16.base_m, al
mov byte ptr gdt_code16.base_h, ah
Получение адреса сегмента, где лежит глобальная таблица дескрипторов
mov ax, data32
;Сдвиг на полбайта, чтобы получить базовый линейный адрес
shl eax, 4
; Начальный адрес сегмента + смещение gdt_null = линейный адрес GDT
add eax, offset gdt_null
Загрузка регистра глобальной таблицы дескрипторов GDTR
mov word ptr pdescr, gdt_size-1
mov dword ptr pdescr+2, eax
lgdt fword ptr pdescr ;Привилегированная команда
Загрузка смещений обработчиков прерываний в шлюзы
lea eax, es:except_1
mov idescr_0_12.offs_l, ax
shr eax, 16
mov idescr_0_12.offs_h, ax
; Обрабатывается отдельно
lea eax, es:except_13
mov idescr_13.offs_l, ax
shr eax, 16
mov idescr_13.offs_h, ax
lea eax, es:except_1
mov idescr_14_31.offs_l, ax
shr eax, 16
mov idescr_14_31.offs_h, ax
Сохранение масок
in al, 21h
mov mask_master, al
in al, 0A1h
mov mask_slave, al
Перепрограммирование ведущего контроллера на новый базовый вектор (32)
mov al, 11h
out 20h, al
mov al, 32 ; это новый базовый вектор
out 21h, al
mov al, 4
out 21h, al
mov al, 1
out 21h, al
Открытие линии А20 (если не откроем, то будут битые адреса, будет пропадать 20ый бит)
in al, 92h
or al, 2
out 92h, al
Запрет аппаратных прерываний (маскируемых)
CLI
Загрузка адреса и размера IDT в IDTR
lidt fword ptr ipdescr
Сам переход в защищенный режим (Установка бита защищенного режим в управляющем регистре CR0)
MOV EAX, CR0
OR EAX, 1
MOV CR0, EAX
Искусственно сконструированная команда дальнего перехода для смены CS:IP
db 0EAh
dw offset pm_start
dw code32s ;селектор - номер дескриптора в таблице дескрипторов
;JMP 16:offset pm_start
Запрет немаскируемых прерываний
mov al, 80h
out 70h, al