啊啊啊啊

实验一：

邻接表：

 1 #include <iostream>
 2 using namespace std;
 3 const int MAX = 30;
 4 typedef int SubType;
 5 typedef bool WeightType;
 6 struct Node//结点
 7 {
 8     SubType sub;
 9     WeightType weight;
10     struct Node* pNext = NULL;
11 };
12 typedef struct Vertex//表顶点
13 {
14     struct Node* pHead;
15 }AdjList[MAX];
16 void Insert_(AdjList adj, SubType v1, SubType v2, WeightType w)
17 {
18     struct Node* s = new struct Node;
19     s->pNext = NULL;
20     s->sub = v2;
21     s->weight = w;
22     if (adj[v1].pHead == NULL)
23     {
24         adj[v1].pHead = s;
25     }
26     else
27     {
28         struct Node* p = adj[v1].pHead;
29         struct Node* pr = NULL;
30         while (p != NULL)
31         {
32             if (p->sub == v2)//已存在，无需插入，修改权值
33             {
34                 p->weight = w;
35                 return;
36             }
37             pr = p;
38             p = p->pNext;
39         }
40         pr->pNext = s;
41     }
42 }
43 void Insert(AdjList adj, SubType v1, SubType v2, WeightType w)
44 {
45     Insert_(adj, v1, v2, w);
46     Insert_(adj, v2, v1, w);
47 }
48 int main()
49 {
50     AdjList G;
51     for (int i = 0; i < MAX; ++i)
52         G[i].pHead = NULL;
53 
54     Insert(G, 0, 2, true);
55 
56     return 0;
57 }

View Code

邻接矩阵：

 1 #include <iostream>
 2 using namespace std;
 3 const int MAX = 30;
 4 typedef int SubType;
 5 typedef bool WeightType;
 6 void Insert(WeightType (*G)[MAX], SubType v1, SubType v2, WeightType w)
 7 {
 8     G[v1][v2] = G[v2][v1] = w;
 9 }
10 int main()
11 {
12     WeightType G[MAX][MAX];
13     for(int i=0;i<MAX;++i)
14         for (int j = 0; j < MAX; ++j)
15         {
16             G[i][j] = i == j ? true : false;
17         }
18     Insert(G, 0, 5, true);
19     return 0;
20 }

View Code

实验二：

BFS+DFS（邻接表）：

  1 #include <iostream>
  2 using namespace std;
  3 const int MAX = 30;
  4 int first = 0;
  5 typedef int SubType;
  6 typedef bool WeightType;
  7 bool visited[MAX][MAX];
  8 bool inQueue[MAX];
  9 typedef struct Node//结点
 10 {
 11     SubType sub;
 12     WeightType weight;
 13     struct Node* pNext = NULL;
 14 };
 15 struct Queue
 16 {
 17     SubType s[MAX];
 18     int r = -1;
 19     int f = -1;
 20 };
 21 Queue q;
 22 typedef struct Vertex//表顶点
 23 {
 24     struct Node* pHead;
 25 }AdjList[MAX];
 26 void Insert_(AdjList adj, SubType v1, SubType v2, WeightType w)
 27 {
 28     struct Node* s = new struct Node;
 29     s->pNext = NULL;
 30     s->sub = v2;
 31     s->weight = w;
 32     if (adj[v1].pHead == NULL)
 33     {
 34         adj[v1].pHead = s;
 35     }
 36     else
 37     {
 38         struct Node* p = adj[v1].pHead;
 39         struct Node* pr = NULL;
 40         while (p != NULL)
 41         {
 42             if (p->sub == v2)//已存在，无需插入，修改权值
 43             {
 44                 p->weight = w;
 45                 return;
 46             }
 47             pr = p;
 48             p = p->pNext;
 49         }
 50         pr->pNext = s;
 51     }
 52 }
 53 void Insert(AdjList adj, SubType v1, SubType v2, WeightType w)
 54 {
 55     Insert_(adj, v1, v2, w);
 56     Insert_(adj, v2, v1, w);
 57 }
 58 void dfs(AdjList G, SubType i)
 59 {
 60     struct Node* p = G[i].pHead;
 61     while (p != NULL)
 62     {
 63         if (!visited[i][p->sub] && p->weight == true)
 64         {
 65             visited[i][p->sub] = visited[p->sub][i] = true;
 66             if (first != 0)  cout << "->";
 67             ++first;
 68             cout << "(" << i << "," << p->sub << ")";
 69             dfs(G, p->sub);
 70         }
 71         p = p->pNext;
 72     }
 73 }
 74 void bfs(AdjList G, SubType i)
 75 {
 76     q.s[++q.f] = i;
 77     inQueue[i] = true;
 78     int cnt = 0;
 79     while (q.r < q.f)
 80     {
 81         SubType n = q.s[++q.r];
 82         if (cnt != 0)cout << "->";
 83             ++cnt;
 84         cout << n;
 85         struct Node* p = G[n].pHead;
 86         while (p != NULL)
 87         {
 88             if (!inQueue[p->sub])
 89             {
 90                 inQueue[p->sub] = true;
 91                 q.s[++q.f] = p->sub;
 92             }
 93             p = p->pNext;
 94         }
 95     }
 96 }
 97 int main()
 98 {
 99     AdjList G;
100     for (int i = 0; i < MAX; ++i)
101         G[i].pHead = NULL;
102     for (int i = 0; i < MAX; ++i)
103         for (int j = 0; j < MAX; ++j)
104         {
105             visited[i][j] = visited[j][i] = false;
106         }
107     Insert(G, 0, 2, true);
108     Insert(G, 5, 2, true);
109     Insert(G, 6, 3, true);
110     Insert(G, 7, 2, true);
111     Insert(G, 9, 3, true);
112     Insert(G, 2, 3, true);
113     cout << "DFS:";
114     dfs(G, 0);
115     cout << endl;
116     cout << "BFS:";
117     bfs(G, 0);
118     return 0;
119 }

View Code

实验三：

最小生成树（邻接表）：

啊啊啊啊

Prim和Kruskal：

  1 #include <iostream>
  2 using namespace std;
  3 typedef int NumType;
  4 typedef int WeightType;
  5 const WeightType INFINITE = 65535;
  6 const NumType MAX = 6;
  7 #define MAXEDGE MAX * MAX
  8 bool InsertFlag = true;
  9 int EdgeCnt = 0;
 10 struct Node//结点
 11 {
 12     NumType sub;
 13     WeightType weight;
 14     struct Node* pNext = NULL;
 15 };
 16 typedef struct Vertex//表顶点
 17 {
 18     struct Node* pHead;
 19 }AdjList[MAX];
 20 struct Edge
 21 {
 22     NumType u, v;
 23     WeightType w;
 24 };
 25 struct Edge* edge = new struct Edge[MAXEDGE];
 26 int r = -1;
 27 void Insert_(AdjList adj, NumType v1, NumType v2, WeightType w)
 28 {
 29     struct Node* s = new struct Node;
 30     s->pNext = NULL;
 31     s->sub = v2;
 32     s->weight = w;
 33     if (adj[v1].pHead == NULL)
 34     {
 35         adj[v1].pHead = s;
 36     }
 37     else
 38     {
 39         struct Node* p = adj[v1].pHead;
 40         struct Node* pr = NULL;
 41         while (p != NULL)
 42         {
 43             if (p->sub == v2)//已存在，无需插入，修改权值
 44             {
 45                 InsertFlag = false;
 46                 p->weight = w;
 47                 return;
 48             }
 49             pr = p;
 50             p = p->pNext;
 51         }
 52         pr->pNext = s;
 53     }
 54 }
 55 void Insert(AdjList adj, NumType v1, NumType v2, WeightType w)
 56 {
 57     InsertFlag = true;//成功插入边
 58     Insert_(adj, v1, v2, w);
 59     Insert_(adj, v2, v1, w);
 60     if (InsertFlag)
 61     {
 62         ++EdgeCnt;
 63         edge[++r].u = v1;
 64         edge[r].v = v2;
 65         edge[r].w = w;
 66      }
 67 }
 68 NumType min[];//存储在最小生成树内的点的编号
 69 bool visited[MAX][MAX];
 70 WeightType prim(AdjList G)//返回最小边权和
 71 {
 72     WeightType ret = 0;//最小和
 73     WeightType dis[MAX];//各点到最小生成树的距离
 74     fill(dis, dis + MAX, INFINITE);//初始化为INFINITE
 75     dis[0] = 0;
 76     struct Node* p = G[0].pHead;
 77     while (p != NULL)
 78     {
 79         dis[p->sub] = p->weight;//把与0相接的点距离0点的距离放入dis
 80         p = p->pNext;
 81     }
 82 
 83     for (int i = 0; i < MAX-1; ++i)//循环MAX次
 84     {
 85         WeightType min = INFINITE;
 86         int k = -1;//存储最小dis的下标
 87         for (int j = 0; j < MAX; ++j)//找出最小dis
 88         {
 89             if (dis[j] != 0 && dis[j] < min)
 90             {
 91                 min = dis[j];
 92                 k = j;
 93             }
 94         }
 95        if (k == -1) return -1;//不连通
 96         ret += min;//更新边权和
 97         dis[k] = 0;//k纳入最小生成树
 98         WeightType temp[MAX];//存储k与相接点的权
 99         fill(temp, temp + MAX, INFINITE);
100         p = G[k].pHead;
101         while (p != NULL)
102         {
103             temp[p->sub] = p->weight;
104             p = p->pNext;
105         }
106         for (int i = 0; i < MAX; ++i)//如果未访问点dis值由于k的纳入变得更小，则更新
107         {
108             if (dis[i] != 0 && temp[i] != INFINITE && temp[i] < dis[i])
109                 dis[i] = temp[i];
110         }
111     }
112     return ret;
113 }
114 //-----------------------Kruskal------------------------
115 NumType root[MAX];
116 NumType FindRoot(NumType x)
117 {
118     NumType t = x;
119     while (root[x] != x)
120     {
121         x = root[x];
122     }
123     return x;
124 }
125 WeightType kruskal(AdjList G)
126 {
127     WeightType ret = 0;
128     int EdgeNum = 0;
129     for (int i = 0; i < EdgeCnt; ++i)//排序
130     {
131         for (int j = 1; j < EdgeCnt; ++j)
132         {
133              if (edge[j].w < edge[j - 1].w)
134             {
135                 struct Edge temp = edge[j];
136                 edge[j] = edge[j - 1];
137                 edge[j - 1] = temp;
138             }
139         }
140     }
141 
142     for (int i = 0; i < EdgeCnt; ++i)
143     {
144         NumType ru = FindRoot(edge[i].u);
145         NumType rv = FindRoot(edge[i].v);
146         if (ru != rv)
147         {
148             root[ru] = rv;//合并集合
149             ret += edge[i].w;
150             ++EdgeNum;
151             if (EdgeNum == MAX - 1) break;//变数为结点数-1，说明生成树构造完成
152         }
153     }
154     if (EdgeNum != MAX - 1) return -1;//图不连通
155     return ret;
156 }
157 
158 int main()
159 {
160     AdjList G;
161     for (int i = 0; i < MAX; ++i)
162         G[i].pHead = NULL;
163     for (int i = 0; i < MAX; ++i)
164         root[i] = i;
165     //构造图
166     Insert(G, 0, 1, 4);
167     Insert(G, 0, 4, 1);
168     Insert(G, 0, 5, 2);
169     Insert(G, 1, 5, 3);
170     Insert(G, 2, 1, 6);
171     Insert(G, 2, 3, 6);
172     Insert(G, 2, 5, 5);
173     Insert(G, 3, 5, 5);
174     Insert(G, 3, 4, 4);
175     Insert(G, 4, 5, 3);
176 
177     cout << "Prim：" << prim(G) <<endl;
178 
179     cout << "Kruskal：" << kruskal(G) << endl;
180 
181     return 0;
182 }

View Code

实验四：

啊啊啊啊

最短路径

