Контрольная работа по "Информатике"

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

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

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

Если в системе  одновременно работаю k пользователей, то одному будет предоставлено (1/k) процессорного  времени, а в системе с одним  пользователем запущено n процессов, то каждому процессу достанется (1/n) процессорного времени. система сама следит за количеством процессов и отслеживает промежутки процессорного времени, выделяемого каждому из процессов (или пользователей).

Лотерейное планирование

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

Справедливое планирование

Во внимание берётся тот, кто запускает процесс. Если один пользователь создал 9 процессов, а параллельный ему второй - 1, то при таком планировании система  распределит время процессора между  пользователями пополам, в то время как другие виды планирования отдали большинство процессорного времени первому пользователю. Данное планирование отведёт ровно 50% процессорного времени одному из двух пользователей, независимо от того, как он будет использовать эти 50%.

 

Вопрос 20. Планирование потоков

Из  лекции:

В потоках планировщик  может быть либо в режиме пользования, либо в режиме ядра:

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

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

 

Из нэта:

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

 

Для всех ОС соблюдается  следующие принципы планирования:

 

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

 

 

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

 

1. Максимальная пропускная способность ЭВМ в целом.
2. Максимальное использование процессора.
3. Минимальное время выполнения одного задания (процесса).

 

 

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

 

Кроме того в  этом случи ОС должна уметь настраиваться  под пожелания отдельных пользователей.

 

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

 

Вопрос 21. Задача обедающих философов

Постановка задачи

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

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

Каждый философ может взять ближайшую вилку (если она доступна), или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

Суть проблемы заключается в том, чтобы разработать модель поведения (параллельный алгоритм), при котором ни один из философов не будет голодать, то есть будет вечно чередовать приём пищи и размышления.

Решение задачи

Относительно  простое решение задачи достигается  путём добавления официанта возле  стола. Философы должны дожидаться разрешения официанта перед тем, как взять вилку. Поскольку официант знает, сколько вилок используется в данный момент, он может принимать решения относительно распределения вилок и тем самым предотвратить взаимную блокировку философов. Если четыре вилки из пяти уже используются, то следующий философ, запросивший вилку, вынужден будет ждать разрешения официанта — которое не будет получено, пока вилка не будет освобождена. Предполагается, что философ всегда пытается сначала взять левую вилку, а потом — правую (или наоборот), что упрощает логику. Официант работает, как семафор — понятие, введённое Дейкстрой в 1965 году.

Чтобы показать, как это решение работает, предположим, что философы обозначены от А до Д по часовой стрелке. Если философы А и В едят, то заняты четыре вилки. Философ Б сидит между А и В, так что ему недоступна ни одна из вилок. В то же время, философы Г и Д имеют доступ к одной неиспользуемой вилке между ними. Предположим, что философ Г хочет есть. Если он тут же берёт свободную вилку, то становится возможна взаимная блокировка философов. Если вместо этого он спрашивает разрешения у официанта, то тот просит его подождать — и можно быть уверенным в том, что как только пара вилок освободится, то по крайней мере один философ сможет взять две вилки. Таким образом, взаимная блокировка становится невозможной.

Задача  обедающих философов

За столом сидят 5 философов. На столе 5 тарелок со спагетти.

Спагетти на столько скользкие, что чтобы  их съесть нужно воспользоваться  двумя вилками, у философов 2 действия: 1 – съесть, 2 – размышлять.

Понять что  одновременно здесь могут есть только 2 философа. Задача сводится к тому, чтобы запрограммировать этот процесс.

Неверное  решение задачи (решение задачи в  лоб):

#define N5

void philosopher (int i)

{ while (TRUE) {

think (); // философ думает

take_fork (i); // берет левую вилку

take_fork ((i+1)%N); // берет правую вилку

edt (); // ест

put_fork (i); // кладет левую вилку

put_fork (i+1)%N); // кладет правую вилку

}}

think – философ думает

 

Правильное решение задачи:

#define N5

#define LEFT (i+N-1)%N //левая вилка

#define RIGHT (i+1)%N //правая вилка

#define THINKING 0 //философ думает

#define HUNGRY 1 //философ хочет взять вилку

#define EATING 2 //философ ест

typedef int semaphore;

int state [N]; //массив состояния философоф

semaphore mutex=1; //защищает критич. секцию

semaphore S[N]; //симафор для каждого философа

----------------------------------------

void philosopher (int i) {

while (TRUE) {

think ();

take_forks (i);

edt ();

put_forks (i);

}}

----------------------------------------

void take_forks (int i) {

down (&mutex);

state [i] = HUNGRY;

test (i);

up (&mutex);

down (&S[i]);

}

----------------------------------------

