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

Алгоритмы планирования:  1.FIFO(очередь) циклический –конец замыкается на 1м Эл-те 2. LIFO-стек(при пакетной обработке заданий) 3. По сроку завершения(в системах реального времени) – задание должно вып-ся в чётко назначенный срок 4.Кратчайшая задача – первая SJF 5.Наименьшего оставшегося времени выполнения SRT 6.Приоритетный.Трехуровневое планирование Приоритет-число,α хар-т степень привелегированности при исп-и ресурсов Относительные приоритеты-если задача вып-ся то она вып-ся до конца Абс-при поступлении задачи если у неё приоритет выше, исп-я задача прерывается Категории алгоритмов планирования  В различных средах требуются различные алгоритмы планирования. 1)В системах пакетной обработки нет пользователей, сидящих за терминалами и ожидающих ответа. В таких системах приемлемы алгоритмы без переключений или с переключениями, но с большим временем, отводимым каждому процессу. Такой метод уменьшает количество переключений между процессами и улучшает эффективность.  2)В интерактивных системах необходимы алгоритмы планирования с переключениями, чтобы предотвратить захват процессора одним процессом.  3)В системах с ограничениями реального времени приоритетность, как это ни стран­но, не всегда обязательна, поскольку процессы знают, что их время ограничено Все системы  Справедливость — предоставление каждому процессу справедливой доли процессорного  Принудительное применение политики — контроль за выполнением принятой политики  Баланс — поддержка занятости всех частей системы  Системы пакетной обработки данных  Пропускная способность — максимальное количество задач в час  Оборотное время — минимизация времени, затрачиваемого на ожидание обслуживания  и обработку задачи интерактивные системы  Использование процессора — поддержка постоянной занятости процессора  Время отклика — быстрая реакция на запросы Соразмерность — выполнение пожеланий пользователя Системы реального времени  Окончание работы к сроку — предотвращение потери данных  Предсказуемость — предотвращение деградации качества в мультимедийных системах  Предназначение планирования - повышение эффективности использования ресурсов ЭВМ. пропускная способность - максимальное кол-во задач выполненных за единицу времени. Оборотное время – статистически усредненное время от момента получения задачи да её выполнения. Оно характеризует время которое среднестатистический пользователь должен ждать получения решения задачи Время запуска задачи - время отклика системы Удобство работы пользователя – время реакции минимальны

Реактивность системы – способность выдерживать заранее заданные интервалы времени между запуском приложения и получением результата.

 

32. _{Алгоритмы планирования}

29. Алгоритм планирования FIFO

Алгоритм без переключений «первым пришел — первым обслужен» является самым простым. Процессам предоставляется доступ к процессору в том порядке, в α они его запрашивают. Чаще всего формируется единая очередь ждущих процессов. Как только появляется 1я задача, она немедленно запускается и работает, сколько необходимо. Остальные задачи ставятся в конец очереди. Когда текущий процесс блокир-ся, запуска-ется следующий в очереди, когда блокировка снимается, процесс - в конец очереди. Преимущество:его легко понять и столь же легко программировать. В этом алгоритме все процессы в состоянии готовности контролируются 1 связным списком. Чтобы выбрать процесс для запуска, нужно всего лишь взять 1й элемент списка и удалить его. Появление нового процесса приводит к помещению его в конец списка  Недостаток: Представьте себе, чт.е. один процесс, ограниченный возможностями процессора, который каждый раз работает ровно 1 с, и много процессов, ограниченных ВОЗМОЖНОСТЯМИ устр-в ввода-вывода, каждый из α очень в небольшой мере исп-т процессор, но должен выполнить 1000 обращений к диску. Процесс, огранич-й возм-ми процессора, запускается, работает 1 с, затем читает блок с диска. Теперь запускаются все процессы вв-вывода и считывают инф-ю с диска. Когда процесс, ограниченный возможностями процессора, получает свой блок с диска, он запускается еще на 1 с, а за ним все процессы, ограниченные возмо-ми устройств вв-вывода.

