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

Вход и выход  из критической области с помощью  команды tsl

enter region:

tsl register.lock /* значение lock копируется в регист. знач переменной уст равным 1 */

стр register.#0 /* Старое значение lock сравнивается с нулем */

jne enter region /* Если оно ненулевое, значит, блок уже была. Уст., поэтому цикл */

ret /* Возврат в вызывающую программу . процесс вошел в критическую область */

leave region:

move 1оск.#0 /* Сохранение О  в переменной lock */

 

Вопрос 12. Семафоры. Решение проблемы producer-consumer с помощью  семафоров

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

P-Proberen, V-Verhogen

down – понижает количество активизаций

up – повышает

И чтение значения семафора и изменение значения семафора, а  так же завершение процесса является единой атомарной операцией. Атомарность  достигается с помощью команды  tsl. В отличие от активного ожидания время работы семафора составляет микросекунды. В случае если переменная функции down = 0 – процесс блокируется. Здесь может работать только функция up, которая изменит значение переменной на 1 и это позволит снова сработать функции down. Таким образом значение переменной остается = 0, но количество активизаций уменьшается на 1.

Семафор является основным элементом работы ядра любой ОС.

Решение задачи производитель-потребитель с помощью семафоров.

 

Producer                Consumer

 

N

#define N100

typedef int semaphore;

semaphore mutex=1;

semaphore empty=N;

semaphore full=0;

void producer (void)

{int item;

while (TRUE) {

item=produce_item();

down (&empty); 1я неделимая атомарная операция

down (&mutex);

insert_item(item);

up (&mutex); 2я неделимая атомарная операция

up (&full);

}

}

void consumer (void)

{int item;

while (TRUE) {

down (&full);

down (&mutex);

item = remove_item();

up (&mutex);

up (&empty);

consume_item (item);

}}

 

Здесь 3 семафора: empty – характеризует наличие свободных элементов буфера, full – характеризует количество заполненных элементов буфера, mutex – блокирующая переменная, она блокирует критическую секцию, пока та не будет освобождена. Имеется две активизации: производитель - Producer и потребитель – Consumer.

Функция produce_item() создает запись, insert_item(item) – записывает в буфер запись, remove_item() – вырезает запись из буфера, consume_item – использование вырезанной записи.

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

 

Вопрос 13. Мьютексы. Решение проблемы producer-consumer с помощью мьютексов

Мьютекс – это  семафор, блокирующий критическую  секцию, используется в основном при  синхронизации потоков. Если значение мьютекса = 0, то критическая секция открыта, если значение мьютекса = какому–нибудь  другому значению, то критическая секция заблокирована.

 

mutex_lock – заблокировать

mutex_unlock – разблокировать

mutex_lock;

tsl Register, mutex

cmp Register, #0

jze ok

CALL thread_yield

jmp mutex_lock

ok: RET

mutex_unlock:

mov mutex, #0

RET

 

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

Если все ядра CPU загружены приблизительно на 100%, то они работают эффективно. Чем ближе эта цифра к 100%, тем эффективнее выполняется программа.

pthread – поток

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

pthread_mutex_init

pthread_mutex_destroy

pthread_mutex_lock – блокировка критической секции и thread_yield в случае если заблокирована

pthread_mutex_trylock – блокировка критической секции и возврат ошибки если секция занята

pthread_mutex_unlock – разблокирование критической секции

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

Мьютексы всегда используются в сочетании с условными переменными:

pthread_cond_init – создание

pthread_cond_destroy - удаление

pthread_cond_wait – блокировка в ожидании сигнала

pthread_cond_signal – сигнал другому потоку на его активизацию

pthread_cond_broadcast – сигнал нескольким потокам на активизацию

 

Решение задачи производитель-потребитель  с помощью мьютексов.

 

#include <stdio.h>

#include <pthread.h>

#define MAX 1000000000

pthread_mutex_t the_mutex;

pthread_cond_t cond c, cond p;

int buffer=0;

void * producer (void * ptr)

{int i;

for (i=1; i<=MAX; i++) {

pthread_mutex_lock (&the_mutex);

while (buffer!=0) pthread_cond_wait (&cond p; &the_mutex);

buffer=i;

pthread_cond_signal (&cond c);

pthread_mutex_unlock (&the_mutex);}

pthread_exit(0);}

