操作系統實驗報告14

實驗內容

• 實驗內容：Peterson 算法。
  • 把 Lecture08 示例 alg.8-1~8-3 拓展到多個讀線程和多個寫線程，應用 Peterson 算法原理設計實現共享內存互斥。

實驗環境

• 架構：Intel x86_64 (虛擬機)
• 操作系統：Ubuntu 20.04
• 匯編器：gas (GNU Assembler) in AT&T mode
• 編譯器：gcc

技術日志

實驗內容原理

Peterson算法

• Peterson算法是一個實現互斥鎖的并發程序設計算法，適用于兩個線程交替執行臨界區和剩余區，并且可以滿足互斥、進步、有限等待等要求，算法使用兩個控制變量flag與turn. 其中flag[n]的值為真，表示編號為n的進程希望進入該臨界區，變量turn保存有權訪問共享資源的進程的編號。可以控制兩個線程訪問同一個共享資源而不發生條件沖突。而且Peterson算法可以擴展到多個線程的情況。

• Peterson算法推廣到N個線程的算法：

  • 使用N個不同的線程級別，用數組level[N]存儲
    • 每一個線程級別都代表另一個在進入臨界區之前的“等候室”
    • 每個線程級別將允許至少一個線程繼續執行進入臨界區，同時保持一個線程在等待
  • 線程級別達到N-1的線程Pi(level(i) == N-1)將退出for循環并進入其臨界區。
  • 任何線程Pi都會將其線程級別lev升級到lev+1(即退出while循環)或：
    • 其他的線程Pj將其線程級別升級到Pi(然后是代碼level(j)==lev和waiting[lev]==j)或：
    • 任何其他線程的線程級別都低于lev。

過程圖解：

線程等候室中的線程不能退出while循環，也不能提升線程級別即使這個線程正在被調度，除非它是當前最高線程級別的唯一線程。任何不在等候室中的線程都將退出while循環，并被提升線程級別如果在被調度的話。

因此，任何低于當前最高線程級別的等候室都必須被占用。

當線程級別為q的線程Pk被調度時，它退出while循環，線程級別升級到q+1并占用q+1線程級別的等候室，Pi被移出等候室。

當線程級別為q+1的線程Pi被調度時，它退出while循環，線程級別升級到q+2，并占用q+2線程級別的等候室。Pt被移出等候室。

一種極端情況是：線程級別為0到N-2的等候室都被線程級別為N-2的線程Pt和線程Ps占用，Pt不能退出while循環即使被調度，因為它與Ps的線程級別相同。

當線程Ps被調度時，它退出while循環，因為它不在等候室中，并立即結束for循環，進入它的臨界區。

進入臨界區的線程將按其等候室編號N-2、N-3、…、2、1和0的順序排列。

代碼部分

代碼基于alg.8-1~8-3和老師給的示例文件alg.15-1-peterson-counter.c改造而來。

• 在頭文件shmdata.h中定義必要的數據和結構

#define TEXT_SIZE 4*1024定義了每一條消息的大小

#define TEXT_NUM 1定義了消息的最大條數

消息的的總大小不能超過當前最大共享內存，不然會發生無效參數的錯誤

#define PERM S_IRUSR|S_IWUSR|IPC_CREAT定義了用戶的讀、寫、創建權限，PERM | 0666代表該文件擁有者、擁有者所在組其他成員、其他用戶組的成員對該文件有讀寫的權限，但是沒有操作的權限，PERM | 0777另外有操作的權限。

#define ERR_EXIT(m) do {perror(m);exit(EXIT_FAILURE); } while(0)

ERR_EXIT(m)定義了一個異常處理的模板

struct shared_struct {int written; /* flag = 0: buffer writable; others: readable */char mtext[TEXT_SIZE]; /* buffer for message reading and writing */ };

shared_struct定義了一個共享內存中使用的結構體，其中mtext[TEXT_SIZE]是提供給消息進行讀寫的緩沖區，written為0時代表緩沖區可寫，為其它值代表緩沖區可讀。

