Главная страница
Навигация по странице:

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

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

  • Алгоритмы планирования . First-Come, First-Served (FCFS) Алгоритмы планирования. Round Robin (RR)

  • Продолжительность очередного CPU burst

  • Процесс Время появления в очереди очередного CPU burst

  • Процесс Время появления в очереди Продолжительность очередного CPU burst

  • Приоритет

  • Механизмы синхронизации процессов.

  • Файл (file)

  • Индексные дескрипторы (i –узлы)

  • Структура и назначение файловой системы.

    		•

    ОС. Вопросы к экзамену по дисциплине Операционные системы 2019 год


    Скачать 0.54 Mb.
    НазваниеВопросы к экзамену по дисциплине Операционные системы 2019 год
    Дата10.01.2020
    Размер0.54 Mb.
    Формат файлаdocx
    Имя файлаVoprosy_k_ekzamenu_po_distsipline_Operatsionnye_sistemy_2019_god.docx
    ТипВопросы к экзамену
    #103408
    страница4 из 6
    1   2   3   4   5   6

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


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

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

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

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

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

    В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и операционная система вынуждена осуществлять планирование выбирая новый процесс для выполнения. В случаях 3 и 4 планирование может как проводиться, так и не проводиться, планировщик не вынужден обязательно принимать решение о выборе процесса для выполнения, процесс, находившийся в состоянии исполнение может просто продолжить свою работу. Если в операционной системе планирование осуществляется только в вынужденных ситуациях, говорят, что имеет место невытесняющее (nonpreemptive) планирование. Если планировщик принимает и вынужденные, и невынужденные решения, говорят о вытесняющем (preemptive) планировании. Термин "вытесняющее планирование"возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом.

    Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh. При таком режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания завершения операции ввода-вывода или по окончании работы). Этот метод планирования относительно просто реализуем и достаточно эффективен, так как позволяет выделить большую часть процессорного времени для работы самих процессов и до минимума сократить затраты на переключение контекста. Однако при невытесняющем планировании возникает проблема возможности полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В такой ситуации спасает только перезагрузка всей вычислительной системы.

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

    1. Алгоритмы планирования. First-Come, First-Served (FCFS)

    2. Алгоритмы планирования. Round Robin (RR)

    3. Алгоритмы планирования. Shortest-Job-First (SJF)

    4. Алгоритмы планирования. Приоритетное планирование

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


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

    First-Come, First-Served (FCFS)


    Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия – First-Come, First-Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO1, сокращение от First In, First Out (первым вошел, первым вышел).

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

    Таблица 3.1.

    Процесс
    p0
    p1
    p2

    Продолжительность очередного CPU burst
    13
    4
    1

    Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков. Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса p0, p1 и p2, для которых известны времена их очередных CPU burst . Эти времена приведены в таблице 3.1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst , что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь.

    Если процессы расположены в очереди процессов, готовых к исполнению, в порядке p0, p1, p2, то картина их выполнения выглядит так, как показано на рисунке 3.2. Первым для выполнения выбирается процесс p0, который получает процессор на все время своего CPU burst , т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс p1, он занимает процессор на 4 единицы времени. И, наконец, возможность работать получает процесс p2. Время ожидания для процесса p0 составляет 0 единиц времени, для процесса p1 – 13 единиц, для процесса p2 – 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае – (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса p0составляет 13 единиц времени, для процесса p1 – 13 + 4 = 17 единиц, для процесса p2 – 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.




    Рис. 3.2. Выполнение процессов при порядке p0,p1,p2

    Если те же самые процессы расположены в порядке p2, p1, p0, то картина их выполнения будет соответствовать рисунку 3.3. Время ожидания для процесса p0 равняется 5 единицам времени, для процесса p1 – 1 единице, для процесса p2 – 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса p0 получается равным 18 единицам времени, для процесса p1 – 5 единицам, для процесса p2– 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени, что почти в 2 раза меньше, чем при первой расстановке процессов.




    Рис. 3.3. Выполнение процессов при порядке p2, p1, p0

    Как мы видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPU burst , то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени – слишком большим получается среднее время отклика в интерактивных процессах.

    Round Robin (RR)


    Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд (см. рис. 3.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.




    Рис. 3.4. Процессы на карусели

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

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

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

    Рассмотрим предыдущий пример с порядком процессов p0, p1, p2 и величиной кванта времени равной 4. Выполнение этих процессов иллюстрируется таблицей 3.2. Обозначение "И" используется в ней для процесса, находящегося в состоянии исполнение, обозначение "Г" – для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1.

    Таблица 3.2.

    Время
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

    p0
    И
    И
    И
    И
    Г
    Г
    Г
    Г
    Г
    И
    И
    И
    И
    И
    И
    И
    И
    И

    p1
    Г
    Г
    Г
    Г
    И
    И
    И
    И






























    p2
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    И



























    Первым для исполнения выбирается процесс p0. Продолжительность его CPU burst больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид p1, p2, p0. Следующим начинает выполняться процесс p1. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов, p2 и p0. Процессор выделяется процессу p2. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу p0 – единственному не закончившему к этому моменту свою работу. Время ожидания для процесса p0 (количество символов "Г" в соответствующей строке) составляет 5единиц времени, для процесса p1 – 4 единицы времени, для процесса p2 – 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса p0 (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса p1 – 8единиц, для процесса p2 – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6)единицы времени.

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

    На производительность алгоритма RR сильно влияет величина кванта времени. Рассмотрим тот же самый пример с порядком процессов p0, p1, p2 для величины кванта времени, равной 1 (см. табл. 3.3.). Время ожидания для процесса p0 составит 5 единиц времени, для процесса p1 – тоже 5 единиц, для процесса p2 – 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

    Таблица 3.3.

    Время
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

    p0
    И
    Г
    Г
    И
    Г
    И
    Г
    И
    Г
    И
    И
    И
    И
    И
    И
    И
    И
    И

    p1
    Г
    И
    Г
    Г
    И
    Г
    И
    Г
    И



























    p2
    Г
    Г
    И













































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

    Shortest-Job-First (SJF)


    При рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным для них является порядок расположения процессов в очереди процессов, готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если бы мы знали время следующих CPU burst для процессов, находящихся в состоянии готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если же таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название "кратчайшая работа первой" или Shortest Job First ( SJF ).

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

    Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии готовность находятся четыре процесса, p0, p1, p2 и p3, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 3.4. Как и прежде, будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода и что временем переключения контекста можно пренебречь.

    Таблица 3.4.

    Процесс
    p0
    p1
    p2
    p3

    Продолжительность очередного CPU burst
    5
    3
    7
    1

    При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс p3, имеющий наименьшее значение продолжительности очередного CPU burst. После его завершения для исполнения выбирается процесс p1, затем p0 и, наконец, p2. Эта картина отражена в таблице 3.5.

    Таблица 3.5.

    Время
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16

    p0
    Г
    Г
    Г
    Г
    И
    И
    И
    И
    И





















    p1
    Г
    И
    И
    И




































    p2
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    И
    И
    И
    И
    И
    И
    И

    p3
    И













































    Как мы видим, среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Легко посчитать, что для алгоритма FCFS при порядке процессов p0, p1, p2, p3 эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7единицам времени, т. е. будет в два раза больше, чем для алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса невытесняющих алгоритмов.

    Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов p0, p1, p2 и p3 с различными временами CPU burst и различными моментами их появления в очереди процессов, готовых к исполнению (см. табл. 3.6.).

    Таблица 3.6.

    Процесс
    Время появления в очереди очередного CPU burst
    Продолжительность

    p0
    0
    6

    p1
    2
    2

    p2
    6
    7

    p3
    0
    5

    В начальный момент времени в состоянии готовность находятся только два процесса, p0 и p3. Меньшее время очередного CPU burst оказывается у процесса p3, поэтому он и выбирается для исполнения (см. таблицу 3.7.). По прошествии 2 единиц времени в систему поступает процесс p1. Время его CPU burst меньше, чем остаток CPU burst у процесса p3, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2 единиц времени процесс p1 завершается, и для исполнения вновь выбирается процесс p3. В момент времени t = 6 в очереди процессов, готовых к исполнению, появляется процесс p2, но поскольку ему для работы нужно 7 единиц времени, а процессу p3 осталось трудиться всего 1 единицу времени, то процесс p3 остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы p0и p2, из которых выбирается процесс p0. Наконец, последним получит возможность выполняться процесс p2.

    Таблица 3.7.

    Время
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

    p0
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    И
    И
    И
    И
    И
    И





















    p1






    И
    И
















































    p2


















    Г
    Г
    Г
    Г
    Г
    Г
    Г
    И
    И
    И
    И
    И
    И
    И

    p3
    И
    И
    Г
    Г
    И
    И
    И







































    Основную сложность при реализации алгоритма SJF представляет невозможность точного знания продолжительности очередного CPU burst для исполняющихся процессов. В пакетных системах количество процессорного времени, необходимое заданию для выполнения, указывает пользователь при формировании задания. Мы можем брать эту величину для осуществления долгосрочного SJF- планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При краткосрочном планировании мы можем делать только прогноз длительности следующего CPU burst, исходя из предыстории работы процесса. Пусть  – величина n -го CPU burst, T(n + 1) – предсказываемое значение для n + 1 -го CPU burst,  – некоторая величина в диапазоне от 0 до 1.

    Определим рекуррентное соотношение



    T(0) положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию. При  мы перестаем следить за последним поведением процесса, фактически полагая

    T(n)= T(n+1)=...=T(0)

    т. е. оценивая все CPU burst одинаково, исходя из некоторого начального предположения.

    Положив , мы забываем о предыстории процесса. В этом случае мы полагаем, что время очередного CPU burst будет совпадать со временем последнего CPU burst:



    Обычно выбирают  для равноценного учета последнего поведения и предыстории. Надо отметить, что такой выбор  удобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным временем CPU burst и полученную сумму разделить на 2, например, сдвинув ее на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора для краткосрочного SJF - планирования.

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


    Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше у процесса приоритет .

    Алгоритмы назначения приоритетов процессов могут опираться как на внутренние параметры, связанные с происходящим внутри вычислительной системы, так и на внешние по отношению к ней. К внутренним параметрам относятся различные количественные и качественные характеристики процесса такие как: ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. Алгоритмы SJF и гарантированного планирования используют внутренние параметры. В качестве внешних параметров могут выступать важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и другие политические факторы. Высокий внешний приоритет может быть присвоен задаче лектора или того, кто заплатил $100 за работу в течение одного часа.

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

    Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и в примере для вытесняющего алгоритма SJF, только им дополнительно еще присвоены приоритеты (см. табл. 3.8.). В вычислительных системах не существует определенного соглашения, какое значение приоритета – 1 или 4 считать более приоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т. е. наиболее приоритетным в нашем примере является процесс p3, а наименее приоритетным – процесс p0.

    Таблица 3.8.

    Процесс
    Время появления в очереди
    Продолжительность очередного CPU burst
    Приоритет

    p0
    0
    6
    4

    p1
    2
    2
    3

    p2
    6
    7
    2

    p3
    0
    5
    1

    Как будут вести себя процессы при использовании невытесняющего приоритетного планирования? Первым для выполнения в момент времени t = 0 выбирается процесс p3, как обладающий наивысшим приоритетом. После его завершения в момент времени t = 5в очереди процессов, готовых к исполнению, окажутся два процесса p0 и p1. Больший приоритет из них у процесса p1, он и начнет выполняться (см. табл. 3.9.). Затем в момент времени t = 8 для исполнения будет избран процесс p2, и лишь потом – процесс p0.

    Таблица 3.9.

    Время
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

    p0
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    И
    И
    И
    И
    И
    И

    p1






    Г
    Г
    Г
    И
    И







































    p2


















    Г
    И
    И
    И
    И
    И
    И
    И


















    p3
    И
    И
    И
    И
    И













































    Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования (см. табл. 3.10.). Первым, как и в предыдущем случае, начнет исполняться процесс p3, а по его окончании – процесс p1. Однако в момент времени t = 6 он будет вытеснен процессом p2 и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше, будет исполняться процесс p0.

    Таблица 3.10.

    Время
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

    p0
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    И
    И
    И
    И
    И
    И

    p1






    Г
    Г
    Г
    И
    Г
    Г
    Г
    Г
    Г
    Г
    Г
    И


















    p2


















    И
    И
    И
    И
    И
    И
    И





















    p3
    И
    И
    И
    И
    И













































    В рассмотренном выше примере приоритеты процессов с течением времени не изменялись. Такие приоритеты принято называть статическими. Механизмы статической приоритетности легко реализовать, и они сопряжены с относительно небольшими издержками на выбор наиболее приоритетного процесса. Однако статические приоритеты не реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов. Начальное значение динамического приоритета, присвоенное процессу, действует в течение лишь короткого периода времени, после чего ему назначается новое, более подходящее значение. Изменение динамического приоритета процесса является единственной операцией над процессами, которую мы до сих пор не рассмотрели. Как правило, изменение приоритета процессов проводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении определенного кванта времени или по завершении процесса. Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования. Схемы с динамической приоритетностью гораздо сложнее в реализации и связаны с большими издержками по сравнению со статическими схемами. Однако их использование предполагает, что эти издержки оправдываются улучшением работы системы.

    Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз по истечении определенного промежутка времени значения приоритетов готовых процессов уменьшаются на 1. Процессу, побывавшему в состоянии исполнение, присваивается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.

    1. Взаимодействующие процессы. Цели организации взаимодействия.

    2. Категории средств обмена информацией между процессами.

    3. Особенности передачи информации с помощью линий связи. Буферизация

    4. Надежность средств связи. Условия надежности при обмене данными.

    5. Нити исполнения (потоки)

    6. Понятие критического ресурса.

    7. Тупики. Условия возникновения.

    8. Основные направления борьбы с тупиками

    9. Механизмы синхронизации процессов.

    10. Примитивы межпроцессного взаимодействия. Семафоры.

    11. Примитивы межпроцессного взаимодействия. Решение задачи «производитель-потребитель».

    12. Примитивы межпроцессного взаимодействия. Решение задачи «обедающие философы».

    13. Примитивы межпроцессного взаимодействия. Решение задачи «читатель-писатель».

    14. Примитивы межпроцессного взаимодействия. Сигналы.

    15. Примитивы межпроцессного взаимодействия. Разделяемая память.

    16. Примитивы межпроцессного взаимодействия. Файлы, отображаемые в память.

    17. Примитивы межпроцессного взаимодействия. Решение задачи «Спящий парикмахер».

    18. Понятие файла.

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

    Немного о терминологии. Слово файл уже несколько десятков лет используется как русское – один из многочисленных примеров программистских неологизмов. Первоначально, когда около 50 лет назад появился данный английский термин, в русскоязычной литературе специалисты пытались ввести другую терминологию – слово file переводили как фонд и даже тека (в смысле хранилище). Однако исторически сложилось иное решение – слово файл стало русским.

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

    1. Классификация файлов.

    Старый пользователь DOS/Windows, не погрязший окончательно в метафоре файлов-документов, возникшей в MacOS (где, надо отдать ей должное, метафора эта вполне оправдана) и внедренной в Windows, начиная с версии 95, помнит о существовании типов файлов, отличающихся своими расширениями, - исполняемых (*.exe, *.com), пакетных (*.bat), текстовых (*.txt), изображений в различных форматах (*.tiff там, или *.gif), и так далее. И потому будет весьма удивлен, когда узнает, что в Unix'ах все они не типизированы никак. И действительно - как ОС может отличить их друг от друга, если имени файла (и, следовательно, расширения) в атрибутах его нет и в помине? В этом смысле говорят, что в Unix нет понятия типизации файла.

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

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

    • каталоги;

    • символические ссылки;

    • специальные файлы устройств;

    • именованные каналы и сокеты;

    • обычные, или регулярные, файлы.

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

    1. Реализация файлов.



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

    1. Список – однонаправленный список блоков. Первое слово каждого блока указатель на следующий блок. (В последнем блоке первое слово пустое) В остальной части блока – данные. В каталоге нужно хранить только адрес первого блока. Недостаток – прямой доступ к блокам файла довольно медленный. Чтобы получить доступ к k-му блоку, ОС должна прочитать первые k-1 блоков по очереди.





    Список с индексацией – указатели на следующие блоки хранятся не прямо в блоках, а в отдельной таблице, загруженной в память: File Allocation Table (FAT). При такой организации прямой доступ к k-му блоку упрощен, т. к. вся цепочка ссылок уже хранится в памяти и дополнительных дисковых операций не требуется. В каталоге хранится одно целое число – номер первого блока. Недостаток состоит в том, что таблица должна постоянно находиться в ОП.

    1. Индексные дескрипторы (i –узлы). С каждым файлом связана структура данных (i-узел), содержащая атрибуты файла и адреса блоков файла. Каждый конкретный i-узел находится в оперативной памяти только тогда, когда соответствующий файл открыт. Если каждый i-узел занимает n байт (в Unix – 64 байта), а одновременно открыто k файлов, то в оперативной памяти будет занято n*k байт. Обычно, эта величина меньше размера FAT таблицы и не зависит от объема диска.

    1. Структура и назначение файловой системы.
    1   2   3   4   5   6

    написать администратору сайта