void * consumer (void * ptr)

{int i; for (i=1; i<=MAX; i++)

{pthread_mutex_lock (&the_mutex);

while (buffer==0)

pthread_cond_wait (&cond c, &the_mutex);

buffer=0;

pthread_cond_signal (&cond p);

pthread_mutex_unlock (&the_mutex);

} pthread_exit (0);

}

int main (int argc, char ** argv) {

pthread_t pro, con;

pthread_mutex_init (&the_mutex, 0);

pthread_cond_init (&cond c, 0);

pthread_cond_init (&cond p, 0);

pthread_create (&con, 0, consumer, 0);

pthread_create (&pro, 0, producer, 0);

pthread_join (pro, 0); pthread_join (con, 0);

pthread_cond_destroy (&cond c);

pthread_cond_destroy (&cond p);

pthread_mutex_destroy (&the_mutex);

}

 

Такой мьютекс  может иметь один из следующих  типов:

• PTHREAD_MUTEX_NORMAL — нет контроля повторного захвата тем же потоком
• PTHREAD_MUTEX_RECURSIVE — повторные захваты тем же потоком допустимы, ведётся счётчик таких захватов
• PTHREAD_MUTEX_ERRORCHECK — повторные захваты тем же потоком вызывают немедленную ошибку

 

Вопрос 14. Мониторы

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

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

Давайте применим концепцию мониторов к решению задачи производитель-потребитель.

monitor ProducerConsumer {

      condition full, empty;

      int count;

      void put() {

         if(count == N) full.wait;

         put_item;

         count += 1;

         if(count == 1) empty.signal;

      }

      void get() {

         if (count == 0) empty.wait;

         get_item();

         count -= 1;

         if(count == N-1) full.signal;

      }

      {

         count = 0;

      }

   }

Producer:

   while(1) {

      produce_item;

      ProducerConsumer.put();

   }

Consumer:

   while(1) {

      ProducerConsumer.get();

      consume_item;

   }

Вопрос 15. Сообщения. Решение проблемы producer-consumer с помощью  сообщений

Сообщения - Для прямой и непрямой адресации достаточно двух примитивов, чтобы описать передачу сообщений по линии связи – send иreceive. В случае прямой адресации мы будем обозначать их так:

send(P, message) – послать сообщение message процессу P ;

receive(Q, message) – получить сообщение message от процесса Q.

В случае непрямой адресации мы будем обозначать их так:

send(A, message) – послать сообщение message в почтовый ящик A ;

receive(A, message) – получить сообщение message из почтового ящика A.

Примитивы send и receive уже имеют скрытый от наших глаз механизм взаимоисключения. Более того, в большинстве систем они уже имеют и скрытый механизм блокировки при чтении из пустого буфера и при записи в полностью заполненный буфер. Реализация решения задачи producer-consumer для таких примитивов становится неприлично тривиальной. Надо отметить, что, несмотря на простоту использования, передача сообщений в пределах одного компьютера происходит существенно медленнее, чем работа с семафорами и мониторами.

Вопрос 16. Барьеры

 

MPI_Send (…);

MPI_Recieve (…).

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

Барьер является библиотечной процедурой barrier и часто применяется в параллельном программировании.

MPI_Barrier ();

Cuda Thread Synchronize ();

 

 

 

 

barrier

 

 

Вопрос 17. Планирование процессов. Категории и задачи планирования

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

 

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

-Предоставление каждому процессу справедливого (одинакового) количество процессорного времени.

-Производится  принудительное выполнение политики  приоритетов выполняющихся процессов.

-Планирование  производится таким образом чтобы поддерживался максимальный баланс занятости системы.

 

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

 

 

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

 

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

 

 

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

 

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

 

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

 

Вопрос 18. Алгоритмы  планирования в пакетных системах

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

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

First-Come, First-Served (FCFS)

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

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

Round Robin (RR)

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

Shortest-Job-First (SJF)

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

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

 

Вопрос 19. Алгоритмы  планирования в интерактивных системах

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

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

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