Управление критическими разделами

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

Если существуют процессы или потоки, которые получают доступ к разделяемым модифицируемым данным, структурам данных или переменным, то все эти данные находятся в критической области (или разделе) кода процессов или потоков. Критический раздел кода — это та его часть, в которой обеспечивается доступ потока или процесса к разделяемому блоку модифицируемой памяти и обработка соответствующих данных. Отнесение раздела кода к критическому можно использовать для управления состоянием «гонок». Например, создаваемые в программе два потока, поток А и поток В, используются для поиска нескольких ключевых слов во всех файлах системы. Поток А просматривает текстовые файлы в каждом каталоге и записывает нужные пути в списочную структуру данных 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.