Понятие мультизадачности, кооперативная и вытесняющая мультизадачность. Мультипрограммирование и мультизадачность – связь двух понятий. Примеры.
Структуры данных, используемые для реализации основных функций ОС. Обобщённые дескрипторы. Объекты ядра ОС Windows NT, используемые для реализации функций управления, диспетчеризации и синхронизации процессов.
Проблема взаимного исключения. Понятие критической секции, её свойства, условия реализации. Примеры.
Взаимное исключение необходимо в том случае, когда несколько процессов работают параллельно с разделяемыми (общими) данными, совместное использование которых может привести к их разрушению или к конфликтной ситуации.
Критическая секция (интервал, участок) - это последовательность команд программы, операции которой связаны с обращением к разделяемым данным, причем параллельное выполнение несколькими процессами действий, заданных в критических секциях, может привести к разрушению этих данных.
Требования к КС:
· в любой момент времени только один процесс может находиться в своей критической секции по данному ресурсу (это главное требование - взаимное исключение);
· ни один процесс не должен ждать бесконечно долго входа в критическую секцию (реализация взаимного исключения не должна приводить к ошибкам или невозможности выполнения процессами своих функций - взаимное исключение только устанавливает порядок доступа к общим ресурсам, исключающий их разрушение);
· ни один процесс не может находиться в своей критической секции бесконечно долго (это следствие предыдущего требования - все процессы в течение приемлемого времени должны получить доступ к разделяемым данным для выполнения своих функций);
|
|
· никакой процесс, находящийся вне своей критической секции, не должен задерживать выполнение других процессов, ожидающих входа в свои критические секции.
Относительно режима работы в КС справедливы утверждения:
· относительные скорости процессов неизвестны;
· программа может останавливаться только вне ее критической секции;
· операции считывания и записи разделяемых данных неделимы;
· процессы не имеют приоритетов, связанных с доступом к общим данным, то есть нет приоритетов на вход в критические секции;
· одновременные обращения к одним и тем же данным для выполнения операции чтения или записи более чем одного процессора приведут к последовательным обращениям в неустановленном порядке.
Программные методы реализации взаимного исключения: примеры на псевдокоде, анализ и сравнение вариантов. Примеры.
1. использование общей переменной (N), указывающей номер процесса, чья очередь войти в критическую секцию в данный момент.
N –н ачальное значение этой переменной должно быть установлено при инициализации системы (до запуска процессов P1 и P2). Предположим, что первым в критическую секцию должен быть допущен процесс P1.
|
|
Процедура инициализации | Первый процесс | Второй процесс |
procedure INIT; common integer N ; begin N := 1 ; start(P1) ; start(P2) end INIT . | process P1; common integer N ; begin while true do begin BEFORE1 ; while N = 2 do ; CS1 ; N := 2 ; AFTER1 ; end end P1 . | process P2; common integer N ; begin while true do begin BEFORE2 ; while N = 1 do ; CS2 ; N := 1 ; AFTER2 ; end end P2 . |
Цикл, вставленный в программы перед началом критических секций, позволяет организовать ожидание момента, когда подойдет очередь данного процесса для входа в критическую секцию. Первым при установленном порядке доступ к разделяемым данным должен получить процесс P1. Оба процесса, дождавшись возможности входа в критическую секцию, выполняют заданные в ней действия и сразу после выхода из критической секции передают очередь на вход следующему процессу, установив его номер в переменной N. Первый процесс передает очередь на доступ к разделяемому ресурсу второму процессу, а второй - первому.
Минус: процесс имеющий право на вход в свою критическую секцию, но пока не вошедший в нее блокирует вход в критические секции другим процессам, которые могут быть готовы к обработке общих данных, но не могут получить к ним доступ
|
|
2. использование переменных-флажков, которые представляют собой признак, показывающий, не находится ли соответствующий ей процесс в своей критической секции.
Процедура инициализации | Первый процесс | Второй процесс |
procedure INIT; common boolean C1,C2 ; begin C1 := false ; C2 := false ; start(P1) ; start(P2) end INIT . | process P1; common boolean C1,C2 ; begin while true do begin BEFORE1 ; while C2 do ; C1 := true ; CS1 ; C1 := false ; AFTER1 ; end end P1 . | process P2; common boolean C1,C2 ; begin while true do begin BEFORE2 ; while C1 do ; C2 := true ; CS2 ; C2 := false ; AFTER2 ; end end P2 . |
Перед входом в критическую секцию каждый процесс проверяет, не находится ли его конкурент в своей критической секции, если нет, то в процессе устанавливается признак (значение true соответствующего этому процессу флажка), что он вошел в критическую секцию (занял ресурс), а после выхода из критической секции этот флажок снова сбрасывается в false, освобождая ресурс. Однако в том случае, когда (хоть это и маловероятно) оба процесса одновременно подойдут к проверке значений флажков своих конкурентов перед входом в критическую секцию, они смогут пройти в нее одновременно. Таким образом, нарушается самое главное требование к реализации критической секции - требование взаимного исключения.
|
|
3.Алгоритм Деккера
Процедура инициализации | Первый процесс | Второй процесс |
procedure INIT; common boolean C1,C2 ; common integer N ; begin C1 := false ; C2 := false ; N := 1 ; start(P1) ; start(P2) end INIT . | process P1; common boolean C1,C2 ; begin while true do begin BEFORE1 ; C1 := true ; while C2 do begin if N = 2 then begin C1 := false ; while N=2 do ; C1 := true ; end end ; CS1 ; C1 := false; N := 2; AFTER1 ; end end P1 . | process P2; common boolean C1,C2 ; begin while true do begin BEFORE2 ; C2 := true ; while C1 do begin if N = 1 then begin C2 := false ; while N=1 do ; C2 := true ; end end ; CS2 ; C2 := false; N:=1; AFTER2 ; end end P2 . |
Порядок входа в критическую секцию процессов, одновременно заявивших о своих намерениях получить доступ к общим данным, устанавливается с помощью целочисленной переменной, в которой фиксируется значение номера процесса, имеющего преимущество на вход в критическую секцию. Причем этот номер учитывается только в случае, когда процессы подошли к критической секции одновременно, то есть не будет нарушено условие, что процессы, не находящиеся в критической секции, не должны мешать другим процессам входить в их критические секции. После выхода из критической секции процесс передает очередь на преимущественный доступ к разделяемым данным своему конкуренту.
Дата добавления: 2018-02-18; просмотров: 452; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!