Алгоритм 2


Скачать 449.39 Kb.
НазваниеАлгоритм 2
страница3/5
Дата публикации06.05.2013
Размер449.39 Kb.
ТипДокументы
userdocs.ru > Информатика > Документы
1   2   3   4   5

Решение с приоритетным записи (глобальные данные)

^ Инициализация глобальных данных при приоритете записи

вспомогательные данные: // глобальные

nr = 0 // количество читающих

snr = 1 // для защиты nr

sw = 1 // для записи

sr = 1 // блокировка одного читателя при запросе на запись

nw = 0 // количество пишущих

snw = 1 // для защиты nw

srr = 1 // блокировка остальных читателей при запросе на запись

алгоритм попытки захвата чтения

начало

ждать srr

ждать sr

ждать snr

nr <- nr + 1;

если nr = 1, то

Ждать(sw);

отпустить

отпустить

отпустить

алгоритм освобождения чтения

начало

ждать snr

nr <- nr - 1;

если nr = 0, то

Отпустить(sw);

отпустить


Решение с приоритетной записью (запись)

алгоритм попытки захвата записи

начало

ждать snw

nw <- nw + 1;

если nw = 1, то

Ждать(sr );

отпустить

Ждать(sw);

алгоритм освобождения записи

начало

Отпустить(sw);

ждать snw

nw <- nw - 1;

если nw = 0, то

Отпустить(sr );

отпустить

Возможные сценарии исполнения алгоритма

Сценарии

Имеются только читатели

1 Устанавливается sw.

2 Нет очередей.

Имеются только писатели

1 Устанавливаются sw и sr .

2 Есть очередь писателей на sw.

Есть читатели и писатели, первым выполняется чтение

1 Читателем устанавливается sw.

2 Писателем устанавливается sr .

3 Все писатели становятся в очередь на sw.

4 Один читатель становится в очередь на sr .

5 Остальные читатели становятся в очередь на srr .

Есть читатели и писатели, первым выполняется запись

1 Писателем устанавливается sw.

2 Писателем устанавливается sr .

3 Все писатели становятся в очередь на sw.

4 Один читатель становится в очередь на sr .

5 Остальные читатели становятся в очередь на srr .
Использование класса boost::shared_mutex

Зачастую простой мьютекс, защищающий память, неоптимален. Например, в онлайн-игре список игровых комнат изменяется нечасто — когда кто-то из игроков решает открыть новую комнату, например, раз в несколько секунд. Считывается же он за одну секунду десятки раз, и выстраивать клиентов в очередь для этого не имеет смысла.

^ Подобные механизмы (так называемая блокировка чтения-записи) существуют во многих языках программирования и библиотеках. Например.

Embarcadero Delphi: IMultiReadExclusiveWrite.

POSIX: pthread_rwlock_t.

Java: ReadWriteLock, ReentrantReadWriteLock.

.NET Framework: System.Threading.ReaderWriterLockSlim.

Boost: boost::shared_mutex.

Пример (читатель)

boost::shared_mutex g_Mutex;

void reader_proc()

{ // . . .

g_Mutex.lock_shared();

// Чтение

g_Mutex.unlock_shared();

// . . .

}

Пример (писатель)

void writer_proc()

{ // . . .

g_Mutex.lock();

// Запись

g_Mutex.unlock();

// . . .

}

Межпроцессное взаимодействие

Объекты синхронизации

Используются для работы с разл. процессами.

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

- События (Windows API)

- Условные переменные (POSIX) (не явл. объектом ядра, поэтому нельзя использовать для разделения между процессами)

- Мьютексы

- Семафоры
События Windows API

