9. Планирование в системах пакетной обработки данных. Дисциплины fcfs, sjn, srn.

1)FCFS(First Come First Served)

Недостаток FCFS высокая зависимость от порядка поступления процесса в систему. Если раньше поступает более длительные процессы, то более короткому приходится очень долго ждать тем самым увеличивается время ожидания и полное время оборота.

Достоинство дешевизна.

2)SJN(Shortest Job Next)

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

3)SRN(Shortest Remain Next)

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

Недостаток не реализуется по той же причине что и предыдущий.

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

 

10. Планирование в интерактивных системах. Дисциплина rr (круговое планирование), дисциплины приоритетного планирования.

1)RR(Round Robin)

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

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

2) Приоритетное планирование

Приоритет – это число определяет степень привилегированности процесса относительно других процессов.

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

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

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

16. Понятие взаимного исключения. Критический участок.

Атомарное действие – действие, которое не может прерываться другим действием.

Активность – набор атомарных операций.

Процесс – набор атомарных команд.

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

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

Условие Бернстайна:

Набор активностей p и q детерминированы, если выполняется следующее условие: множество входных данных p и выходной q не пересекаются, и выходные данные p и выходные q не пересекаются. Иначе набор активностей может быть недетерминированным.

I(p) ∩ O(q)=0; O(p) ∩ O(q)=0

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

Критический участок (секция) – участок кода программы, в котором производятся действия с критическим ресурсом.

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

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

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

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

While ( true )

{

пролог

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

эпилог

остальная часть

}

Алгоритмы:

1) Запрет прерываний;

2) Переменная замок;

3) Строгое чередование;

4) Флаги готовности;

5) Алгоритм Деккера;

6) Алгоритм булочный.