1. Понятие процесса. Процесс как единица декомпозиции системы. Диаграмма состояний процесса с демонстрацией действий, выполняемых в режиме ядра. Планирование и диспетчеризация. Классификация алгоритмов планирования. Примеры алгоритмов планирования, соотнесенные с типами ОС. Процессы и потоки. Типы потоков.
2. Обеспечение монопольного доступа к разделяемым данным в задаче «читатели-писатели»: реализация на базе Win32 API (пример кодов лабораторной работы «читатели-писатели» для ОС Windows).
Понятие процесса. Процесс как единица декомпозиции системы
Процесс - это программа в стадии выполнения.
2 характерные черты процесса:
- Процесс владеет ресурсами (Resource Ownership).
- Процесс имеет защищенное виртуальное адресное пространство. Адресным пространством процесс владеет все время.
Время от времени процесс владеет следующими ресурсами: физическая память, каналы, устройства ввода/вывода, файлы и т.п.
По идеолгии Unix процесс часть времени выполняется в режиме задачи, и тогда он выполняет собственный код, а часть времени в режиме ядра и тогда выполняется реентерабельный код ОС (код чистых процедур) - код, который не изменяет сам себя.
Коды ОС = ресурсы ОС. Из чистых процедур данные выносятся в соответствующие таблицы. Код может находиться в разных точках одной процедуры. Он не изменяется. Разные процессы могут исполнить этот код.
Диаграмма состояний процесса с демонстрацией действий, выполняемых в режиме ядра
На скриншоте только схему!
Порождение – присваивание процессу строки в таблице процессов.
Готовность – попадание в очередь готовых процессов – получили все необходимые ресурсы.
Блокировка: в случае неполучения доступа к нужному ресурсу. Стадия "ожидания" получения доступа.
Завершение: освобождается выделенная память.
Вытеснение: при многозадачности процесс может вытесняться, если пришел более приоритетный процесс.
Планирование и диспетчеризация
Планирование - организация очереди процессов (постановка процесса в очередь).
Диспетчеризация - непосредственное выделение процессу процессорного времени.
Классификация алгоритмов планирования
- Без переключения / с переключением — переключение процессора на выполнение другого процесса, когда истек квант.
- С приоритетами / без приоритетов.
- С вытеснением / без вытеснением — возможно только в системах с приоритетным планированием. Вытеснение при появлении процесса с более высоким приоритетом.
Приоритеты:
- Статические - назначаются до выполнения и не меняются в процесса.
- Динамические - меняются в процессе выполнения.
Примеры алгоритмов планирования, соотнесенные с типами ОС
Алгоритмы планирования:
- FIFO - first in first out – без вытеснения, без приоритетов. После блокировки будет поставлен в конец очереди.
- SJF - shortest job first – кратчайшее задание первыми - меньшее количество процессорного времени. Приводило к тому, что задания с большим процессорным временем все время откладывались в конец очереди — бесконечное откладывание - ситуация, когда процесс никогда не получает необходимых для выполнения ресурсов (точнее, кванта времени). Возникает, когда диспетчер всегда отдаёт квант другому процессу, так как его приоритет больше.
- SRT - shortest remaining time (наименьшее оставшееся время). В этом алгоритме выполняющийся процесс может быть прерван (вытесняется с очереди на выполнение), если поступит процесс с меньшим оценочным временем выполнения, чем оставшееся время процесса текущего. Проблема - бесконечное откладывание.
- HRR - highest response rationext – наибольшее относительное время ответа. В этом алгоритме приоритет вычисляется по формуле: 𝑃 = (𝑡𝑤+𝑡𝑠)/𝑡𝑠, где 𝑡𝑠 – запрошенное время обслуживания. 𝑡𝑤 – время ожидания в очереди готовых процессов.
Процессы и потоки. Типы потоков
Поток - это непрерывная часть кода процесса, которая может выполняться с другими частями кода выполняемой программы. Поток становится единицей диспетчеризации в системе.
Свойства потока:
- Не имеет собстенного адресного пространства (выполняется в адресном пространстве процесса).
- Является единицей диспетчеризации. Именно потоку выделяется процессорное время. Поток начинает выполнять код. Значит, поток владеет счетчиком команд (регистр IP.)
Владельцем ресурсов является процесс. Поток владеет аппаратным контекстом и счетчиком команд.
Типы потоков:
- Потоки режима пользователя.
- Потоки режима ядра.
О потоках режима пользователя ядро ничего не знает. Должна быть специальная библиотека уровня пользователя (предоставляет функционал работы с потоками).
При переключении потоков (одного процесса) переключается только аппаратный контекст. При переключении потока другого процесса будет переключен полный контекст.
Обеспечение монопольного доступа к разделяемым данным в задаче «читатели-писатели»: реализация на базе Win32 API (пример кодов лабораторной работы «читатели-писатели» для ОС Windows)
Для реализации задачи были определены три счетчика: ждущих читателей, ждущих писателей, активных читателей, - одна логическая переменная (активный писатель) и два события с автосбросом, позволяющие известить ожидающие потоки о наступлении события. Проверка логической переменной и счетчика активных читателей позволяет обеспечить монопльный доступ процессов-писателей к разделяемым данным: процесс-писатель в очереди писателей ожидает событие CanWrite, после чего устанавливает значение логической переменной, равным 1. Новый процесс-читатель не сможет начать свою работу, пока работает процесс-писатель и событие CanRead не будет переведено в сигнальное состояние с помощью функции SetEvent(). Мьютекс включался в программу искусственно (в нем нет необходимости) для знакомства в этим средством взаимоисключения.
Примечание: если сделать событие CanWrite с ручным сбросом, resetevent переведет событие в занятое состояние и логическая переменная станет не нужной.
Псевдокод (Источник - https://github.com/qwertyKira00/Study/blob/OS/lab6/Lab_rab_6_wind.docx)
RESOURCE MONITOR;
var
active_readers : integer;
active_writer : logical;
can_read, can_write : conditional;
procedure star_read
begin
if (active_writer or turn(can_write)) then wait(can_read);
active_readers++; //инкремент читатетей
signal(can_read);
end;
procedure stop_read
begin
active_readers--; //декремент читателей
if (active_readers = 0) then signal(can_write);
end;
procedure start_write
begin
if ((active_readers > 0) or active_writer) then wait(can_write);
active_writer:= true;
end;
procedure stop_write
begin
active_writer:= false;
if (turn(can_read) then signal(can_read)
else signal(can_write);
end;
begin
active_readers:=0;
active_writer:=false;
end.
HANDLE CanWrite;
HANDLE CanRead;
HANDLE MUTEX;
LONG SHARED_RESOURCE = 0;
bool active_writer = false;
LONG active_readers = 0;
LONG writers_queue = 0; //quantity of writers waiting for CanWrite
LONG readers_queue = 0; //quantity of readers waiting for CanRead
HANDLE writerThreads[WRITERS], readerThreads[READERS];
int writerID[WRITERS], readerID[READERS];
int value = 0;
void Start_Write()
{
InterlockedIncrement(&writers_queue);
if (active_readers > 0 || active_writer)
WaitForSingleObject(CanWrite, INFINITE);
InterlockedDecrement(&writers_queue);
active_writer = true;
}
void Stop_Write()
{
active_writer = false;
if (WaitForSingleObject(CanRead, 0) != WAIT_OBJECT_0)
SetEvent(CanRead);
else
SetEvent(CanWrite);
}
DWORD WINAPI Write(LPVOID Id)
{
int id = *(int *)Id;
for (int i = 0; i < ITERATIONS_NUMBER; i++)
{
int delay = rand() % 200;
Start_Write();
value++;
printf("%sWriter with id = %d wrote %d. Delay = %d\n", GREEN, id, value, delay);
Stop_Write();
Sleep(delay);
}
}
void Start_Read()
{
InterlockedIncrement(&readers_queue);
if (active_writer || WaitForSingleObject(CanWrite, 0) == WAIT_OBJECT_0)
WaitForSingleObject(CanRead, INFINITE);
WaitForSingleObject(MUTEX, INFINITE);
InterlockedDecrement(&readers_queue);
InterlockedIncrement(&active_readers);
SetEvent(CanRead);
ReleaseMutex(MUTEX);
}
void Stop_Read()
{
InterlockedDecrement(&active_readers);
if (active_readers == 0)
SetEvent(CanWrite);
}
DWORD WINAPI Read(LPVOID Id)
{
int id = *(int *)Id;
for (int i = 0; i < ITERATIONS_NUMBER; i++)
{
int delay = rand() % 200;
Start_Read();
printf("%sReader with id = %d read %d. Delay = %d\n", WHITE, id, value, delay);
Stop_Read();
Sleep(delay);
}
}
Инициализация событий
CanWrite = CreateEvent(NULL, FALSE, FALSE, NULL);
CanRead = CreateEvent(NULL, FALSE, FALSE, NULL);
Я думаю, здесь каждый возьмет свой код. Но на всякий случай предупрежу, что CanWrite должен быть с ручным сбросом (у меня это не совсем верно реализовано). Такая реализация, как считает Рязанова, лучше. Слова Рязановой: Для писателей можно использовать событие с ручным сбросом. Тогда resetevent переведет событие в занятое состояние и логическая переменная вообще-то станет не нужной.