執行程序命令：

gcc -o shmread.o shmread.c -pthread gcc -o shmwrite.o shmwrite.c -pthread gcc shmcon.c -pthread ./a.out myshm

實現細節解釋：

首先，進程shmcon會先創建一個共享內存區，然后使用execv()函數引發兩個子進程，分別為讀進程和寫進程，兩個子進程異步執行，并將IPC鍵值和兩個子進程分別要創建的線程數目作為參數傳遞給子進程，這樣保證了讀進程和寫進程創建的讀線程和寫線程數目一致，保證讀寫的正確。

shmcon.c：

// shmcon.c文件 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/stat.h> #include <sys/wait.h> #include <sys/shm.h> #include <sys/syscall.h> #include <fcntl.h> #include <unistd.h>#include "shmdata.h"#define gettid() syscall(__NR_gettid) /* wrap the system call syscall(__NR_gettid), __NR_gettid = 224 */ #define gettidv2() syscall(SYS_gettid) /* a traditional wrapper */#define THREAD_NUM 10 // 讀寫進程所要創建線程數int main(int argc, char *argv[]) {struct stat fileattr;key_t key; // 即int類型int shmid; // 共享內存標識符void *shmptr;struct shared_struct *shared; // 共享內存結構體pid_t childpid1, childpid2;char pathname[80], key_str[10], thread_num_str[10];int shmsize, ret;// 確定共享內存的大小shmsize = TEXT_NUM*sizeof(struct shared_struct);// 獲取共享文件對象路徑名if(argc <2) {printf("Usage: ./a.out pathname\n");return EXIT_FAILURE;}strcpy(pathname, argv[1]);if(stat(pathname, &fileattr) == -1) {ret = creat(pathname, O_RDWR);if (ret == -1) {ERR_EXIT("creat()");}printf("shared file object created\n");}// 獲取IPC鍵值key = ftok(pathname, 0x27);if(key == -1) {ERR_EXIT("shmcon: ftok()");}// 獲取共享內存標識符shmid = shmget((key_t)key, shmsize, 0666|PERM);if(shmid == -1) {ERR_EXIT("shmcon: shmget()");}// 把共享內存區對象映射到調用進程的地址空間，允許本進程訪問共享內存shmptr = shmat(shmid, 0, 0);if(shmptr == (void *)-1) {ERR_EXIT("shmcon: shmat()");}// 獲取共享結構體，并把共享結構體的結構體的成員變量written設為0，表示緩沖區可寫但不可讀shared = (struct shared_struct *)shmptr;shared->written = 0;// 斷開與共享內存附加點的地址，本進程不能訪問共享內存if(shmdt(shmptr) == -1) {ERR_EXIT("shmcon: shmdt()");}// 將IPC鍵值和讀寫進程所要創建的線程數作為參數傳遞給讀寫進程sprintf(key_str, "%x", key);sprintf(thread_num_str, "%d", THREAD_NUM);char *argv1[] = {" ", key_str, thread_num_str, 0};childpid1 = vfork();if(childpid1 < 0) {ERR_EXIT("shmcon: 1st vfork()");} else if(childpid1 == 0) {// 異步執行讀進程execv("./shmread.o", argv1);}else {childpid2 = vfork();if(childpid2 < 0) {ERR_EXIT("shmcon: 2nd vfork()");}else if (childpid2 == 0) {// 異步執行寫進程execv("./shmwrite.o", argv1);}else {// 等待子進程都結束后父進程再執行wait(&childpid1);wait(&childpid2);// 釋放共享內存區if (shmctl(shmid, IPC_RMID, 0) == -1) {ERR_EXIT("shmcon: shmctl(IPC_RMID)");}else {printf("The program is over\n"); }}}exit(EXIT_SUCCESS); }