Конечный результат: каждый из процессов, ограниченных возм-ми устр-в вв-вывода, считывает 1 блок данных в секунду, и им потребуется по 1000 с, чтобы закончить работу. Если алгоритм планирования будет прерывать процесс, ограниченный возм-ми процессора, раз в 10 мс, процессы, огранич-е возм-ми устр-в ввода-вывода, закончат за 10 с вместо 1000 с и не очень замедлят работу процесса, огранич-го возм-ми процессора.

 

Алгоритм планирования Кратчайшая задача – первая  алгоритм без переключений для систем пакетной обработки, предполагающий, что временные отрезки работы известны заранее. Например, работники страховой компании могут довольно точно предсказать, сколько вре­мени займет обработка пакета из 1000 исков, поскольку они делают это каждый день. Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую задачу.  Алгоритм оптимизирует задачу. Рассмотрим, четы­ре процесса со временем выполнения а. Ь, си iLПервая задача выполняется за время а, вторая — за время а + й и т. д. Среднее оборотное время будет равно (4а + ЗЬ + 2с + '/)/4. Очевидно, что вклад времени а в среднее больше, чем всех остальных интервалов времени, поэтому первой должна выполняться самая корот­кая задача, а последней — самая длинная, вносящая вклад, равный собственному оборотному времени. Точно так же рассматривается система из любого количества задач.

Следует отметить, что эта схема работает лишь в случае одновременного нали­чия задач. В качестве контрпримера можно рассмотреть пять задач. -4. В, С, D и Е, причем первые две доступны стразу же. а три оставшиеся — еще через три минуты. Время выполнения этих задач составляет 2,4,1.1 и 1 мин соответственно. Вначале можно выбрать только А или В, поскольку остальные недоступны. Если руковод­ствоваться алгоритмом «Кратчайшая задача — первая», задачи будут запушены в следующем порядке: А, В, С, D, Е, и среднее оборотное время составит 4,6 мин. Если же запустить их в порядке В, С, D, Е, А, то среднее оборотное время составит 4,4 мин.

 

Алгоритмы планирования. Наименьшего оставшегося времени выполнения. Версией алгоритма «Кратчайшая задача» с переключениями является алгоритм наимень­шего оставшегося времени выполнения. В соответствии с этим алгоритмом плани­ровщик каждый раз выбирает процесс с наименьшим оставшимся временем вы­полнения. В этом случае также необходимо заранее знать время выполнения задач. Когда поступает новая задача, ее полное время выполнения сравнивается с оставшимся временем выполнения текущей задачи. Если время выполнения но­вой задачи меньше, текущий процесс приостанавливается и управление передает­ся новой задаче. Эта схема позволяет быстро обслуживать короткие запросы.

 

Алгоритмы планир-я. Алгоритм трёхуровневое планирование

Системы пакетной обработки позволяют реализовать трехуровневое планирова­ние. По мере поступления в систему новые задачи сначала помешаются в очередь, хранящуюся на диске. Впускной планировщик вы­бирает задание и передает его системе. Остальные задания остаются в очереди. Характерный алгоритм входного контроля может заключаться в выборе смеси из процессов, ограниченных возможностями процессора, и процессов, ограниченных возможностями устройств ввода-вывода. Также возможен алгоритм, в α устан-ся приоритет коротких задач перед длинными. Впускной планировщик волен придержать неα задания во входной очереди, а пропустить зада­ние, поступившее позже остальных. Как только задание попало в систему, для него будет создан соотв процесс, и он может тут же вступить н борьбу за доступ к процессору. Тем не менее возможна ситуация, когда процессов слишком много и они все в памяти не помещаются, тогда неαе из них будут выгружены на диск.Второй уровень планирования определяет, какие процессы можно хранить в памяти, а какие — на диске. Этим занимается планировщик памяти. С одной стороны, распределение процессов необходимо часто пересматривать, чтобы у процессов, хранящихся на диске, был шанс получить доступ к процессору. С другой, перемещение процесса с диска в память требует затрат, поэтому к диску следует обращаться не чаще, чем раз в сек. Если содержимое опер памяти будет слишком часто меняться, проп спос-ть диска будет расх-ся впустую, что замедлит файловый вв-вывод. Для оптимизации эфф-сти системы планировщик памяти должен решить, сколько и каких процессов может 1временно нах-ся в памяти. Кол-тво процессов, 1временно нах-ся В памяти, наз-ся степенью многозадачности. Если планировщик памяти обладает инф-й о том, какие процессы ограничены возм-ми процессора, а какие - возм-ми устр-в вв-вывода, он может пытаться поддерживать смесь этих процессов в памяти..  Планировщик памяти периодически просматривает процессы, находящиеся на диске, чтобы решить, какой из них переместить в память. Среди критериев: 1.   Сколько времени прошло, как процесс был выгружен на диск или загружен с диска? 2.   Сколько времени процесс уже использовал процессор? 3.   Каков размер процесса (маленькие процессы не мешают)? 4.   Какова важность процесса?

Третий уровень планирования отвечает за доступ процессов, находящихся в со­стоянии готовности, к процессору. Когда идет разговор о «планировщике», обычно имеется в виду именно планировщик процессора. Этим планировщиком использу­ется любой подходящий к ситуации алгоритм, как с прерыванием, так и без.

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

• Циклическое планирование

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

(Приоритет-число,α хар-т степень привелегированности при исп-и ресурсов Относительные приоритеты-если задача вып-ся то она вып-ся до конца Абс-при поступлении задачи если у неё приоритет выше, исп-я задача прерывается)

Циклическое планирование  Одним из наиболее старых, простых, справедливых и часто используемых является алгоритм циклического планирования. Каждому процессу предоставля­ется неα интервал времени процессора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а управ­ление передается другому процессу. если процесс блокируется или прекращает работу раньше, переход управления происходит в этот момент. Реализация циклич планирования проста. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности согласно рисунку 2.23, а. Когда процесс исчерпал свои лимит времени, он отправляется в конец списка (рис. 2.23, б). Единственным интересным моментом этого алгоритма является длина кванта. Переключение с одного процесса на другой занимает неα время — необхо­димо сохранить и загрузить регистры и карты памяти, обновить таблицы и спис­ки, сохранить и перезагрузить кэш памяти и т. п. Важен и тот фактор, что если установленное значение кванта больше среднего интервала работы процессора, переключение процессов будет происходить редко. Напротив, большинство процессов будут совершать блокирующую операцию прежде, чем истечет длительность кванта, вызывая переключение процессов. Устранение принудительных переключений процессов улучшает произв-ть системы, так как переключения процессов будут происходить только когда это логически необходимо, т е когда процесс заблокировался и не может продолжать работу.

Вывод: слишком малый квант приведет к частому переключению процессов и небольшой эффективности, но слишком большой квант может привести к медленному реагированию на короткие интерактивные запросы. Значение кванта 20-50 мс -разумный компромисс.

Приоритетное планирование    Приоритет-число,α хар-т степень привелегированности при исп-и ресурсов Относительные приоритеты-если задача вып-ся то она вып-ся до конца Абс-при поступлении задачи если у неё приоритет выше, исп-я задача прерывается  В ситуации компьютера с большим числом пользователей процессы могут быть не равнозначны.. Основная идея: каждому процессу присваи­вается приоритет, и управление передастся готовому к работе процессу с самым высоким пр-м. Даже на ПК с 1 пользователем может происходить несколько процессов, отдельные из α являются более важными, чем дру­гие. Демон, отвечающий за пересылку эл почты в фоновом режиме, име­ет более низкий приоритет, чем процесс, отображающий на экране видеофильм в реальном времени.Чтобы предотвратить беск- работу процессов с высоким приоритетом, планировщик может уменьшать приоритет процесса с каждым тактом часов (прерывании по таймеру). Если в рез-е приоритет текущего процесса окажется ниже, чем приоритет следующего процесса, произойдет переключение. Возможно предоставление каждому процессу макс отрезка времени работы. Как только время кончилось, упр-е передается следующе­му по приоритету процессу. Приоритеты процессам могут присваиваться статически или динамически. В системе UN'IX есть команда nice, позволяющая пользователю добровольно снизить приоритет своих процессов, чтобы быть вежливым по отношению к остальным польз-м. Система может динамически назначать приоритеты для достижения своих це­лей. Например, неα процессы сильно ограничены возм-ми устр-в ввода-вывода и большую часть времени проводят в ожидании завершение операций ввода-вывода. Когда бы ни потребовался процессор такому процессу, его следует немедленно предоставить, чтобы процесс мог начать следующий запрос ввода-вывода, который будет выполняться параллельно с вычислениями другого процесса. Если заставить такой процесс, длительное время ждать доступа к процессору, он будет неоправданно долго находиться в памяти. Простой алгоритм обслуживания процессов, ограни­ченных возможностями устройств ввода-вывода, состоит в установке приоритета, равного 1/f, где f— часть исп-го в последний раз кванта. Процесс, исп-й всего 1 мс из 50 мс кванта, получит приоритет 50, процесс, использовавший 25 мс, получит приоритет 2, а исп-й весь квант - 1.

Часто бывает удобно сгруппировать процессы в классы по приоритетам и исп-ть приоритетное планирование среди классов, но циклическое планир-е внутри каждого класса. На рис. 2.24 представлена система с 4 классами приоритетов. Алгоритм планирования: пока в классе 4 есть готовые к запуску процессы, они запускаются один за другим согласно алг-му циклического планирования, и каждому отводится квант времени. При этом классы с более низким приоритетом не будут их беспокоить. Если в классе 4 нет готовых к запуску процессов, запускаются процессы класса 3 и т. д. Если при­оритеты постоянны, до процессов класса 1 процессор может не дойти никогда.

Планирование в системах реального времени. В системах реального времени существенную роль играет время. Чаще всего одно или несколько внешних физических устройств генерируют входные сигналы, и компьютер должен адекватно на них реагировать в течение заданного промежут­ка времени. Например, компьютер в проигрывателе компакт-дисков получает биты от дисковода и должен за очень маленький промежуток времени конвертировать их в музыку. Если процесс конвертации будет слишком долгим, звук окажется искаженным. Подобные системы также используются для наблюдения за пациен­тами в палатах интенсивной терапии, в качестве автопилота самолета, для управ­ления роботами на автоматизированном производстве. В любом из этих случаев запоздалая реакция ничуть не лучше, чем отсутствие реакции. Системы реального времени делятся на жесткие системы реального времени, что означает наличие жестких сроков для каждой задачи (в них обязательно надо укладываться), и гибкие системы реального времени, в которых нарушения вре­менного графика нежелательны, но допустимы. В обоих случаях реализуется раз­деление программы па несколько процессов, каждый из которых предсказуем. Эти процессы чаще всего бывают короткими л завершают свою работу в течение секун­ды. Когда появляется внешний сигнал, именно планировщик должен обеспечить соблюдение графика. Внешние события, на α система должна реагировать, можно разделить на периодические(возникающие через регулярные интервалы времени) и непери­одические ' (пикающие непредсказуемо). Возможно наличие нескольких периодических потоков событий, которые система должна обрабатывать. В зав-ти от времени, затрач на обработку каждого из событий, может оказаться, что система не в состоянии своевременно обработать все события. Если в систему поступает т периодич событий, событие с номером / поступает с периодом Рiiи на его обработку уходит С, секунд работы процессора, вес потоки могут быть сво­евременно обработаны только при выполнении условия.  Системы реального времени, удовлетворяющие этому условию, называются поддающимися планированию или планируемыми. Алгоритмы планирования для систем реального времени могут быть как ста­тическими, так и динамическими. В первом случае все решения планирования принимаются заранее, еще до запуска системы. Во втором случае решения пла­нирования принимаются по ходу дела. Статическое планирование применимо толь­ко при наличии достоверной инф-и о работе, которую необходимо выпол­нить; и о временном графике, которого нужно придерживаться. Динамическое планирование не нуждается в подобных ограничениях. На этом мы отложим изу­чение алгоритмов планирования и вернемся к ним в главе 7. посвященной муль­тимедийным системам реального времени.

 

2. _{ОС UNIX.}

   1. _{Основные характеристики ОС UNIX.}

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

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

3.) Интерфейс пользователя. Пользователь взаимодействует с системой UNIX на использовании командных языков. После входа пользователя в систему у него запускается командный интерпретатор shell (оболочка).