void put_forks (i) {

down (&mutex);

state [i] = THINKING;

test (LEFT);

test (RIGHT);

up (&mutex);

}

----------------------------------------

void test (i) {

if (state [i] == HUNGRY&

&state [LEFT]! = EATING&

&state [RIGHT]! = EATING)

{state [i] = EATING;

up (&S[i]);

}}

Задача обедающих  философов помогает решать проблему одновременного доступа процессов к общим ресурсам.

 

Вопрос 22. Задача читателей-писателей

Задача читателей  и писателей

Применяется в БД. Суть в том, что при изменении БД читатель не должен иметь доступ к  БД.

typedef int semaphore;

semaphore mutex =1 ;

semaphore db =1;

int rc = 0;

---------------------------------------------------------------

void reader (void) {

while (TRUE) {

down (&mutex);

rc = rc+1;

if (rc==1) down (&db);

up (&mutex);

read_data_base ();

down (&mutex);

rc = rc -1;

if (rc==0) up (&db);

up (&mutex);

use_data_read (); }}

---------------------------------------------------------------

void write void {

while (TRUE) {

thank_up_data ();

down (&db);

write_data_base ();

up (&db);

}}

Вопрос 23. Понятие  взаимоблокировки. Выгружаемый и  невыгружаемый ресурс

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

Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.

Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).

Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).

Проблема взаимоблокировок процессов  возникает при борьбе за невыгружаемый  ресурсы.

Условия необходимые  для взаимоблокировки:

1. Условие взаимного исключения - в какой-то момент времени, ресурс занят только одним процессом или свободен.
2. Условие удержания и ожидания - процесс, удерживающий ресурс может запрашивать новые ресурсы.
3. Условие отсутствия принудительной выгрузки ресурса.
4. Условие циклического ожидания - должна существовать круговая последовательность из процессов, каждый, из которого ждет доступа к ресурсу, удерживаемому следующим членом последовательности.

 

Вопрос 24. Условия  возникновения взаимоблокировки. Граф распределения ресурсов

Условия необходимые для взаимоблокировки:

1. Условие взаимного исключения - в какой-то момент времени, ресурс занят только одним процессом или свободен.
2. Условие удержания и ожидания - процесс, удерживающий ресурс может запрашивать новые ресурсы.
3. Условие отсутствия принудительной выгрузки ресурса.
4. Условие циклического ожидания - должна существовать круговая последовательность из процессов, каждый, из которого ждет доступа к ресурсу, удерживаемому следующим членом последовательности.

 
Пример графа распределения ресурсов.

 
Данный граф изображает систему с тремя процессами и четырьмя видами ресурсов: ресурсы видов 1 и 3 имеют по одному экземпляру, ресурс вида 2 – два экземпляра, ресурс вида 4 – три экземпляра. Процесс 1 претендует на ресурс 1, который занят процессом 2. Процесс 2 претендует на ресурс 3, который занят процессом 3. Две единицы ресурса 2 отданы процессам 1 и 2. Ресурс 4 не распределялся (все три единицы свободны).

 

??? Вопрос 25. Поиск взаимоблокировки при использовании одного ресурса каждого типа

Начнем с  самого простого варианта: в системе существует только один ресурс каждого типа. Подобная система могла бы иметь один сканер, одно устройство для записи компакт-дисков, один плоттер и один накопитель на магнитной ленте, то есть не более чем по одному представителю каждого класса. Другими словами, мы исключаем из рассмотрения системы с двумя одновременно подключенными принтерами. Мы обратимся к ним позже и будем использовать другой метод. Для такой системы можно сконструировать граф ресурсов вида, продемонстрированного на рис. 3. Если этот граф содержит один или больше циклов, значит, произошла взаимоблокировка и блокирован любой процесс, являющийся частью цикла. Если в графе нет циклов, система не попала в тупик. В качестве примера более сложной системы, чем те, которые мы рассматривали до сих пор, обсудим систему с семью процессами, обозначенными буквами от А до G, и шестью ресурсами, обозначенными буквами от R до W. Состояние системы, то есть то, какой процесс владеет каким ресурсом и какой ресурс запрашивается процессом в данный момент, соответствует следующему списку:

1. Процесс Л  занимает ресурс R и хочет получить  ресурс S.

2. Процесс В  ничего не использует, но хочет  получить ресурс Т.

3. Процесс С  ничего не использует, но хочет  получить ресурс S.

4. Процесс D занимает ресурс U и хочет получить ресурсы S и Т.

5. Процесс Е  занимает ресурс T и хочет получить  ресурс V.

6. Процесс F занимает  ресурс W и хочет получить ресурс S.

7. Процесс G занимает  ресурс V и хочет получить ресурс U.