讀進程shmread和寫進程shmwrite首先會根據父進程傳來的IPC鍵值獲取共享內存，然后根據父進程傳來的創建線程數分別創建多個讀線程和寫線程，線程執行函數中使用了N個線程的Peterson算法實現了互斥鎖，多個讀線程和多個寫線程分別對共享內存區的內容進行同時的讀和寫，同時讀操作和寫操作使用共享結構體的成員變量written防止沖突，實現了多線程讀寫。

shmread.c：

// shmread.c文件 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <pthread.h> #include <signal.h> #include <sys/stat.h> #include <sys/wait.h> #include <sys/shm.h> #include <sys/syscall.h> #include <fcntl.h> #include <unistd.h>#include "shmdata.h"#define gettid() syscall(__NR_gettid) /* wrap the system call syscall(__NR_gettid), __NR_gettid = 224 */ #define gettidv2() syscall(SYS_gettid) /* a traditional wrapper */#define MAX_N 1024 // 所能創建線程的最大數目static int counter = 0; // 臨界區中的進程個數 int level[MAX_N]; // 線程級別數組，每個元素分別對應第0到第MAX_N-1個線程 int waiting[MAX_N-1]; // 線程等候室數組，每個元素分別對應線程級別0到MAX_N-2的線程 int read_thread_num = 20; // 默認的創建線程數目 struct shared_struct *shared; // 共享結構體static void *ftn(void *arg) {// 獲取線程編號int *numptr = (int *)arg;int thread_num = *numptr;int lev, k;// 最多有read_thread_num-1個線程等候室for (lev = 0; lev < read_thread_num-1; ++lev) {// 設置此線程的線程級別為lev，lev從0到read_thread_num-2，每次循環都會提升一次此線程的線程級別level[thread_num] = lev;// 設置等候室中線程級別為lev的線程為此線程waiting[lev] = thread_num;// 如果等候室中線程級別為lev的線程為此線程，那么線程被阻塞進入等待while (waiting[lev] == thread_num) {// 如果在此期間，任何線程級別小于此線程的線程j提升線程級別到或大于此線程，那么此線程將被踢出等候室，當被調度時退出while循環for (k = 0; k < read_thread_num; k++) {// 從0到read_thread_num-1，如果存在不是這個線程的一個線程k，線程級別大于等于這個線程，那么退出for循環if(level[k] >= lev && k != thread_num) {break;}// 再次檢查線程等候室數組中的線程級別為lev的線程是否此線程，如果不等于，退出for循環if(waiting[lev] != thread_num) {break;}}// 其它任何線程的線程優先級都小于此線程的話，退出while循環，進入臨界區if(k == read_thread_num) {break;} }} // 臨界區代碼起始處counter++;// 如果臨界區內有多于一個線程，那么終止進程if (counter > 1) {printf("ERROR! more than one processes in their critical sections\n");kill(getpid(), SIGKILL);}counter--;// 共享結構體的成員變量written為0時，說明緩沖區不可讀，線程等待緩沖區可讀written為1之后再繼續執行while (shared->written == 0);// 打印讀出的信息之后，把共享結構體的成員變量重新written設為0，令緩沖區可寫printf("%*s%s is read by read-thread-%d tid=%ld\n", 30, " ", shared->mtext, thread_num, gettid());shared->written = 0;// 臨界區代碼結束處// 將此線程在level數組中的線程級別設為-1，表示線程結束，可以讓其它的線程級別為read_thread_num-2的線程退出while循環進入臨界區level[thread_num] = -1; pthread_exit(0); }int main(int argc, char *argv[]) {void *shmptr = NULL;int shmid;key_t key;// 獲取從父進程傳遞來的IPC鍵值sscanf(argv[1], "%x", &key);// 獲取從父進程傳遞來的創建線程個數sscanf(argv[2], "%d", &read_thread_num);// 獲取共享內存標識符shmid = shmget((key_t)key, TEXT_NUM*sizeof(struct shared_struct), 0666|PERM);if (shmid == -1) {ERR_EXIT("shread: shmget()");}// 共享內存區對象映射到調用進程的地址空間，允許本進程訪問共享內存shmptr = shmat(shmid, 0, 0);if(shmptr == (void *)-1) {ERR_EXIT("shread: shmat()");}// 獲取共享內存結構體shared = (struct shared_struct *)shmptr;// 初始化level和waiting數組memset(level, (-1), sizeof(level));memset(waiting, (-1), sizeof(waiting));int i, ret;int thread_num[read_thread_num];pthread_t ptid[read_thread_num];// 傳入參數數組for (i = 0; i < read_thread_num; i++) {thread_num[i] = i + 1;}// 打印讀線程的總數printf("total read-thread number = %d\n", read_thread_num); // 創建read_thread_num個讀線程for (i = 0; i < read_thread_num; i++) {ret = pthread_create(&ptid[i], NULL, &ftn, (void *)&thread_num[i]);if(ret != 0) {fprintf(stderr, "pthread_create error: %s\n", strerror(ret));}}// 主線程等待所有子線程退出后再繼續執行for (i = 0; i < read_thread_num; i++) {ret = pthread_join(ptid[i], NULL);if(ret != 0) {perror("pthread_join()");}}// 斷開與共享內存附加點的地址，本進程不能訪問共享內存if (shmdt(shmptr) == -1) {ERR_EXIT("shmread: shmdt()");}return 0; }