4.) Атрибуты файлов. Владелец может назначить защиту файла со стороны 3х классов пользователей: собственно владельца; группы пользователей, к которой принадлежит владелец;  всех пользова-телей, имеющих доступ к системе. Каждый файл имеет 3 вида разрешения на доступ: чтение (r); запись (w); выполнение (x).

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

6.) Привилегированный пользователь — Центральной частью системы UNIX являет-ся ядро (kernel). Ядро идентифицирует каждого пользователя по его идентифи-катору UID (UserIdentifier), уникальному целому значению, присвоенному пользова-телю при регистрации в системе. Кроме того, каждый пользователь относится к группе пользователей, которая идентифи- цируется некоторым целым значением GID (Group Identifier).

Администратору системы выделяется нулевое значение UID. Пользователь с таким значением UID называется суперпользователь (superuser) или root. Он имеет неограниченные права на доступ к любому файлу и на выполнение любой программы. На суперпользователя не распространяется ограничение на исполь- зуемые ресурсы.

7.) Стандартные файлы - многие команды работают по умолчанию со стандартными файлами:

Standard Input (S.I.) – стандартный поток ввода;

Standard Output (S.O.) – стандартный поток вывода;

Diagnostic Output (D.O.) – диагностический поток вывода.

Однако есть средства изменения умолчаний. Эти средства называются перенаправлением ввода и вывода (<,>).

