OperationSystems

Лабораторные работы № 1, 2 Упрощенная реализация менеджера процессов

1.Методические указания

1.1.Основные сведения

1.1.1.Понятие операционной системы

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

1.1.2.Процессы

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

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

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

–Инициализация системы.

–Выполнение изданного работающим процессом системного запроса на создание процесса.

–Запрос пользователя на создание процесса

–Инициирование пакетного задания.

В UNIX для вывода списка запущенных процессов используется программа ps. В Windows 95/98/ME достаточно нажать CTRL+ALT+DEL, в более поздних версиях можно воспользоваться диспетчером задач, вызываемым этой же комбинацией трех клавиш.

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

–Обычный выход (преднамеренно).

–Выход по ошибке (преднамеренно).

–Выход по неисправимой ошибке (непреднамеренно).

–Уничтожение другим процессом (непреднамеренно).

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

cat chapter1 chapter2 chapter3 | grep tree

первый процесс cat объединяет и выводит три файла. Но отправляет она их содержимое не на экран, а на стандартный ввод программы grep. Второй процесс – grep, отбирает все строки, содержащие слово “tree”. В зависимости от относительных скоростей процессов, может получиться, что grep уже готов к запуску, но входных данных для этого процесса еще нет. В этом случае процесс блокируется до поступления входных данных.

Три возможные состояния процесса:

–Работающий (в этот конкретный момент использующий процессор).

–Готовый к работе (процесс временно приостановлен, чтобы позволить выполняться другому процессу).

–Заблокированный (процесс не может быть запущен прежде, чем произойдет некое внешнее событие).

Действие

1		2
		3
Блокировка	4	Готовность

Рис.1

На рис.1 представлена диаграмма состояний:

1)Процесс блокируется, ожидая входных данных.

2)Планировщик выбирает другой процесс.

3)Планировщик выбирает этот процесс.

4)Доступны входные данные.

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

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

1.1.3.Потоки

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

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

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

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

–программный счетчик;

–стек;

–регистры;

–потоки-потомки;

–состояние.

Потоки разделяют:

–адресное пространство;

–глобальные переменные;

–открытые файлы;

–таймеры;

–семафоры;

–статистическую информацию.

Как и любой процесс, поток может находиться водном из нескольких состояний: рабочем, заблокированном, готовности или завершенном.

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

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

И наконец, концепция потоков полезна в системах с несколькими процессорами, где возможен настоящий параллелизм.

1.1.4.Средства синхронизации и взаимодействия процессов

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

1.1.4.1.Тупики

Тупики (взаимные блокировки, дедлоки (deadlocks), клинчи (clinch)) имеют место, когда процесс ожидает ресурс, который в данный момент принадлежит другому процессу.

Пример: Процесс1 захватывает ресурс А и, для того чтобы продолжать работу, ждет возможности захватить ресурс Б. В тоже время Процесс2 захватывает ресурс Б и ждет возможности захватить ресурс А. Развитие этого сценария заблокирует оба процесса – ни один из них не будет исполняться.

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

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

Проблема тупиков включает в себя следующие задачи:

–предотвращение тупиков;

–распознавание тупиков;

–восстановление системы после тупиков.

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

1.Семафоры

В1965 году Дейкстра (E.W. Dijkstra) предложил использовать целую переменную для подсчета сигналов запуска, сохраненных на будущее. Им был предложен новый тип переменных, так называемые семафоры, значение которых может быть нулем (в случае отсутствия сохраненных сигналов активизации) или некоторым положительным числом, соответствующим количеству отложенных активизирующих сигналов.

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

2.Мьютексы

Иногда используется упрощенная версия семафора, называемая мьютексом (mutex, сокращение от mutual exclusion – взаимное исключение). Мьютекс не способен считать, он может лишь управлять взаимным исключением доступа к совместно используемым ресурсам или кодам. Реализация мьютекса проста и эффективна, что делает использование мьютексов особенно полезным в случае потоков, действующих только в пространстве пользователя.

