First-Come, First-Served (FCFS) (42)

Оглавление

Планирование. Вопросы 39-50 (12 вопросов)

Критерии планирования и требования к алгоритмам (39). 1

Параметры планирования (40). 2

Вытесняющее и невытесняющее планирование (41). 2

First-Come, First-Served (FCFS) (42). 3

Round Robin (RR) (43). 3

Shortest-Job-First (SJF) (44). 4

Гарантированное планирование (45). 5

Приоритетное планирование (46). 5

Многоуровневые очереди (Multilevel Queue) (47). 5

Взаимодействующие процессы (48). 6

Категории средств обмена информацией (49). 6

Логическая организация механизма передачи информации (49). 6

Нити исполнения (50). 8

 

Планирование

Критерии планирования и требования к алгоритмам (39)

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

1. Справедливость распределения процессорного времени

2. Эффективность использования процессора

3. Сокращение времени выполнения

4. Сокращение времени ожидания

5. Сокращение времени отклика

Желательные свойства:

1. предсказуемость. Одно и то же задание должно выполняться приблизительно за одно и то же время. Применение алгоритма планирования не должно приводить, к примеру, к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток – при втором запуске.

2. минимальными накладными расходами - больше времени на выполнение, меньше на планирование

3. Равномерная загрузка ресурсов (предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы)

4. Масштабируемость

Параметры планирования (40)

Алгоритмы долгосрочного планирования используют в своей работе статические и параметры системы:

1. Каким пользователем запущен процесс

2. приоритет

3. процессорное время

4. соотношение процессорного времени и времени операций ввода-вывода.

5. ресурсы

Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают динамические характеристики процессов: количество свободных ресурсов на данный момент.

Для среднесрочного планирования:

1. время с момента выгрузки на диск или загрузки в ОП

2. ОП

3. Предоставленное процессорное время

 

Для краткосрочного планирования:

1 .промежуток времени непрерывного использования процессора CPU burst

2. промежуток времени непрерывного ожидания ввода-вывода –I/O burst

Вытесняющее и невытесняющее планирование (41)

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

1. Когда процесс переводится из состояния исполнение в состояние закончил исполнение.

2. Когда процесс переводится из состояния исполнение в состояние ожидание.

3. Когда процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера).

4. Когда процесс переводится из состояния ожидание в состояние готовность (завершилась операция ввода-вывода или произошло другое событие). Подробно процедура такого перевода рассматривалась в лекции 2 (раздел "Переключение контекста"), где мы показали, почему при этом возникает возможность смены процесса, находящегося в состоянии исполнение.

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

Алгоритмы планирования

Round Robin (RR) (43)

Модификацией алгоритма FCFS в режиме вытесняющего планирования.

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

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

· Продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов.

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

Буферизация

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

2. Буфер ограниченной емкости

3. Буфер неограниченной емкости

Поток ввода/вывода и сообщения

Существует две модели передачи данных по каналам связи – поток ввода-вывода и сообщения.

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

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

Если разрешить процессу, создавшему трубу, сообщать о ее местонахождении в системе другим процессам, сделав вход и выход трубы каким-либо образом видимыми для всех остальных, например, зарегистрировав ее в операционной системе под определенным именем, мы получим объект, который принято называть FIFO или именованный pipe. Именованный pipe может использоваться для организации связи между любыми процессами в системе.

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

И потоковые линии связи, и каналы сообщений всегда имеют буфер конечной длины. Когда мы будем говорить о емкости буфера для потоков данных, мы будем измерять ее в байтах. Когда мы будем говорить о емкости буфера для сообщений, мы будем измерять ее в сообщениях.

Надежность

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

1. Не происходит потери информации.

2. Не происходит повреждения информации.

3. Не появляется лишней информации.

4. Не нарушается порядок данных в процессе обмена.

Передача данных через разделяемую память является надежным способом связи.

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

Подобные действия могут быть возложены:

· на ОС

· на процессы, обменивающиеся данными;

· совместно на систему и процессы. ОС может обнаруживать ошибки при передаче данных и извещать об этом взаимодействующие процессы для принятия ими решения о дальнейшем поведении.

 

Завершение

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

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

Нити исполнения (50)

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

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

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

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

 

Оглавление

Планирование. Вопросы 39-50 (12 вопросов)

Критерии планирования и требования к алгоритмам (39). 1

Параметры планирования (40). 2

Вытесняющее и невытесняющее планирование (41). 2

First-Come, First-Served (FCFS) (42). 3

Round Robin (RR) (43). 3

Shortest-Job-First (SJF) (44). 4

Гарантированное планирование (45). 5

Приоритетное планирование (46). 5

Многоуровневые очереди (Multilevel Queue) (47). 5

Взаимодействующие процессы (48). 6

Категории средств обмена информацией (49). 6

Логическая организация механизма передачи информации (49). 6

Нити исполнения (50). 8

 

Планирование

Критерии планирования и требования к алгоритмам (39)

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

1. Справедливость распределения процессорного времени

2. Эффективность использования процессора

3. Сокращение времени выполнения

4. Сокращение времени ожидания

5. Сокращение времени отклика

Желательные свойства:

1. предсказуемость. Одно и то же задание должно выполняться приблизительно за одно и то же время. Применение алгоритма планирования не должно приводить, к примеру, к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток – при втором запуске.

2. минимальными накладными расходами - больше времени на выполнение, меньше на планирование

3. Равномерная загрузка ресурсов (предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы)

4. Масштабируемость

Параметры планирования (40)

Алгоритмы долгосрочного планирования используют в своей работе статические и параметры системы:

1. Каким пользователем запущен процесс

2. приоритет

3. процессорное время

4. соотношение процессорного времени и времени операций ввода-вывода.

5. ресурсы

Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают динамические характеристики процессов: количество свободных ресурсов на данный момент.

Для среднесрочного планирования:

1. время с момента выгрузки на диск или загрузки в ОП

2. ОП

3. Предоставленное процессорное время

 

Для краткосрочного планирования:

1 .промежуток времени непрерывного использования процессора CPU burst

2. промежуток времени непрерывного ожидания ввода-вывода –I/O burst

Вытесняющее и невытесняющее планирование (41)

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

1. Когда процесс переводится из состояния исполнение в состояние закончил исполнение.

2. Когда процесс переводится из состояния исполнение в состояние ожидание.

3. Когда процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера).

4. Когда процесс переводится из состояния ожидание в состояние готовность (завершилась операция ввода-вывода или произошло другое событие). Подробно процедура такого перевода рассматривалась в лекции 2 (раздел "Переключение контекста"), где мы показали, почему при этом возникает возможность смены процесса, находящегося в состоянии исполнение.

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

Алгоритмы планирования

First-Come, First-Served (FCFS) (42)

первым пришел, первым обслужен.  Невытесняющее, берет первый процесс из очереди. Очередь подобного типа имеет в программировании специальное наименование – FIFO¹, сокращение от First In, First Out (первым вошел, первым вышел).

+ легкость его реализации

- среднее время ожидания т среднее время выполнения существенно зависят от порядка в очереди

Round Robin (RR) (43)

Модификацией алгоритма FCFS в режиме вытесняющего планирования.

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

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

· Продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов.

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