shmwrite.c：

// shmwrite.c文件 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <pthread.h> #include <signal.h> #include <sys/stat.h> #include <sys/wait.h> #include <sys/shm.h> #include <sys/syscall.h> #include <fcntl.h> #include <unistd.h>#include "shmdata.h"#define gettid() syscall(__NR_gettid) /* wrap the system call syscall(__NR_gettid), __NR_gettid = 224 */ #define gettidv2() syscall(SYS_gettid) /* a traditional wrapper */#define MAX_N 1024 // 所能創建線程的最大數目static int counter = 0; // 臨界區中的進程個數 int level[MAX_N]; // 線程級別數組，每個元素分別對應第0到第MAX_N-1個線程 int waiting[MAX_N-1]; // 線程等候室數組，每個元素分別對應線程級別0到MAX_N-2的線程 int write_thread_num = 20; // 默認的創建線程數目 struct shared_struct *shared; // 共享結構體static void *ftn(void *arg) {// 獲取線程編號int *numptr = (int *)arg;int thread_num = *numptr;int lev, k;char buffer[BUFSIZ + 1];// 最多有write_thread_num-1個線程等候室for (lev = 0; lev < write_thread_num-1; ++lev) {// 設置此線程的線程級別為lev，lev從0到write_thread_num-2，每次循環都會提升一次此線程的線程級別level[thread_num] = lev;// 設置等候室中線程級別為lev的線程為此線程waiting[lev] = thread_num;// 如果等候室中線程級別為lev的線程為此線程，那么線程被阻塞進入等待while (waiting[lev] == thread_num) {// 如果在此期間，任何線程級別小于此線程的線程j提升線程級別到或大于此線程，那么此線程將被踢出等候室，當被調度時退出while循環for (k = 0; k < write_thread_num; k++) {// 從0到write_thread_num-1，如果存在不是這個線程的一個線程k，線程級別大于等于這個線程，那么退出for循環if(level[k] >= lev && k != thread_num) {break;}// 再次檢查線程等候室數組中的線程級別為lev的線程是否此線程，如果不等于，退出for循環if(waiting[lev] != thread_num) {break;}}// 其它任何線程的線程優先級都小于此線程的話，退出while循環，進入臨界區if(k == write_thread_num) {break;} }}// 臨界區代碼起始處counter++;// 如果臨界區內有多于一個線程，那么終止進程if (counter > 1) {printf("ERROR! more than one processes in their critical sections\n");kill(getpid(), SIGKILL);}counter--;// 共享結構體的成員變量written為1時，說明緩沖區不可寫，線程等待緩沖區可寫written為0之后再繼續執行while (shared->written == 1);// 寫入信息之后，把共享結構體的成員變量written重新設為1，令緩沖區可讀sprintf(buffer, "\"message from thread tid=%ld\"", gettid());printf("\nwrite-thread-%d tid=%ld writes: %s\n", thread_num, gettid(), buffer);strncpy(shared->mtext, buffer, TEXT_SIZE);shared->written = 1;// 臨界區代碼結束處// 將此線程在level數組中的線程級別設為-1，表示線程結束，可以讓其它的線程級別為write_thread_num-2的線程退出while循環進入臨界區level[thread_num] = -1; pthread_exit(0); }int main(int argc, char *argv[]) {void *shmptr = NULL;int shmid;key_t key;// 獲取從父進程傳遞來的IPC鍵值sscanf(argv[1], "%x", &key);// 獲取從父進程傳遞來的創建線程個數sscanf(argv[2], "%d", &write_thread_num);// 獲取共享內存標識符shmid = shmget((key_t)key, TEXT_NUM*sizeof(struct shared_struct), 0666|PERM);if (shmid == -1) {ERR_EXIT("shread: shmget()");}// 共享內存區對象映射到調用進程的地址空間，允許本進程訪問共享內存shmptr = shmat(shmid, 0, 0);if(shmptr == (void *)-1) {ERR_EXIT("shread: shmat()");}// 獲取共享內存結構體shared = (struct shared_struct *)shmptr;// 初始化level和waiting數組memset(level, (-1), sizeof(level));memset(waiting, (-1), sizeof(waiting));int i, ret;int thread_num[write_thread_num];pthread_t ptid[write_thread_num];// 傳入參數數組for (i = 0; i < write_thread_num; i++) {thread_num[i] = i + 1;}// 打印寫線程的總數printf("total wrtie-thread number = %d\n", write_thread_num); // 創建write_thread_num個寫線程for (i = 0; i < write_thread_num; i++) {ret = pthread_create(&ptid[i], NULL, &ftn, (void *)&thread_num[i]);if(ret != 0) {fprintf(stderr, "pthread_create error: %s\n", strerror(ret));}}// 主線程等待所有子線程退出后再繼續執行for (i = 0; i < write_thread_num; i++) {ret = pthread_join(ptid[i], NULL);if(ret != 0) {perror("pthread_join()");}}// 斷開與共享內存附加點的地址，本進程不能訪問共享內存if (shmdt(shmptr) == -1) {ERR_EXIT("shmread: shmdt()");}return 0; }

