Шпаргалка по "Программированию и компьютерам"

 Для управления процессами в ОС существует специальная  структура называемая дескриптором процессов. В ней содержится следующая  информация:

 - идентификатор  процесса PID;

 - приоритет  процесса;

 - область  памяти, используемая процессом;

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

 Потоки

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

 В ОС возможны следующие режимы работы с потоками: либо ОС управляет потоками, либо она  управляет процессами, либо бывает смешенное управление. Логика управления потоками ложится на прикладную программу.

 Если ОС поддерживает управление потоками, то она обеспечивает планирование (диспетчеризацию) потоков самостоятельно.

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

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

 Планирование  процессов

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

 Стратегия планирования определяет, какие именно процессы будут выполняться. Критерием  выбора процесса может быть следующее:

 1) Возможность  заканчивать вычисление в том  порядке в каком они были  начаты.

 2) Отдавать  предпочтение более коротким  процессам, т.е. требующим меньше времени.

 3) Предоставлять  равные возможности для всех  процессов.

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

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

 Во втором случае процесс выбирается из очереди  с учетом его важности (приоритета).

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

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

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

 Динамическое  планирование

 Недостаток  прошлого метода в том, что процесс  с низким приоритетом будет долго выполняться или совсем не выполниться. В динамическом планировании ОС может повышать или понижать приоритет. Например в Windows 2000 gпричиной для повышения приоритета является работа с графикой. В этой ОС предполагается 32 класса приоритета, которые делятся на классы реального времени (значение приоритета от 16 до 31) и переменного приоритета (от 0 до 15). Пользовательские процессы могут иметь значение приоритета от 1 до 15. Причем ОС может уменьшить значение приоритета для оптимизации своей работы. Диспетчер останавливает выполнение потока после того, как тот израсходовал свой квант времени и если этот поток относиться к диапазону динамического приоритета, то ОС понижает приоритет потока на 1. Т.е. потто требующий много вычислений постепенно теряет свой приоритет до значение базового приоритета. С другой стороны ОС увеличивает приоритет потока после выхода его из состояния блокировки, причем добавка к приоритету зависит от причин блокировки, максимальное значение не может быть выше 15.

 Рассмотрим  некоторые наиболее известные  дисциплины диспетчеризации процесса:

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

 2) SJN (следующим  выполняется самое короткое задание). Из названия следует, что при  данной диспетчеризации первой  будет выполнена наиболее короткая  очередь. Однако возникает необходимость  оценивать требуемое машинное время для каждой задачи, что не очень удобно. Данная дисциплина диспетчеризации предполагает одну очередь заданий, т.е. задания которые раньше были заблокированы, вновь попадают в конец очереди. Чтобы преодолеть этот недостаток была разработана другая дисциплина.

 3) SRT, т.е.  задача, которая требует наименьшего  времени для своего завершения.

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

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

 4) RR. Предполагается, что каждая задача получает  процессорное время некоторыми  порциями (квантами). Если квант времени  процесса заканчивается, то этот процесс из состояния готовности переходит в состояние ожидания и переносится в конец очереди, а управление передается другому процессу.

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

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

 Планирование  процессов в Unix (Linux).

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

 Самым распространенным алгоритмом планирования является циклический  алгоритм RR (Round Robin) при котором каждому процессу выделяются кванты времени, а сами процессы выстраиваются в кольцевую очередь.

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

 Жизненный Циклы процесса

 Возможны  следующие состояния процесса:

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

 2) Процесс  работает в режиме ядра. При  этом процесс выполняет системные  инструкции ядра от имени процесса.

 3) Процесс  не выполняется, но готов к  выполнению и ожидает когда  его выберет планировщик.

 4) Процесс  находится в состоянии сна  в связи с ожиданием каких-либо  ресурсов.

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

 6) Процесс только что создан системным вызовом fork и находится в переходном состоянии: он существует, но не готов к запуску и не находиться в состоянии сна.

 7) Процесс  выполнил системный вызов exit и перешел в состояние зомби (zombie, defunct). Как такового процесса не существует, но остаются записи, содержащие код возврата и временную статистику его выполнения, доступную для родительского процесса. Это состояние является конечным в жизненном цикле процесса.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 3. Взаимодействие процессов.  Понятие критической  секции. Средства  межпроцессорного  взаимодействия в  Linux: программыне  и FIFO каналы, сообщения,  семафоры, сокеты.

 

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

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

 2)Совместное  использование данных. Различные  процессы могут работать с  одной и той же динамической  базой данных или с разделённым  файлом, совместно изменяя их содержание.

 3)Реализация  модульной конструкции системы.  Примером может служить микроядерный  способ построения ОС. Когда различные  её части представляют отдельные  процессы, взаимодействующие путём  передачи сообщений через микроэлемент.

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

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

 Важным  понятием при изучении способов синхронизации  процессов является понятие критической секции (critical section) программы.

 Критическая секция – это часть программы, исполнение которой может привести к возникновению race condition (состояние гонки, состояние состязания) для определенного набора программ.

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

 Средства  межпроцессного взаимодействия в Unix

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

 1) Программные каналы (pipes)

 Простейшей  разновидностью каналов являются конвееры.

 Cut файл 1 /vc

 В этом конвеере стандартный выход программы cut передается на стандартный вход программы vc. Таким  образом, создается программный  канал между этими командами.