Понятие процесса программа вычислительные ресурсы (память, файловые дискрипторы, сокеты, блокировки) текущее состояние Таненбаум: Процесс – это адресное пространство и единая нить управления

Процесс как объект ОС Структура для процесса (Process control block) название ссылка на родителя состояние программный счетчик указатель на стек выделенные области памяти другая информация по ресурсам (файлы,...) служебная информация (учетная, планировочная,...)

Нити (threads) Нити – это несколько потоков управления в рамках одного процесса. программный счетчик регистры стек Дилемма: управления нитями внутри процесса (green threads) с помощью средств ОС (native threads)

Запуск процесса родитель клонирование или загрузка из файла выделение ресурсов, запись программы в память блокирующее и неблокирующее порождение

Работа процесса Состояния: готовность ожидание блокировка переключение контекста Контекст: регистровый динамический пользовательский

Жизненный цикл процесса

Переключение контекста

Завершение процесса информация о процесее остается до обращения к ней родителя зависимость порожденных процесоов от родительского при завершении

Обработка прерываний Таблица дескрипторов прерываний: вектора прерываний (адреса процедур обработки прерываний) Clock interrupt

Планирование процессов долгосрочное среднесрочное краткосрочное вытесняющее невытесняющее

Требования к алгоритмам планирования (специфичные) справедливость эффективность сокращение полного времени выполнения (turnaround time) сокращение времени ожидания (waiting time) сокращение времени отклика (response time)

Требования к алгоритмам планирования (общие) стабильность (предсказуемость) эффективное использование ресурсов: минимальные накладные расходы равномерная загрузка масштабируемость

Алгоритмы планирования Первый пришел, первый обслужен (FCFS) Круговая система (Round Robin)

Алгоритмы планирования (2) Многоуровневые очереди Сперва самая короткая работа (SJF) Гарантированное планирование Приоритетное планирование Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

Планирование в UNIX/Linux O(1) Приоритетное гарантированное по классам: прерывания реального времени пользовательские (time-sharing) batch-процессы (idle) фиксированный приоритет эпохи время отклика для интерактивных процессов учет SMP/SMT

Межпроцессное взаимодействие (IPC) передача сообщений между процессами конкуренция за критические ресурсы зависимость одного процесса от другого }

Причины взаимодействия Повышение скорости работы Совместное использование данных Модульная конструкция какой-либо системы (например, микроядерная архитектура ОС) Комбинация существующих решений (принцип UNIX: Small pieces loosely joined)

Состязание за ресурсы (race conditions) Вопрос при разработке ОС – выбор примитивных (атомарных) операций для взаимно исключяющего доступа к общим ресурсам.

Критические области процесса Правила: Несколько процессов не должны одновременно исполнять свою критическую области Не должно быть рассчета на ту или иную скорость и кол-во ЦП Процессы, выполняемые вне своей критической области, не могут блокировать другие процессы Ни один процесс не должен ждать вечно для входа в критическую область

Алгоритм Петерсона int turn; /* whose turn is it? */ int interested[N]; /* all values initially 0 (FALSE)*/ void enter_region(int process) /* process is 0 or 1 */ { int other; /* number of the other process */ other = 1 - process; /* the opposite of process */ interested[process] = TRUE; /* show that you are interested */ turn = process; /* set flag */ while (turn == process && interested[other] == TRUE) /* null statement */; } void leave_region(int process) /* process: who is leaving */ { interested[process] = FALSE; /* indicate departure from critical region */ }

Использование TSL enter_region: TSL REGISTER,LOCK |copy LOCK to register and set LOCK to 1 CMP REGISTER,#0 |was LOCK zero? JNE ENTER_REGION |if it was non zero, LOCK was set, so loop RET |return to caller; critical region entered leave_region: MOVE LOCK,#0 |store a 0 in LOCK RET |return to caller

Использование семафоров #define N 100 /* number of slots in the buffer */ typedef int semaphore; /* semaphores are a special kind of int */ semaphore mutex = 1; /* controls access to critical region */ semaphore empty = N; /* counts empty buffer slots */ semaphore full = 0; /* counts full buffer slots */ void producer(void) { int item; while (TRUE){ /* TRUE is the constant 1 */ item = produce_item(); /* generate something to put in buffer */ down(&empty); /* decrement empty count */ down(&mutex); /* enter critical region */ insert_item(item); /* put new item in buffer */ up(&mutex); /* leave critical region */ up(&full); /* increment count of full slots */ }

Использование семафоров (2) void consumer(void) { int item; while (TRUE){ /* infinite loop */ down(&full); /* decrement full count */ down(&mutex); /* enter critical region */ item = remove_item(); /* take item from buffer */ up(&mutex); /* leave critical region */ up(&empty); /* increment count of empty slots */ consume_item(item); /* do something with the item */ }

Использование монитора monitor ProducerConsumer condition full, empty; integer count; procedure insert(item: integer); begin if count = N then wait(full); insert_item(item); count := count + 1; if count = 1 then signal(empty) end; function remove: integer; begin if count = 0 then wait(empty); remove = remove_item; count := count 1; if count = N 1 then signal(full) end; count := 0; end monitor;

Использование монитора (2) procedure producer; begin while true do begin item = produce_item; ProducerConsumer.insert(item) end end; procedure consumer; begin while true do begin item = ProducerConsumer.remove; consume_item(item) end end;

Обмен сообщениями сигнальными канальный разделяемая память

Канальный способ потоковый (pipe, FIFO) передача сообщений (сокеты) Адресация: прямая: симметричная ассиметричная непрямая Буферизация?

Передача сообщений Shared nothing Почтовые ящики, рандеву

Передача сообщений (пример) void producer(void) { while (TRUE) { item = produce_item(); /* generate something to put in buffer */ receive(consumer, &m); /* wait for an empty to arrive */ build_message(&m, item); /* construct a message to send */ send(consumer, &m); /* send item to consumer */ } void consumer(void) { for (i = 0; i < N; i++) send(producer, &m); /* send N empties */ while (TRUE) { receive(producer, &m); /* get message containing item */ item = extract_item(&m); /* extract item from message */ send(producer, &m); /* send back empty reply */ consume_item(item); /* do some1thing with the item */ }