分析：

在shmcon.c文件中，改變要創建的線程數量，可以對程序進行測試

測試用例1：

當創建的讀線程和寫線程數量分別為10個時：

#define THREAD_NUM 10

可以看到，多個讀線程并發進行讀，多個寫線程并發進行寫，由于使用了Peterson算法和成員變量written，讀寫有序進行，每次寫入一個內容，讀出的是相同的內容，多個讀線程并發讀沒有沖突，多個寫線程并發寫也沒有沖突，在讀線程和寫線程數量分別為10時，線程數量較少，程序可以正常進行。

測試用例2：

當創建的讀線程和寫線程數量分別為100個時：

#define THREAD_NUM 100

可以看到，多個讀線程并發進行讀，多個寫線程并發進行寫，讀寫有序進行，每次寫入一個內容，讀出的是相同的內容，多個讀線程并發讀沒有沖突，多個寫線程并發寫也沒有沖突，程序可以正常進行，在讀線程和寫線程數量分別為100時，線程數量一般，因為for循環的循環次數增多，所以程序運行的速度稍微變慢。

測試用例3：

當創建的讀線程和寫線程數量分別為500個時：

#define THREAD_NUM 500

可以看到，多個讀線程并發進行讀，多個寫線程并發進行寫，讀寫有序進行，每次寫入一個內容，讀出的是相同的內容，多個讀線程并發讀沒有沖突，多個寫線程并發寫也沒有沖突，程序可以正常進行。在讀線程和寫線程數量分別為500時，線程數量較多，因為for循環的循環次數變的太多，所以程序運行的速度非常的慢。

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的操作系统实验报告14：Peterson 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。