Создание процессов и потоков. Модели процессов и потоков. Планирование заданий, процессов и потоков. Взаимодействие и синхронизация процессов и потоков.

Лекция 5 5.1. Создание процессов и потоков. Модели процессов и потоков Создать процесс – это, прежде всего, создать описатель процесса: несколько информационных структур, содержащих все сведения (атрибуты) о процессе, необходимые операционной системе для управления им. В число таких сведений могут входить: идентификатор процесса, данные о расположении в памяти исполняемого модуля, степень привилегированности процесса (приоритет и права доступа) и т.п. Примерами таких описателей процесса являются [10, 17]: • • • • блок управления задачей (ТСВ – Task Control Block) в OS/360; управляющий блок процесса (PCB – Process Control Block) в OS/2; дескриптор процесса в UNIX; объект-процесс (object-process) в Windows. Создание процесса включает загрузку кодов и данных исполняемой программы данного процесса с диска в операционную память. Для этого нужно найти эту программу на диске, перераспределить оперативную память и выделить память исполняемой программе нового процесса. Кроме того, при работе программы обычно используется стек, с помощью которого реализуются вызовы процедур и передача параметров. Множество, в которое входят программа, данные, стеки и атрибуты процесса, называется образом процесса. Типичные элементы образа процесса приведены ниже. Информация Описание Данные пользователя Изменяемая часть пользовательского адресного пространства (данные программы, пользовательский стек, модифицируемый код) Пользовательская программа Программа, которую необходимо выполнить Системный стек Один или несколько системных стеков для хранения параметров и адресов вызова процедур и системных служб Управляющий блок процесса Данные, необходимые операционной системе для управления процессом Местонахождение образа процесса зависит от используемой схемы управления памятью. В большинстве современных ОС с виртуальной памятью образ процесса состоит из набора блоков (сегменты, страницы или их комбинация), не обязательно расположенных последовательно. Такая организация памяти позволяет иметь в основной памяти лишь часть образа процесса (активная часть), в то время как во вторичной памяти находится полный образ. Когда в основную память загружается часть образа, она туда не переносится, а копируется. Однако если часть образа в основной памяти модифицируется, она должна быть скопирована на диск. При управлении процессами ОС использует два основных типа информационных структур: блок управления процессом ( дескриптор процесса) и контекст процесса. Дескрипторы процессов объединяются в таблицу процессов, которая размещается в области ядра. На основании информации, содержащейся в таблице процессов, ОС осуществляет планирование и синхронизацию процессов. В дескрипторе (блоке управления) процесса содержится такая информация о процессе, которая необходима ядру в течение всего жизненного цикла процесса независимо от того, находится он в активном или пассивном состоянии и находится ли образ в оперативной памяти или на диске. Эту информацию можно разделить на три категории: • • • информация по идентификации процесса; информация по состоянию процесса; информация, используемая при управлении процессом. Каждому процессу присваивается числовой идентификатор, который может быть просто индексом в первичной таблице процессов. В любом случае должно существовать некоторое отображение, позволяющее операционной системе найти по идентификатору процесса соответствующие ему таблицы. При создании нового процесса идентификаторы указывают родительский и дочерние процессы. В операционных системах, не поддерживающих иерархию процессов, например, в Windows, все созданные процессы равноправны, но один из 18-ти параметров, возвращаемых вызывающему (родительскому) процессу, представляет собой дескриптор нового процесса. Кроме того, процессу может быть присвоен идентификатор пользователя, который указывает, кто из пользователей отвечает за данное задание. Информация по состоянию и управлению процессом включает следующие основные данные: • • • • • • • • • • состояние процесса, определяющее готовность процесса к выполнению (выполняющийся, готовый к выполнению, ожидающий какого-либо события, приостановленный); данные о приоритете (текущий приоритет, по умолчанию, максимально возможный); информация о событиях – идентификация события, наступление которого позволит продолжить выполнение процесса; указатели, позволяющие определить расположение образа процесса в оперативной памяти и на диске; указатели на другие процессы (в частности, находящиеся в очереди на выполнение); флаги, сигналы и сообщения, имеющие отношение к обмену информацией между двумя независимыми процессами; данные о привилегиях, определяющих права доступа к определенной области памяти или возможности выполнять определенные виды команд, использовать системные утилиты и службы; указатели на ресурсы, которыми управляет процесс (например, перечень открытых файлов); сведения по истории использования ресурсов и процессора; информация, связанная с планированием. Эта информация во многом зависит от алгоритма планирования. Сюда относятся, например, такие данные, как время ожидания или время, в течение которого процесс выполнялся при последнем запуске, количество выполненных операций ввода-вывода и др. Контекст процесса содержит информацию, позволяющую системе приостанавливать и возобновлять выполнение процесса с прерванного места. В контексте процесса содержится следующая основная информация [10]: • • содержимое регистров процессора, доступных пользователю; содержимое счетчика команд; • • • состояние управляющих регистров и регистров состояния; коды условий, отражающие результат выполнения последней арифметической или логической операции (например, знак равенства нулю, переполнения); указатели вершин стеков, хранящие параметры и адреса вызова процедур и системных служб. Следует заметить, что часть этой информации, известная как "слово состояния программы" (Program Status Word – PSW), фиксируется в специальном регистре процессора (например, в регистре EFLAGS в процессорах Pentium). Самую простую модель процесса можно построить исходя из того, что в любой момент времени процесс либо выполняется, либо не выполняется, т.е. имеет только два состояния. Если бы все процессы были бы всегда готовы к выполнению, то очередь по этой схеме могла бы работать вполне эффективно. Такая очередь работает по принципу обработки в порядке поступления, а процессор обслуживает имеющиеся в наличии процессы круговым методом (Round-robin). Каждому процессу отводится определенный промежуток времени, по истечении которого он возвращается в очередь. Однако в таком простом примере подобная реализация не является адекватной: часть процессов готова к выполнению, а часть заблокирована, например, по причине ожидания ввода-вывода. Поэтому при наличии одной очереди диспетчер не может просто выбрать для выполнения первый процесс из очереди. Перед этим он должен будет просматривать весь список, отыскивая незаблокированный процесс, который находится в очереди дальше других. Отсюда представляется естественным разделить все невыполняющиеся процессы на два типа: готовые к выполнению и заблокированные. Полезно добавить еще два состояния, как показано на рис. 5.1. Рис. 5.1. Состояния процесса В чем достоинства и недостатки такой модели и как устранить эти недостатки? Поскольку процессор работает намного быстрее выполнения операций ввода-вывода, то вскоре все находящиеся в памяти процессы оказываются в состоянии ожидания ввода-вывода. Таким образом, процессор может простаивать даже в многозадачной системе. Что делать? Можно увеличить емкость основной памяти, чтобы в ней умещалось больше процессов. Но такой подход имеет два недостатка: во-первых, возрастает стоимость памяти, а вовторых, "аппетит" программиста в использовании памяти возрастает пропорционально ее объему, так что увеличение объема памяти приводит к увеличению размера процессов, а не к росту их числа. Другое решение проблемы – свопинг, перенос части процессов из оперативной памяти на диск и загрузка другого процесса из очереди приостановленных (но не блокированных!) процессов, находящихся во внешней памяти. На этом мы прервем рассмотрение модели процессов и их выполнения. Как уже отмечалось, более эффективными являются многопоточные системы. В таких системах при создании процесса ОС создается для каждого процесса минимум один поток выполнения. При создании потоков, так же как и при создании процессов, ОС генерирует специальную информационную структуру – описатель потока, который содержит идентификатор потока, данные о правах доступа и приоритете, о состоянии потока и другую информацию. Описатель потока можно разделить на две части:атрибуты блока управления и контекст потока. Заметим, что в случае многопоточной системы процессы контекста не имеют, так как им не выделяется процессор. Есть два способа реализации пакета потоков [17]: • • в пространстве пользователя или на уровне пользователя (User-level threads – ULT); в ядре или на уровне ядра (kernel-level threads – KLT). Рассмотрим эти способы, их преимущества и недостатки. В программе, полностью состоящей из ULT-потоков, все действия по управлению потоками выполняются самим приложением. Ядро о потоках ничего не знает и управляет обычными однопоточными процессами (рис. 5.2). Рис. 5.2. Потоки в пространстве пользователя Наиболее явное преимущество этого подхода состоит в том, что пакет потоков на уровне пользователя можно реализовать даже в ОС, не поддерживающей потоки. Если управление потоками происходит в пространстве пользователя, каждому процессу необходима собственная таблица потоков. Она аналогична таблице процессов с той лишь разницей, что отслеживает такие характеристики потоков, как счетчик команд, указатель вершины стека, регистры состояния и т. п. Когда поток переходит в состояние готовности или блокировки, вся информация, необходимая для повторного запуска, хранится в таблице потоков. По умолчанию приложение в начале своей работы состоит из одного потока и его выполнение начинается как выполнение этого потока. Такое приложение вместе с составляющим его потоком размещается в одном процессе, который управляется ядром. Выполняющийся поток может породить новый поток, который будет выполняться в пределах того же процесса. Новый поток создается с помощью вызова специальной подпрограммы из библиотеки, предназначенной для работы с потоками. Передача управления этой программе происходит в результате вызова соответствующей процедуры. Таких процедур может быть по крайней мере четыре: thread-create, thread-exit, threadwait и thread-yield, но обычно их больше. Библиотека подпрограмм для работы с потоками создает структуру данных для нового потока, а потом передает управление одному из готовых к выполнению потоков данного процесса, руководствуясь некоторым алгоритмом планирования. Когда управление переходит к библиотечной программе, контекст текущего процесса сохраняется в таблице потоков, а когда управление возвращается к потоку, его контекст восстанавливается. Все эти события происходят в пользовательском пространстве в рамках одного процесса. Ядро даже "не подозревает" об этой деятельности и продолжает осуществлять планирование процесса как единого целого и приписывать ему единое состояние выполнения. Использование потоков на уровне пользователя имеет следующие преимущества [17]: 1. высокая производительность, поскольку для управления потоками процессу не нужно переключаться в режим ядра и обратно. Процедура, сохраняющая информацию о потоке, и планировщики являются локальными процедурами, их вызов существенно более эффективен, чем вызов ядра; 2. имеется возможность использования различных алгоритмов планирования потоков в различных приложениях (процессах) с учетом их специфики; 3. использование потоков на пользовательском уровне применимо для любой операционной системы. Для их поддержки в ядро системы не требуется вносить каких-либо изменений. Однако имеются и недостатки по сравнению с использованием потоков на уровне ядра: • • • в типичной ОС многие системные вызовы являются блокирующими. Когда в потоке, работающем на пользовательском уровне, выполняется системный вызов, блокируется не только этот поток, но и все потоки того процесса, к которому он относится; в стратегии с наличием потоков только на пользовательском уровне приложение не может воспользоваться преимуществом многопроцессорной системы, так как ядро закрепляет за каждым процессом только один процессор. Поэтому несколько потоков одного и того же процесса не могут выполняться одновременно. В сущности, получается мультипрограммирование в рамках одного процесса; при запуске одного потока ни один другой поток не будет запущен, пока первый добровольно не отдаст процессор. Внутри одного процесса нет прерываний по таймеру, в результате чего невозможно создать планировщик для поочередного выполнения потоков. Рассмотрим теперь потоки на уровне ядра. В этом случае в области приложения система поддержки исполнения программ не нужна, нет необходимости и в таблицах потоков в каждом процессе. Вместо этого есть единая таблица потоков, отслеживающая все потоки в системе. Если потоку необходимо создать новый поток или завершить имеющийся, он выполняет запрос ядра, который создает или завершает поток, внося изменения в таблицу потоков (рис. 5.3). Рис. 5.3. Потоки в пространстве ядра Любое приложение можно запрограммировать как многопоточное, при этом все потоки приложения поддерживаются в рамках единого процесса. Ядро поддерживается информацией контекста процесса как единого целого, а также контекстами каждого отдельного потока процесса. Планирование осуществляется ядром, исходя из состояния потоков. С помощью такого подхода удается избавиться от основных недостатков потоков пользовательского уровня. Возможно планирование работы нескольких потоков одного и того же процесса на нескольких процессорах: 1. реализуется мультипрограммирование в режимах нескольких процессов (вообще – всех); 2. при блокировке одного из потоков процесса ядро может выбрать для выполнения другой поток этого же процесса; 3. процедуры ядра могут быть многопоточными. Главный недостаток связан с необходимостью двукратного переключения режимов пользовательский – ядро, ядро – пользовательский для передачи одного потока к другому в рамках одного и того же процесса. 5.2. Планирование заданий, процессов и потоков Основная цель планирования вычислительного процесса заключается в распределении времени процессора (нескольких процессоров) между выполняющимися заданиями пользователей таким образом, чтобы удовлетворять требованиям, предъявляемым пользователями к вычислительной системе. Такими требованиями могут быть, как это уже отмечалось, пропускная способность, время отклика, загрузка процессора и др. Все виды планирования, используемые в современных ОС, в зависимости от временного масштаба, делятся на долгосрочное, среднесрочное, краткосрочное и планирование ввода-вывода. Рассматривая частоту работы планировщика, можно сказать, что долгосрочное планирование выполняется сравнительно редко, среднесрочное несколько чаще. Краткосрочный планировщик, называемый часто диспетчер (dispatcher), обычно работает, определяя, какой процесс или поток будет выполняться следующим. Ниже приведен перечень функций, выполняемых планировщиком каждого вида. Вид планирования Выполняемые функции Долгосрочное Решение о добавлении задания (процесса) в пул выполняемых в системе Среднесрочное Решение о добавлении процесса к числу процессов, полностью или частично размещенных в основной памяти Краткосрочное Решение о том, какой из доступных процессов (потоков) будет выполняться процессором Планирование ввода-вывода Решение о том, какой из запросов процессов (потоков) на операцию ввода-вывода будет выполняться свободным устройством ввода-вывода Место планирования в графе состояний и переходов процессов показано на рис. 5.4. В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), т.е. решения принимаются во время работы системы на основе анализа текущей ситуации, не используя никаких предложений о мультипрограммной смеси. Найденное оперативно решение в таких условиях редко бывает оптимальным. Рис. 5.4. Место планирования в графе процессов Другой тип планирования – статический (предварительный), может быть использован только в специализированных системах с заданным набором задач (заранее определенным), например, в управляющих вычислительных системах или системах реального времени. В этом случае статический планировщик (или предварительный планировщик) принимает решение не во время работы системы, а заранее (off-line). Результатом его работы является расписание – таблица, в которой указано, какому процессу, когда и на какое время должен быть предоставлен процессор. При этом накладные расходы ОС на исполнение расписания значительно меньше, чем при динамическом планировании. Краткосрочный планировщик (диспетчер) реализует найденное решение, т.е. переключает процессор с одного процесса (потока) на другой. Он вызывается при наступлении события, которое может приостановить текущий процессор или предоставить возможность прекратить выполнение данного процесса (потока) в пользу другого. Примерами этих событий могут быть: • • • • прерывание таймера; прерывание ввода-вывода; вызовы операционной системы; сигналы. Среднесрочное планирование является частью системы свопинга. Обычно решение о загрузке процесса в память принимается в зависимости от степени многозадачности (например, OS MFT, OS MVT). Кроме того, в системе с отсутствием виртуальной памяти среднесрочное планирование тесно связано с вопросами управления памятью. Диспетчеризация сводится к следующему: • • • сохранение контекста текущего потока, который требуется сменить; загрузка контекста нового потока, выбранного в результате планирования; запуск нового потока на выполнение. Поскольку переключение контекстов существенно влияет на производительность вычислительной системы, программные модули ОС выполняют эту операцию при поддержке аппаратных средств процессора. В мультипрограммной системе поток (процесс, если операционная система работает только с процессами) может находиться в одном из трех основных состояний: • • • выполнение – активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором; ожидание – пассивное состояние потока, находясь в котором, поток заблокирован по своим внутренним причинам (ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса); готовность – также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые ресурсы, готов выполняться, но процессор занят выполнением другого потока). В течение своей жизни каждый поток переходит из одного состояния в другое в соответствии с алгоритмом планирования потоков, принятом в данной операционной системе. В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в остальных состояниях – несколько. Эти потоки образуют очереди, соответственно, ожидающих и готовых потоков. Очереди организуются путем объединения в списки описателей отдельных потоков. С самых общих позиций все множество алгоритмов планирования можно разделить на два класса: вытесняющие и не вытесняющие алгоритмы планирования. Не вытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по своей инициативе, не отдает управление операционной системе, для того чтобы она выбрала из очереди готовый к выполнению поток. Вытесняющие (preemptive) алгоритмы – это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается операционной системой, а не активной задачей. В первом случае механизм планирования распределяется между операционной системой и прикладными программами. Во втором случае функции планирования потоков целиком сосредоточены в операционной системе. Недостатком первого типа алгоритмов планирования является необходимость разработки такого приложения, которое будет "дружественным" по отношению к другим выполняемым одновременно с ним программам. Для этого в приложении должны быть предусмотрены частные передачи управления операционной системе. Крайним проявлением недружественности приложения является его зависание, которое приводит к общему краху системы. Потому распределение функций планирования между ОС и приложениями достаточно сложно в программистском отношении и используется, как правило, в специализированных системах с фиксированным набором задач. В то же время существенным преимуществом невытесняющего планирования является более высокая скорость переключения потоков. Однако почти во всех ОС (UNIX, Windows, OS/2, VAX/VMS и др.) реализованы вытесняющие алгоритмы планирования. В основе многих таких алгоритмов лежит концепция квантования. В соответствии с ней каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант. Смена активного потока происходит, если: • • • • поток завершается и покинул систему; произошла ошибка; поток перешел в состояние ожидания; исчерпан квант времени, отведенный данному потоку. Поток, который исчерпал свой квант, переводится в состояние готовности и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых потоков. Кванты, выделяемые потокам, могут быть равными или различными (типичное значение десятки – сотни мс). Например, первоначально каждому потоку назначается достаточно большой квант, а величина каждого следующего кванта уменьшается до некоторой заранее заданной величины. В таком случае преимущество получают короткие задачи, которые успевают выполняться в течение первого кванта (второго и т.д.), а длительные вычисления будут проводиться в фоновом режиме. Некоторые потоки, получив квант времени, используют его не полностью, например, из-за необходимости выполнить ввод или вывод данных. В результате может возникнуть ситуация, когда потоки с интенсивным вводом-выводом используют только небольшую часть выделенного им процессорного времени. Можно исправить эту "несправедливость", изменив алгоритм планирования, например, так: создать две очереди потоков, очередь 1 – для потоков, которые пришли в состояние готовности в результате исчерпания кванта времени, и очередь 2 – для потоков, у которых завершилась операция ввода-вывода. При выборе потока для выполнения сначала просматривается вторая очередь, и если она пуста, квант выделяется потоку из первой очереди. Отметим три замечания об алгоритмах, основанных на квантовании. Первое. Переключение контактов потоков связано с потерями процессорного времени, которые не зависят от величины кванта, но зависят от частоты переключения. Поэтому чем больше квант, тем меньше суммарные затраты процессорного времени на переключение потоков. Второе. С увеличением кванта может быть ухудшено качество обслуживания пользователей, связанное с ростом времени реакции системы. Третье. В алгоритмах, основанных на квантовании, ОС не имеет никаких сведений о решаемых задачах (длинные или короткие, интенсивен "ввод-вывод" или нет, важно быстрое исполнение или нет и т.п.). Дифференциация обслуживания при квантовании базируется на "истории существования" потока в системе. Важной концепцией, лежащей в основе многих вытесняющих алгоритмов планирования, является приоритетное обслуживание. Оно предполагает наличие у потоков некоторой изначально известной характеристики – приоритета, на основании которого определяется порядок выполнения потоков. Чем выше приоритет, тем выше привилегии потока, тем меньше времени поток находится в очередях. Приоритет задается числом (целым или дробным, положительным или отрицательным). В большинстве ОС, поддерживающих потоки, приоритет потока связан с приоритетом процесса, в рамках которого выполняется поток. Приоритет процесса назначается операционной системой при его создании, его значение включается в описатель процесса и используется при назначении приоритета потоком этого процесса. При назначении приоритетов вновь созданному процессу ОС учитывается, является ли этот процесс системным или прикладным, каков статус пользователя, запустившего процесс (администратор, пользователь, часть и т.п.), было ли явное указание пользователя на присвоение процессу определенного уровня приоритета. Поток может быть инициирован не только по команде пользователя, но и в результате выполнения системного вызова другим потоком. В этом случае ОС учитывает значения параметров системного вызова. Изменения приоритета могут происходить по инициативе самого потока, когда он обращается с соответствующим вызовом к ОС, или по инициативе пользователя, когда он выполняет соответствующую команду. Кроме этого, сама ОС может изменить приоритеты потоков в зависимости от ситуации, складывающейся в системе. В последнем случае приоритеты называются динамическими в отличие от неизменяемых, фиксированных приоритетов. Возможности пользователей влиять на приоритеты процессов и потоков ограничены ОС. Обычно это разрешается администраторам, и то в определенных пределах. В большинстве случаев ОС присваивает приоритеты потокам по умолчанию. Существует две разновидности приоритетного планирования: с относительными и абсолютными приоритетами. В обоих случаях на выполнение выбирается поток, имеющий наивысший приоритет. Но определение момента смены активного потока решается по-разному. В системах с относительными приоритетами активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (по вводу-выводу, например), или не завершится, или не произойдет ошибка. В системах с абсолютными приоритетами выполнение активного потока прерывается еще и по причине появления потока, имеющего более высокий приоритет, чем у активного потока. В этом случае прерванный поток переходит в состояние готовности. В качестве примера рассмотрим организацию приоритетного обслуживания в Windows. Здесь приоритеты организованны в виде двух групп, или классов: реального времени и переменные. Каждая из групп состоит из 16 уровней приоритетов (рис. 5.5). Потоки, требующие немедленного внимания, находятся в классе реального времени, который включает такие функции, как осуществление коммуникаций и задачи реального времени [17]. Рис. 5.5. Планирование в Windows В целом, поскольку W2K использует вытесняющий планировщик с учетом приоритетов, потоки с приоритетами реального времени имеют преимущество по отношению к прочим потокам. В однопроцессорной системе, когда становится готовым к выполнению поток с более высоким приоритетом, чем выполняющийся в настоящий момент, текущий поток вытесняется и начинает выполняться поток с более высоким приоритетом. Приоритеты из разных классов обрабатываются несколько по-разному. В классе приоритетов реального времени все потоки имеют фиксированный приоритет (от 16 до 31), который никогда не изменяется, и все активные потоки с определенным уровнем приоритета располагаются в круговой очереди данного класса (tкв=20 мс для W2K Professional, 120 мс – для однопроцессорных серверов). В классе переменных приоритетов поток начинает работу с базового приоритета процесса, который может принимать значение от 1 до 15. Каждый поток, связанный с процессом имеет, свой базовый приоритет, равный базовому приоритету процесса, или отличающийся от него не более чем на 2 уровня в большую или меньшую сторону. После активации потока его динамический приоритет может колебаться в определенных пределах – он не может упасть ниже наименьшего базового приоритета данного класса, т.е. 15 (для потоков с приоритетом 16 и выше никогда не делается никаких изменений приоритетов). Когда же увеличивается приоритет потока? Во-первых, когда завершается операция ввода-вывода и освобождается ожидающий ее поток, его приоритет увеличивается, чтобы дать шанс этому потоку запуститься быстрее и снова запустить операцию вводавывода. Суть в том, чтобы поддержать занятость устройств ввода-вывода. Величина, на которую увеличивается приоритет, зависит от устройства ввода-вывода. Как правило, это 1 – для диска, 2 – для последовательной линии, 6 – для клавиатуры и 8 – для звуковой карты. Во-вторых, если поток ждал семафора, мьютекса или другого события, то когда он отпускается, к его приоритету добавляется 2 единицы, если это поток переднего плана (т.е. управляет окном, к которому направляется ввод с клавиатуры), и одна единица – в противном случае. Таким образом, интерактивный процесс получает преимущество перед большим количеством других процессов. Наконец, если поток графического интерфейса пользователя просыпается, потому что стал доступен оконный ввод, он также получает прибавку к приоритету. Эти увеличения приоритета не вечны. Они незамедлительно вступают в силу, но если поток использует полностью свой следующий квант, он теряет один пункт приоритета. Если он использует еще квант, то перемещается еще на уровень ниже и т.д. вплоть до своего базового уровня. Последняя модификация алгоритма планирования W2K заключается в том, что когда окно становится окном переднего плана, все его потоки получают более длительные кванты времени (величина прибавки хранится в системном реестре). Поток, созданный в системе, может находиться в одном из 6 состояний в соответствии с графом, приведенным на рис. 5.6. 5.3. Взаимодействие и синхронизация процессов и потоков В мультипрограммных однопроцессорных системах процессы чередуются, обеспечивая эффективное выполнение программ. В многопроцессорных системах возможно не только чередование, но и перекрытие процессов. Обе эти технологии, которые можно рассматривать как примеры параллельных вычислений, порождают одинаковые проблемы. Выполнение процессов и потоков в мультипрограммной среде всегда имеет асинхронный характер – невозможно предсказать относительную скорость выполнения процессов. Момент прерывания потоков, время нахождения их в очередях к разделяемым ресурсам, порядок выбора потоков для выполнения – все эти события являются результатом стечения многих обстоятельств и являются случайными, это справедливо как по отношению к потокам одного процесса, выполняющим общий программный код, так и по отношению к потокам разных процессов, каждый из которых выполняет собственную программу. Способы взаимодействия процессов (потоков) можно классифицировать по степени осведомленности одного процесса о существовании другого [10]. 1. Процессы не осведомлены о наличии друг друга (например, процессы разных заданий одного или различных пользователей). Это независимые процессы, не предназначенные для совместной работы. Хотя эти процессы и не работают совместно, ОС должна решать вопросы конкурентного использования ресурсов. Например, два независимых приложения могут затребовать доступ к одному и тому же диску или принтеру. ОС должна регулировать такие обращения. 2. Процессы косвенно осведомлены о наличии друг друга (например, процессы одного задания). Эти процессы не обязательно должны быть осведомлены о наличии друг друга с точностью до идентификатора процесса, однако они разделяют доступ к некоторому объекту, например, буферу ввода-вывода, файлу или БД. Такие процессы демонстрируют сотрудничество при разделении общего объекта. 3. Процессы непосредственно осведомлены о наличии друг друга (например, процессы, работающие последовательно или поочередно в рамках одного задания). Такие процессы способны общаться один с другим с использованием идентификаторов процессов и изначально созданы для совместной работы. Эти процессы также демонстрируют сотрудничество при работе. Таким образом, потенциальные проблемы, связанные с взаимодействием и синхронизацией процессов и потоков, могут быть представлены следующей таблицей. Степень осведомленности Взаимосвязь Процессы не Конкуренция осведомлены друг о друге Влияние одного процесса на другой • • Процессы косвенно осведомлены о наличии друг друга Сотрудничество с использованием разделения • Потенциальные проблемы Результат работы одного процесса не зависит от действий других. Возможно влияние одного процесса на время работы другого • • • Взаимоисключения Взаимоблокировки Голодание Результат работы одного процесса может зависеть от информации, полученной от других. • • • • Взаимоисключения Взаимоблокировки Голодание Синхронизация Процессы непосредственно осведомлены о наличии друг друга Сотрудничество с использованием связи • Возможно влияние одного процесса на время работы другого • Результат работы одного процесса зависит от информации, полученной от других процессов. Возможно влияние одного процесса на время работы другого • • • Взаимоблокировки (расходуемые ресурсы) Голодание При необходимости использовать один и тот же ресурс параллельные процессы вступают в конфликт (конкурируют) друг с другом. Каждый из процессов не подозревает о наличии остальных и не повергается никакому воздействию с их стороны. Отсюда следует, что каждый процесс не должен изменять состояние любого ресурса, с которым он работает. Примерами таких ресурсов могут быть устройства ввода-вывода, память, процессорное время, часы. Между конкурирующими процессами не происходит никакого обмена информацией. Однако выполнение одного процесса может повлиять на поведение конкурирующего процесса. Это может, например, выразиться в замедлении работы одного процесса, если ОС выделит ресурс другому процессу, поскольку первый процесс будет ждать завершения работы с этим ресурсом. В предельном случае блокированный процесс может никогда не получить доступ к нужному ресурсу и, следовательно, никогда не сможет завершиться. В случае конкурирующих процессов (потоков) возможно возникновение трех проблем. Первая из них – необходимость взаимных исключений (mutual exclusion). Предположим, что два или большее количество процессов требуют доступ к одному неразделяемому ресурсу, как например принтер (рис. 5.7). О таком ресурсе будем говорить как о критическом ресурсе, а о части программы, которая его использует, – как о критическом разделе (critical section) программы. Крайне важно, чтобы в критической ситуации в любой момент могла находиться только одна программа. Например, во время печати файла требуется, чтобы отдельный процесс имел полный контроль над принтером, иначе на бумаге можно получить чередование строк двух файлов. Рис. 5.7. Критическая секция Осуществление взаимных исключений создает две дополнительные проблемы. Одна из них – взаимоблокировки (deadlock) или тупики. Рассмотрим, например, два процесса – P1 и P2, и два ресурса – R1 и R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к общим ресурсам. Тогда возможно возникновение следующей ситуации: ОС выделяет ресурс R1 процессу Р2, а ресурс R2 – процессу Р1. В результате каждый процесс ожидает получения одного из двух ресурсов. При этом ни один из них не освобождает уже имеющийся ресурс, ожидая получения второго ресурса для выполнения функций, требующих наличие двух ресурсов. В результате процессы оказываются взаимно заблокированными. Очень удобно моделировать условия возникновения тупиков, используя направленные графы [17] (предложено Holt, 1972). Графы имеют 2 вида узлов: процессы-кружочки и ресурсы-квадратики. Ребро, направленное от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется. В нашем примере это будет изображено так, как показано на рис. 5.8 а). Ребро, направленное от процесса (кружка) к ресурсу (квадрату), означает, что процесс в данный момент заблокирован и находится в состоянии ожидания доступа к этому ресурсу. В нашем примере граф надо достроить, как показано на рис. 5.8 б) или в). Цикл в графе означает наличие взаимной блокировки процессов. Существует еще одна проблема у конкурирующих процессов – голодание. Предположим, что имеется 3 процесса ( Р1, Р2, Р3 ), каждому из которых периодически требуется доступ к ресурсам R. Представим ситуацию, в которой Р1 обладает ресурсом, а Р2 и Р3 приостановлены в ожидании освобождения ресурса R. После выхода Р1 из критического раздела доступ к ресурсу будет получен одним из процессов Р2 или Р3. Рис. 5.8. Тупиковая ситуация Пусть ОС предоставила доступ к ресурсу процессу Р3. Пока он работает с ресурсом, доступ к ресурсу вновь требуется процессу Р1. В результате по освобождении ресурса R процессом Р3 может оказаться, что ОС вновь предоставит доступ к ресурсу процессу Р1. Тем временем процессу Р3 вновь требуется доступ к ресурсу R. Таким образом, теоретически возможна ситуация, в которой процесс Р2 никогда не получит доступ к требуемому ему ресурсу, несмотря на то, что никакой взаимной блокировки в данном случае нет. Рассмотрим случай сотрудничества с использованием разделения. Этот случай охватывает процессы (потоки), взаимодействующие с другими процессами (потоками), без наличия явной информации о них. Например, несколько потоков могут обращаться к разделяемым переменным (глобальным) или совместно используемым файлам или базам данных. Поскольку данные хранятся в ресурсах (устройствах памяти), в этом случае также возможны проблемы взаимоблокировок, взаимоисключения и голодания. Единственное отличие в том, что доступ к данным может осуществляться в двух режимах – чтения и записи, и взаимоисключающими должны быть только операции записи. Однако в этом случае вносится новое требование синхронизации процессов для обеспечения согласованности данных. Пусть имеются два процесса, представленные последовательностью неделимых (атомарных) операций: P: a; b; c; и Q: d; e; f; где a, b, c, d, e, f – атомарные операции. При последовательном выполнении активностей мы получаем следующую последовательность атомарных действий: PQ: a b c d e f Что произойдет при исполнении этих процессов псевдопараллельно, в режиме разделения времени? Процессы могут расслоиться на неделимые операции с различным их чередованием, то есть может произойти то, что на английском языке принято называть словом interleaving. Возможные варианты чередования: а b c d e f a b d c e f a b d e c f a b d e f c a d b c e f ...... d e f a b c В данном случае атомарные операции активностей могут чередоваться всевозможными способами с сохранением своего порядка расположения внутри процессов. Так как псевдопараллельное выполнение двух процессов приводит к чередованию их неделимых операций, результат псевдопараллельного выполнения может отличаться от результата последовательного выполнения. Пусть есть два процесса P и Q, состоящие из двух атомарных операций: P: x=2; y=x-1; Q: x=3; y=x+1 Что мы получим в результате их псевдопараллельного выполнения, если переменные x и y являются общими для процессов? Легко видеть, что возможны четыре разных набора значений для пары (x, y): (3, 4), (2, 1), (2, 3) и (3, 2). Будем говорить, что набор процессов детерминирован, если всякий раз при псевдопараллельном исполнении для одного и того же набора входных данных он дает одинаковые выходные данные. В противном случае он недетерминирован. Выше приведен пример недетерминированного набора программ. Понятно, что детерминированный набор активностей можно безбоязненно выполнять в режиме разделения времени. Для недетерминированного набора такое исполнение нежелательно. Можно ли до получения результатов, заранее, определить, является ли набор активностей детерминированным или нет? Для этого существуют достаточные условия Бернстайна [17]. Изложим их применительно к программам с разделяемыми переменными. Введем наборы входных и выходных переменных программы. Для каждой атомарной операции наборы входных и выходных переменных – это наборы переменных, которые атомарная операция считывает и записывает. Набор входных переменных программы R(P) ( R от слова read ) суть объединение наборов входных переменных для всех ее неделимых действий. Аналогично, набор выходных переменных программы W(P) ( W от слова write ) суть объединение наборов выходных переменных для всех ее неделимых действий. Например, для программы P: x = u + v; y = x * w; получаем R(P) = {u, v, x, w}, W(P) = {x, y}. Заметим, что переменная x присутствует как в R(P), так и в W(P). Теперь сформулируем условия Бернстайна. Если для двух данных процессов P и Q: • • • пересечение W(P) и W(Q) пусто, пересечение W(P) с R(Q) пусто, пересечение R(P) и W(Q) пусто, тогда выполнение P и Q детерминировано. Если эти условия не соблюдены, возможно, что параллельное выполнение P и Q детерминировано, но возможно, что и нет. Случай двух процессов естественным образом обобщается на их большее количество. Условия Бернстайна информативны, но слишком жестки. По сути дела, они требуют практически невзаимодействующих процессов. Однако хотелось бы, чтобы детерминированный набор образовывал процессы, совместно использующие информацию и обменивающиеся ею. Для этого нам необходимо ограничить число возможных чередований атомарных операций, исключив некоторые чередования с помощью механизмов синхронизации выполнения программ и обеспечив тем самым упорядоченный доступ программ к некоторым данным. Про недетерминированный набор программ говорят, что он имеет race condition (состояние гонки, состояние состязания). В приведенном выше примере процессы состязаются за вычисление значений переменных x и y. Задачу упорядоченного доступа к разделяемым данным (устранение race condition), в том случае, если нам не важна его очередность, можно решить, если обеспечить каждому процессу эксклюзивное право доступа к этим данным. Каждый процесс, обращающийся к разделяемым ресурсам, исключает для всех других процессов возможность одновременного с ним общения с этими ресурсами, если это может привести к недетерминированному поведению набора процессов. Такой прием называется взаимоисключением (mutual exclusion). Если очередность доступа к разделяемым ресурсам важна для получения правильных результатов, то одними взаимоисключениями уже не обойтись. При сотрудничестве с использованием связи различные процессы принимают участие в общей работе, которая их объединяет. Связь обеспечивает возможность синхронизации, или координации, различных действий процессов. Обычно можно считать, что связь состоит из сообщений определенного вида. Примитивы для отправки и получения сообщений могут быть предоставлены языком программирования или ядром операционной системы. Поскольку в процессе передачи сообщений не происходит какого-либо совместного использования ресурсов, взаимоисключения не требуется, хотя проблемы взаимоблокировок и голодания остаются актуальными. В качестве примера взаимоблокировки можно привести ситуацию, при которой каждый из двух процессов заблокирован ожиданием сообщения от другого процесса. Голодание можно проиллюстрировать следующим образом. Пусть есть три процесса Р1, Р2, Р3, а те, в свою очередь, пытаются связаться с процессом Р1. Может возникнуть ситуация, когда Р1 и Р2 постоянно связываются друг с другом, а Р3 остается заблокированным, ожидая связи с процессом Р1.