Диспетчеризация пассажирских перевозок

 

Мною был произведен переход от среднего уровня планирования к верхнему уровню. Так как не было задано ограничений по ресурсам, на верхнем уровне

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Синхронизация процессов

2.1 Теоретическое положение управления процессами

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

Состояние процессов

В многозадачной (многопроцессной) системе процесс может находиться в одном из трех основных состояний:

- ВЫПОЛНЕНИЕ - активное  состояние процесса, во время  которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

- ОЖИДАНИЕ - пассивное  состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

- ГОТОВНОСТЬ - также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

В ходе жизненного цикла  каждый процесс переходит из одного состояния в другое в соответствии с алгоритмом планирования процессов, реализуемым в данной операционной системе. Типичный граф состояний процесса показан на рисунке 1.

В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ - несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

 

 

Рис.5. Граф состояний  процесса в многозадачной среде 

 Проблема синхронизации

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

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

Критическая секция

Важным понятием синхронизации  процессов является понятие "критическая  секция" программы (CS). Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым данным. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Простейший способ обеспечить взаимное исключение - позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.

 Синхронизация  процессов на основе семафорных  
операций

Для устранения активного  ожидания процесса CPU  может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. На рисунке 12 показан фрагмент алгоритма процесса, использующего эти функции. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

Обобщающее средство синхронизации процессов предложил  Дейкстра, который ввел два новых  примитива. В абстрактной форме  эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

V(S) : переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S) : уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

 

В частном случае, когда  семафор S может принимать только значения 0 и 1, он превращается в блокирующую  переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

Рассмотрим использование  семафоров для взаимоисключения процессов.

Двоичный семафор

 С каждым семафором  связывается список процессов,  ожидающих разрешения пройти  семафор.

ОС может выполнить  три действия над процессами:

1. может назначить для исполнения готовый процесс;
2. может заблокировать исполняющийся процесс и поместить его в список, связанный с конкретным семафором;
3. может деблокировать процесс, тем самым переводя его в готовое к исполнению состояние и позволяя ему когда-нибудь возобновить исполнение.

 

Находясь в списке заблокированных, ожидающий процесс  не проверяет семафор непрерывно, как в случае активного ожидания. Вместо него на процессоре может исполняться другой процесс (рис. 6, 7).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 6. Временная диаграмма для двоичного семафора (S)

 

Замечание: все CS должны быть одинаковы по длительности, поэтому чтобы упростить временные диаграммы здесь и далее применено сокращение -                           

           До момента t₁ ресурс был не занят. В момент t₁ процесс Pr1, выполняет операцию P(S) и входит в критический участок (CS).

В момент t₂ процесс Pr2 выполняет операцию P(S) – занять ресурс, это приводит к изменению: S = -1 – означает, что Pr2 в состоянии блокирования.

В момент t₃ – конец критического участка для процесса Pr1. Выполняется операция V(S) – освободить, это приводит к увеличению значения S на единицу (т.е. S=0). Для процесса блокированного (Pr2) это сигнал на разблокировку и предоставления ему ресурса.

В момент t₄ процесс Pr2 освобождает ресурс, выполняется операция V(S), которая изменяет значение S на 1 (т.е. S=1).

Достоинство синхронизации  на основе семафорных операций – отсутствие активного ожидания представления ресурса.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 7. Временная диаграмма для двоичного семафора (семафоры - S1 и S2)

 

Б – блокировано, СS1 и CS2 – критические участки 1 и 2, идентифицированные семафорами S1 и S2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2 Исходная таблица семафорных  операций

Табл.№ 2  Таблица семафорных операций.

Шаг	Модельное время	Семафорные операции	РЕСУРС	ПРИЧИНА	Владелец
1	3	p(w)	winchester	a1 takes	нет
2	7	p(f)	flop	a2 takes	нет
3	31	v(f)	flop	a2 frees	a2
4	32	v(w)	winchester	a1 frees	a1
5	33	p(w)	winchester	a6 takes	нет
6	40	p(w)	winchester	a5 waiting a6	a6
7	53	v(w)	winchester	a6 frees/a5 takes	a6
8	83	v(w)	winchester	a5 frees	a5
9	100	p(p)	printer	a1 takes	нет
10	105	p(f)	flop	a8 takes	нет
11	133	v(p)	printer	a1 frees	a1
12	144	v(f)	flop	a8 frees	a8
13	176	p(f)	flop	a1 takes	нет
14	179	p(w)	winchester	a7 takes	нет
15	182	p(w)	winchester	a6 waiting a7	a7
16	200	v(f)	flop	a1 frees	a1
17	200	v(w)	winchester	a7 frees/a6 takes	a7
18	204	p(w)	winchester	a4 waiting a6	a6
19	209	p(t)	tty	a5 takes	нет
20	209	p(w)	winchester	a3 waiting a6	a6
21	237	v(w)	winchester	a6 frees/a4 takes	a6
22	258	v(w)	winchester	a4 frees/a3 takes	a4
23	277	v(w)	winchester	a3 frees	a3
24	288	p(t)	tty	a4 waiting a5	a5
25	343	p(w)	winchester	a5 takes	нет
26	349	p(f)	flop	a3 takes	нет
27	384	v(f)	flop	a3 frees	a3
28	384	v(w)	winchester	a5 frees	a5
29	390	p(p)	printer	a7 takes	Нет
30	394	p(f)	flop	a5 takes	Нет
31	398	p(w)	winchester	a1 takes	Нет
32	402	p(w)	winchester	a3 waiting a1	a1
33	417	v(w)	winchester	a1 frees/a3 takes	a1
34	421	v(f)	flop	a5 frees	a5
35	435	v(t)	tty	a5 frees/a4 takes	a5
36	437	v(w)	winchester	a3 frees	a3
37	443	p(p)	printer	a4 waiting a7	a7
38	446	p(p)	printer	a3 waiting a7	a7
39	460	p(t)	tty	a1 waiting a4	a4
40	462	p(p)	printer	a5 waiting a7	a7