Контекст и дескриптор процесса
На протяжении существования процесса его выполнение может быть многократно прервано и продолжено. Для того чтобы возобновить выполнение процесса, необходимо восстановить состояние его операционной среды.
Состояние операционной среды отображается состоянием регистров и программного счетчика, режимом работы процессора, указателями на открытые файлы, информацией о незавершенных операциях ввода-вывода, кодами ошибок выполняемых данным процессом системных вызовов и т.д. Эта информация называется контекстом процесса.
Кроме этого, операционной системе для реализации планирования процессов требуется дополнительная информация: идентификатор процесса, состояние процесса, данные о степени привилегированности процесса, место нахождения кодового сегмента и другая информация. В некоторых ОС (например, в ОС UNIX) информацию такого рода, используемую ОС для планирования процессов, называют дескриптором процесса.
Дескриптор процесса по сравнению с контекстом содержит более оперативную информацию, которая должна быть легко доступна подсистеме планирования процессов.
Контекст процесса содержит менее актуальную информацию и используется операционной системой только после того, как принято решение о возобновлении прерванного процесса.
Очереди процессов представляют собой дескрипторы отдельных процессов, объединенные в списки.
Таким образом, каждый дескриптор содержит, по крайней мере, один указатель на другой дескриптор, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать процессы, переводить процессы из одного состояния в другое.
Программный код только тогда начнет выполняться, когда для него операционной системой будет создан процесс. Создать процесс - это значит:
- создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст;
- включить дескриптор нового процесса в очередь готовых процессов;
- загрузить кодовый сегмент процесса в оперативную память или в область свопинга.
1.1.2. Алгоритмы планирования процессов
В однозадачной ОС используется группа алгоритмов «без предпочтения». К ним относятся алгоритмы: FIFO (первый пришел, первый обслужен), SJF (кратчайшее задание – первым), HRN (модификация алгоритма SJF, учитывающая длительность ожидания задания в очереди).
Планирование процессов в мультипрограммных ОС включает в себя решение следующих задач:
- определение момента времени для смены выполняемого процесса;
- выбор процесса на выполнение из очереди готовых процессов;
- переключение контекстов «старого» и «нового» процессов.
Первые две задачи решаются программными средствами, а последняя - в значительной степени аппаратно.
Существует множество различных алгоритмов планирования процессов, по разному решающих вышеперечисленные задачи, преследующих различные цели и обеспечивающих различное качество мультипрограммирования. Среди этого множества алгоритмов рассмотрим подробнее две группы наиболее часто встречающихся алгоритмов: алгоритмы, основанные на квантовании, и алгоритмы, основанные на приоритетах.
В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:
- процесс завершился и покинул систему,
- произошла ошибка,
- процесс перешел в состояние ОЖИДАНИЕ,
- исчерпан квант процессорного времени, отведенный данному процессу.
Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Граф состояний процесса, изображенный на рисунке 1.1, соответствует алгоритму планирования, основанному на квантовании.
Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По разному может быть организована очередь готовых процессов: циклически, по правилу «первый пришел – первый обслужился» (FIFO) или по правилу «последний пришел – первый обслужился» (LIFO).
Для обеспечения более «справедливого» распределения времени процессора используются многоуровневые очереди с обратными связями. Новый процесс входит в сеть очередей с конца верхней очереди. Он перемещается по этой очереди, реализующей принцип FIFO, пока не получит в свое распоряжение ЦП. Если задание завершается или освобождает ЦП, чтобы подождать завершения операции ввода-вывода или наступления некоторого события, то оно, это задание, выходит из сети очередей. Если выделенные квант времени истекает до того, как процесс добровольно освободит ЦП, этот процесс помещается в конец следующей очереди более низкого уровня. Этот процесс в следующий раз получит в свое распоряжение ЦП, когда он достигнет начала данной очереди, если при этом не будет ожидающих в первой очереди. Если данный процесс будет продолжать использовать полный квант времени, предоставляемый на каждом уровне, он продолжит переход в конец очереди следующего нижележащего уровня. Обычно в системе предусматривается некоторая очередь самого нижнего уровня, которая реализует принцип циклического обслуживания и в которой данный процесс циркулирует до тех пор, пока не завершится. Во многих структурах многоуровневых очередей с обратными связями квант времени, предоставляемый данному процессу при переходе в каждую очередь более низкого уровня, увеличивается.
Другая группа алгоритмов использует понятие «приоритет» процесса. Приоритет – это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии.
Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими.
Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты.
В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности. На рисунке 4.2 показаны графы состояний процесса для алгоритмов с относительными (а) и абсолютными (б) приоритетами.
Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетами процессов.
Рисунок 1.2 – Графы состояний процессов в системах
а) с относительными приоритетами; б) с абсолютными приоритетами
1.1.3. Вытесняющие и невытесняющие алгоритмы планирования
Существует два основных типа процедур планирования процессов - вытесняющие (preemptive) и невытесняющие (non-preemptive).
Non-preemptive multitasking - невытесняющая многозадачность - это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.
Preemptive multitasking - вытесняющая многозадачность - это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается планировщиком операционной системы, а не самой активной задачей.
Понятия preemptive и non-preemptive иногда отождествляются с понятиями приоритетных и бесприоритетных дисциплин, что совершенно неверно, а также с понятиями абсолютных и относительных приоритетов, что неверно отчасти. Вытесняющая и невытесняющая многозадачность - это более широкие понятия, чем типы приоритетности. Приоритеты задач могут как использоваться, так и не использоваться и при вытесняющих, и при невытесняющих способах планирования. Так в случае использования приоритетов дисциплина относительных приоритетов может быть отнесена к классу систем с невытесняющей многозадачностью, а дисциплина абсолютных приоритетов - к классу систем с вытесняющей многозадачностью. А бесприоритетная дисциплина планирования, основанная на выделении равных квантов времени для всех задач, относится к вытесняющим алгоритмам.
Основным различием между preemptive и non-preemptive вариантами многозадачности является степень централизации механизма планирования задач. При вытесняющей многозадачности механизм планирования задач целиком сосредоточен в операционной системе, и программист пишет свое приложение, не заботясь о том, что оно будет выполняться параллельно с другими задачами. При этом операционная система выполняет следующие функции: определяет момент снятия с выполнения активной задачи, запоминает ее контекст, выбирает из очереди готовых задач следующую и запускает ее на выполнение, загружая ее контекст.
При невытесняющей многозадачности механизм планирования распределен между системой и прикладными программами. Прикладная программа, получив управление от операционной системы, сама определяет момент завершения своей очередной итерации и передает управление ОС с помощью какого-либо системного вызова, а ОС формирует очереди задач и выбирает в соответствии с некоторым алгоритмом (например, с учетом приоритетов) следующую задачу на выполнение. Такой механизм создает проблемы, как для пользователей, так и для разработчиков.
Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например, на форматирование диска, пользователь не может переключиться с этой задачи на другую задачу, например, на текстовый редактор, в то время как форматирование продолжалось бы в фоновом режиме. Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина завершит свою задачу.
Поэтому разработчики приложений для non-preemptive операционной среды, возлагая на себя функции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить "дружественное" отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая им управление. Крайним проявлением "недружественности" приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет зависшую задачу с выполнения.
Однако распределение функций планировщика между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент времени отдачи управления, то при этом исключаются нерациональные прерывания программ в "неудобные" для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит эти данные. Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу.
1.1.4. Модель процесса и функции подсистемы управления процессами учебной операционной системы
В качестве модели процесса учебной операционной системы будем использовать поток исоплнения (нить), которому в виртуальной машине Java соответствует класс Thread. Как и в реальных ОС мы будем различать дескриптор и контекст процесса.
Дескриптор должен, как минимум, содержать следующую информацию:
1) PID (Process ID) – идентификатор процесса. Целое число в диапазоне от 1 до 232. Будем считать, что присвоение идентификаторов происходит по возрастающий, т. е. идентификатор нового процесса больше, чем идентификатор процесса, созданного перед ним. Процесс, обеспечивающий функции ядра ОС имеет PID равный 0;
2) PPID - идентификатор родительского процесса Parent Process ID. Целое число в диапазоне от 1 до 232. Идентификатор процесса, породившего данный процесс;
3) STATE - код состояния процесса. 1 – готов, 2 – ожидание ресурса, 4 – временно приостановлен, 8 – завершен, 16 – выполнение;
4) PRIOR - базовый приоритет процесса (целое число от 1 до 32). Определяет минимальный уровень приоритета, который может быть присвоен процессу;
6) CONTEXT - указатель на контекст процесса.
Под контекстом (Context) процесса учебной операционной системы будем понимать объект, соответсвующий потоку исполнения. В реальных операционных системах функция создания процесса exec (CreateProcess), как минимум, должна содержать путь к исполняемому файлу. В нашей модели вместо имени исполняемого файла мы будем указывать один из трех фиксированных типов процесса. Например, процесс первого типа выводит символ в окно терминала, процесс второго типа выводит заданное сообщение, а процесс третьего типа - текущее время. Действия, которые выполняют модели процессов определяются вариантом задания.
Во время жизни модели процессов с некоторой вероятностью обращаются к восьми критическим ресурсам системы (аналог Mutex). Если ресурс захвачен одним из процессов, конкурирующий процесс переводится операционной системой в состояние ожидания до тех пор, пока ресурс не освободится. При освобождении ресурса все процессы, ожидающие ресурс переводятся в состояние готовности.
Подсистема управления процессами учебной ОС включает в себя: список процессов и внутрисистемную функцию void mainkernel() (для диспетчеризации процессов) и набор API-функции для управления процессами:
- int CreateProcess(int ProcType, int baseprior) - данная функция создает поток исполнения, заданного переменной ProcType. Параметр Context - указатель на структуру Context, а baseprior задает абсолютный приоритет процесса;
- void MyResume(int pid) - запускает модель процесса с дескриптором pid на выполнение;
- void MySuspend(int pid) - приостанавливает выполнение процесса с дескриптором pid;
- void MyTerminate(int pid) - завершает выполнение процесса;
- int MyWaitResource(int pid, int nr) – информирует подсистему управления процессами, что процесс с идентификатором pid просит доступ к критическому ресурсу nr;
- void MyFreeResource(int nr) – информирует подсистему управления процессами, что процесс с идентификатором pid просит доступ к критическому ресурсу nr.
Внутрисистемная функция void mainkernel() выполняет обязанности планировщика (т.е. выполняет выбор процесса из списка готовых для перевода в состояние выполнения, уничтожает завершившиеся процессы, а также распределяет процессорное время). Эта функция выполняется в бесконечном цикле до завершения работы программы. Способ планирования и вид мультизадачности определяется вариантом задания.
1.1.5. Рекомендации по реализации подсистемы управления процессами
Модель операционной системы.Для создания модели операционной системы предлагается разработать класс OS, в интерфейс которого входят вышеперечисленные API-функции подсистемы управления процессами.
class OS {
OS() {...};
public int CreateProcess(int ProcType, int baseprior)
{
...
return pid;
}
public void MyResume(int pid) {
...
}
public void MySuspend(int pid){
...
} ...
}
}
В состав класса OS необходимо включить информацию об очереди процессов, ожидающих времени процессора. Как известно, процесс в реальных ОС, представляется двумя информационными структурами: дескриптором и контекстом. В нашей модели в состав дескриптора необходимо, как минимум, включить:
class Description {
int pid; //Уникальный идентификатор процесса
int state; //Состояние процесса
int prior; //Приоретет
MyProcess context; //Указатель на конетекст процесса
...
}
Очередь дескрипторов рекомендуется реализовать одним из классов, реализующим интерфейс Collection или List, например ArrayList.
Модель процесса.Как следует из предыдущего раздела, в учебной операционной системе модель процесса представляет собой поток, который в в вечном цикле выполняет действия, определенные вариантом задания, а также случайным образом вызывает API-функции управления процессами.
Приведем пример описания класса потока, который выводит в окно терминала текущее время:
class NTimerThread implements Runnable{
Thread t;
NTimerThread () //Конструктор класса
{
t = new Thread(this); //создаем новый поток
t.start(); //и запускаем его
}
public void run() //определяем действия, которые выполняет поток
{
try
{
while (true) //Поток выполняется в вечном цикле
{
Date d=new Date(); //Получаем текущую дату
System.out.println(d.toString()); //Переводим ее в строку
Thread.sleep(1000); //Приостанавливаем себя на секунду, чтобы дать возможность
//отработать другим и вывести следующее время ровно через секунду
}
} catch (InterruptedException e) {
System.out.println("Thread");
}
}
};
Данная модель процесса не имеет точек соприкосновения с моделью подсистемы управления процессами. Для реализации взаимодействия необходимо использовать вышеописанные функции управления процессами. Например, с вероятностью 0.2 поток-модель завершает свою работу:
while (true) //Поток выполняется в вечном цикле
{
Random rand= new Random();
Date d=new Date(); //Получаем текущую дату
System.out.println(d.toString()); //Переводим ее в строку
Thread.sleep(1000); //Приостанавливаем себя на секунду, чтобы дать возможность
//отработать другим и вывести следующее время ровно через секунду
if (rand.nextDouble()<0.2) os.myterminate(pid); //С вероятностью 0.2 завершаем себя с помощью
//API нашей операционной системы }>
Здесь os - объект типа OS, а pid - дескриптор модели процесса. Для того чтобы, модель процесса могла знать свой идентификатор, а планировщик процессов мог управлять процессами вне зависимости от их типов, предлагается использовать универсальный абстрактный класс для описания сущности "модел процесса (контекст)":
abstract class MyProcess implements Runnable
{
int pid;
Thread t;
...
public void resume()
{
t.start();
}
public void suspend()
{
t.suspend();
}
public void terminate()
{
t.stop();
}
...
}
Тогда,
class NThread extends MyProcess implements Runnable{
OS os;
NThread (OS myos, int apid){
os=myos;
pid=apid;
t = new Thread(this);
...
}
Планировщик процессов.В состав подсистемы управления процессами должна входить, функция void MainKernel (), которая реализует заданный вариантом задания алгоритм планирования процессов и распределяет процессорное время. Эта функция запускается автоматически после старта модели ОС и выполняется в вечном цикле до завершения работы. Рекомендуется помещать данную функцию в отдельный поток исполнения.Примерный алгоритм работы функции mainkernel
1) Выбрать из очереди готовых процессов процесс, которому будет предоставлен квант машинного времени
2) Перевести процесс в состояние выполнения. Для этого использовать метод MyProcess. resume()
3) Предоставить квант времени для исполнения процесса (можно использовать Threed.sleep() для приостановки потока);
4) Остановить выбранный процесс по истечению его кванта, например использоватьMyProcess. suspend();
5) Проверить состояние процесса. Если он завершен – удалить дескриптор процесса из очереди.
6) Вызвать процедуру планирования для выбора очередного процесса, которому будет предоставлено машинное время. Перейти к п.1.
Интерфейс пользователя.Интерфейсная часть должна обеспечивать возможность создания новых процессов, вывод списка функционирующих процессов, приостановки и завершения процессов.
При реализации интерфейса необходимо, как минимум, разделить потоки сообщений, генерируемых моделями процессов и потоки команд управления операционной системой. В связи с этим, предлагается в потоках исполнения использовать вывод в консоль (System.out.println()).Интерфейс управления реализовать в виде фрейма
Рисунок 1.3 – Интерфейс подсистемы управления процессами
В командной строке пользователь модели вводит команду управления. Рекомендуется, как минимум, реализовать следующие команды:
1) Создание нового процесса: exec T P , где T - тип процесса, P - приоритет (Например, exec 1 6).
2) Уничтожение существующего процесса: kill PID, где PID - идентификатор уничтожаемого процесса .
3) Вывод списка процессов: ps.
Список команд может быть пополнен командами приостановки, возобновления процессов, вывода состояния критического ресурса и т.п.