Шпаргалка по ОС. 1. Понятие операционной системы, ее отношение к аппаратуре и программному обеспечению
 Скачать 123.67 Kb.
|
|
Unix: int pthread_kill(pthread_t tid, int signum);SIGSTOP – сигнал остановки. SIGCONT – возобновить работу. | ||
| 31. Ожидание завершения нити. В определенной степени эта функция аналогична функциям ожидания окончания процессов, но относится к уровню нитей. В конечном счете, она предназначена для той же цели – согласования совместной работы нитей на основе самого глобального по смыслу действия – полного завершения работы отдельной выполняемой программной единицы. В Unix, поддерживающей стандарт POSIX, для ожидания нити служит функция pthread_join, имеющая прототип int pthread_join(pthread_t tid, void** status). В Windows для ожидания завершения нити служит уже частично рассматривавшаяся универсальная функция ожидания WaitForSingleObject. Для ожидания завершения нити в качестве первого аргумента этой функции следует взять хэндл ожидаемой нити, а в качестве второго – значение предельного времени ожидания, в простейшем случае INFINITE. Каких-либо особенностей, отличающих ее от других форм ожидания, эта функция не имеет при использовании для ожидания нити. В Windows для ожидания завершения нити служит уже частично рассматривавшаяся универсальная функция ожидания WaitForSingleObject. Для ожидания завершения нити в качестве первого аргумента этой функции следует взять хэндл ожидаемой нити, а в качестве второго – значение предельного времени ожидания, в простейшем случае INFINITE. Каких-либо особенностей, отличающих ее от других форм ожидания, эта функция не имеет при использовании для ожидания нити. Unix: int pthread_join(pthread_t tid, void** status). Эта функция возвращает код возврата из нити, причем такой код формируется функцией pthread_exit(), завершающую нить ожидаемуя нить. Функция пригодна для ожидания только конкретной нити, идентификатор которой задается первым ее аргументом. Второй аргумент вызова функции (указатель на указатель) позволяет получить любой тип результата, предусмотренный программистом | 32. Абстрактные критические интервалы. Если несколько процессов или нитей используют общие данные, то результат совместного использования этих данных может быть совершенно непредсказуем. Примером таких общих данных является использование общей для процессов очереди, куда эти процессы включают запрос на некоторое действие. Введем некоторые термины, сложившиеся в теории параллельных процессов. Зависимость результатов процесса от непредусмотренного в программе взаимодействия с другими процессами называют состязанием процессов. Теоретическим средством устранить состязание между процессами является решение запретить прерывания, на основе которых организована параллельность процессов. Но такое решение запрещает (хотя бы на время) параллельное выполнение процессов, к тому же годится только для однопроцессорных систем. Более общим понятием, чем общие данные является, понятие ресурса, которое кроме общих данных может быть и общедоступной аппаратурой. Участок программы, в котором нить производит обращение к общему (разделяемому с другими нитями) ресурсу, называется критическим интервалом нити.Для устранения состязаний процессов (или нитей) используют монополизацию ресурса. Монополизация ресурса – это временное предоставление его в исключительное использование одной нити. Критический интервал нити поэтому ограничивают с начала и конца специальными управляющими конструкциями операционной системы, в абстрактном изложении называемыми прологом и эпилогом критического интервала. Назначение этих конструкций – обеспечить нахождение в критическом интервале только одной нити. | |
| 33. Абстрактные двоичные семафоры. Общий подход к монополизации ресурсов с помощью специальных системных операций предложил голландский математик Е. Дейкстра. Этот подход состоит в построении и использовании семафоров. Семафор – это защищенная от прямого доступа переменная, значения которой можно опрашивать и изменять только с помощью специальных операций P и V; кроме того, в самом начале к семафору применяется операция инициализации.Простейшей формой семафоров являются двоичные семафоры, которые могут принимать только значения 0 и 1. Операции P и V над двоичными семафорами определяются следующим образом. Пусть S - двоичный семафор.Для удобства и сокращения формулировок будем временно называть абстрактный процесс – задачей. Операция P(S) выполняет действия: если S равно 1, то занести в S значение 0, иначе БЛОКИРОВАТЬ нить по семафору S, и если очередь готовых задач не пуста, то УСТАНОВИТЬ на процессор задачу из этой очереди. Операция V(S) выполняет действия: если список задач, заблокированных по семафору S, не пуст, то ДЕБЛОКИРОВАТЬ задачу из этой очереди (т.е. перевести ее в очередь готовых задач), иначе занести в S значение 1. Для двоичных семафоров значение семафора 1 обозначает, что ресурс, защищаемый семафором, свободен, а значение семафора 0 – что ресурс занят. | 34. Абстрактные семафоры с внутренним счетчиком. Более сложной формой семафора является считающий, который по определению принимает любые неотрицательные значения. Операции P и V для считающего семафора S определяются следующими описаниями действий: P(S) : если S > 0, то S S - 1, иначе WAIT(S); V(S) : если список задач, заблокированных по семафору S, не пуст, то ДЕБЛОКИРОВАТЬ задачу из этой очереди (т.е. перевести ее в очередь готовых задач), иначе S S +1.Эта форма семафоров обусловила название операций: P – proberen (проверить), V – verholen (увеличить) на голландском языке. Считающий семафор показывает число единиц свободного ресурса. Считающий семафор может быть обобщен путем распространения его значений на отрицательные числа следующим определением операций P и V: P(S) : S S - 1; если S < 0, то WAIT(S); V(S) : S S +1; если S 0, то ДЕБЛОКИРОВАТЬ задачу из этой очереди (т.е. перевести ее в очередь готовых задач).Обобщенный считающий семафор своим значением равен разности между числом единиц наличного ресурса и числом запросов на них. При S 0 значение такого семафора показывает число свободных единиц ресурса, при S < 0 – число задач, заблокированных по семафору S. | |
| 35. Семафоры взаимоисключения в Windows. (1) Семафоры mutex отличаются от двоичных семафоров тем, что операцию V над семафором может осуществить только тот процесс, который выполнил предыдущую операцию P над ним без блокировки от такого действия. Для описания и использования этого ограничения вводится понятие владения семафором. Операции, аналогичные абстрактным P и V, над семафорами взаимоисключения называются по-разному. Так, в операционной системе Windows запрос на владение таким семафором (аналогичный операции P) использует универсальную функцию ожидания любого объекта с именем WaitForSingleObject. Для аналога операции V в рассматриваемых ОС разработчиками приняты следующие названия: в Windows – ReleaseMutex.для его создания необходимо явное приказание операционной системе. Это приказание имеет имя CreateMutex в ОС Windows. В результате этих вызовов исполняемая программа (точнее, конкретный процесс, работающий по этой программе) получают хэндл семафора взаимоисключения в качестве результата вызова. Имея хэндл, нить может использовать функции запроса владения и в дальнейшем – освобождения семафора владельцем mutex. | 35. Семафоры взаимоисключения в Windows. (2) Для создания сем-ра: HANDLE CreateMutex(SECURITY_ATTRIBUTES *MtxAttrs (адрес атрибутов защиты), BOOL bInitialOwner (наследование), STR *Name (имя сем-ра)); Ф-ия создает семафор и возвращает его хэндл. Для доступа к сем-ру,созданному др.процессом: HANDLE OpenMutex(DWORD DesiredAccess, BOOL bInheritHandle, STR *Name); DesiredAccess: MUTEX_ALL_ACCESS(заданы все возможн флаги доступа) или SYNCHRONIZE (полученный хэндл можно исп-ть в любых ф-иях ожидания события). Параметр bInheritHandle показывает,будет ли наследоваться хэндл сем-ра потомками данного процесса.Чтоб наследов-е происходило, параметр задавать TRUE. Для запроса владения семафора Windows использует общую функцию ожидания WaitForSingleObject, а для его закрытия - общую функцию CloseHandle. | |
| 36. Семафоры взаимоисключения в POSIX. Запрос на владение сем-ром (операция P) в Unix: int pthread_mutex_lock(ptread_mutex_t* hmtx) Для аналога операции V (отказ от владения сем-ром): int pthread_mutex_unlock(ptread_mutex_t* hmtx) Для создания сем-ра: int pthread_mutex_init (ptread_mutex_t *hmtx, ptread_mutexattr_*pattr) Т.к. в Unix нет ф-ий открытия доступа к mutex-семафору,созданному др процессом,то нет и ф-ии закрытия такого mutex-семафора. Для удаления из ОС mutex-сем-ра - после прекращения надобности в нем: int pthread_mutex_destroy( ptread_mutex_t* hmtx). Ф-ия int pthread_mutex_trylock(ptread_mutex_t* hmtx) - не блокирует, а возвращает отличное от 0 значение, если семафор занят. Все ф-ии описаны в заголовочном файле pthread.h. Во всех этих ф-иях 1 аргумент -указатель на хэндл сем-ра. В ф-ии инициализации 2 аргумент определяет атрибуты для нового mutex-сем-ра. Атрибуты могут задаваться с пом констант: USINC_PROCESS (сем-р может исп-ться др процессом), USINC_THREAD(сем-р может исп-ться нитями только в одном процессе). В Linux семафоры взаимоисключения предоставляют дополнительные возможности. Они связаны с попытками нити захватить семафор, уже принадлежащий ей. Эти возможности называют типами mutex семафоров. Имеются три таких типа: быстрый семафор, рекурсивный семафор и контролирующий семафор. Попытка захвата быстрого семафора приводит к блокировке нити, но такая же попытка для рекурсивного семафора не приводит к блокировке. При этом для освобождения mutex семафора оказывается нужным выполнить вызов функции pthread_mutex_unlock() столько раз, сколько перед этим выполнялось вызовов функции pthread_mutex_lock(). | 37. Семафоры событий в Windows. Другой современной формой семафоров является семафор событий. Он предназначен для организации ожидания некоторого события, и когда такое событие произойдет, выполнение сможет продолжить не одна, а все нити, дожидающиеся этого события. Wndows: Cоздает семафор событий: CreateEvent(адрес атрибута защиты, BOOL ManualReset //переустановка состояния в nonsignaled, BOOL InitialState //состояние, если true то был сигнал о событии, имя семафора); Запуск сигнала события: SetEvent(HANDLE hev); ResetEvent – переустановить сост-е в nonsignaled («выкл» сигнал о событии). В автономном режиме WaitForSingleObject(HANDLE hevsem, timeout); -ч/з некот-е время timeout Event-сем-р, созданный ф-ией CreateEvent,автоматически сбрасывается (освобождается). После вып-ния ф-ии WaitForSingleObject (по сигналу Event) пробуждается только одна из ожидающих нитей. 38. Условные переменные в POSIX.В операционной системе Unix нет даже термина семафор событий, но в ней имеются универсальные семафоры, даже более мощные, чем считающие абстрактные семафоры Дейкстры, и еще одна интересная вариация идеи семафора, названная условными переменными. В основном условные переменные соответствуют семафорам событий рассмотренных выше операционных систем и особенно семафорам событий с автоматическим режимом работы. Условные переменные используются для того, чтобы заблокировать нити до выполнения определенных условий, а момент выполнения такого условия можно рассматривать как событие. Для создания условной переменной используется системная функция с именем pthread_cond_init. Она имеет прототип int pthread_cond_init(pthread_cond_t * pcond адрес условной переменной, значение которой возвращает данная функция, pthread_condattr_t * pcond_attr=0 дает указатель на структуру атрибутов, которые определяют свойства этой условной переменной) Для задания срабатывания условной переменной, т.е. появления события выполнения условия этой переменной, существует функция pthread_cond_signal с прототипом int pthread_cond_signal(pthread_cond_t * cond). В результате выполнения этой функции всем нитям, ожидающим срабатывания условной переменной, посылается сигнал об этом событии. Ожидание события срабатывания условной переменной задается функцией pthread_cond_wait с прототипом int pthread_cond_wait(pthread_cond_t * cond созданной ранее условной переменной, pthread_mutex_t * mutex созданного ранее семафора взаимоисключения).После использования, условная переменная должна быть уничтожена вызовом функции с прототипом int pthread_cond_destroy(pthread_cond_t * cond).Особенностью условных переменных в Unix является то, что сигнал, посылаемый такой переменной, действует только в том случае, если его в этот момент ожидает какая-то нить. Если же этот сигнал был послан в отсутствие ожидающей нити, а позже некоторая нить запросила ожидание этого же сигнала, то она будет заблокирована до момента следующей выдачи сигнала. Тем самым, условная переменная Unix все же заметно отличается от семафоров событий в Windows. | |
| 39. Использование барьеров POSIX для синхронизации потоков. Барьер – это механизм синхронизации, который позволяет приостановить выполнение потоков у некоторой точки программы до тех пор, пока все потоки не дойдут до этого места, и только затем продолжить выполнение дальше. В отличие от join-а, где мы ожидаем завершения выполнения потока, при использовании барьеров мы ожидаем встречи (рандеву, rendezvous) этих потоков в определённой точке. Мы определяем количество потоков, которые должны прибыть к этой точке, блокируем их там, а когда набирается нужное число потоков, разблокируем их все, позволяя работать дальше.Для создания барьера необходимо создать переменную типа pthread_barrier_t. Инициализация барьера происходит с помощью функции int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned count); Здесь первый аргумент – это указатель на нашу переменную – барьер. Вторая переменная – атрибуты барьера (если их нет, то пишем NULL), последний аргумент – число потоков, которые должны вызвать pthread_barrier_wait, чтобы преодолеть (разблокировать) барьер. Функция может возвращать ошибки EBUSY – система обнаружила, что данный барьер уже инициализирован и используется. EINVAL – неверные атрибуты барьера Кроме того, она обязательно возвратит ошибку, если EAGAIN – не хватает ресурсов для создания барьера EINVAL – если число потоков count равно нулю ENOMEM – не хватает памяти для создания барьера pthread_barrier_init выделяет нужные для работы барьера ресурсы, поэтому необходимо очищать их после использования с помощью функции int pthread_barrier_destroy(pthread_barrier_t *barrier); В случае удачного завершения, как обычно, функция возвращает 0. Возможны следующие ошибки EBUSY – система обнаружила, что барьер в настоящее время используется (например, используется функцией pthread_barrier_wait) EINVAL – переданный аргумент ссылается на переменную, которая не является барьером Собственно синхронизация осуществляется с помощью функции int pthread_barrier_wait(pthread_barrier_t *barrier); Поток, которые вызывает функцию pthread_barrier_wait блокируется в месте вызова, до тех пор, пока количество потоков, вызвавших pthread_barrier_wait не станет равным значению count, которое было задано при инициализации этого барьера. В случае вызова функция возвращает значение PTHREAD_BARRIER_SERIAL_THREAD для произвольного синхронизированного потока, и 0 для всех остальных. Функция возвратит EINVAL – если переданный аргумент не ссылается на инициализированный барьер.Если функция pthread_barrier_wait возвращает значение PTHREAD_BARRIER_SERIAL_THREAD, это значит, что барьер может быть уничтожен. То есть, нельзя просто так уничтожать барьер в каком-то из потоков, так как порядок завершения потоков не детерминирован | 40. Средства множественных ожиданий. Множественные ожидания событий или освобождения общих ресурсов возникают, когда по существу решаемой задачи может оказаться необходимым ожидать не одного, а более чем одного события или ресурса. В Windows для множественного ожидания предназначена универсальная функция WaitForMultipleObjects с прототипом DWORD WaitForMultipleObjects(DWORD cObjects, CONST HANDLE *phObjects, BOOL fWaitAll, DWORD Timeout); где параметр cObjects для данного применения задает число семафоров в наборе, параметр phObjects – адрес массива хэндлов отдельных семафоров в наборе, параметр Timeout – время ожидания в миллисекундах или записывается символической константой INFINITE– для бесконечного ожидания. С помощью параметра fWaitAll определяется вариант ожидания – ожидать срабатывания всех семафоров в наборе (значение параметра для этого должно быть TRUE) или ожидание завершается при срабатывании хотя бы одного семафора в наборе (при значении FALSE этого параметра). Возвращаемые значения этой функции, равные сумме константы WAIT_OBJECT_0 и числового значения k, информируют программу, что ожидание было прекращено по причине срабатывания k-го семафора в наборе. В операционной системе Unix не предусмотрено стандартных средств для множественного ожидания срабатывания набора mutex-семафоров или семафоров ожидания (условных переменных). Вместо этого присутствуют мощные программные средства, позволяющие строить произвольные наборы считающих семафоров. | |
| 41. Программные семафоры с внутренним счетчиком в Windows. (счётчик – подсчёт числа свободных единиц ресурса; счётчик >=0, если <0 – заблокир.) Создание: HANDLE CreateSemaphore( SECURITY_ATTRIBUTES *pSemaphoreAttributes, LONG lInitialCount, LONG lMaximumCount, LPCTSTR lpName).HANDLE CreateSemaphore(адрес атрибутов защиты или NULL, LONG начальное значение счётчика, LONG maxValue //допустимое знач-е счётчика, имя семафора или NULL); значение семафора (>=0)); Ожидание таких семафоров: WaitForSingleObject(HANDLE hsem, timeout); если значение семафора =0, то ожидание, иначе уменьшение на 1. Функция освобождения считающего семафора:BOOL ReleaseSemaphore(HANDLE hSemaphore, LONG cReleaseCount, LONG *plPreviousCount).– увеличивает значение внутреннего счетчика семафора на заданное при вызове функции значение аргумента cReleaseCount, причем параметр plPreviousCount должен содержать адрес переменной, в которой возвращается предыдущее значение этого счетчика или значение NULL, если такое предыдущее значение не требуется в программе. cReleaseCount обязательно должно быть больше нуля и не больше lMaximumCount. Когда значение внутреннего счетчика семафора больше нуля, он считается открытым, т.е. выполнение функции ожидания для такого состояния счетчика не блокирует нить. Все нити процесса, создавшего считающий семафор, могут им пользоваться. Если считающий семафор создан другим процессом, то для доступа к нему этот семафор необходимо открыть с помощью функции OpenSemaphore, которая имеет прототип:HANDLE OpenSemaphore(DWORD access, DWORD inherit, имя семафора); 43. Массивы семафоров в Unix (семафоры System V). В операционной системе Unix ее классические семафоры представляют собой не отдельные объекты, а целые группы (массивы) счетчиков семафоров, причем эти внутренние счетчики семафоров могут принимать любые неотрицательные значения. Отдельный внутренний семафор в такой группе описывается структурой sem, заданной как typedef struct sem { ushort semval; //Значение семафора pid_t sempid; // ID процесса, выполнившего последнюю операцию ushort semncnt; // Число процессов,ожидающих увеличения счетчика ushort semzcnt; // Число процессов, ожидающих обнуления семафора }; Для получения доступа к семафору и для его создания, если он не существовал, предназначена системная функция semget(), имеющая прототип int semget (key_t key имя семафора, int nsems число счетчиков (внутренних одиночных семафоров), которые требуется создать, int semflag права доступа к создаваемому семафору и флаги его создания). Флаги создания семафоров задаются символическими константами IPC_CREAT и IPC_EXCL. Первая из них задает режим создания семафора для функции semget(), а при отсутствии этой константы выполняется открытие семафора с указанным параметром key идентификатором. Флаг IPC_EXCL при создании семафора требует, чтобы при наличии одноименного семафора (уже существующего семафора с тем же значением идентификатора key) функция semget() возвращает ошибку. Для основных операций над семафорами используется функция с именем semop. int semop (int hsem, struct sembuf* opsem, size_t nops), где hsem – хэндл (идентификатор) семафора, созданного или открытого ранее функцией semget(), opsem – адрес массива описания структур операции над отдельным семафором в группе, а параметр nops задает число внутренних операций, выполняемых в вызове функции, т.е. число используемых элементов в массиве, заданном opsem. | 42. Программные семафоры с внутренним счетчиком в POSIX. Для использования семафоров в Unix нужно подключить #include Функция sem_post увеличивает на 1 текущее значение общего семафора, на идентификатор которого указывает аргумент sem. Если прежнее значение семафора было 0 и есть нити, заблокированные в своей операции sem_wait, одна из них разблокируется, но какая именно - не определено.Функция sem_wait уменьшает на 1 текущее значение общего семафора, на идентификатор которого указывает аргумент sem. Если прежнее значение семафора было 0, нить, выполняющая функцию sem_wait блокируется до изменения значения семафора. Для использования семафоров в Unix нужно подключить #include int sem_init(sem_t *sem, int pshared, unsigned int value) – возвращает семафор sem_t *sem – адрес семафора ,int pshared – задает, будет ли данный семафор применяться для взаимодействия между процессами, а не только между нитями внутри одного процесса. Для использования семафора в пределах только одного процесса, этот параметр должен быть равен 0.int value – начальное значение семафора, int sem_wait(sem_t *sem) – блокирует нить, если внутреннее значение семафора уже равно нулю; или уменьшению на 1 внутреннего значения семафора – в ином случае.,int sem_post(sem_t *sem) – деблокирует нить, ранее остановленную по доступу к семафору, или увеличивает внутреннее значения семафора, если нет нитей, блокированных по доступу к этому семафору.Дополнительно предлагается еще две программных функции с прототипами sem_trywait(sem_t *sem) через возвращаемое значение отображается ситуация: 1 – семафор занят (возврат EAGAIN), 0- свободен. Sem_getvalue(sem_t *hsem, int shader, int value) – возвращает текущее значение общего семафора, на идентификатор которого указывает аргумент sem по адресу, задаваемому value. 44. Проблема тупиков при взаимодействии программных единиц. Семафоры широко используются как средство синхронизации потоков и процессов. В Unix-системах реализованы три типа семафоров – семафоры System V, семафоры POSIX и семафоры в разделяемой памяти. Состояние семафора определяется значением некоторой внутренней переменной и переданным ему параметром. В зависимости от этих значений семафор либо приостанавливает выполнение обратившегося к нему потока (до тех пор, пока другой поток не переведет семафор в другое состояние), либо изменяет значение внутренней переменной, разрешив потоку дальнейшее выполнение. Возникновение тупиков является потенциальной проблемой любой ОС. Они возникают, когда имеется группа процессов, каждый из которых пытается иметь эксклюзивный доступ к некоторым ресурсам или претендует на ресурсы, принадлежащие другому процессу. В итоге все они оказываются в состоянии бесконечного ожидания, т.е. в состоянии тупика. Системная тупиковая ситуация или зависание системы является следствием того, что один или более процессов находятся в состоянии тупика. Условия возникновения тупиков: -процессы требуют предоставления им права монопольного управления ресурсами, которые им выделяются (условие взаимоисключения); -процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (условие ожидания ресурсов); -ресурсы нельзя отобрать у процессов, удерживающих их, пока эти ресурсы не будут использованы для завершения работы (условие неперераспределяемости);-существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся следующему процессу цепи (условие кругового ожидания). Процесс А Процесс В | |