Мьютекс – переменная, которая может находиться водном из двух состояний: блокированном или неблокированном. Поэтому для описания мьютекса требуется всего один бит, хотя чаще используется целая переменная, у которой 0 означает неблокированное состояние, а все остальные значения соответствуют блокированному состоянию. Значение мьютекса устанавливается двумя процедурами. Если поток (или процесс) собирается войти в критическую область, он вызывает процедуру mutex_lock. Если мьютекс не заблокирован (то есть вход в критическую область разрешен), запрос выполняется и вызывающий поток может попасть в критическую область.

3.Критические секции

Критические секции (critical section) подобны мьютексам, однако между ними существуют два главных отличия:

–мьютексы могут быть совместно использованы в различных процессах;

–если критическая секция принадлежит другому процессу, ожидающий процесс блокируется вплоть до освобождения критической секции; в отличие от этого, мьютекс разрешает продолжение по истечении тайм-аута.

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

4.Гонки

Гонки (race conditions) – это ситуации, в которых два или более процесса обрабатывают разделяемые данные, и конечный результат зависит от соотношения скоростей процессов. То есть два или более процесса пытаются получить доступ к общему ресурсу и изменить его состояние.

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

2. Реализация потоков Windows 2.1.Создание и завершение потоков

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

HANDLE CreateThread
(
LPSECURITY_ATTRIBUTES lpThreadAttributes,		// дескриптор защиты
SIZE_T dwStackSize,	// начальный размер стека
LPTHREAD_START_ROUTINE lpStartAddress,		// функция потока
LPVOID lpParameter,	// параметр потока
DWORD dwCreationFlags,	// опции создания
LPDWORD lpThreadId	// идентификатор потока
);

Функция, заканчивающая работу потока

VOID ExitThread
(
DWORD dwExitCode	// код выхода для этого потока
);

ExitThread - предпочтительный метод завершения работы потока. Когда эта функция вызывается (или явно или при помощи возврата из процедуры потока), стек текущего

потока освобождается, а поток завершает работу. Функция точки входа всех связанных динамически подключаемых библиотек (DLL) вызывается со значением, указывающим, что поток отключается от DLL.

Функция, проверяющая текущее состояние указанного объекта. Если данный объект находится в неотмеченном со стоянии, выполнение потока приостанавливается.

DWORD WaitForSingleObject
(
HANDLE hHandle,	//дескриптор объекта
DWORD dwMilliseconds	//интервал времени
);

Функция WaitForSingleObject возвращает свое значение в двух случаях: когда указанный объект устанавливается в отмеченное состояние, и когда истекает время ожидания. В процессе ожидания поток практически не использует процессорное время. Перед завершением своей работы функция изменяет состояние некоторых объектов синхронизации. Изменения происходят только в том случае, если изменение состояния объекта привело к выходу из функции. Например, счетчик семафора уменьшается на единицу.

Функция WaitForSingleObject может использоваться со следующими объектами:

–извещениями об изменениях;

–вводом с системной консоли;

–объектами событий;

–заданиями;

–мютексами;

–процессами;

–семафорами;

–потоками;

–таймерами ожидания.

2.2.Средства синхронизации 2.2.1.Мьютекс

Функция для инициализации мьютекса.

HANDLE CreateMutex

(

LPSECURITY_ATTRIBUTES lpMutexAttributes, // атрибут безопасности

BOOL bInitialOwner,	// флаг начального владельца
LPCTSTR lpName	// имя объекта
);

Результатом будет дескриптор объекта mutex, если такое имя есть, то дескпритор с у щ е с т ву ю щ е г о. Ф у н к ц и я G e t L a s t E r r o r ( ) п р и в ы з о в е буд е т в ы д а в а т ь

ERROR_ALREADY_EXISTS.

Функция, открывающая мьютекс.

HANDLE OpenMutex

(

DWORD	fdwAccess,	// требуемый доступ
BOOL	fInherit,	// флаг наследования

LPCTSTR lpszMutexName

// адрес имени объекта Mutex

);

С помощью функции OpenMutex несколько задач могут открыть один и тот же объект Mutex и затем выполнять одновременное ожидание для этого объекта.

Функция, освобождающая мьютекс.

BOOL ReleaseMutex

(

HANDLE hMutex // дескриптор mutex

);

Данная функция при успешном выполнении вернет ненулевое значение.

