![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Управление критическими разделами
Параллельно выполняемые процессы (или потоки в одном процессе) могут совместно использовать структуры данных, переменные или отдельные данные. Разделение глобальной памяти позволяет процессам или потокам взаимодействовать друг с другом и получать доступ к общим данным. При использовании нескольких процессов разделяемая глобальная память является внешней по отношению к ним. Внешнюю структуру данных можно использовать для передачи данных или команд между процессами. Если же необходимо организовать взаимодействие потоков, то они могут иметь доступ к структурам данных или переменным, являющимся частью одного и того же процесса, которому они принадлежат. Если существуют процессы или потоки, которые получают доступ к разделяемым модифицируемым данным, структурам данных или переменным, то все эти данные находятся в критической области (или разделе) кода процессов или потоков. Критический раздел кода — это та его часть, в которой обеспечивается доступ потока или процесса к разделяемому блоку модифицируемой памяти и обработка соответствующих данных. Отнесение раздела кода к критическому можно использовать для управления состоянием «гонок». Например, создаваемые в программе два потока, поток А и поток В, используются для поиска нескольких ключевых слов во всех файлах системы. Поток А просматривает текстовые файлы в каждом каталоге и записывает нужные пути в списочную структуру данных TextFiles, а затем инкрементирует переменную FileCount. Поток В выделяет имена файлов из списка TextFiles, декрементирует переменную FileCount, после чего просматривает файл на предмет поиска в нем заданных ключевых слов. Файл, который их содержит, переписывается в другой файл, и инкрементируется еще одна переменная FoundCount. К переменной FoundCount поток А доступа не имеет. Потоки А и В могут выполняться одновременно на отдельных процессорах. Поток А выполняется до тех пор, пока не будут просмотрены все каталоги, в то время как поток В просматривает каждый файл, путь к которому выделен из переменной TextFiles. Упомянутый список поддерживается в отсортированном порядке, и в любой момент его содержимое можно отобразить на экране. Здесь возможна масса проблем. Например, поток В может попытаться выделить имя файла из списка TextFiles до того, как поток А его туда поместит. Поток В может попытаться декрементировать переменную SearchCount до того, как поток А её инкрементирует, или же оба потока могут попытаться модифицировать эту переменную одновременно. Кроме того, во время сортировки элементов списка TextFiles поток А может попытаться записать в него имя файла, или поток В будет в это время пытаться выделить из него имя файла для выполнения своей задачи. Описанные проблемы—это примеры условий «гонок», при которых несколько потоков (или процессов) пытаются одновременно модифицировать один и тот же блок общей памяти. Если потоки или процессы одновременно лишь читают один и тот же блок памяти, условия «гонок» не возникают. Они возникают в случае, когда несколько процессов или потоков одновременно получают доступ к одному и тому же блоку памяти, и по крайней мере один из этих процессов или потоков делает попытку модифицировать данные. Раздел кода становится критическим, когда он делает возможными одновременные попытки изменить один и тот же блок памяти. Один из способов защитить к ритический раздел — разрешить только монопольный доступ к блоку памяти. Монопольный доступ означает, что к разделяемому блоку памяти будет иметь доступ один процесс или поток в течении короткого промежутка времени, при этом всем остальным процессам или потокам запрещено (путем блокировки) входить в свои критические разделы, которые обеспечивают доступ к тому же самому блоку памяти. Для управления условиями «гонок» можно использовать такой механизм блокировки, как взаимо - исключающий семафор, или мьютекс (mutex— сокращение от «mutual exclusion», - взаимное исключение). Мьютекс используется для блокирования критического раздела: он блокируется до входа в критический раздел, а при выходе из него - деблокируется: Блокирование мьютекса // Вход в критический раздел. // Доступ к разделяемой модифицируемой памяти. // Выход из критического раздела. Деблокирование мьютекса Класс pthread_mutex_t позволяет смоделировать мьютексный объект. Прежде, чем объект типа pthread_mutex_t можно будет использовать, его необходимо инициализировать. Для инициализации мьютекса используется функция pthread_mutex_init(). Инициализированный мьютекс можно заблокировать деблокировать и разрушить с помощью функций pthread_mutex_lock(), pthread_mutex_unlock () и pthread_mutex_destroy () соответственно. В программе 4.5 содержится функция, которая выполняет поиск текстовых файлов, а в программе 4.6 — функция, которая просматривает каждый текстовый файл на предмет содержания в нем заданных ключевых слов. Каждая функция выполняется потоком. Основной поток реализован в программе 4.7. Эти программы реализуют модель «изготовитель-потребитель» для делегирования задач потокам. Программа4.5 содержит поток-«изготовитель», а программа 4.6 — поток-«потребитель». Критические разделы выделены в них полужирным шрифтом. // Программа 4.5 1 int isDirectory(string FileName) 2 { 3 struct stat StatBuffer; 5 lstat(FileName.c_str(), & StatBuffer); 6 if((StatBuffer.st_mode & S_IFDIR) == -1) 7 { 8 cout < < «could not get stats on file» < < endl; 9 return(0); 10 } 11 else{ 12 if(StatBuffer.st_mode & S_IFDIR){ 13 return(1); 14 } 15 } 16 return(0); 17 } 20 int isRegular(string FileName) 21 { 22 struct stat StatBuffer; 24 lstat(FileName.c_str(), & StatBuffer); 25 if((StatBuffer.st_mode & S_IFDIR) == -1) 26 { 27 cout < < «could not get stats on file» < < endl; 28 return(0); 29 } 30 else{ 31 if(StatBuffer.st_mode & S_IFREG){ 32 return(1); 33 } 34 } 35 return(0); 36 } 39 void depthFirstTraversal(const char *CurrentDir) 40 { 41 DIR *DirP; 42 string Temp; 43 string FileName; 44 struct dirent *EntryP; 45 chdir(CurrentDir); 46 cout < < «Searching Directory: " < < CurrentDir < < endl; 47 DirP = opendir(CurrentDir); 49 if(DirP == NULL){ 50 cout < < «could not open file» < < endl; 51 return; 52 } 53 EntryP = readdir(DirP); 54 while(EntryP! = NULL) 55 { 56 Temp.erase(); 57 FileName.erase(); 58 Temp = EntryP-> d_name; 59 if((Temp! = ".») & & (Temp! = "..»)){ 60 FileName.assign(CurrentDir); 61 FileName.append(1, '/'); 62 FileName.append(EntryP-> d_name); 63 if(isDirectory(FileName)){ 64 string NewDirectory; 65 NewDirectory = FileName; 66 depthFirstTraversal(NewDirectory.c_str()); 67 } 68 else{ 69 if(isRegular(FileName)){ 70 int Flag; 71 Flag = FileName.find(".cpp»); 72 if(Flag > 0){ 73 pthread_mutex_lock(& CountMutex); 74 FileCount++; 75 pthread_mutex_unlock(& CountMutex); 76 pthread_mutex_lock(& QueueMutex); 77 TextFiles.push(FileName); 78 pthread_mutex_unlock(& QueueMutex); 79 } 80 } 81 } 83 } 84 EntryP = readdir(DirP); 85 } 86 closedir(DirP); 87 } 91 void *task(void *X) 92 { 93 char *Directory; 94 Directory = static_cast< char *> (X); 95 depthFirstTraversal(Directory); 96 return(NULL); 98 } Программа 4.6 содержит поток-«потребитель», который выполняет ных ключевых слов. // Программа 4.6 1 void *keySearch(void *X) 2 { 3 string Temp, Filename; 4 less< string> Comp; 6 while(! Keyfile.eof() & & Keyfile.good()) 7 { 8 Keyfile > > Temp; 9 if(! Keyfile.eof()){ 10 KeyWords.insert(Temp); 11 } 12 } 13 Keyfile.close(); 15 while(TextFiles.empty()) 16 { } 18 while(! TextFiles.empty()) 19 { 20 pthread_mutex_lock(& QueueMutex); 21 Filename = TextFiles.front(); 22 TextFiles.pop(); 23 pthread_mutex_unlock(& QueueMutex); 24 Infile.open(Filename.c_str()); 25 SearchWords.erase(SearchWords.begin(), SearchWords.end()); 27 while(! Infile.eof() & & Infile.good()) 28 { 29 Infile > > Temp; 30 SearchWords.insert(Temp); 31 } 33 Infile.close(); 34 if(includes(SearchWords.begin(), SearchWords.end(), KeyWords.begin(), KeyWords.end(), Comp)){ 35 Outfile < < Filename < < endl; 36 pthread_mutex_lock(& CountMutex); 37 FileCount--; 38 pthread_mutex_unlock(& CountMutex); 39 FoundCount++; 40 } 41 } 42 return(NULL); 44 } Программа 4.7 содержит основной поток для потоков модели «изготовитель-потребитель», реализованных в программах 4.5 и 4.6. // Программа 4.7 1 #include < sys/stat.h> 2 #include < fstream> 3 #include < queue> 4 #include < algorithm> 5 #include < pthread.h> 6 #include < iostream> 7 #include < set> 9 pthread_mutex_t QueueMutex = PTHREAD_MUTEX_INITIALIZER; 10 pthread_mutex_t CountMutex = PTHREAD_MUTEX_INITIALIZER; 12 int FileCount = 0; 13 int FoundCount = 0; 15 int keySearch(void); 16 queue< string> TextFiles; 17 set < string, less< string> > KeyWords; 18 set < string, less< string> > SearchWords; 19 ifstream Infile; 20 ofstream Outfile; 21 ifstream Keyfile; 22 string KeywordFile; 23 string OutFilename; 24 pthread_t Thread1; 25 pthread_t Thread2; 27 void depthFirstTraversal(const char *CurrentDir); 28 int isDirectory(string FileName); 29 int isRegular(string FileName); 31 int main(int argc, char *argv[]) 32 { 33 if(argc! = 4){ 34 cerr < < «need more info» < < endl; 35 exit (1); 36 } 38 Outfile.open(argv[3], ios:: app||ios:: ate); 39 Keyfile.open(argv[2]); 40 pthread_create(& Thread1, NULL, task, argv[1]); 41 pthread_create(& Thread2, NULL, keySearch, argv[1]); 42 pthread_join(Thread1, NULL); 43 pthread_join(Thread2, NULL); 44 pthread_mutex_destroy(& CountMutex); 45 pthread_mutex_destroy(& QueueMutex); 47 cout < < argv[1] < < " contains " < < FoundCount < < " files that contains all keywords.» < < endl; 48 return(0); 49 } С помощью мьютексов доступ к разделяемой памяти для чтения или записи данных разрешается получить только одному потоку. Для гарантии безопасности работы функций, определенных пользователем, можно использовать и другие механизмы и методы, которые реализуют одну из моделей PRAM: • EREW (монопольное чтение и монопольная запись) • CREW (параллельное чтение и монопольная запись) • ERCW (монопольное чтение и параллельная запись) • CRCW (параллельное чтение и параллельная запись) Мьютексы используются для реализации EREW-алгоритмов, которые рассматриваются в главе 5.
|