1. Процессы: взаимодействие параллельных процессов – монопольный доступ и взаимоисключение; программная реализация взаимоисключения – примеры, семафоры – определение, виды семафоров, примеры использования множественных семафоров из лабораторных работ «производство-потребление» и «читатели-писатели».
Необходимость монопольного доступа к разделяемым переменным при взаимодействии параллельных процессов обусловлена тем, что при немонопольном доступе возможно возникновение потерянного обновления (ситуация, когда при одновременном изменении одной переменной разными процессами теряются все изменения, кроме последнего). Рассмотрим данную ситуацию на примере:
Пусть есть 2 процесса: P1, P2.
Пусть у них имеются следующие участки кодов (myvar - разделяемая переменная):
| P1 | P2 |
|---|---|
| mov eax, myvar | mov eax, myvar |
| inc eax | inc eax |
| mov myvar, eax | mov myvar, eax |
При выполнении этих 2 процессов параллельно (или квазипараллельно) возможен следующий порядок команд:
| Команды P1 | eax | myvar | eax | Команды P2 |
|---|---|---|---|---|
| 0 | ||||
| mov eax, myvar | 0 | 0 | ||
| 0 | 0 | 0 | mov eax, myvar | |
| 0 | 0 | 1 | inc eax | |
| 0 | 1 | 1 | mov myvar, eax | |
| inc eax | 1 | 1 | 1 | |
| mov myvar, eax | 1 | 1 | 1 |
(myvar должен был стать 2, но стал 1)
Действия, подобные описанным, называются критическими. Секции кода - критическими секциями. Необходимо обеспечить монопольное использование разделяемых параллельными процессами ресурсов. Монопольный доступ к разделяемому ресурсу обеспечивается методами взаимоисключения, то есть если одни процесс находится в критической секции по некоторой разделяемой переменной, другой процесс не может войти в критическую секцию по той же переменной, пока 1 не освободит её.
Способы взаимоисключения:
- Программный
- Аппаратный
- Семафоры
- Мониторы
Утеряна реализация, требуется помощь
В данной реализации второй процесс мог не успеть установить флаг, тогда первый процесс также пройдет цикл while, следовательно снова получаем одновременный доступ.
Утеряна реализация, требуется помощь
Негативные ситуации:
- Бесконечное откладывание
- Тупик (deadlock)
- Захват и освобождение одних и тех же ресурсов
Семафоры – определение, виды семафоров, примеры использования множественных семафоров из лабораторных работ «производство-потребление» и «читатели-писатели».
Семафор — неотрицательная защищенная переменная, на которой определены 2 неделимые операции: P(S) (passeren, пропустить) и V(S) (vrygeven, освободить).
- Операция V(S) - инкремент, S = S + 1. Если S = 0, то операция V(S) может активизировать некоторый процесс блокированный на семафоре.
- Операция P(S) - декремент значения семафора, S = S - 1. Если S = 0, то декремент невозможен и процесс блокируется до тех пор, пока другой процесс не освободит ресурс.
Семафоры исключают активное ожидание на процессоре, но платой за это является переход в режим ядра. Команды, определенные на семафоре являются системными вызовами.
Процесс может создать семафор и изменять его. Удалить семафор может либо процесс создавший его, либо привелегированный процесс. При захвате и освобождении семафора происходит переключение в режим ядра, следовательно происходит переключение контекста.
Виды семафоров:
- Бинарный - принимает только 0 и 1.
- Считающий - прнимает неотрицательные целые значения.
- Множественные семафоры - массив считающих семафоров. Одной неделимой операцией можноз изменить все или часть семафоров набора.
Способы взаимодействий:
- Взаимоисключения, организация монопольного доступа процесса к разделяемой переменной (задача "Читатели-писатели")
- Синхронизация, когда процесс заинтересован в действиях другого процесса (задача "Производство-потребление")
#define BIN_SEM 0
#define BUFF_FULL 1
#define BUFF_EMPTY 2
struct sembuf CONS_LOCK[] = {
{ BUFF_FULL, -1, 0 },
{ BIN_SEM, -1, 0 }
};
struct sembuf CONS_RELEASE[] = {
{ BUFF_EMPTY, 1, 0 },
{ BIN_SEM, 1, 0 }
};
int consumer_run(cbuffer_t *const buf, const int sid, const int consid) {
srand(time(NULL) + consid + 3);
if (!buf) {
return 1;
}
for (int i = 0; i < 8; i++) {
int sleep_time = rand() % CONS_TIME_RANGE + CONS_TIME_START;
sleep(sleep_time);
if (-1 == semop(sid, CONS_LOCK, SEM_SIZE)) {
return 3;
}
char symb;
if (-1 == read_buffer(buf, &symb)) {
return 2;
}
printf("Consumer %d read: %c\n", consid + 1, symb);
if (-1 == semop(sid, CONS_RELEASE, SEM_SIZE)) {
return 3;
}
}
return 0;
}
struct sembuf PROD_LOCK[] = {
{ BUFF_EMPTY, -1, 0 },
{ BIN_SEM, -1, 0 }
};
struct sembuf PROD_RELEASE[] = {
{ BUFF_FULL, 1, 0 },
{ BIN_SEM, 1, 0 }
};
int producer_run(cbuffer_t *const buf, const int sid, const int prodid) {
srand(time(NULL) + prodid);
if (!buf) {
return 1;
}
for (size_t i = 0; i < 8; i++) {
int sleep_time = rand() % PROD_TIME_RANGE + PROD_TIME_START;
sleep(sleep_time);
if (-1 == semop(sid, PROD_LOCK, SEM_SIZE)) {
return 3;
}
const char symb = (buf->write_pos % 26) + 'a';
if (-1 == write_buffer(buf, symb)) {
return 2;
}
printf("Producer %lu write: %c\n", prodid + 1, symb);
if (-1 == semop(sid, PROD_RELEASE, SEM_SIZE)) {
return 3;
}
}
return 0;
}#define ACTIVE_READER 0
#define ACTIVE_WRITER 1
#define WRITE_QUEUE 2
#define READ_QUEUE 3
struct sembuf READER_LOCK[] = {
{ READ_QUEUE, 1, 0 },
{ ACTIVE_WRITER, 0, 0 },
{ WRITE_QUEUE, 0, 0 },
{ ACTIVE_READER, 1, 0 },
{ READ_QUEUE, -1, 0 },
};
struct sembuf READER_RELEASE[] = {
{ ACTIVE_READER, -1, 0 },
};
struct sembuf WRITER_LOCK[] = {
{ WRITE_QUEUE, 1, 0 },
{ ACTIVE_READER, 0, 0 },
{ ACTIVE_WRITER, 0, 0 },
{ ACTIVE_WRITER, 1, 0 },
{ WRITE_QUEUE, -1, 0 },
};
struct sembuf WRITER_RELEASE[] = {
{ ACTIVE_WRITER, -1, 0 },
};
int start_read(int sid) {
return semop(sid, READER_LOCK, 5) != -1;
}
int stop_read(int sid) {
return semop(sid, READER_RELEASE, 1) != -1;
}
int start_write(int sid) {
return semop(sid, WRITER_LOCK, 5) != -1;
}
int stop_write(int sid) {
return semop(sid, WRITER_RELEASE, 1) != -1;
}
int reader_run(int *const shared_mem, const int sid, const int rid) {
srand(time(NULL) + rid);
if (!shared_mem) {
return 1;
}
for (size_t i = 0; i < 8; i++) {
int sleep_time = rand() % TIME_RANGE + TIME_START;
sleep(sleep_time);
if (!start_read(sid)) {
return 2;
}
int readed = *shared_mem;
fprintf(stdout, "Reader %d read: %d\n", rid + 1, readed);
if (!stop_read(sid)) {
return 3;
}
}
return 0;
}
int writer_run(int *const shared_mem, const int sid, const int wid) {
if (!shared_mem) {
return 1;
}
for (size_t i = 0; i < ITER_CNT; i++) {
int sleep_time = rand() % TIME_RANGE + TIME_START;
sleep(sleep_time);
if (!start_write(sid)) {
return 4;
}
int updated = ++(*shared_mem);
fprintf(stdout, "Writer %d write: %d\n", wid + 1, updated);
if (!stop_write(sid)) {
return 5;
}
}
return 0;
}В Windows при создании процесса, ему назначается базовый приоритет. Относительно базового приоритета процесса потоку назначается относительный приоритет.
Планирование осуществляется на основании приоритетов потоков, готовых к выполнению. Поток с более низким приоритетом вытесняется планировщиком, когда поток с более высоким приоритетом становится готовым к выполнению. По истечению кванта времени текущего потока, ресурс передается первому — самому приоритетному — потоку в очереди готовых на выполнение.
Раз в секунду диспетчер настройки баланса сканирует очередь готовых потоков. Если обнаружены потоки, ожидающие выполнения более 4 секунд, диспетчер настройки баланса повышает их приоритет до 15. Как только квант истекает, приоритет потока снижается до базового приоритета. Если поток не был завершен за квант времени или был вытеснен потоком с более высоким приоритетом, то после снижения приоритета поток возвращается в очередь готовых потоков.
Чтобы минимизировать расход процессорного времени, диспетчер настройки баланса сканирует лишь 16 готовых потоков. Кроме того, диспетчер повышает приоритет не более чем у 10 потоков за один проход: обнаружив 10 потоков, приоритет которых следует повысить, он прекращает сканирование. При следующем проходе сканирование возобновляется с того места, где оно было прервано в прошлый раз. Наличие 10 потоков, приоритет которых следует повысить, говорит о необычно высокой загруженности системы.
В Windows используется 32 уровня приоритета: целое число от 0 до 31, где 31 — наивысший приоритет, из них:
- от 16 до 31 — уровни реального времени;
- от 0 до 15 — динамические уровни, уровень 0 зарезервирован для потока обнуления страниц.
Уровни приоритета потоков назначаются Windows API и ядром операционной системы.
Windows API сортирует процессы по классам приоритета, которые были назначены при их создании:
- реального времени (real-time, 4);
- высокий (high, 3);
- выше обычного (above normal, 6);
- обычный (normal, 2);
- ниже обычного (below normal, 5);
- простой (idle, 1).
Затем назначается относительный приоритет потоков в рамках процессов:
- критичный по времени (time critical, 15);
- наивысший (highest, 2);
- выше обычного (above normal, 1);
- обычный (normal, 0);
- ниже обычного (below normal, -1);
- низший (lowest, -2);
- простой (idle, -15).
Исходный базовый приоритет потока наследуется от базового приоритета процесса. Процесс по умолчанию наследует свой базовый приоритет у того процесса, который его создал.
Соответствие между приоритетами Windows API и ядра системы приведено в следующей таблице.
Текущий приоритет потока в динамическом диапазоне — от 1 до 15 — может быть повышен планировщиком вследствие следующих причин:
- повышение вследствие событие планировщика или диспетчера;
- повышение приоритета владельца блокировки;
- повышение приоритета после завершения ввода/вывода (таблица ниже);
- повышение приоритета вследствие ввода из пользовательского интерфейса;
- повышение приоритета вследствие длительного ожидания ресурса исполняющей системы;
- повышение вследствие ожидания объекта ядра;
- повышение приоритета в случае, когда готовый к выполнению поток не был запущен в течение длительного времени;
- повышение приоритета проигрывания мультимедиа службой планировщика MMCSS.
Текущий приоритет потока в динамическом диапазоне может быть понижен до базового приоритета путем вычитания всех повышений.
Потоки, на которых выполняются различные мультимедийные приложения, должны выполняться с минимальными задержками. В Windows эта задача решается путем повышения приоритетов таких потоков драйвером MMCSS -- MultiMedia Class Scheduler Service. Приложения, которые реализуют воспроизведение мультимедиа, указывают драйверу MMCSS задачу из списка:
- аудио;
- игры;
- распределение;
- захват;
- воспроизведение;
- задачи администратора многоэкранного режима.
Одно из наиболее важных свойств для планирования потоков -- категория планирования -- первичный фактор определяющий приоритет потоков, зарегистрированных в MMCSS. Различные категории планирования представленны в таблице ниже.
| Категория | Приоритет | Описание |
|---|---|---|
| High (Высокая) | 23-26 | Потоки профессионального аудио (Pro Audio), запущенные с приоритетом выше, чем у других потоков на системе, за исключением критических системных потоков |
| Medium (Средняя) | 16-22 | Потоки, являющиеся частью приложений первого плана, например Windows Media Player |
| Low (Низкая) | 8-15 | Все остальные потоки, не являющиеся частью предыдущих категорий |
| Exhausted (Исчерпавших потоков) | 1-7 | Потоки, исчерпавшие свою долю времени центрального процессора, выполнение которых продолжиться, только если не будут готовы к выполнению другие потоки с более высоким уровнем приоритета |
Функции MMCSS временно повышают приоритет потоков, зарегистрированных с MMCSS до уровня, соответствующего их категориям планирования. Далее, их приоритет снижается до уровня, соответствующего категории Exhausted, для того чтобы другие потоки могли получить ресурс.