2.2.2.Семафор

Функция для создания семафора.

HANDLE CreateSemaphore

(

LPSECURITY__ATTRIBUTES lpSemaphoreAttributes, //атрибут безопасности

LONG lInitialCount,	//начальное значение счетчика
LONG lMaximumCount,	/ /м а к с и м а л ь н о е з н а ч е н и е
счетчика
LPCTSTR lpName	/ /а д р е с и м е н и о б ъ е к т а
Semaphore
);

После того как семафор успешно создан, поток может обратиться к ресурсу, защищенному семафором, с помощью одной из wait-функций. При этом wait-функции передается дескриптор семафора.

Функция, увеличивающая значение счетчика.

BOOL ReleaseSemaphore
(
HANDLE hSemaphore,	//дескриптор семафора
LONG lReleaseCount,	//увеличение счетчика
LPLONG lpPreviousCount	/ /п р е д ы д у щ е е з н а ч е н и е
счетчика
);

3. Реализация потоков POSIX 3.1.Интерфейс POSIX

POSIX (Portable Operating Interface for Computer Environments – независимый от платформы системный интерфейс для компьютерного окружения) – это стандарт IEEE (Institute of Electrical and Electronics Engineers – институт инженеров по электротехнике и радиоэлектронике), описывающий системные интерфейсы для открытых операционных систем.

Этот стандарт подробно описывает систему виртуальной памяти, многозадачность и технологию переноса операционных систем. Таким образом, на самом деле POSIX представляет собой множество стандартов POSIX.1 – POSIX.12.

3.2.Компиляция программ POSIX API

Стандартным средством компиляции программ для многих UNIX-систем является компилятор GNU C(C++). Интегрированные среды разработки обычно являются программными надстройками над GNU C. В Linux такими надстройками являются среды:

•K-Develop (среда связанная с менеджером окон KDE, по интерфейсу близка к

Visual Studio);

•XWPE (текстовая IDE, по возможностям близка к Turbo-C);

•C-Forge (графическая IDE в X-window);

•ANJTA и др. IDE gnu C для UNIX.

Для выполнения лабораторных работ можно использовать компилятор GNU C в независимости от наличия IDE. В ОС Linux данный компилятор запускается из командной строки командой:

gcc <имя исходного файла .с> -o <имя исполняемого файла>

ключи:

•L – путь к дополнительным библиотекам (/usr/lib для библиотеки нитей в linux);

•l (L малое) – имя библиотеки (pthread для библиотеки нитей в linux);

•I – путь к включаемым файлам (/usr/inc для библиотеки нитей в linux).

Пример:

gcc /home/sergey/lab2.c -o /home/sergey/laba2.exe -I /usr/inc/ -L /usr/lib/ -lpthread

Следует учесть, что библиотеки в ОС Linux имеют префикс lib и расширения .so, .a . При использовании ключа l префикс lib заменяется на сам ключ l, а расширение опускается. В нашем примере библиотека нитей должна была называться libpthread.so и находиться в каталоге /usr/lib/. Кроме того, следует заметить, что в UNIX-системах не принято присваивать исполняемым файлам имена с расширениями (как в DOS или Windows), за исключением файлов с библиотеками.

3.3.Создание и завершение потоков

Функция для создания потока с атрибутами, указанными в attr, выполняющего функцию start_routine с аргументом arg.

int pthread_create (pthread_t *restrict thread,

const pthread_attr_t *restrict attr,

void *(*start_routine)(void*),void *restrict arg);

Аргументы:

•thread – сюда будет помещен идентификатор созданного потока;

•attr – атрибуты потока (если NULL, то используются стандартные);

•start_routine – функция, которую будет выполнять поток;

•arg – аргументы для фукнции (обычно – структура с заданием).

Функция, приостанавливающая текущий поток до завершения потока, указанного в параметре thread.

int pthread_join (pthread_t thread, void **value_ptr);

Аргументы:

•thread – поток, которого дожидается текущий поток;

•value_ptr – возвращаемое значение, или NULL, если оно не интересует.

3.4.Средства синхронизации 3.4.1.Мьютекс

Функция для инициализации мьютекса.