Фильтры

Последний из приведенных выше примеров (с командой grep) можно использовать для иллюстрации еще одного важного понятия, а именно, программы-фильтра. Фильтры — это команды (или программы), которые воспринимают входной поток данных, производят над ним некоторые преобразования и выдают результат на стандартный вывод (откуда его можно перенаправить куда-то еще по желанию пользователя). К числу команд-фильтров относятся уже упоминавшиеся выше команды cat, more, less, wc, cmp, diff, а также следующие команды.

Таблица 5.1. Команды-фильтры

Особым фильтром является команда tee, которая " раздваивает" входной поток, с одной стороны направляя его на стандартный вывод, а с другой — в файл (имя которого вы должны задать). Легко видеть, что по своему действию команда tee аналогична оператору перенаправления 1> & file.

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

О перенаправлении и фильтрах можно было бы говорить очень много. Но этот материал имеется в большинстве книг по UNIX и Linux, например у Петерсена [П1.4] и Келли-Бутла [П1.8]. Поэтому ограничимся сказанным, и перейдем к рассмотрению так называемой среды или окружения, создаваемого оболочкой.

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

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

Простой пятиуровневый конвейер в RISC-процессорах

На иллюстрации справа показан простой пятиуровневый конвейер в RISC-процессорах. Здесь:

· IF (англ. Instruction Fetch) — получение инструкции,

· ID (англ. Instruction Decode) — раскодирование инструкции,

· EX (англ. Execute) — выполнение,

· MEM (англ. Memory access) — доступ к памяти,

· WB (англ. Register write back) — запись в регистр.

Вертикальная ось — последовательные независимые инструкции, горизонтальная — время. Зелёная колонка описывает состояние процессора в один момент времени, в ней самая ранняя, верхняя инструкция уже находится в состоянии записи в регистр, а самая последняя, нижняя инструкция только в процессе чтения.

20. Распределение памяти

В персональных компьютерах традиционно принято два основных способа распределения оперативной памяти.
Первый способ, который начинает свой путь от IBM PC, когда даже 512 Кбайт оперативной памяти было чрезвычайно много, делит всю память на ряд небольших областей. Причем такой принцип остается даже у совр_еменных компьютеров в момент первоначальной работы BIOS и при переходе процессора в реальный режим, который характеризуется возможностью использования только 1 Мбайт памяти.
Второй способ реализуется, когда процессор переключается в защищенный режим и использует линейную модель памяти. Для разных поколений процессоров имеются некоторые различия, но надо учитывать, что современный процессор считает, что физическая память не имеет сегментации.
Основная часть ОЗУ (в пределах первого мегабайта, от 0 до начала видеопамяти) размером в 640 Кбайт называется стандартной памятью (Conventional Memory). Она используется для размещения кода программ, запущенных пользователем или операционной системой. В ней также хранятся различные данные, необходимые для работы программ.
За пределами 1 Мбайт существует область памяти НМA (High Memory Area), которая появилась из-за ошибки в процессоре 286. Эти дополнительные 64 Кбайт, если загружен драйвер HIMEM.EXE, можно использовать для хранения кода и данных любой программы. Правда, чаще всего этот подарок программистам и пользователям занимается под размещение резидентной части операционной системы и различных драйверов. Пользователь может самостоятельно указать, какие программы должны загружаться в эту память, например, корректируя системные файлы операционной системы MS-DOS — AUTOEXEC.BAT и CONFIG.SYS.
Между верхней границей стандартной памяти и до конца первого мегабайта существует область UMA (Upper Memory Area) размером 384 Кбайт, в которой расположены видеопамять, адресное пространство ПЗУ видеоадаптера и BIOS (а также ПЗУ других внешних устройств). Это пространство между верхней границей ПЗУ видеоадаптера и до начала BIOS, т. е. от С8000h до F0000h, у стандартного персонального компьютера почти всегда не занято. Чтобы использовать свободную часть этой памяти, например для размещения кода операционной системы, используют драйвер EMM386.EXE. Соответственно, надо указать в файлах AUTOEXEC.BAT и CONFIG.SYS, что пользователь разрешил использовать эту память.

21.

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

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

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

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

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

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

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

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

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

22.

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

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

First-Come, First-Served (FCFS)

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

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

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

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

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

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

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

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

23.