Dijkstra：

  1 #include <iostream>
  2 using namespace std;
  3 const int INFINITE = 65535;
  4 const int N = 10;
  5 int pre[N];
  6 int r = -1;
  7 int G[N][N];
  8 void Dijkstra(int(*G)[N], int start, int dis[])
  9 {
 10     bool visited[N];
 11     for (int i = 0; i < N; ++i) dis[i] = G[start][i];
 12     dis[start] = 0;
 13     for (int i = 0; i < N; ++i) visited[i] = false;
 14     visited[start] = true;
 15     for (int i = 0; i < N; ++i)
 16     {
 17         dis[i] = G[start][i];
 18         pre[i] = start;
 19     }
 20     dis[start] = 0;
 21     for (int i = 0; i < N; ++i)
 22     {
 23         int min = INFINITE;
 24         int k = 0;
 25         for (int j = 0; j < N; ++j)
 26         {
 27             if (dis[j] < min && visited[j] == false)
 28             {
 29                 min = dis[j];
 30                 k = j;
 31             }
 32         }
 33         visited[k] = true;
 34         for (int v = 0; v < N; ++v)
 35         {
 36             if (dis[k] + G[k][v] < dis[v] && visited[v] == false)
 37             {
 38                 dis[v] = dis[k] + G[k][v];
 39                 pre[v] = k;
 40             }
 41 
 42         }
 43     }
 44 }
 45 void set(int i, int j, int w)
 46 {
 47     G[i][j] = G[j][i] = w;
 48 }
 49 int main()
 50 {
 51     for (int i = 0; i < N; ++i)
 52         for (int j = 0; j < N; ++j)
 53             G[i][j] = INFINITE;
 54     set(0, 1, 50);
 55     set(0, 5, 1);
 56     set(0, 8, 18);
 57     set(1, 5, 7);
 58     set(1, 2, 5);
 59     set(2, 5, 2);
 60     set(2, 3, 7);
 61     set(2, 6, 10);
 62     set(3, 4, 8);
 63     set(3, 7, 1);
 64     set(3, 6, 10);
 65     set(4, 7, 1);
 66     set(5, 6, 1);
 67     set(5, 8, 15);
 68     set(6, 8, 5);
 69     set(6, 7, 1);
 70     set(6, 9, 3);
 71     set(8, 9, 1);
 72     set(7, 9, 1);
 73     int dis[N];//start到其余点的距离
 74     int start = 0;
 75     Dijkstra(G, start, dis);
 76 
 77     for (int i = 0; i < N; ++i)
 78     {
 79         if (i == start)continue;
 80         cout << start << "到" << i << "的最短路径长度：" << dis[i] << " ";
 81         cout << "路径：";
 82         int out[N];
 83         int rOut = -1;
 84         int e = i;
 85         while (e != start)
 86         {
 87             out[++rOut] = e;
 88             e = pre[e];
 89         }
 90         out[++rOut] = start;
 91         bool outFirst = true;
 92         while (rOut != -1)
 93         {
 94             if (!outFirst)
 95                 cout << "->";
 96             cout << out[rOut--];
 97             outFirst = false;
 98         }
 99         cout << endl;
100     }
101     return 0;
102

View Code

实验五

最短路径

Floyd：

 1 #include <iostream>
 2 using namespace std;
 3 const int INFINITE = 65535;
 4 const int N = 10;
 5 int G[N][N];
 6 int pre[N];
 7 int r = -1;
 8 int dis[N][N];
 9 int path[N][N];//保存路径
10 void Floyd(int(*G)[N])
11 {
12     for (int i = 0; i < N; ++i)
13         for (int j = 0; j < N; ++j)
14         {
15             dis[i][j] = G[i][j];
16             path[i][j] = j;
17         }
18 
19     for (int i = 0; i < N; ++i)
20         dis[i][i] = 0;
21     for(int k=0; k<N; ++k)
22         for(int i=0; i<N; ++i)
23             for (int j = 0; j < N; ++j)
24             {
25                 if (dis[i][k] != INFINITE && dis[k][j] != INFINITE && dis[i][k] + dis[k][j] < dis[i][j])
26                 {
27                     dis[i][j] = dis[i][k] + dis[k][j];
28                     path[i][j] = path[i][k];
29                 }
30             }
31 }
32 void print(int s, int e)
33 {
34     int t = path[s][e];
35     cout << "->" << t;
36     if (t == e) return;
37     print(t, e);
38 }
39 void Print(int s, int e)
40 {
41     cout << s;
42     print(s, e);
43 }
44 void set(int i, int j,int w)
45 {
46     G[i][j] = G[j][i] = w;
47 }
48 int main()
49 {
50     for (int i = 0; i < N; ++i)
51         for (int j = 0; j < N; ++j)
52             G[i][j] = INFINITE;
53     set(0, 1, 50);
54     set(0, 5, 1);
55     set(0, 8, 18);
56     set(1, 5, 7);
57     set(1, 2, 5);
58     set(2, 5, 2);
59     set(2, 3, 7);
60     set(2, 6, 10);
61     set(3, 4, 8);
62     set(3, 7, 1);
63     set(3, 6, 10);
64     set(4, 7, 1);
65     set(5, 6, 1);
66     set(5, 8, 15);
67     set(6, 8, 5);
68     set(6, 7, 1);
69     set(6, 9, 3);
70     set(8, 9, 1);
71     set(7, 9, 1);
72     Floyd(G);
73 
74     for (int i = 0; i < N; ++i)
75     {
76         for (int j = 0; j < N; ++j)
77         {
78             cout << i << "到" << j << "最短路径长度：" << dis[i][j] << endl;
79             cout << "路径为：";
80             Print(i, j);
81             cout << endl;
82         }
83         cout << endl;
84     }
85     return 0;
86 }

View Code

啊啊啊啊

实验六：图的综合应用

啊啊啊啊

  1 #include <iostream>
  2 using namespace std;
  3 const int INFINITE = 65535;
  4 const int MAX = 20;
  5 typedef int WeightType;
  6 typedef int NumType;//结点编号类型
  7 const int N = 17;
  8 int E = 0;//边数
  9 WeightType G[MAX][MAX];
 10 struct Edge
 11 {
 12     NumType u, v;
 13     WeightType w;
 14 };
 15 struct Edge* edge = new struct Edge[N*N];
 16 int rEdge = -1;
 17 void set(int i, int j, WeightType w)
 18 {
 19     if (G[i][j] == INFINITE)
 20     {      
 21         ++E;
 22         edge[++rEdge].u = i;
 23         edge[rEdge].v = j;
 24         edge[rEdge].w = w;
 25     }
 26     G[i][j] = G[j][i] = w;
 27 }
 28 struct Queue
 29 {
 30     int s[MAX];
 31     int r = -1, f = -1;
 32 };
 33 Queue q;
 34 bool inQueue[MAX];
 35 bool VISITED[MAX];
 36 
 37 void DFS(int i)
 38 {
 39     VISITED[i] = true;
 40     for (int j = 0; j < N; ++j)
 41     { 
 42         if (VISITED[j] == false && G[i][j] != INFINITE )
 43         {
 44             cout << "(" << i << "->" << j << ")";
 45             DFS(j);
 46         }
 47     }
 48 }
 49 void BFS(int i)
 50 {
 51     q.s[++q.f] = i;
 52     inQueue[i] = true;
 53     int cnt = 0;
 54     while (q.r < q.f)
 55     {
 56         int n= q.s[++q.r];
 57         if (cnt != 0)cout << "->";
 58             ++cnt;
 59         cout << n;
 60         for (int j = 0; j < N; ++j)
 61         {
 62             if (inQueue[j] == false && G[n][j] != INFINITE)
 63             {
 64                 q.s[++q.f] = j;
 65                 inQueue[j] = true;
 66             }
 67         }
 68     }
 69 }
 70 //Prim
 71 int dis[N];
 72 WeightType Prim()//返回最小边权和
 73 {
 74     WeightType ret = 0;//最小和
 75     WeightType dis[MAX];//各点到最小生成树的距离
 76     fill(dis, dis + MAX, INFINITE);//初始化为INFINITE
 77     dis[0] = 0;//从0开始
 78     for (int i = 1; i < N; ++i)//把与0相接的点距离0点的距离放入dis
 79     {
 80         if (G[0][i] != INFINITE)
 81             dis[i] = G[0][i];
 82     }
 83 
 84     for (int i = 0; i < N - 1; ++i)//循环MAX次
 85     {
 86         WeightType min = INFINITE;
 87         int k = -1;//存储最小dis的下标
 88         for (int j = 0; j < MAX; ++j)//找出最小dis
 89         {
 90             if (dis[j] != 0 && dis[j] < min)
 91             {
 92                 min = dis[j];
 93                 k = j;
 94             }
 95         }
 96         if (k == -1) return -1;//不连通
 97         ret += min;//更新边权和
 98         dis[k] = 0;//k纳入最小生成树
 99         WeightType temp[MAX];//存储k与相接点的权
100         fill(temp, temp + MAX, INFINITE);
101         for (int i = 0; i < N; ++i)
102         {
103             if (temp[i] = G[k][i]);
104         }
105         for (int i = 0; i < MAX; ++i)//如果未访问点dis值由于k的纳入变得更小，则更新
106         {
107             if (dis[i] != 0 && temp[i] != INFINITE && temp[i] < dis[i])
108                 dis[i] = temp[i];
109         }
110     }
111     return ret;
112 }
113 //Kruskal
114 NumType root[MAX];
115 NumType FindRoot(NumType x)
116 {
117     NumType t = x;
118     while (root[x] != x)
119     {
120         x = root[x];
121     }
122     return x;
123 }
124 WeightType Kruskal()
125 {
126     WeightType ret = 0;
127     int EdgeNum = 0;
128     for (int i = 0; i < E; ++i)//排序
129     {
130         for (int j = 1; j < E; ++j)
131         {
132             if (edge[j].w < edge[j - 1].w)
133             {
134                 struct Edge temp = edge[j];
135                 edge[j] = edge[j - 1];
136                 edge[j - 1] = temp;
137             }
138         }
139     }
140     for (int i = 0; i < E; ++i)
141     {
142         NumType ru = FindRoot(edge[i].u);
143         NumType rv = FindRoot(edge[i].v);
144         if (ru != rv)
145         {
146             root[ru] = rv;//合并集合
147             ret += edge[i].w;
148             ++EdgeNum;
149             if (EdgeNum == N - 1) break;//边数为结点数-1，说明生成树构造完成
150         }
151     }
152     if (EdgeNum != N - 1) return -1;//图不连通
153     return ret;
154 }
155 //Dijkstra
156 void Dijkstra(int s)
157 {
158     int pre[N];
159     int dis[N];
160     bool visited[N];
161     for (int i = 0; i < N; ++i) visited[i] = false;
162     visited[s] = true;
163     for (int i = 0; i < N; ++i)
164     {
165         dis[i] = G[s][i];
166         pre[i] = s;
167     }
168     dis[s] = 0;
169     for (int i = 0; i < N; ++i)
170     {
171         int min = INFINITE;
172         int k = 0;
173         for (int j = 0; j < N; ++j)
174         {
175             if (dis[j] < min && visited[j] == false)
176             {
177                 visited[j] = true;
178                 min = dis[j];
179                 k = j;
180             }
181         }
182         for (int v = 0; v < N; ++v)
183         {
184             if (dis[k] + G[k][v] < dis[v])
185             {
186                 dis[v] = dis[k] + G[k][v];
187                 pre[v] = k;
188             }
189         }
190     }
191     for (int i = 0; i < N; ++i)
192     {
193         if (i == s)continue;
194         cout << s << "到" << i << "的最短路径长度：" << dis[i] << " ";
195         cout << "路径：";
196         int out[N];
197         int rOut = -1;
198         int e = i;
199         while (e != s)
200         {
201             out[++rOut] = e;
202             e = pre[e];
203         }
204         out[++rOut] = s;
205         bool outFirst = true;
206         while (rOut != -1)
207         {
208             if (!outFirst)
209                 cout << "->";
210             cout << out[rOut--];
211             outFirst = false;
212         }
213         cout << endl;
214     }
215 }
216 //Floyd
217 int Dis[N][N];
218 int path[N][N];//保存路径
219 void Floyd()
220 {
221     for (int i = 0; i < N; ++i)
222         for (int j = 0; j < N; ++j)
223         {
224             Dis[i][j] = G[i][j];
225             path[i][j] = j;
226         }
227 
228     for (int i = 0; i < N; ++i)
229         Dis[i][i] = 0;
230     for (int k = 0; k < N; ++k)
231         for (int i = 0; i < N; ++i)
232             for (int j = 0; j < N; ++j)
233             {
234                 if (Dis[i][k] != INFINITE && Dis[k][j] != INFINITE && Dis[i][k] + Dis[k][j] < Dis[i][j])
235                 {
236                     Dis[i][j] = Dis[i][k] + Dis[k][j];
237                     path[i][j] = path[i][k];
238                 }
239             }
240 }
241 void print(int s, int e)
242 {
243     int t = path[s][e];
244     cout << "->" << t;
245     if (t == e) return;
246     print(t, e);
247 }
248 void Print(int s, int e)
249 {
250     cout << s;
251     print(s, e);
252 }
253 
254 int main()
255 {
256     for (int i = 0; i < MAX; ++i)
257         for (int j = 0; j < MAX; ++j)
258             G[i][j] = (i==j ? 0 : INFINITE);
259     int order;
260     for (int i = 0; i < MAX; ++i)
261         VISITED[i] = false;
262     for (int i = 0; i < MAX; ++i)
263         inQueue[i] = false;
264     for (int i = 0; i < N; ++i)
265         root[i] = i;
266     //构造图
267     set(0, 1, 1); set(0, 14, 1); set(1, 2, 10); set(2, 14, 1); set(14, 13, 1); set(13, 12, 10);
268     set(2, 3, 10); set(12, 16, 1); set(3, 4, 1); set(11, 4, 1); set(16, 10, 1); set(15, 10, 1);
269     set(10, 9, 20); set(11, 9, 1); set(15, 7, 1); set(5, 7, 1); set(5, 6, 10); set(6, 9, 1);
270     set(4, 8, 1); set(2, 7, 1); set(4, 5, 1);
271     cout << "选择功能" << endl
272         << "1.使用DFS遍历输出图" << endl
273         << "2.使用BFS遍历输出图" << endl
274         << "3.求最小生成树（Prim算法）" << endl
275         << "4.求最小生成树（Kruskal算法）" << endl
276         << "5.求点s到其余点的最短路径（Dijkstra算法）" << endl
277         << "6.求各点间的最短路径（Floyd算法）" << endl;
278     
279     while (cin >> order)
280     {
281         if (order == 1)//dfs
282         {
283             cout << "输入起点：";
284             int s;
285             cin >> s;
286             DFS(s);
287         }
288         if (order == 2)//bfs
289         {
290             cout << "输入起点：";
291             int s;
292             cin >> s;
293             BFS(s);
294         }
295         if (order == 3)
296         {
297             cout << "最小生成树边权和(Prim)："<<Prim();
298         }
299         if (order == 4)
300         {
301             cout << "最小生成树边权和(Kruskal)：" << Kruskal();
302         }
303         if (order == 5)
304         {
305             cout << "输入点s编号：";
306             int s;
307             cin >> s;
308             Dijkstra(s);
309         }
310         if (order == 6)
311         {
312             Floyd();
313             for (int i = 0; i < N; ++i)
314             {
315                 for (int j = 0; j < N; ++j)
316                 {
317                     cout << i << "到" << j << "最短路径长度：" << Dis[i][j] << endl;
318                     cout << "路径为：";
319                     Print(i, j);
320                     cout << endl;
321                 }
322                 cout << endl;
323             }
324         }
325         cout << endl << "已完成,请输入：";
326     }
327 
328         
329     return 0;
330

  1 #include <iostream>
  2 using namespace std;
  3 const int INFINITE = 65535;
  4 const int MAX = 20;
  5 typedef int WeightType;
  6 typedef int NumType;//结点编号类型
  7 const int N = 17;
  8 int E = 0;//边数
  9 WeightType G[MAX][MAX];
 10 struct Edge
 11 {
 12     NumType u, v;
 13     WeightType w;
 14 };
 15 struct Edge* edge = new struct Edge[N * N];
 16 int rEdge = -1;
 17 void set(int i, int j, WeightType w)
 18 {
 19     if (G[i][j] == INFINITE)
 20     {
 21         ++E;
 22         edge[++rEdge].u = i;
 23         edge[rEdge].v = j;
 24         edge[rEdge].w = w;
 25     }
 26     G[i][j] = G[j][i] = w;
 27 }
 28 struct Queue
 29 {
 30     int s[MAX];
 31     int r = -1, f = -1;
 32 };
 33 Queue q;
 34 bool inQueue[MAX];
 35 bool VISITED[MAX];
 36 
 37 void DFS(int i)
 38 {
 39     VISITED[i] = true;
 40     for (int j = 0; j < N; ++j)
 41     {
 42         if (VISITED[j] == false && G[i][j] != INFINITE)
 43         {
 44             cout << "(" << i << "->" << j << ")";
 45             DFS(j);
 46         }
 47     }
 48 }
 49 void BFS(int i)
 50 {
 51     q.s[++q.f] = i;
 52     inQueue[i] = true;
 53     int cnt = 0;
 54     while (q.r < q.f)
 55     {
 56         int n = q.s[++q.r];
 57         if (cnt != 0)cout << "->";
 58         ++cnt;
 59         cout << n;
 60         for (int j = 0; j < N; ++j)
 61         {
 62             if (inQueue[j] == false && G[n][j] != INFINITE)
 63             {
 64                 q.s[++q.f] = j;
 65                 inQueue[j] = true;
 66             }
 67         }
 68     }
 69 }
 70 //Prim
 71 int dis[N];
 72 WeightType Prim()//返回最小边权和
 73 {
 74     WeightType ret = 0;//最小和
 75     WeightType dis[MAX];//各点到最小生成树的距离
 76     fill(dis, dis + MAX, INFINITE);//初始化为INFINITE
 77     dis[0] = 0;//从0开始
 78     for (int i = 1; i < N; ++i)//把与0相接的点距离0点的距离放入dis
 79     {
 80         if (G[0][i] != INFINITE)
 81             dis[i] = G[0][i];
 82     }
 83 
 84     for (int i = 0; i < N - 1; ++i)//循环MAX次
 85     {
 86         WeightType min = INFINITE;
 87         int k = -1;//存储最小dis的下标
 88         for (int j = 0; j < MAX; ++j)//找出最小dis
 89         {
 90             if (dis[j] != 0 && dis[j] < min)
 91             {
 92                 min = dis[j];
 93                 k = j;
 94             }
 95         }
 96         if (k == -1) return -1;//不连通
 97         ret += min;//更新边权和
 98         dis[k] = 0;//k纳入最小生成树
 99         WeightType temp[MAX];//存储k与相接点的权
100         fill(temp, temp + MAX, INFINITE);
101         for (int i = 0; i < N; ++i)
102         {
103             if (temp[i] = G[k][i]);
104         }
105         for (int i = 0; i < MAX; ++i)//如果未访问点dis值由于k的纳入变得更小，则更新
106         {
107             if (dis[i] != 0 && temp[i] != INFINITE && temp[i] < dis[i])
108                 dis[i] = temp[i];
109         }
110     }
111     return ret;
112 }
113 //Kruskal
114 NumType root[MAX];
115 NumType FindRoot(NumType x)
116 {
117     NumType t = x;
118     while (root[x] != x)
119     {
120         x = root[x];
121     }
122     return x;
123 }
124 WeightType Kruskal()
125 {
126     WeightType ret = 0;
127     int EdgeNum = 0;
128     for (int i = 0; i < E; ++i)//排序
129     {
130         for (int j = 1; j < E; ++j)
131         {
132             if (edge[j].w < edge[j - 1].w)
133             {
134                 struct Edge temp = edge[j];
135                 edge[j] = edge[j - 1];
136                 edge[j - 1] = temp;
137             }
138         }
139     }
140     for (int i = 0; i < E; ++i)
141     {
142         NumType ru = FindRoot(edge[i].u);
143         NumType rv = FindRoot(edge[i].v);
144         if (ru != rv)
145         {
146             root[ru] = rv;//合并集合
147             ret += edge[i].w;
148             ++EdgeNum;
149             if (EdgeNum == N - 1) break;//边数为结点数-1，说明生成树构造完成
150         }
151     }
152     if (EdgeNum != N - 1) return -1;//图不连通
153     return ret;
154 }
155 //Dijkstra
156 void Dijkstra(int s)
157 {
158     int pre[N];
159     int dis[N];
160     bool visited[N];
161     for (int i = 0; i < N; ++i) visited[i] = false;
162     visited[s] = true;
163     for (int i = 0; i < N; ++i)
164     {
165         dis[i] = G[s][i];
166         pre[i] = s;
167     }
168     dis[s] = 0;
169     while (1)
170     {
171         int min = INFINITE;
172         int k = 0;
173         for (int j = 0; j < N; ++j)
174         {
175             if (dis[j] < min && visited[j] == false)
176             {
177                 min = dis[j];
178                 k = j;
179             }
180         }
181         visited[k] = true;
182         if (min == INFINITE)break;
183         for (int v = 0; v < N; ++v)
184         {
185             if (dis[k] + G[k][v] < dis[v] && visited[v] == false )
186             {
187                 dis[v] = dis[k] + G[k][v];
188                 pre[v] = k;
189             }
190         }
191     }
192     for (int i = 0; i < N; ++i)
193     {
194         if (i == s)continue;
195         cout << s << "到" << i << "的最短路径长度：" << dis[i] << " ";
196         cout << "路径：";
197         int out[N];
198         int rOut = -1;
199         int e = i;
200         while (e != s)
201         {
202             out[++rOut] = e;
203             e = pre[e];
204         }
205         out[++rOut] = s;
206         bool outFirst = true;
207         while (rOut != -1)
208         {
209             if (!outFirst)
210                 cout << "->";
211             cout << out[rOut--];
212             outFirst = false;
213         }
214         cout << endl;
215     }
216 }
217 //Floyd
218 int Dis[N][N];
219 int path[N][N];//保存路径
220 void Floyd()
221 {
222     for (int i = 0; i < N; ++i)
223         for (int j = 0; j < N; ++j)
224         {
225             Dis[i][j] = G[i][j];
226             path[i][j] = j;
227         }
228 
229     for (int i = 0; i < N; ++i)
230         Dis[i][i] = 0;
231     for (int k = 0; k < N; ++k)
232         for (int i = 0; i < N; ++i)
233             for (int j = 0; j < N; ++j)
234             {
235                 if (Dis[i][k] != INFINITE && Dis[k][j] != INFINITE && Dis[i][k] + Dis[k][j] < Dis[i][j])
236                 {
237                     Dis[i][j] = Dis[i][k] + Dis[k][j];
238                     path[i][j] = path[i][k];
239                 }
240             }
241 }
242 void print(int s, int e)
243 {
244     int t = path[s][e];
245     cout << "->" << t;
246     if (t == e) return;
247     print(t, e);
248 }
249 void Print(int s, int e)
250 {
251     cout << s;
252     print(s, e);
253 }
254 
255 int main()
256 {
257     for (int i = 0; i < MAX; ++i)
258         for (int j = 0; j < MAX; ++j)
259             G[i][j] = (i == j ? 0 : INFINITE);
260     int order;
261     //构造图
262     set(0, 1, 1); set(0, 14, 1); set(1, 2, 10); set(2, 14, 1); set(14, 13, 1); set(13, 12, 10);
263     set(2, 3, 10); set(12, 16, 1); set(3, 4, 1); set(11, 4, 1); set(16, 10, 1); set(15, 10, 1);
264     set(10, 9, 20); set(11, 9, 1); set(15, 7, 1); set(5, 7, 1); set(5, 6, 10); set(6, 9, 1);
265     set(4, 8, 1); set(2, 7, 1); set(4, 5, 1);
266     cout << "选择功能" << endl
267         << "1.使用DFS遍历输出图" << endl
268         << "2.使用BFS遍历输出图" << endl
269         << "3.求最小生成树（Prim算法）" << endl
270         << "4.求最小生成树（Kruskal算法）" << endl
271         << "5.求点s到其余点的最短路径（Dijkstra算法）" << endl
272         << "6.求各点间的最短路径（Floyd算法）" << endl;
273 
274     while (cin >> order)
275     {
276         if (order == 1)//dfs
277         {
278             for (int i = 0; i < MAX; ++i)
279                 VISITED[i] = false;
280             cout << "输入起点：";
281             int s;
282             cin >> s;
283             DFS(s);
284         }
285         if (order == 2)//bfs
286         {
287             for (int i = 0; i < MAX; ++i)
288                 inQueue[i] = false;
289             q.f = q.r = -1;
290             cout << "输入起点：";
291             int s;
292             cin >> s;
293             BFS(s);
294         }
295         if (order == 3)
296         {
297             cout << "最小生成树边权和(Prim)：" << Prim();
298         }
299         if (order == 4)
300         {
301             for (int i = 0; i < N; ++i)
302                 root[i] = i;
303             cout << "最小生成树边权和(Kruskal)：" << Kruskal();
304         }
305         if (order == 5)
306         {
307             cout << "输入点s编号：";
308             int s;
309             cin >> s;
310             Dijkstra(s);
311         }
312         if (order == 6)
313         {
314             Floyd();
315             for (int i = 0; i < N; ++i)
316             {
317                 for (int j = 0; j < N; ++j)
318                 {
319                     cout << i << "到" << j << "最短路径长度：" << Dis[i][j] << endl;
320                     cout << "路径为：";
321                     Print(i, j);
322                     cout << endl;
323                 }
324                 cout << endl;
325             }
326         }
327         cout << endl << "已完成,请输入：";
328     }
329 
330 
331     return 0;
332 }

View Code

实验八：

多线程

哲学家就餐

啊啊啊啊

问题：

  1 #include <stdio.h>
  2 #include <pthread.h>
  3 #include <semaphore.h>
  4 #define N 5//number of philosofer
  5 #define LEFT i
  6 #define RIGHT (i+1)%N
  7 sem_t chopstick[N];
  8 sem_t four;
  9 sem_t one;
 10 pthread_t thread[N];
 11 int philosopher[N];//their number
 12 int func_num = 0;
 13 void thinking(int i)
 14 {
 15     printf("philosopher %d is thingking(func%d)\n", i + 1, func_num);
 16     sleep(1);
 17 }
 18 void eating(int i)
 19 {
 20     printf("philosopher %d is eating(func%d)\n", i + 1, func_num);
 21     sleep(1);
 22 }
 23 void* func1(void* param)//初始方法
 24 {
 25     int i = *((int*)param);
 26     while (1)
 27     {
 28         thinking(i);
 29         sem_wait(&chopstick[LEFT]);
 30         sem_wait(&chopstick[RIGHT]);
 31         eating(i);
 32         sem_post(&chopstick[LEFT]);
 33         sem_post(&chopstick[RIGHT]);
 34         thinking(1);
 35     }
 36     pthread_exit(NULL);
 37 }
 38 void* func2(void* param)//不对称的方法
 39 {
 40     int i = *((int*)param);
 41     while (1)
 42     {
 43         thinking(i);
 44         if (i % 2 == 0)
 45         {
 46             sem_wait(&chopstick[LEFT]);
 47             sem_wait(&chopstick[RIGHT]);
 48             eating(i);
 49             sem_post(&chopstick[RIGHT]);
 50             sem_post(&chopstick[LEFT]);
 51         }
 52         else
 53         {
 54             sem_wait(&chopstick[RIGHT]);
 55             sem_wait(&chopstick[LEFT]);
 56             eating(i);
 57             sem_post(&chopstick[LEFT]);
 58             sem_post(&chopstick[RIGHT]);
 59         }
 60         thinking(i);
 61     }
 62     pthread_exit(NULL);
 63 }
 64 void* func3(void* param)//最多4个哲学家同时就餐
 65 {
 66     int i = *((int*)param);
 67     while (1)
 68     {
 69         thinking(i);
 70         sem_wait(&four);
 71         sem_wait(&chopstick[LEFT]);
 72         sem_wait(&chopstick[RIGHT]);
 73         eating(i);
 74         sem_post(&chopstick[RIGHT]);
 75         sem_post(&chopstick[LEFT]);
 76         sem_post(&four);
 77         thinking(i);
 78     }
 79     pthread_exit(NULL);
 80 }
 81 void* func4(void* param)//只有当左右筷子都可用时才拿起筷子
 82 {
 83     int i = *((int*)param);
 84     while (1)
 85     {
 86         thinking(i);
 87         sem_wait(&one);
 88         sem_wait(&chopstick[LEFT]);
 89         sem_wait(&chopstick[RIGHT]);
 90         sem_post(&one);
 91         eating(i);
 92         sem_post(&chopstick[RIGHT]);
 93         sem_post(&chopstick[LEFT]);
 94         thinking(i);
 95     }
 96     pthread_exit(NULL);
 97 }
 98 void thread_create()
 99 {
100     int t;
101     for (int i = 0; i < N; ++i)
102     {
103         //t=pthread_create(&thread[i],NULL,func1,&philosopher[i]); func_num = 1;
104         //t=pthread_create(&thread[i],NULL,func2,&philosopher[i]); func_num = 2;
105             //t=pthread_create(&thread[i],NULL,func3,&philosopher[i]); func_num = 3;
106         t = pthread_create(&thread[i], NULL, func4, &philosopher[i]); func_num = 4;
107         if (t != 0)
108             printf("failed in creating thread%d\n", i);
109     }
110 }
111 thread_wait()
112 {
113     for (int i = 0; i < N; ++i)
114     {
115         pthread_join(thread[i], NULL);
116         printf("thread %d is ended", i);
117     }
118 }
119 int main()
120 {
121     for (int i = 0; i < N; ++i)
122     {
123         sem_init(&chopstick[i], 0, 1);
124         philosopher[i] = i;
125     }
126     sem_init(&four, 0, 4);
127     sem_init(&one, 0, 4);
128     thread_create();
129     thread_wait();
130     return 0;
131 }

View Code

多线程共享资源：多个线程共享变量sum

 1 #include <stdio.h>
 2 #include <pthread.h>
 3 #include<time.h>
 4 #include <semaphore.h>
 5 #define N 10
 6 pthread_t thread[100];
 7 unsigned long int sum=0;
 8 
 9 void count(void *param)
10 {    
11     int i = *((int*)param);
12     while(1)
13     {
14     if(sum == 1024)break;        
15     sum += 1;
16     printf("thread%d: sum = %d\n", i,sum);
17     }
18 }
19 void thread_create()
20 {
21     int t;
22     for(int i=0; i<N; ++i)
23     {
24           t=pthread_create(&thread[i],NULL,count, &i);
25         if(t != 0)
26         {
27               printf("failed in creating thread%d\n",i);
28         }
29     }
30 }
31 thread_wait()
32 {
33     for(int i=0; i<N; ++i)
34     {
35         pthread_join(thread[i],NULL);
36         printf("thread %d is ended\n", i);
37     }
38 }
39 int main()
40 {
41    thread_create();
42    thread_wait();
43     return 0;
44 }

View Code

实验九：　　

1、设计并实现操作系统读者写者问题读者优先算法。

只要有一个读者在读，其他读者就无需等待

为什么？因为如果有读者了，说明在读写者的竞争中，读者得到了资源，后面来的读者就可以直接读了

2、设计并实现操作系统读者写者问题写者优先算法。

放一起：

  1 #include <stdio.h>
  2 #include <pthread.h>
  3 #include <semaphore.h>
  4 #define N_reader 3
  5 #define N_writer 3
  6 pthread_t reader_thread[3], writer_thread[3];
  7 struct student
  8 {
  9     char name[10];
 10     int id;
 11 };
 12 struct student idr[N_reader], idw[N_writer];
 13 int read_count = 0;
 14 int write_count = 0;
 15 sem_t  mutex;
 16 sem_t rcnt_mutex;
 17 sem_t wcnt_mutex;
 18 sem_t rw_mutex;//读者-写者、写者-写者之间的互斥，
 19 sem_t r_mutex;
 20 sem_t w_mutex;
 21 sem_t out_mutex;
 22 void reading(int i)
 23 {
 24     printf("reader%d is reading2\n",i);
 25 
 26 }
 27 void writing(int i)
 28 {
 29     printf("writer%d is writng2\n",i);
 30 }
 31 //--------------读者优先-----------------
 32 void* read1(void *param)
 33 {
 34     int i = *((int*)param);
 35     while(1)
 36     {
 37         sem_wait(&mutex);
 38         ++read_count;
 39         if(read_count == 1)
 40             sem_wait(&rw_mutex);
 41         sem_post(&mutex);
 42         reading(i);
 43         sem_wait(&mutex);
 44         --read_count;
 45         if(read_count == 0)
 46             sem_post(&rw_mutex);
 47         sem_post(&mutex);
 48 sleep(1);
 49     }
 50     pthread_exit(NULL);
 51 }
 52 void* write1(void *param)
 53 {
 54     int i = *((int*)param);
 55     while(1)
 56     {
 57         sem_wait(&rw_mutex);
 58         writing(i);
 59         sem_post(&rw_mutex);
 60     sleep(1);
 61     }
 62     pthread_exit(NULL);
 63 }
 64 //--------------写者优先-----------------
 65 void read2(void *param)
 66 {
 67     int i = *((int*)param);
 68     while(1)
 69     {
 70     sem_wait(&out_mutex);
 71         sem_wait(&r_mutex);//只有在写完成后才能获得r_mutex
 72 
 73         sem_wait(&rcnt_mutex);
 74             ++read_count;
 75         if(read_count == 1)
 76             sem_wait(&w_mutex);//如果是第一个读者，上w_mutex，防止读的时候写入，可以多个读者同时读
 77         sem_post(&rcnt_mutex);
 78         sem_post(&r_mutex);
 79     sem_post(&out_mutex);
 80 
 81         reading(i);
 82 
 83         sem_wait(&rcnt_mutex);
 84             --read_count;
 85         if(read_count == 0)
 86             sem_post(&w_mutex);//读完之后，释放w_mutex
 87         sem_post(&rcnt_mutex);
 88 
 89 
 90         sleep(1);
 91     }
 92     pthread_exit(NULL);
 93 }
 94 void write2(void *param)
 95 {
 96     int i = *((int*)param);
 97     while(1)
 98     {
 99         sem_wait(&wcnt_mutex);
100             ++write_count;
101         if(write_count == 1)
102             sem_wait(&r_mutex);//上r_mutex，防止读者进入队列
103         sem_post(&wcnt_mutex);
104 
105         sem_wait(&w_mutex);//与其他写操作互斥
106         writing(i);
107         sem_post(&w_mutex);
108 
109         sem_wait(&wcnt_mutex);
110             --write_count;
111         if(write_count == 0)
112             sem_post(&r_mutex);//只有当所有写者完成操作，才释放r_mutex
113         sem_post(&wcnt_mutex);
114         
115         sleep(1);
116     }
117     pthread_exit(NULL);
118 }
119 void thread_create()
120 {
121     int t;
122     for(int i=0; i<N_writer; ++i)
123     {
124         t=pthread_create(&writer_thread[i],NULL,write2,&idw[i].id);
125         if(t != 0)
126         {
127         printf("failed in creating thread%d\n",i);
128         }
129     }
130     for(int i=0; i<N_reader; ++i)
131     {
132         t=pthread_create(&reader_thread[i],NULL,read2,&idr[i].id);
133         if(t != 0)
134         {
135         printf("failed in creating thread%d\n",i);
136         }
137     }
138 }
139 thread_wait()
140 {
141     for(int i=0; i<N_reader; ++i)
142     {
143         pthread_join(reader_thread[i],NULL);
144         printf("reader_thread %d is ended\n", i);
145     }
146     for(int i=0; i<N_writer; ++i)
147     {
148         pthread_join(writer_thread[i],NULL);
149         printf("writer_thread %d is ended\n", i);
150     }
151 }
152 int main()
153 {
154     sem_init(&mutex,0,1);
155     sem_init(&rw_mutex,0,1);
156     sem_init(&r_mutex,0,1);
157     sem_init(&w_mutex,0,1);
158     sem_init(&rcnt_mutex,0,1);
159     sem_init(&wcnt_mutex,0,1);
160     sem_init(&out_mutex,0,1);
161     for(int i=0; i<N_reader+N_writer; ++i)
162     {
163            idr[i].id = i+1;
164         idw[i].id = i+1;
165     }
166     thread_create();
167     thread_wait();
168     return 0;
169 }

View Code

末尾有“2”的为写者优先的程序运行结果

啊啊啊啊

实验十：

 1 #include <stdio.h>
 2 #include <pthread.h>
 3 #include <unistd.h>
 4 #include <semaphore.h>
 5 #define N 10
 6 pthread_t thread[N];
 7 bool choosing[N];
 8 int number[N];
 9 
10 void process(int i) {
11     while (1) {
12         // 当前进程i正在取号
13         choosing[i] = true;
14         // number为上一个已发放的排队号加1
15         int max = 0;
16         for (int k = 0; k < i - 1; ++k)
17         {
18             if (number[k] > max)
19                 max = number[k];
20         }
21         number[i] = 1 + max;
22         // 当前进程i取号完毕
23         choosing[i] = false;
24         // 迭代所有进程
25         for (j = 0; j < N;  ++j)
26         {
27             // 若当前迭代到的进程j正在取号，则等待其取号完毕
28             while (choosing[j]);
29             // 同时满足，当前进程才能通过
30             while (number[j] != 0 && ((number[j] < number[i]) || ((number[j] == number[i]) && j < i)));
31         }
32         // 临界区代码
33         printf("thread %d, number[i] = %d\n", i, number[i]);
34         // 当前进程注销排队号
35         // 一旦线程在临界区执行完毕，需要把自己的排队签到号码置为0，表示处于非临界区
36         number[i] = 0;
37 
38         // 其它代码
39     }
40 }
41 
42 void thread_create() { //进程创建
43     int t;
44     for (int i = 0; i < N; ++i) {
45         tmp = pthread_create(&thread[i], NULL, process, &i);
46         if (tmp != 0) {
47             printf("线程%d创建失败\n", i);
48         }
49     }
50 }
51 void thread_wait() {
52     for (int i = 0; i < N; ++i) {
53         pthread_join(thread[i], NULL);
54         printf("线程%d结束\n", i);
55     }
56 }
57 int main()
58 {
59     number[0] = 1;
60     thread_create();
61     thread_wait();
62     for(int )
63     return 0;
64 }

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <unistd.h>
  4 #include <sys/types.h>
  5 #include <pthread.h>
  6 #include <assert.h>
  7 /*
  8 *线程池里所有运行和等待的任务都是一个CThread_worker（即struct worker）
  9 *由于所有任务都在链表里，所以是一个链表结构
 10 */
 11 typedef struct worker
 12 {
 13     /*回调函数，任务运行时会调用此函数，注意也可声明成其它形式*/
 14     void *(*process) (void *arg);
 15     void *arg;/*回调函数的参数*/
 16     struct worker *next;
 17 } CThread_worker;
 18 
 19 /*线程池结构*/
 20 typedef struct
 21 {
 22     pthread_mutex_t queue_lock;//互斥锁
 23     pthread_cond_t queue_ready;//触发条件
 24     /*链表结构，线程池中所有等待任务*/
 25     CThread_worker *queue_head;
 26     /*是否销毁线程池*/
 27     int shutdown;
 28     pthread_t *threadid;
 29     /*线程池中允许的活动线程数目*/
 30     int max_thread_num;
 31     /*当前等待队列的任务数目*/
 32     int cur_queue_size;
 33 } CThread_pool;
 34 
 35 int pool_add_worker (void *(*process) (void *arg), void *arg);
 36 void *thread_routine (void *arg);//线程要执行的函数
 37 
 38 static CThread_pool *pool = NULL;
 39 void pool_init (int max_thread_num)//初始化线程池
 40 {
 41     pool = (CThread_pool *) malloc (sizeof (CThread_pool));
 42     pthread_mutex_init (&(pool->queue_lock), NULL);//被初始化为未锁住状态
 43     pthread_cond_init (&(pool->queue_ready), NULL);
 44     pool->queue_head = NULL;
 45     pool->max_thread_num = max_thread_num;
 46     pool->cur_queue_size = 0;
 47     pool->shutdown = 0;
 48     pool->threadid =
 49         (pthread_t *) malloc (max_thread_num * sizeof (pthread_t));
 50     int i = 0;
 51     for (i = 0; i < max_thread_num; i++)
 52     { 
 53         pthread_create (&(pool->threadid[i]), NULL, thread_routine,
 54                 NULL);//创建线程
 55     }
 56 }
 57 /*向线程池中加入任务，然后唤醒一个等待中的线程（如果有的话）*/
 58 int pool_add_worker (void *(*process) (void *arg), void *arg)
 59 {
 60     /*构造一个新任务*/
 61     CThread_worker *newworker = (CThread_worker *) malloc (sizeof (CThread_worker));
 62     newworker->process = process;//要执行的函数
 63     newworker->arg = arg;//函数参数
 64     newworker->next = NULL;/*别忘置空*/
 65     pthread_mutex_lock (&(pool->queue_lock));//将任务加到队列前，要上互斥锁
 66     /*将任务加入到等待队列中*/
 67     CThread_worker *member = pool->queue_head;//member指向任务队列的头
 68     if (member != NULL)//尾插法插入newworker
 69     {
 70         while (member->next != NULL)
 71             member = member->next;
 72         member->next = newworker;
 73     }
 74     else//队列为空
 75     {
 76         pool->queue_head = newworker;//直接插入newworker
 77     }
 78     assert (pool->queue_head != NULL);//表达式pool->queue_head != NULL必须为true
 79     pool->cur_queue_size++;//当前队列数加一
 80     pthread_mutex_unlock (&(pool->queue_lock));//完成添加队列的操作，解互斥锁
 81     /*好了，等待队列中有任务了，唤醒一个等待线程；
 82     注意如果所有线程都在忙碌，这句没有任何作用*/
 83     pthread_cond_signal (&(pool->queue_ready));//触发线程，使其脱离阻塞状态
 84     return 0;
 85 }
 86 
 87 /*销毁线程池，等待队列中的任务不会再被执行，但是正在运行的线程会一直
 88 把任务运行完后再退出*/
 89 int pool_destroy ()
 90 {
 91     if (pool->shutdown)
 92         return -1;/*防止两次调用*/
 93     pool->shutdown = 1;
 94     /*唤醒所有等待线程，线程池要销毁了*/
 95     pthread_cond_broadcast (&(pool->queue_ready));
 96     /*阻塞等待线程退出，否则就成僵尸了*/
 97     int i;
 98     for (i = 0; i < pool->max_thread_num; i++)
 99         pthread_join (pool->threadid[i], NULL);
100     free (pool->threadid);
101     /*销毁等待队列*/
102     CThread_worker *head = NULL;
103     while (pool->queue_head != NULL)
104     {
105         head = pool->queue_head;
106         pool->queue_head = pool->queue_head->next;
107         free (head);
108     }
109     /*条件变量和互斥量也别忘了销毁*/
110     pthread_mutex_destroy(&(pool->queue_lock));
111     pthread_cond_destroy(&(pool->queue_ready));
112     
113     free (pool);
114     /*销毁后指针置空是个好习惯*/
115     pool=NULL;
116     return 0;
117 }
118 
119 void * thread_routine (void *arg)//线程中要执行的函数
120 {
121     printf ("starting thread 0x%x\n", pthread_self ());//pthread_self()获得线程自身id
122     while (1)
123     {
124         pthread_mutex_lock (&(pool->queue_lock));
125         /*如果等待队列为0并且不销毁线程池，则处于阻塞状态; 注意
126         pthread_cond_wait是一个原子操作，等待前会解锁，唤醒后会加锁*/
127         while (pool->cur_queue_size == 0 && !pool->shutdown)
128         {
129             printf ("thread 0x%x is waiting\n", pthread_self ());
130             pthread_cond_wait (&(pool->queue_ready), &(pool->queue_lock));
131         }
132         /*线程池要销毁了*/
133         if (pool->shutdown)
134         {
135             /*遇到break,continue,return等跳转语句，千万不要忘记先解锁*/
136             pthread_mutex_unlock (&(pool->queue_lock));
137             printf ("thread 0x%x will exit\n", pthread_self ());
138             pthread_exit (NULL);
139         }
140         printf ("thread 0x%x is starting to work\n", pthread_self ());//线程处理中
141         /*assert是调试的好帮手*/
142         assert (pool->cur_queue_size != 0);
143         assert (pool->queue_head != NULL);
144         
145         /*等待队列长度减去1，并取出链表中的头元素*/
146         pool->cur_queue_size--;
147         CThread_worker *worker = pool->queue_head;
148         pool->queue_head = worker->next;
149         pthread_mutex_unlock (&(pool->queue_lock));
150         /*调用回调函数，执行任务*/
151         (*(worker->process)) (worker->arg);
152         free (worker);
153         worker = NULL;
154     }
155     /*这一句应该是不可达的*/
156     pthread_exit (NULL);
157 }
158 void *
159 myprocess (void *arg)//回调函数
160 {
161     printf ("threadid is 0x%x, working on task %d\n", pthread_self (),*(int *) arg);
162     sleep (1);/*休息一秒，延长任务的执行时间*/
163     return NULL;
164 }
165 int main (int argc, char **argv)
166 {
167     pool_init (3);/*线程池中最多三个活动线程*/
168     /*连续向池中投入10个任务*/
169     int *workingnum = (int *) malloc (sizeof (int) * 50);
170     int i;
171     for (i = 0; i < 50; ++i)
172     {
173         workingnum[i] = i;
174         pool_add_worker (myprocess, &workingnum[i]);
175     }
176     /*等待所有任务完成*/
177     sleep (5);
178     /*销毁线程池*/
179     pool_destroy ();
180     free (workingnum);
181     return 0;
182 }

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <unistd.h>
  4 #include <sys/types.h>
  5 #include <pthread.h>
  6 #include <assert.h>
  7 #define bool int
  8 #define true 1
  9 #define false 0
 10 typedef struct worker//任务结构体
 11 {
 12     /*回调函数，任务运行时会调用此函数，注意也可声明成其它形式*/
 13     void* (*process) (void* arg);
 14     void* arg;/*回调函数的参数*/
 15     struct worker* next;
 16 } CThread_worker;
 17 typedef struct PCB
 18  {
 19     pthread_t thread;
 20     int thread_id;//线程名字
 21     int arriveTime;//到达时间
 22     int runTime;//估计运行时间
 23     char status;//进程状态
 24         struct PCB* next;//链接指针
 25 }PCB;
 26 typedef struct
 27 {
 28     pthread_mutex_t queue_lock;//互斥锁
 29     pthread_cond_t queue_ready;//触发条件
 30     /*链表结构，线程池中所有等待任务*/
 31     CThread_worker* queue_head;
 32     /*是否销毁线程池*/
 33     int shutdown;
 34     PCB* pcbPointer;
 35     /*线程池中允许的活动线程数目*/
 36     int max_thread_num;
 37     /*当前等待队列的任务数目*/
 38     int cur_queue_size;
 39 }CThread_pool;
 40 
 41 struct CycleQueue {
 42     PCB* preThread;//当前进程的前一个进程
 43     PCB* present;//当前进程
 44 };
 45 
 46 int pool_add_worker(void* (*process) (void* arg), void* arg);
 47 void* thread_routine(void* arg);//线程要执行的函数
 48 static CThread_pool* pool = NULL;
 49 
 50 void pool_init(int max_thread_num)//初始化线程池
 51 {
 52     pool = (CThread_pool*)malloc(sizeof(CThread_pool));
 53     pthread_mutex_init(&(pool->queue_lock), NULL);//被初始化为未锁住状态
 54     pthread_cond_init(&(pool->queue_ready), NULL);
 55     pool->queue_head = NULL;
 56 pool->pcbPointer = NULL;
 57     pool->max_thread_num = max_thread_num;//3个
 58     pool->cur_queue_size = 0;
 59     pool->shutdown = 0;
 60     struct PCB *ptemp = NULL;
 61 srand(time(0));//随机种子，用于产生随机到达时间，估计运行时间
 62     for(int i=0; i<max_thread_num; ++i)
 63     {
 64         struct PCB* s = (PCB*)malloc(sizeof(PCB));
 65         s->thread_id = i+1;
 66         s->arriveTime = rand() % 5;
 67         s->runTime = rand()%5 + 1;
 68         s->status = 'N';//进程状态
 69         if(NULL == pool->pcbPointer)
 70             pool->pcbPointer = s;
 71         else
 72         {
 73 ptemp = pool->pcbPointer;
 74             while(ptemp->next)
 75             {
 76                 ptemp = ptemp->next;
 77             }
 78             ptemp->next = s;
 79         }
 80         printf("PCB%d, arrive:%d, run:%d, status:%c\n",s->thread_id, s->arriveTime, s->runTime, s->status);
 81     }
 82     int i = 0;
 83     for (ptemp = pool->pcbPointer; ptemp != NULL; ptemp = ptemp->next)
 84     {
 85         pthread_create(&(ptemp->thread), NULL, thread_routine, NULL);//创建了3个线程，执行routine函数
 86 printf("thread created\n");
 87     }
 88 }
 89 int pool_add_worker(void* (*process) (void* arg), void* arg)
 90 {
 91     /*构造一个新任务*/
 92     CThread_worker* newworker = (CThread_worker*)malloc(sizeof(CThread_worker));
 93     newworker->process = process;//myprocess函数
 94     newworker->arg = arg;//函数参数，为 &50
 95     newworker->next = NULL;/*别忘置空*/
 96     pthread_mutex_lock(&(pool->queue_lock));//将任务加到队列前，要上互斥锁
 97     /*将任务加入到等待队列中*/
 98     CThread_worker* member = pool->queue_head;//member指向任务队列的头
 99     if (member != NULL)//尾插法插入newworker
100     {
101         while (member->next != NULL)
102             member = member->next;
103         member->next = newworker;
104     }
105     else//队列为空
106     {
107         pool->queue_head = newworker;//直接插入newworker
108     }
109     assert(pool->queue_head != NULL);//表达式pool->queue_head != NULL必须为true
110     pool->cur_queue_size++;//当前队列数加一
111     pthread_mutex_unlock(&(pool->queue_lock));//完成添加队列的操作，解互斥锁
112     /*好了，等待队列中有任务了，唤醒一个等待线程；
113     注意如果所有线程都在忙碌，这句没有任何作用*/
114     pthread_cond_signal(&(pool->queue_ready));//触发线程，使其脱离阻塞状态
115     return 0;
116 }
117 int pool_destroy()
118 {
119     if (pool->shutdown)
120         return -1;/*防止两次调用*/
121     pool->shutdown = 1;
122     /*唤醒所有等待线程，线程池要销毁了*/
123     pthread_cond_broadcast(&(pool->queue_ready));
124     /*阻塞等待线程退出，否则就成僵尸了*/
125     int i;
126    // for (i = 0; i < pool->max_thread_num; i++)
127    //    pthread_join(pool->threadid[i], NULL);
128 
129 for(struct PCB* ptemp = pool->pcbPointer; ptemp != NULL; ptemp = ptemp->next)
130 {
131     pthread_join(ptemp->thread, NULL);    
132 }
133 
134    // free(pool->pcbPointer);
135     /*销毁等待队列*/
136     CThread_worker* head = NULL;
137     while (pool->queue_head != NULL)
138     {
139         head = pool->queue_head;
140         pool->queue_head = pool->queue_head->next;
141         free(head);
142     }
143     /*条件变量和互斥量也别忘了销毁*/
144     pthread_mutex_destroy(&(pool->queue_lock));
145     pthread_cond_destroy(&(pool->queue_ready));
146 
147     free(pool);
148     /*销毁后指针置空是个好习惯*/
149     pool = NULL;
150     return 0;
151 }
152 void* thread_routine(void* arg)//线程中要执行的函数
153 {
154     printf("starting thread 0x%x\n", pthread_self());//pthread_self()获得线程自身id
155     while (1)
156     {
157         pthread_mutex_lock(&(pool->queue_lock));
158         /*如果等待队列为0并且不销毁线程池，则处于阻塞状态; 注意
159         pthread_cond_wait是一个原子操作，等待前会解锁，唤醒后会加锁*/
160         while (pool->cur_queue_size == 0 && !pool->shutdown)
161         {
162             printf("thread 0x%x is waiting\n", pthread_self());
163             pthread_cond_wait(&(pool->queue_ready), &(pool->queue_lock));
164         }
165         /*线程池要销毁了*/
166         if (pool->shutdown)
167         {
168             /*遇到break,continue,return等跳转语句，千万不要忘记先解锁*/
169             pthread_mutex_unlock(&(pool->queue_lock));
170             printf("thread 0x%x will exit\n", pthread_self());
171             pthread_exit(NULL);
172         }
173         printf("thread 0x%x is starting to work\n", pthread_self());//线程处理中
174         /*assert是调试的好帮手*/
175         assert(pool->cur_queue_size != 0);
176         assert(pool->queue_head != NULL);
177 
178         /*等待队列长度减去1，并取出链表中的头元素*/
179         pool->cur_queue_size--;
180         CThread_worker* worker = pool->queue_head;
181         pool->queue_head = worker->next;
182         pthread_mutex_unlock(&(pool->queue_lock));
183         /*调用回调函数，执行任务*/
184         (*(worker->process)) (worker->arg);
185         free(worker);
186         worker = NULL;
187     }
188     /*这一句应该是不可达的*/
189     pthread_exit(NULL);
190 }
191 myprocess(void* arg)
192 {
193     printf("threadid is 0x%x, working on task %d\n", pthread_self(), *(int*)arg);
194     sleep(1);/*休息一秒，延长任务的执行时间*/
195     return NULL;
196 }
197 int main(int argc, char** argv)
198 {
199     pool_init(5);/*线程池中最多三个活动线程*/
200     /*连续向池中投入10个任务*/
201     int* workingnum = (int*)malloc(sizeof(int) * 10);//int数组
202     int i;
203     for (i = 0; i < 10; ++i)
204     {
205       workingnum[i] = i;
206       //pool_add_worker(myprocess, &workingnum[i]);
207     }
208     /*等待所有任务完成*/
209     sleep(5);
210     /*销毁线程池*/
211     pool_destroy();
212     free(workingnum);
213     return 0;
214 }

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <semaphore.h>
  4 #include <unistd.h>
  5 #include <sys/types.h>
  6 #include <pthread.h>
  7 #define bool int
  8 #define true 1
  9 #define false 0
 10 #define thread_maxn 500//9
 11 typedef struct TCB
 12 {
 13     int thread_id;
 14     int arriveTime;
 15     int runTime;
 16     bool thrFinished;
 17     struct TCB* next;
 18 }TCB;
 19 struct tcb_queue
 20 {
 21     struct TCB *thread[thread_maxn];
 22     int r, f;
 23 };
 24 struct tcb_queue Queue;
 25 struct tcb_queue showQueue;
 26 
 27 sem_t sem[thread_maxn];//信号量，用于唤醒线程
 28 TCB* lHead = NULL;//存储线程信息
 29 TCB* nowRun;//目前正在运行的线程
 30 int nFinish = 0;
 31 int nowTime = 0;//目前时间计数
 32 TCB* tcb = NULL;
 33 
 34 void show_tcb()
 35 {
 36     printf("(show)目前队列的情况为：");
 37     while (Queue.r != Queue.f)
 38     {
 39         showQueue.f = (showQueue.f+1)%thread_maxn;
 40         Queue.r = (Queue.r + 1) % thread_maxn;
 41         showQueue.thread[showQueue.f] = Queue.thread[Queue.r];
 42         printf("%d ", Queue.thread[Queue.r]->thread_id);
 43     }
 44     while (showQueue.r != showQueue.f)
 45     {
 46         Queue.f = (Queue.f  + 1) % thread_maxn;
 47         showQueue.r = (showQueue.r + 1) % thread_maxn;
 48         Queue.thread[Queue.f] = showQueue.thread[showQueue.r];
 49     }
 50     printf("print finished\n");
 51 }
 52 void create_tcb()
 53 {
 54     TCB* ptemp = tcb;
 55     srand(time(0));
 56     for (int i = 0; i < thread_maxn-1; ++i)
 57     {
 58         TCB* s = (TCB*)malloc(sizeof(TCB));
 59         s->arriveTime = rand() % 9;
 60         s->runTime = rand() % 9 + 1;
 61         s->thread_id = i;
 62         s->thrFinished = false;
 63         s->next = NULL;
 64         if (tcb == NULL)
 65         {
 66             tcb = s;
 67         }
 68         else
 69         {
 70             ptemp = tcb;
 71             while (ptemp && ptemp->next)
 72             {
 73                 ptemp = ptemp->next;
 74             }
 75             ptemp->next = s;
 76         }
 77     }
 78     printf("tcb Created\n");
 79 }
 80 typedef struct
 81 {
 82     pthread_mutex_t queue_lock;//互斥锁
 83     int shutdown;//销毁
 84     pthread_t* threadid;
 85     int cur_queue_size;
 86 } CThread_pool;
 87 void* thread_routine(void* arg);//线程要执行的函数
 88 static CThread_pool* pool = NULL;
 89 void pool_init()//初始化线程池
 90 {
 91     pool = (CThread_pool*)malloc(sizeof(CThread_pool));
 92     pthread_mutex_init(&(pool->queue_lock), NULL);//被初始化为未锁住状态
 93     pool->shutdown = 0;
 94     pool->threadid = (pthread_t*)malloc(thread_maxn * sizeof(pthread_t));
 95     TCB* ptemp = tcb;
 96     while (ptemp != NULL)
 97     {
 98         pthread_create(&(pool->threadid[ptemp->thread_id]), NULL, thread_routine, ptemp);//创建线程
 99         printf("thread%d created\n", ptemp->thread_id);
100         ptemp = ptemp->next;
101     }
102 }
103 void* thread_routine(void* arg)//线程中要执行的函数
104 {
105     TCB* ptemp = (TCB*)arg;
106     printf("starting ptemp->thread_id = %d\n", ptemp->thread_id);
107     while (ptemp->runTime > 0)
108     {
109 sleep(1);
110         sem_wait(&sem[ptemp->thread_id]);//挂起，等待唤醒
111 printf("%dBEING WOKEN\n",ptemp->thread_id);
112         pthread_mutex_lock(&(pool->queue_lock));
113         --(ptemp->runTime);
114         printf("nowTime = %d,目前轮转的线程为：%d\n",nowTime, ptemp->thread_id);
115         sleep(1);
116         if (ptemp->runTime == 0)
117         {
118             ++nFinish;
119             ptemp->thrFinished = true;//该线程已完成
120             //出队列
121             Queue.r = (Queue.r + 1) % thread_maxn;//out
122         }
123         else
124         {//未完成
125             Queue.r = (Queue.r + 1) % thread_maxn;//out
126             Queue.f = (Queue.f+1)%thread_maxn;
127             Queue.thread[Queue.f] = ptemp;
128             printf("nowTime = %d,线程%d估计剩余时间为%d\n",nowTime, ptemp->thread_id, ptemp->runTime);
129         }
130         pthread_mutex_unlock(&(pool->queue_lock));
131     }
132     pthread_exit(NULL);//不可达
133     return;
134 }
135 void init_sem()
136 {
137     for (int i = 0; i < thread_maxn-1; ++i)//初始化各线程信号量
138     {
139         sem_init(&sem[i], 0, 0);
140     }
141 }
142 void RoundRobin()//时间片轮转算法调度线程
143 {
144     while (1)
145     {
146         //加锁
147         pthread_mutex_lock(&(pool->queue_lock));
148         if (nFinish == thread_maxn-1)//如果所有线程都完成了
149             break;
150         printf("当前时间为%d\n", nowTime);
151         TCB* ptemp = tcb;
152         while (ptemp)
153         {
154             if (ptemp->arriveTime == nowTime)
155             {
156                 //入队
157 printf("thread %d inqueue\n", ptemp->thread_id);
158                 Queue.f = (Queue.f+1)%thread_maxn;
159                 Queue.thread[Queue.f] = ptemp;
160                 printf("nowTime = %d,线程%d到达，估计运行时间：%d\n",nowTime, ptemp->thread_id, ptemp->runTime);
161             }
162             ptemp = ptemp->next;
163         }
164         if (Queue.r != Queue.f)
165         {
166             nowRun = Queue.thread[(Queue.r + 1) % thread_maxn];
167             printf("thread operate, nowrun = %d\n",nowRun->thread_id);
168             sem_post(&sem[nowRun->thread_id]);//对应线程执行一次操作
169         }
170         //输出队列
171         printf("print queue %d and %d\n",Queue.r, Queue.f);
172     show_tcb();
173         ++nowTime;
174         pthread_mutex_unlock(&(pool->queue_lock));
175         sleep(1);
176     }
177 }
178 int main()
179 {
180     showQueue.f = showQueue.r = 0;
181     Queue.r = Queue.f = 0;
182     create_tcb();
183     pool_init();//初始化线程池
184     init_sem();//初始化线程信号量
185     RoundRobin();
186     printf("rr finished\n");
187     
188     TCB* ptemp = tcb;
189     while (ptemp)
190     {
191         pthread_join(pool->threadid[ptemp->thread_id], NULL);
192         printf("thread%d finished", ptemp->thread_id);
193         ptemp = ptemp->next;
194     }
195     sleep(5);
196     //销毁线程池
197     return 0;
198 }

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <semaphore.h>
  4 #include <unistd.h>
  5 #include <sys/types.h>
  6 #include <pthread.h>
  7 #define bool int
  8 #define true 1
  9 #define false 0
 10 #define thread_maxn 5//9
 11 void bubble_sort();
 12 
 13 typedef struct TCB
 14 {
 15     int thread_id;
 16     int arriveTime;
 17     int runTime;
 18     bool thrFinished;
 19     struct TCB* next;
 20 }TCB;
 21 struct tcb_queue
 22 {
 23     struct TCB *thread[thread_maxn];
 24     int r, f;
 25 };
 26 struct tcb_queue Queue;
 27 struct tcb_queue showQueue;
 28 
 29 sem_t sem[thread_maxn];//信号量，用于唤醒线程
 30 TCB* lHead = NULL;//存储线程信息
 31 TCB* nowRun;//目前正在运行的线程
 32 int nFinish = 0;
 33 int nowTime = 0;//目前时间计数
 34 TCB* tcb = NULL;
 35 
 36 void show_rr()
 37 {
 38     printf("(show)目前队列的情况为：");
 39     while (Queue.r != Queue.f)
 40     {
 41         showQueue.f = (showQueue.f+1)%thread_maxn;
 42         Queue.r = (Queue.r + 1) % thread_maxn;
 43         showQueue.thread[showQueue.f] = Queue.thread[Queue.r];
 44         printf("%d ", Queue.thread[Queue.r]->thread_id);
 45     }
 46     while (showQueue.r != showQueue.f)
 47     {
 48         Queue.f = (Queue.f  + 1) % thread_maxn;
 49         showQueue.r = (showQueue.r + 1) % thread_maxn;
 50         Queue.thread[Queue.f] = showQueue.thread[showQueue.r];
 51     }
 52     printf("print finished\n");
 53 }
 54 void show_tcb()
 55 {
 56     printf("show_tcb");
 57     TCB* ptemp = tcb;
 58 while(ptemp)
 59 {
 60     printf("thread%d: arrive:%d, left:%d\n",ptemp->thread_id, ptemp->arriveTime, ptemp->runTime);
 61 ptemp = ptemp->next;
 62 }
 63     printf("show_tcb finished\n");
 64 }
 65 void create_tcb()
 66 {
 67     TCB* ptemp = tcb;
 68     srand(time(0));
 69     for (int i = 0; i < thread_maxn-1; ++i)
 70     {
 71         TCB* s = (TCB*)malloc(sizeof(TCB));
 72         s->arriveTime = rand() % 9;
 73         s->runTime = rand() % 9 + 1;
 74         s->thread_id = i;
 75         s->thrFinished = false;
 76         s->next = NULL;
 77         if (tcb == NULL)
 78         {
 79             tcb = s;
 80         }
 81         else
 82         {
 83             ptemp = tcb;
 84             while (ptemp && ptemp->next)
 85             {
 86                 ptemp = ptemp->next;
 87             }
 88             ptemp->next = s;
 89         }
 90     }
 91     printf("tcb Created\n");
 92 }
 93 typedef struct
 94 {
 95     pthread_mutex_t queue_lock;//互斥锁
 96     int shutdown;//销毁
 97     pthread_t* threadid;
 98     int cur_queue_size;
 99 } CThread_pool;
100 void* thread_routine(void* arg);//线程要执行的函数
101 static CThread_pool* pool = NULL;
102 void pool_init()//初始化线程池
103 {
104     pool = (CThread_pool*)malloc(sizeof(CThread_pool));
105     pthread_mutex_init(&(pool->queue_lock), NULL);//被初始化为未锁住状态
106     pool->shutdown = 0;
107     pool->threadid = (pthread_t*)malloc(thread_maxn * sizeof(pthread_t));
108     TCB* ptemp = tcb;
109     while (ptemp != NULL)
110     {
111         pthread_create(&(pool->threadid[ptemp->thread_id]), NULL, thread_routine, ptemp);//创建线程
112         printf("thread%d created\n", ptemp->thread_id);
113         ptemp = ptemp->next;
114     }
115 }
116 void* thread_routine(void* arg)//线程中要执行的函数
117 {
118     TCB* ptemp = (TCB*)arg;
119     printf("starting ptemp->thread_id = %d\n", ptemp->thread_id);
120     while (ptemp->runTime > 0)
121     {
122 sleep(1);
123         sem_wait(&sem[ptemp->thread_id]);//挂起，等待唤醒
124 printf("%dBEING WOKEN\n",ptemp->thread_id);
125         pthread_mutex_lock(&(pool->queue_lock));
126         //--(ptemp->runTime);
127 ptemp->runTime -= 2;
128         printf("nowTime = %d,目前轮转的线程为：%d\n",nowTime, ptemp->thread_id);
129         sleep(1);
130         if (ptemp->runTime <= 0)
131         {
132             ++nFinish;
133             ptemp->thrFinished = true;//该线程已完成
134             //出队列
135             Queue.r = (Queue.r + 1) % thread_maxn;//out
136         }
137         else
138         {//未完成
139             Queue.r = (Queue.r + 1) % thread_maxn;//out
140             Queue.f = (Queue.f+1)%thread_maxn;
141             Queue.thread[Queue.f] = ptemp;
142             printf("nowTime = %d,线程%d估计剩余时间为%d\n",nowTime, ptemp->thread_id, ptemp->runTime);
143         }
144         pthread_mutex_unlock(&(pool->queue_lock));
145 sleep(1);
146     }
147     pthread_exit(NULL);//不可达
148     return;
149 }
150 void init_sem()
151 {
152     for (int i = 0; i < thread_maxn-1; ++i)//初始化各线程信号量
153     {
154         sem_init(&sem[i], 0, 0);
155     }
156 }
157 void RoundRobin()//时间片轮转算法调度线程
158 {
159  TCB* ptemp = tcb;
160     while (1)
161     {
162         //加锁
163         pthread_mutex_lock(&(pool->queue_lock));
164         if (nFinish == thread_maxn-1)//如果所有线程都完成了
165             break;
166        // printf("当前时间为%d\n", nowTime);
167        // TCB* ptemp = tcb;
168        // while (ptemp)
169 while(ptemp && ptemp->arriveTime == nowTime)
170         {
171             //if (ptemp->arriveTime == nowTime)
172             {
173                 //入队
174 printf("thread %d inqueue\n", ptemp->thread_id);
175                 Queue.f = (Queue.f+1)%thread_maxn;
176                 Queue.thread[Queue.f] = ptemp;
177                 printf("nowTime = %d,线程%d到达，估计运行时间：%d\n",nowTime, ptemp->thread_id, ptemp->runTime);
178             }
179             ptemp = ptemp->next;
180         }
181         if (Queue.r != Queue.f)
182         {
183             nowRun = Queue.thread[(Queue.r + 1) % thread_maxn];
184             printf("thread operate, nowrun = %d\n",nowRun->thread_id);
185 sleep(1);         
186    sem_post(&sem[nowRun->thread_id]);//对应线程执行一次操作
187 sleep(1);
188         }
189         //输出队列
190         printf("print queue %d and %d\n",Queue.r, Queue.f);
191     show_rr();
192         ++nowTime;
193         pthread_mutex_unlock(&(pool->queue_lock));
194         sleep(1);
195     }
196 }
197 int pool_destroy()
198 {
199     if (pool->shutdown)
200         return -1;
201     pool->shutdown = 1;
202     TCB* ptemp = tcb;
203     ptemp = tcb;
204     while (ptemp)
205     {
206         pthread_join(pool->threadid[ptemp->thread_id], NULL);
207         printf("thread%d finished\n", ptemp->thread_id);
208         ptemp = ptemp->next;
209     }
210     free(ptemp);
211     free(pool->threadid);
212     printf("pool is freeed\n");
213 
214     pthread_mutex_destroy(&(pool->queue_lock));
215     free(pool);
216     /*销毁后指针置空是个好习惯*/
217     pool = NULL;
218 }
219 int main()
220 {
221     showQueue.f = showQueue.r = 0;
222     Queue.r = Queue.f = 0;
223     create_tcb();
224 show_tcb();
225     bubble_sort();//tcb sort
226     pool_init();//初始化线程池
227     init_sem();//初始化线程信号量
228     RoundRobin();
229     printf("rr finished\n");
230     
231     sleep(5);
232 
233 pool_destroy();
234     //销毁线程池
235     return 0;
236 }
237 
238 void bubble_sort()//tcb
239 {
240     TCB* ptemp = NULL;
241     for (int i = 0; i < thread_maxn; ++i)
242     {
243         ptemp = tcb;
244         while (ptemp && ptemp->next)
245         {
246             if (ptemp->arriveTime > ptemp->next->arriveTime)
247             {
248                 TCB* p_next = ptemp->next->next;
249                 TCB* p_pre = ptemp;
250                 TCB* p_pre_pre = tcb;
251                 if (p_pre_pre == p_pre)
252                 {
253                     p_pre_pre = NULL;
254                 }
255                 else
256                 {
257                     while (p_pre_pre != NULL && p_pre_pre->next != p_pre)
258                     {
259                         p_pre_pre = p_pre_pre->next;
260                     }
261                 }
262                 ptemp = ptemp->next;
263                 ptemp->next = p_pre;
264                 p_pre->next = p_next;
265                 if (p_pre_pre != NULL)
266                 {
267                     p_pre_pre->next = ptemp;
268                 }
269                 else
270                 {
271                       tcb = ptemp;
272                 }
273             }
274                 ptemp = ptemp->next;
275         }
276     }
277 }

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <semaphore.h>
  4 #include <unistd.h>
  5 #include <sys/types.h>
  6 #include <pthread.h>
  7 #define bool int
  8 #define true 1
  9 #define false 0
 10 #define THREAD_MAXN 5//线程数
 11 #define RUNTIME_SUB 1//每次运行线程减去的运行时间
 12 //-----结构体定义
 13 typedef struct TCB//存储线程信息
 14 {
 15     int thread_id;//线程编号
 16     int arriveTime;//线程到达时间
 17     int runTime;//持续时间
 18     int finishTime;//完成时间
 19     int wholeTime;//周转时间
 20     double weightWholeTime;//带权周转时间
 21     bool Finished;//线程是否完成
 22     struct TCB* next;//使用链式存储方式
 23 }TCB;
 24 struct tcb_queue//TCB队列定义
 25 {
 26     struct TCB* tcbQueue[THREAD_MAXN];//TCB指针数组
 27     int r,f;
 28 };
 29 struct thread_pool//线程池结构体
 30 {
 31     pthread_mutex_t tcb_lock;//互斥锁
 32     int fDestroyed;//线程池是否被销毁
 33     pthread_t *threadid;//存储线程标识符指针
 34     TCB *nowRunThread;//指向当前正在运行的线程 
 35     int nExist;//现存现存
 36     int nFinish;//当前已完成的线程数
 37     sem_t sem[THREAD_MAXN];//用于控制线程的信号量
 38     struct tcb_queue pool->rrQueue;//轮转队列
 39     struct tcb_queue pool->showQueue;//用于辅助打印的队列
 40     TCB *tcb;//存储TCB
 41 };
 42 //-----全局变量定义
 43 thread_pool POOL;
 44 static thread_pool *pool = &POOL;//全局变量pool，指向线程池
 45 int nowTime;//当前已走过的时间
 46 //-----函数声明
 47 void bubble_sort();//给TCB排序
 48 void show_rr();//打印轮转队列
 49 void show_tcb();//打印所有线程的信息
 50 void pool_init();//初始化线程池
 51 void thread_run_func(void* param);//线程里运行的函数
 52 void round_robin();//时间片轮转算法的调度函数
 53 int pool_destroy();//销毁线程池
 54 //main
 55 int main()
 56 {
 57     pool_init();
 58     printf("TCB初始化完成！\n");
 59     printf("打印初始TCB：\n");
 60     show_tcb();
 61     printf("TCB按到达时间排序后：\n");
 62     bubble_sort();
 63     show_tcb();
 64     printf("所有线程已完成\n");
 65     sleep(5);//等待所有线程完成
 66     pool_destroy();
 67     return 0;
 68 }
 69 //函数定义
 70 void bubble_sort()//给TCB排序,按arriveTime升序排列
 71 {
 72 TCB* ptemp = NULL;
 73 for(int i=0; i<THREAD_MAXN; ++i)
 74 {
 75     ptemp = pool->tcb;
 76     while(ptemp && ptemp->next)
 77     {
 78         if(ptemp->arriveTime > ptemp->next->arriveTime)
 79         {//交换两个节点
 80             TCB *p_next = ptemp->next->next;
 81             TCB *p_pre = ptemp;
 82             TCB *p_pre_pre = pool->tcb;
 83             if(p_pre_pre == p_pre)
 84             {
 85                 p_pre_pre = NULL;
 86             }
 87             else
 88             {
 89                 while(p_pre_pre && p_pre_pre->next != p_pre)
 90                 {
 91                     p_pre_pre = p_pre_pre->next;
 92                 }
 93             }
 94             ptemp = ptemp->next;
 95             ptemp->next = p_pre;
 96             p_pre->next = p_next;
 97             if(p_pre_pre)
 98             {
 99                 p_pre_pre->next = ptemp;
100             }
101             else
102             {
103                 pool->tcb = ptemp;
104             } 
105         }
106         ptemp = ptemp->next;
107     }    
108 }
109 }
110 void show_rr()//打印轮转队列
111 {
112 printf("目前在轮转队列中线程为：\n");
113 while(pool->rrQueue.r != pool->rrQueue.f)
114 {
115     pool->showQueue.f = (pool->showQueue.f + 1) % THREAD_MAXN;
116     pool->rrQueue.r = (pool->rrQueue.r + 1) % THREAD_MAXN;
117     pool->showQueue.tcbQueue[pool->showQueue.f] = pool->rrQueue.tcbQueue[pool->rrQueue.r];
118     printf("%d ",pool->rrQueue.tcbQueue[pool->rrQueue.r]->thread_id);
119 }
120 while(pool->showQueue.r != pool->showQueue.f)//将队列放回
121 {
122     pool->rrQueue.f = (pool->rrQueue.f + 1) % THREAD_MAXN;
123     pool->showQueue.r = (pool->showQueue.r + 1) % THREAD_MAXN;
124     pool->rrQueue.tcbQueue[pool->rrQueue.f] = pool->showQueue.tcbQueue[pool->showQueue.r];
125 }
126 printf("\n");
127 }
128 void show_tcb()//打印所有线程的信息
129 {
130 TCB *ptemp = pool->tcb;
131 printf("打印所有线程的信息：\n");
132 while(ptemp)
133 {
134     printf("线程%d：到达时间：%d，剩余时间：%d\n", ptemp->thread_id, ptemp->arriveTime, ptemp->runTime);
135     ptemp = ptemp->next;
136 }
137 printf("\n");
138 }
139 void pool_init()//初始化线程池
140 {
141 pool = (thread_pool*)malloc(sizeof(thread_pool));
142 pool->pthread_mutex_init(&(pool->tcb_lock));//初始为未锁住状态
143 pool->fDestroyed = 0;//线程池是否被销毁
144 pool->nowRunThread = NULL;//指向当前正在运行的线程 
145 pool->nExist = 0;//现存线程
146 pool->nFinish = 0;//当前已完成的线程数
147 pool->rrQueue.r = pool->rrQueue.q = 0;//轮转队列
148 pool->showQueue.r = pool->showQueue.r = 0;//用于辅助打印的队列
149 //创建并初始化TCB
150 TCB* ptemp = pool->tcb;
151 srand(time(0));
152 for(int i=0; i<THREAD_MAXN-1; ++i)
153 {
154     TCB* s = (*TCB)malloc(sizeof(TCB));
155     s->arriveTime = rand()%9;
156     s->runTime = rand()%9+1;
157     s->thread_id = i;//编号令为0
158     s->Finished = fsemalse;
159     s->next = NULL;
160     //尾插入
161     if(pool->tcb == NULL)//第一个节点
162         tcb = s;
163     else
164     {
165         ptemp = pool->tcb;
166         while(ptemp && ptemp->next)
167         {
168             ptemp = ptemp->next;
169         }
170         ptemp->next = s;
171     }
172 }
173 //初始化信号量sem
174 ptemp = pool->tcb;
175 while(ptemp)
176 {
177     sem_init(&(ptemp->thread_id), 0, 0);
178     ptemp = ptemp->next;
179 }
180 //创建线程
181 ptemp = pool->tcb;
182 threadid = (pthread_t*)malloc(sizeof(pthread_t) * THREAD_MAXN);
183 while(ptemp)
184 {
185     //把ptemp作为参数传入thread_run_func()
186     int t;
187     t = pthread_create(&(pool->threadid[ptemp->thread_id]), \
188                             NULL, thread_run_func, ptemp);
189     if(!t)//线程创建成功
190     {
191         printf("线程%d创建成功!\n", ptemp->thread_id);
192     }
193     else
194     {
195         printf("线程创建失败!\n");
196     }
197     ptemp = ptemp->next;
198 }
199 printf("线程池pool初始化完成！\n");
200 }
201 void thread_run_func(void *param)//线程里运行的函数
202 {
203 TCB *ptemp = (*TCB)param;
204 // prtinf("线程%d开始了", ptemp->thread_id);
205 while(ptemp->runTime > 0)
206 {
207     printf("线程%d正在等待……\n");
208     sleep(1);
209     sem_wait(&(pool->sem[ptemp->thread_id]));//唤醒
210     printf("线程%d已被唤醒！\n");
211     pthread_mutex_lock(&(pool->tcb_lock));//上互斥锁
212     ptemp->runTime -= RUNTIME_SUB;
213     printf("当前时间为：%d，轮转的线程为线程%d，该线程剩余时间：%d->%d\n",\
214             nowTime, ptemp->thread_id, ptemp->runTime+RUNTIME_SUB, ptemp->runTime<0?0:ptemp->runTime);
215     sleep(1);
216     if(ptemp->runTime <= 0)//线程已经完成
217     {
218         ++pool->nFinish;
219         ptemp->Finished = true;
220         //出队
221         pool->rrQueue.r = (pool->rrQueue.r+1)%THREAD_MAXN;
222     }
223     else
224     {//还未完成
225         //出队
226         pool->rrQueue.r = (pool->rrQueue.r+1)%THREAD_MAXN;
227         //入队
228         pool->rrQueue.f = (pool->rrQueue.f + 1) % THREAD_MAXN;
229         pool->rrQueue.thread[pool->rrQueue.f] = ptemp;
230     }
231     pthread_mutex_unlock(&(pool->tcb_lock));
232     sleep(1);
233 }
234 pthread_exit(NULL);
235 }
236 void round_robin()//时间片轮转算法的调度函数
237 {
238     TCB *ptemp = pool->tcb;
239     while(1)
240     {
241         sleep(1);
242         pthread_mutex_lock(&(pool->tcb_lock));
243         if(pool->nFinished == THREAD_MAXN-1)//所有线程完成
244             break;
245         while(ptemp && ptemp->arriveTime == nowTime)
246         {
247             printf("当前时间为：%d，线程%d进入轮转队列，剩余运行时间：%d\n", \
248                 nowTime, ptemp->thread_id, ptemp->runTime);
249             pool->rrQueue.f = (pool->rrQueue.f+1)%THREAD_MAXN;
250             pool->rrQueue.tcbQueue[pool->rrQueue.f] = ptemp;
251             ptemp = ptemp->next;
252         }
253         if(pool->rrQueue.r != pool->rrQueue.f)
254         {
255             pool->nowRunThread = pool->rrQueue.tcbQueue[(pool->rrQueue+1)%THREAD_MAXN];
256             printf("准备唤醒线程线程%d\n",pool->nowRunThread->thread_id);
257             sleep(1);
258             sem_post(&(pool->sem[pool->nowRunThread->thread_id]));
259         }
260         show_rr();
261         ++nowTime;
262         pthread_mutex_unlock(&(pool->tcb_lock));
263         sleep(1);
264     }
265 }
266 int pool_destroy()//销毁线程池
267 {
268     if(pool->fDestroyed)//防止重复销毁
269         return -1;
270     pool->fDestroyed = 1;
271     TCB* ptemp = pool->tcb;
272     while(ptemp)
273     {
274         pthread_join(pool->threadid[ptemp->thread_id], NULL);
275         printf("线程%d已结束\n",ptemp->thread_id);
276         ptemp = ptemp->next;
277     }
278     free(ptemp);
279     free(pool->threadid);
280     pthread_mutex_destroy(&(pool->tcb_lock));
281     free(pool);
282     pool = NULL;
283     printf("线程池pool已被销毁！\n");
284 }

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <semaphore.h>
  4 #include <unistd.h>
  5 #include <time.h>
  6 #include <sys/types.h>
  7 #include <pthread.h>
  8 #define bool int
  9 #define true 1
 10 #define false 0
 11 #define THREAD_MAXN 5//线程数
 12 #define RUNTIME_SUB 1//每次运行线程减去的运行时间
 13 //-----结构体定义
 14 typedef struct TCB//存储线程信息
 15 {
 16     int thread_id;//线程编号
 17     int arriveTime;//线程到达时间
 18     int runTime;//持续时间
 19     int finishTime;//完成时间
 20     int wholeTime;//周转时间
 21     double weightWholeTime;//带权周转时间
 22     bool Finished;//线程是否完成
 23     struct TCB* next;//使用链式存储方式
 24 }TCB;
 25 struct tcb_queue//TCB队列定义
 26 {
 27     struct TCB* tcbQueue[THREAD_MAXN];//TCB指针数组
 28     int r,f;
 29 };
 30 struct thread_pool//线程池结构体
 31 {
 32     pthread_mutex_t tcb_lock;//互斥锁
 33     int fDestroyed;//线程池是否被销毁
 34     pthread_t *threadid;//存储线程标识符指针
 35     struct TCB *nowRunThread;//指向当前正在运行的线程 
 36     int nExist;//现存现存
 37     int nFinish;//当前已完成的线程数
 38     sem_t sem[THREAD_MAXN];//用于控制线程的信号量
 39     struct tcb_queue rrQueue;//轮转队列
 40     struct tcb_queue showQueue;//用于辅助打印的队列
 41     struct TCB *tcb;//存储TCB
 42 };
 43 //-----全局变量定义
 44 static struct thread_pool *pool = NULL;//全局变量pool，指向线程池
 45 int nowTime;//当前已走过的时间
 46 //-----函数声明
 47 void bubble_sort();//给TCB排序
 48 void show_rr();//打印轮转队列
 49 void show_tcb();//打印所有线程的信息
 50 void pool_init();//初始化线程池
 51 void thread_run_func(void* param);//线程里运行的函数
 52 void round_robin();//时间片轮转算法的调度函数
 53 int pool_destroy();//销毁线程池
 54 //main
 55 int main()
 56 {
 57     pool_init();
 58     printf("打印初始TCB：\n");
 59     show_tcb();
 60     printf("TCB按到达时间排序后：\n");
 61     bubble_sort();
 62     show_tcb();
 63     round_robin();
 64     sleep(5);//等待所有线程完成
 65     pool_destroy();
 66     return 0;
 67 }
 68 //函数定义
 69 void bubble_sort()//给TCB排序,按arriveTime升序排列
 70 {
 71 TCB* ptemp = NULL;
 72 for(int i=0; i<THREAD_MAXN; ++i)
 73 {
 74     ptemp = pool->tcb;
 75     while(ptemp && ptemp->next)
 76     {
 77         if(ptemp->arriveTime > ptemp->next->arriveTime)
 78         {//交换两个节点
 79             TCB *p_next = ptemp->next->next;
 80             TCB *p_pre = ptemp;
 81             TCB *p_pre_pre = pool->tcb;
 82             if(p_pre_pre == p_pre)
 83             {
 84                 p_pre_pre = NULL;
 85             }
 86             else
 87             {
 88                 while(p_pre_pre && p_pre_pre->next != p_pre)
 89                 {
 90                     p_pre_pre = p_pre_pre->next;
 91                 }
 92             }
 93             ptemp = ptemp->next;
 94             ptemp->next = p_pre;
 95             p_pre->next = p_next;
 96             if(p_pre_pre)
 97             {
 98                 p_pre_pre->next = ptemp;
 99             }
100             else
101             {
102                 pool->tcb = ptemp;
103             } 
104         }
105         ptemp = ptemp->next;
106     }    
107 }
108 }
109 void show_rr()//打印轮转队列
110 {
111 printf("当前时间为：%d\n",nowTime);
112 if(pool->rrQueue.r == pool->rrQueue.f)
113 {
114     printf("目前还没有线程到达\n");
115 }
116 else
117 {
118     printf("目前轮转队列为：\n");
119 }
120 while(pool->rrQueue.r != pool->rrQueue.f)
121 {
122     pool->showQueue.f = (pool->showQueue.f + 1) % THREAD_MAXN;
123     pool->rrQueue.r = (pool->rrQueue.r + 1) % THREAD_MAXN;
124     pool->showQueue.tcbQueue[pool->showQueue.f] = pool->rrQueue.tcbQueue[pool->rrQueue.r];
125     printf("%d ",pool->rrQueue.tcbQueue[pool->rrQueue.r]->thread_id);
126 }
127 while(pool->showQueue.r != pool->showQueue.f)//将队列放回
128 {
129     pool->rrQueue.f = (pool->rrQueue.f + 1) % THREAD_MAXN;
130     pool->showQueue.r = (pool->showQueue.r + 1) % THREAD_MAXN;
131     pool->rrQueue.tcbQueue[pool->rrQueue.f] = pool->showQueue.tcbQueue[pool->showQueue.r];
132 }
133 printf("\n\n");
134 }
135 void show_tcb()//打印所有线程的信息
136 {
137 TCB *ptemp = pool->tcb;
138 printf("打印所有线程的信息：\n");
139 while(ptemp)
140 {
141     printf("线程%d：到达时间：%d，剩余时间：%d\n", ptemp->thread_id, ptemp->arriveTime, ptemp->runTime);
142     ptemp = ptemp->next;
143 }
144 printf("\n");
145 }
146 void pool_init()//初始化线程池
147 {
148 pool = (struct thread_pool*)malloc(sizeof(struct thread_pool));
149 pthread_mutex_init(&(pool->tcb_lock), NULL);//初始为未锁住状态
150 pool->fDestroyed = 0;//线程池是否被销毁
151 pool->nowRunThread = NULL;//指向当前正在运行的线程 
152 pool->nExist = 0;//现存线程
153 pool->nFinish = 0;//当前已完成的线程数
154 pool->rrQueue.r = pool->rrQueue.f = 0;//轮转队列
155 pool->showQueue.r = pool->showQueue.r = 0;//用于辅助打印的队列
156 pool->tcb = NULL;
157 //创建并初始化TCB
158 TCB* ptemp = pool->tcb;
159 srand(time(0));
160 for(int i=0; i<THREAD_MAXN-1; ++i)
161 {
162     TCB* s = (TCB*)malloc(sizeof(TCB));
163     s->arriveTime = rand()%9;
164     s->runTime = rand()%9+1;
165     s->thread_id = i;//编号令为0
166     s->Finished = false;
167     s->next = NULL;
168     //尾插入
169     if(!pool->tcb)//第一个节点
170     {
171         pool->tcb = s;
172     }
173     else
174     {
175         ptemp = pool->tcb;
176         while(ptemp && ptemp->next)
177         {
178             ptemp = ptemp->next;
179         }
180         ptemp->next = s;
181     }
182 }
183 //初始化信号量sem
184 ptemp = pool->tcb;
185 int i=0;
186 while(ptemp != NULL)
187 {
188     int i = ptemp->thread_id;
189     sem_init(&i, 0, 0);
190     ptemp = ptemp->next;
191 }
192 //创建线程
193 ptemp = pool->tcb;
194 pool->threadid = (pthread_t*)malloc(sizeof(pthread_t) * THREAD_MAXN);
195 while(ptemp != NULL)
196 {
197     //把ptemp作为参数传入thread_run_func()
198     int t;
199     t = pthread_create(&(pool->threadid[ptemp->thread_id]), \
200                             NULL, thread_run_func, ptemp);
201     if(!t)//线程创建成功
202     {
203         printf("线程%d创建成功!\n", ptemp->thread_id);
204     }
205     else
206     {
207         printf("线程创建失败!\n");
208     }
209     ptemp = ptemp->next;
210 }
211 printf("线程池pool初始化完成！\n");
212 }
213 void thread_run_func(void *param)//线程里运行的函数
214 {
215 TCB *ptemp = (TCB*)param;
216 // prtinf("线程%d开始了", ptemp->thread_id);
217 while(ptemp->runTime > 0)
218 {
219     printf("线程%d正在等待……\n", ptemp->thread_id);
220     sleep(1);
221     sem_wait(&(pool->sem[ptemp->thread_id]));//唤醒
222     printf("线程%d已被唤醒！\n",ptemp->thread_id);
223     pthread_mutex_lock(&(pool->tcb_lock));//上互斥锁
224     ptemp->runTime -= RUNTIME_SUB;
225     printf("当前时间为：%d，轮转的线程为线程%d，该线程剩余时间：%d->%d\n",\
226             nowTime, ptemp->thread_id, ptemp->runTime+RUNTIME_SUB, ptemp->runTime<0?0:ptemp->runTime);
227     sleep(1);
228     if(ptemp->runTime <= 0)//线程已经完成
229     {
230         ++pool->nFinish;
231         ptemp->Finished = true;
232         //出队
233         pool->rrQueue.r = (pool->rrQueue.r+1)%THREAD_MAXN;
234     }
235     else
236     {//还未完成
237         //出队
238         pool->rrQueue.r = (pool->rrQueue.r+1)%THREAD_MAXN;
239         //入队
240         pool->rrQueue.f = (pool->rrQueue.f + 1) % THREAD_MAXN;
241         pool->rrQueue.tcbQueue[pool->rrQueue.f] = ptemp;
242     }
243     pthread_mutex_unlock(&(pool->tcb_lock));
244     sleep(1);
245 }
246 pthread_exit(NULL);
247 }
248 void round_robin()//时间片轮转算法的调度函数
249 {
250     TCB *ptemp = pool->tcb;
251     while(1)
252     {
253         sleep(1);
254         pthread_mutex_lock(&(pool->tcb_lock));
255         if(pool->nFinish == THREAD_MAXN-1)//所有线程完成
256             break;
257         while(ptemp && ptemp->arriveTime == nowTime)
258         {
259             printf("当前时间为：%d，线程%d进入轮转队列，运行时间：%d\n", \
260             nowTime, ptemp->thread_id, ptemp->runTime);
261             pool->rrQueue.f = (pool->rrQueue.f+1)%THREAD_MAXN;
262             pool->rrQueue.tcbQueue[pool->rrQueue.f] = ptemp;
263             ptemp = ptemp->next;
264         }
265         if(pool->rrQueue.r != pool->rrQueue.f)
266         {
267             pool->nowRunThread = pool->rrQueue.tcbQueue[(pool->rrQueue.r+1)%THREAD_MAXN];
268             printf("准备唤醒线程%d\n",pool->nowRunThread->thread_id);
269             sleep(1);
270             sem_post(&(pool->sem[pool->nowRunThread->thread_id]));
271         }
272         show_rr();
273         ++nowTime;
274         pthread_mutex_unlock(&(pool->tcb_lock));
275         sleep(1);
276     }
277 }
278 int pool_destroy()//销毁线程池
279 {
280     if(pool->fDestroyed)//防止重复销毁
281         return -1;
282     pool->fDestroyed = 1;
283     TCB* ptemp = pool->tcb;
284     while(ptemp)
285     {
286         pthread_join(pool->threadid[ptemp->thread_id], NULL);
287         printf("线程%d已结束\n",ptemp->thread_id);
288         ptemp = ptemp->next;
289     }
290     free(ptemp);
291     free(pool->threadid);
292     pthread_mutex_destroy(&(pool->tcb_lock));
293     free(pool);
294     pool = NULL;
295     printf("线程池pool已被销毁！\n");
296 }

View Code

相关推荐