8.) Режимы переднего и заднего плана – обычно команды выполняются в режиме переднего плана (foreground), т.е. «пока вы ждете». Однако если во время выполнения некоторой команды вы хотите выполнять другие команды, то эту (первую) команду можно выполнить в режиме заднего плана (background). Для того чтобы команда выполнялась в режиме заднего плана, необходимо ее закончить знаком &

2. _{Что такое командный интерпретатор?}

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

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

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

ОС Linux использует несколько различных видов интерпретаторов. Наиболее распространенными среди них являются:

• sh. Bourne Shell. Прообраз командных интерпретаторов сегодняшнего дня. В современных Linux-системах sh представляет собой символическую ссылку на файл bash;

• bash. Bourne-Again SHell. Основной командный интерпретатор ОС Linux. Представляет собой развитие ash и sh. Поддерживает богатый язык написания скриптов, удобный интерфейс для редактирования командной строки, автопродолжение команд и множество других полезных возможностей;

• tcsh. C Shell. Расширенная версия интерпретатора C Shell, использующегося в BSD-системах. Поддерживает функцию автозавершения текста и расширенные возможности редактирования;

• zsh. Очень развитый командный интерпретатор, объединяющий в себе возможности csh, bash с дополнительными, такими как: улучшенная поддержка автопродолжения, более развитые возможности редактирования, расширенные файловые шаблоны и ряд других;

• nash. Not A SHell. Предельно облегченная оболочка, предназначенная для интерпретации сценариев в linuxrc файлах, при загрузке с виртуального диска initrd. Не позволяет работать пользователю в интерактивном режиме.