^ HANDLE WINAPI CreateEvent (

__in_opt LPSECURITY_ATTRIBUTES lpEventAttributes,

__in BOOL bManualReset,

__in BOOL bInitialState,

__in_opt LPCTSTR lpctszName //не обязательно указатель на строку, опр-ет имя события );

^ HANDLE WINAPI OpenEvent (

__in DWORD dwDesiredAccess,

__in BOOL bInheritHandle,

__in LPCTSTR lpctszName // -- - -- );
Мьютексы Windows API

HANDLE WINAPI CreateMutex (

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

__in BOOL bInitialOwner, //Флаг начального владельца – свободен или занят

__in_opt LPCTSTR lpctszName //Имя );

^ HANDLE WINAPI OpenMutex (

__in DWORD dwDesiredAccess, //Константа, опр-ет, что хотим сделать (чтобы использовать мьютекс, необх. только синхронизировать права доступа

__in BOOL bInheritHandle, //Определяет, можно ли дескриптор наследовать в дочерних процессах

__in LPCTSTR lpctszName );
Семафоры Windows API

^ HANDLE WINAPI CreateSemaphore (

__in_opt LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,

__in LONG lInitialCount, //Начальное

__in LONG lMaximumCount, //Максимальное значение счетчика

__in_opt LPCTSTR lpctszName );

^ HANDLE WINAPI OpenSemaphore (

__in DWORD dwDesiredAccess,

__in BOOL bInheritHandle,

__in LPCTSTR lpctszName );

Использование разделяемых событий в Windows API

Пример (event.h)

#ifndef EVENT_H__

#define EVENT_H__

#define MY_IPC_EVENT_NAME \

"event_CB44CFBF 52C3 487A 95A0 1233F5A4393C"

#define MY_IPC_MUTEX_NAME \

"mutex_0DF33C8C 71FF 4358 B10A AD7F0B7484F7"

#endif // EVENT_H__

//GUID (глобальный уникальный идентификатор)
^ Пример (main_parent.cpp)

#include "event.h"

// . . .

int main()

{ HANDLE hEvent = CreateEvent(

NULL, // lpEventAttributes

FALSE, // bManualReset

FALSE, // bInitialState

_T(MY_IPC_EVENT_NAME)); // lpctszName

// . . .

}

Строковая константа определена в заголовочном файле

Клиент гарантировано открылся после сервера

^ Пример (main_child.cpp)

#include "event.h"

// . . .

int main()

{ HANDLE hEvent = OpenEvent(

SYNCHRONIZE, // dwDesiredAccess КОНСТАНТА

FALSE, // bInheritHandle

_T(MY_IPC_EVENT_NAME)); // lpctszName //макрос, если объявлен юникод

// . . .

}

работает как с utf-16 как с юникодом, define _T(s) добавляет букву L (L##S), т.е. находится в более широкой кодировке)

функции принимают все строки в формате unicode
Способы доступа к объектам ядра в других процессах

Средства межпроцессного обмена дескрипторами

- Именованные объекты;

- Наследование дескрипторов дочерними процессами;

- Дублирование дескрипторов (DuplicateHandle()).

Семафоры POSIX

#include

#include

#include

int sem_init (

sem_t *pSem,

int nPShared, //Равен 0, если хотим сделать локальным для одного процесса, не 0 – разделять между разными (fork()ed)

unsigned int uValue);

sem_t *sem_open(

const char *pcszName, int nOFlag,

/* unsigned long ulMode, unsigned int uValue */ ...);

возможные значения флагов параметров функции sem_open()

nOFlag

O_CREAT – задает операцию создания. Если сброшен – только пытается найти ?. Передается две доп. переменные.

O_EXCL – эксклюзивный. Пытается создать. Если уже существует, то возвр. NULL в качестве указателя. Если флаг не указан, в комбинации с O_CREAT возвращает ук-ль на начало

ulMode

^ S_IRWXU S_IRUSR S_IWUSR S_IXUSR

S_IRWXG S_IRGRP S_IWGRP S_IXGRP

S_IRWXO S_IROTH S_IWOTH S_IXOTH

Мюьтексы POSIX

int pthread_mutex_init (

pthread_mutex_t *pMutex,

const pthread_mutexattr_t *pcAttr); //Указатель на аттрибуты

значения параметра функции pthread_mutexattr_setpshared()

nPShared

PTHREAD_PROCESS_PRIVATE

PTHREAD_PROCESS_SHARED

int pthread_mutexattr_init( pthread_mutexattr_t *pAttr);

int pthread_mutexattr_destroy(pthread_mutexattr_t *pAttr);

#ifdef _POSIX_THREAD_PROCESS_SHARED

int pthread_mutexattr_setpshared(pthread_mutexattr_t *pAttr,int nPShared); #endif
Разделяемая память POSIX

Сущ-ют средства, которые позволяют процессам обмениваться данными. Запрашиваем память, подключаемся в адресное пространство процесса, начиная с нек. адреса. Мб видна другим процессам.

POSIX shmget()

#include

#include

int shmget(key_t nKey, //Ключ, опред. ID, номер участка

int nSize, int nShmFlg);

Предназначениа для создания дескриптора области памяти. Параметры аналогичны:

возможные значения флагов параметров функции shmget()

nKey IPC_PRIVATE

nShmFlg^ IPC_CREAT IPC_EXCL

младшие 9 бит – флаги, которые задают права доступа на разделяемую память

Создает объект и возвращает дескриптор

#include

#include

void *shmat (//-at – attach, подключение данной области текущей памяти

int nShmId, //дескриптор области, то, что возвр. пред. функция

const void *pvShmAddr, //адрес в адресном пространстве процессов, NULL – ядро ОС самостоятельно находит адрес, чтобы подключить зад. обл. разделяемой памяти

int nShmFlg); //Флаг – поределяет способ

int shmdt(const void *pvShmAddr);
возможные значения флагов параметров функции shmat()

nShmFlg

^ SHM_RND (SHMLBA) – если указ-м конкретный адрес, то адрес будет выровнен

SHM_RDONLY – процесс только считывает, записывать не может

Пример

const key_t g_cKey = 1917;

// . . .

int nShmId = shmget(g_cKey,

sizeof (struct connect), //размер раздела памяти

^ IPC_CREAT | 0644); //флаг, пытается создать область памяти

if (nShmId < 0) //-1 если нет

{

perror("shmget"); //печатает такое сообщение в консоли

exit(1);

}

struct connect *pConnect = (struct connect *) shmat(nShmId, NULL, 0); //явное преобразование указателя // . . .

shmdt(pConnect); //отсоединяет от адр. пространства текущего процесса.

Проблема – ключ-идентификатор трудно выбрать

При помощи fork можно задавать параметры командной строки, перед. дочернему процессу.

Решение проблемы дублирования ключей

Варианты

- Использование в качестве ключа константы IPC_PRIVATE.

- Генерирование ключа при помощи функции ftok().

POSIX ftok()

#include

#include

key_t ftok(const char *pcszPathName, int nProjId);

По заданному файлу генерируем ключ. Пар-ры – (путь, номер проекта?)

stat() – функция для получения различных параметров. Вернет один ключ, даже если запускался в разл. процессах.

Разделяемая память Windows API

^ ANDLE WINAPI CreateFileMapping( //Создание объекта для работы с разд. памятью

__in HANDLE hFile,

__in_opt LPSECURITY_ATTRIBUTES lpAttributes, //NULL

__in DWORD dwProtect, //Способ доступа в памяти

__in DWORD dwMaximumSizeHigh,

__in DWORD dwMaximumSizeLow,

__in_opt LPCTSTR lpctszName );

возможные значения флагов параметров функции

dwProtect

PAGE_READONLY – исп. код из памяти и читать

PAGE_READWRITE

PAGE_WRITECOPY – режим копирования при записи

^ PAGE_EXECUTE_READ . . .

LPVOID WINAPI MapViewOfFile( //подсоединяет к адр. пространству процесса и возвр. указатель на ней

__in HANDLE hFileMappingObject,

__in DWORD dwDesiredAccess,

__in DWORD dwFileOffsetHigh, //смещение внутри обл. памяти, NULL – общая память

__in DWORD dwFileOffsetLow,

__in SIZE_T dwNumberOfBytesToMap //Размер );

BOOL WINAPI UnmapViewOfFile( //Передает адр. пр-во, отсоединяет.

__in LPCVOID lpcvBaseAddress );

dwDesiredAccess

FILE_MAP_READ

FILE_MAP_WRITE (и чтение тоже)

FILE_MAP_COPY

Каналы POSIX

нек. обл. памяти, в режиме очереди FIFO

POSIX pipe()

#include //

int pipe(int anFD[2]); // anFD[0] чтение, anFD[1] запись – указатель на массив из 2х дескрипторов

int dup2(int nOldFD, int nNewFD); //Дескриптор файла, новое значение. Закрывает файл, если нужно. Открывает 1, делает равным 1

ssize_t read(int nFD, void *pvBuf, size_t uCount); //то же, что и size_t но со значением nCount, если нет проблем

ssize_t write(int nFD, const void *pcvBuf, size_t uCount);

int eof(int nFD);

int close(int nFD); //Закрытие файла

Использование каналов в POSIX

Пример

$ ls j | more

Выводит содержимое текущего каталога, по умолчанию – список файлов | Считывает файл и выводит его постранично, если слишком большой

^ Реализация bash

1 pipe(anFD)

2 fork() (2 раза)

3 close(anFD[i]) (2 раза)

1 Создает канал для обмена, передает массив, создает директории 2 Создание процесса в POSIX В дочернем 0, в род. ID

Реализация ls

1 dup2(anFD[1], 1) //1 – вывод на консоль

2 close(anFD[i]) (2 раза)

3 execve("ls", argv, envp)

Тот же заполненный массив из двух дескрипторов, созд. новый дескриптор. То, что выводим на консоль, попадет в канал, 2й дескриптор продолжит существовать.

Реализация more

1 dup2(anFD[0], 0)

2 close(anFD[i]) (2 раза)

3 execve("more", argv, envp)

попадает в канал и читается другим процессом
1   2   3   4   5

Похожие:

Алгоритм 2 iconАлгоритм
Ш 55 Разгром Японии и самурайская угроза. — М.: Изд-во Алгоритм; Изд-во Эксмо, 2005. — 512 с, ил
Алгоритм 2 iconРазрешение записи
Для уменьшения объема хранимой видеоинформации в видеорегистраторах применяются различные алгоритмы ее компрессии. В сетевых видеорегистраторах...
Алгоритм 2 iconАннотация Слово «алгоритм»
Слово «алгоритм» не случайно введено в название книги: мне представляется, что есть возможность «разложить по полочкам» самые сложные...
Алгоритм 2 iconСтатья «Алгоритм решения изобретательских задач» в Википедии Это...
Алгоритм решения изобретательских задач[1][2][3][4][5][6][7][8][9][10] раздел теории решения изобретательских задач (триз), разработаной...
Алгоритм 2 iconПрограмма упорядоченное множество ко­манд, реализу­ющих алгоритм решения задачи
Алгоритм упорядоченное множе­ство фор­ма­ль­ных предписаний, выпол­нение которых приводит к решению задачи. Команда элементарная...
Алгоритм 2 iconАлгоритм работы системы

Алгоритм 2 icon6. задача о рюкзаке
Циклический алгоритм целочисленного программирования
Алгоритм 2 iconУкрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12
Алгоритм 2 iconЗаконодательное обоснование
Алгоритм действий граждан в случае обнаружения несанкционированных раскопок – с. 6
Алгоритм 2 iconПризрак толпы / Карл Ясперс, Жан Бодрийар. М.: Алгоритм, 2007. 272 с. Философский
Призрак толпы / Карл Ясперс, Жан Бодрийар. — М.: Алгоритм, 2007. — 272 с. — Философский
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница