热爱互联网

多线程模拟磁盘调度算法

多线程模拟磁盘调度算法。
学过操作系统的童鞋都懂得。
hei,孩纸,课设别直接抄哥的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
/*
  * 假设磁盘有 N 个磁道. ( 0 ---  N-1 )
  *	总共有 M 个磁盘访问请求,这 M 个请求对于算法来说是未知的,也就是说,先预先产生 M 个访问点作为本次测试
  *	的数据,然后根据时间片轮换的原则,边访问磁盘,边把将要访问的磁盘位置插入等待队列,利用多线程去模拟。
  * 请求的 M 个磁道访问位置随机产生,按逆序(为了方便删除)存放在 request 数组中,为什么要预先存放在request
	数组的原因仅仅是为了公平的比较这个四个磁盘调度算法。
	算法进行的过程中,通过多线程,一个一个的从 request 数组中读出,按照算法的逻辑来进行运算。
	也就是说算法是动态的,这就非常接近的模拟了现实中操作系统的磁盘调度算法。
	磁头的初始位置随机产生。
	4种磁盘调度算法:
	1、FCFS(first come first server)
	2、SSTF(shortest seek time first)
	3、SCAN(左右来回访问磁道(这里假定先向左))
	4、C-SCAN (先向一端移动访问磁道(这里假定先向右),然后迅速的移动到左端,再向右移动访问直到右端点,..)
	注意:在C-SCAN算法中,从右端迅速移动到左端,只算一次寻道次数,因为这个过程并没有访问磁道。
	每个算法都由两个部分组成,一部分是寻道算法,另一部分是将 即将要访问的点插入到等待队列中,。
	这两个部分通过互斥对象 hMutex 分别互斥同步执行。
	( 为了模拟寻道处理的时间,寻道后将其挂起1ms(调用Sleep(1)),但这样会程序运行非常慢,不过这里
	   还是用了这个方法,不然看不到 SSTF 算法的优势,:)
	 )
	 *
		 可调整请求数 M 的大小来观察各算法的结果。
		 M的值不同,相对结果可能相差很大。
		 M 较小时C-SCAN可能有优势一些,但M较大时 SSTF 的优势就体现出来了,.......
	 *
*/
#include<windows.h>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<iterator>
using namespace std;
/****************************************************/
const int N=200;   //磁道数,磁道编号从 0 到 N-1
const int M=100;	//请求数
int pos;		   //磁头的初始位置,随机产生
vector<int>request; // 本次测试的 M 个请求,按逆序存放
HANDLE hMutex; //互斥对象,读写等待队列需互斥
						 //FCFS算法不需要使用多线程,直接计算即可。
//SSTF算法
priority_queue<int,vector<int>,greater<int> >que; //最小优先队列
int pos_SSTF; //磁头当前位置,下同
vector<int>SSTF_request;
//SCAN算法
vector<int>v_scan; //v_scan[i]记录此时第i个位置有v_scan[i]次访问
int num_SCAN; //记录v_scan中有多少个待访问的点
int dir_SCAN; //记录当前移动的方向,为0表示向左,为1表示向右
vector<int>SCAN_request;
//C_SCAN算法
vector<int>v_c_scan; //v_c_scan[i]记录此时第i个位置有v_c_scan[i]次访问
int num_C_SCAN; //记录v_c_scan中有多少个待访问的点
vector<int>C_SCAN_request;
//各个算法总共访问磁道的次数
int ans_FCFS,ans_SSTF,ans_SCAN,ans_C_SCAN;
/***************************************************/
void init()  //初始化
{
	 request.resize(M);
	 for(int i=0;i<m;++i)
		 request[i] = rand()%N;
	 pos = rand()%N;
	 pos_SSTF = pos; //SSTF算法需要磁头的初始位置
	 SSTF_request.assign(request.begin(),request.end());
	 SCAN_request.assign(request.begin(),request.end());
	 C_SCAN_request.assign(request.begin(),request.end());
	 //清空
	 while(!que.empty())
		 que.pop();
	 v_scan.resize(N); // 0 -- N-1
	 v_c_scan.resize(N); // 0 -- N-1
	 fill(v_scan.begin(),v_scan.end(),0);
	 fill(v_c_scan.begin(),v_c_scan.end(),0);
	 num_SCAN = num_C_SCAN = 0;
	 dir_SCAN = 0 ;
	 ans_FCFS=ans_SSTF=ans_SCAN=ans_C_SCAN=0; //
	 //创建互斥对象
	 hMutex = CreateMutex(NULL,FALSE,NULL);
}
/******************************************************/
/******************************************************/
DWORD WINAPI _SSTF_FIND(LPVOID lpParameter) //SSTF算法 --- 寻道
{
	while(1)
	{
		WaitForSingleObject(hMutex,INFINITE);
		if(que.empty() && SSTF_request.empty()) //为空,说明已经处理完本次测试的所有数据
			break;
		else if(!que.empty())  //磁头 从 pos_SSTF 移动到 que.top() 位置
		{					   //需要处理一个点同时存在多次访问的情况
			int t,temp = que.top();
			do
			{
				ans_SSTF += abs(pos_SSTF-que.top());
				pos_SSTF = que.top();
				que.pop();
				Sleep(1);
				t=-1;
				if(!que.empty())
					t=que.top();
			}while(temp==t); //temp == t 就说明该点此时存在多次访问
		}
		ReleaseMutex(hMutex);
	}
	return 0;
}
DWORD WINAPI _SSTF_INSERT(LPVOID lpParameter) //SSTF算法  --- 插入
{
	while(1)
	{
		WaitForSingleObject(hMutex,INFINITE);
		if(SSTF_request.empty())
			break;
		else //把 SSTF_request的末尾元素插入到队列que 中,然后删除末尾元素
		{
			que.push(SSTF_request.back());
			SSTF_request.pop_back();
		}
		ReleaseMutex(hMutex);
	}
	return 0;
}
/***********************************************************/
/***********************************************************/
DWORD WINAPI _SCAN_FIND(LPVOID lpParameter) //SCAN算法 --- 寻道
{
	int i=pos;
	while(1)
	{
		WaitForSingleObject(hMutex,INFINITE);
		if(num_SCAN<=0 && SCAN_request.empty()) //为空,说明已经处理完本次测试的所有数据
			break;
		if(num_SCAN>0 )
		{
			if(!dir_SCAN) //向左
			{
				-- ans_SCAN; //先减1
				for(;i>=0 ;--i)
				{
					++ ans_SCAN; //
					if(num_SCAN<=0)
						break;
					while(v_scan[i] && num_SCAN>0) //该点有访问
					{
						-- v_scan[i];
						Sleep(1);
						-- num_SCAN;
					}
					if(0 == i)
					{
						dir_SCAN = 1 ; //向右
						break;
					}
				}
			}
			else //向右
			{
				-- ans_SCAN; //
				for(;i<n ;++i)
				{
					++ ans_SCAN;
					if(num_SCAN<=0)
						break;
					while(v_scan[i] && num_SCAN>0) //该点有访问
					{
						-- v_scan[i];
						Sleep(1); //
						-- num_SCAN;
					}
					if(N-1 == i)
					{
						dir_SCAN = 0 ; //向左
						break;
					}
				}
			}
		}
		ReleaseMutex(hMutex);
	}
	return 0;
}
DWORD WINAPI _SCAN_INSERT(LPVOID lpParameter)//SCAN算法 --- 插入
{
	while(1)
	{
		WaitForSingleObject(hMutex,INFINITE);
		if(SCAN_request.empty())
			break;
		else
		{
			++ v_scan[SCAN_request.back()]; //该点的待访问次数加1
			++ num_SCAN;
			SCAN_request.pop_back();
		}
		ReleaseMutex(hMutex);
	}
	return 0;
}
/***********************************************************/
/************************************************************/
DWORD WINAPI _C_SCAN_FIND(LPVOID lpParameter) //C_SCAN算法 --- 寻道
{
	int i=pos;
	while(1)
	{
		WaitForSingleObject(hMutex,INFINITE);
		if(num_C_SCAN<=0 && C_SCAN_request.empty()) //为空,说明已经处理完本次测试的所有数据
			break;
		if(num_C_SCAN>0 )
		{
			-- ans_C_SCAN;
			for(;i<n;++i)
			{
				++ ans_C_SCAN;
				if(num_C_SCAN<=0)
					break;
				while(v_c_scan[i] && num_C_SCAN>0)//该点有访问
				{
					-- v_c_scan[i];
					Sleep(1);
					-- num_C_SCAN;
				}
				if( N-1 == i)
				{
					i=-1; //
					++ ans_C_SCAN;
				}
			}
		}
		ReleaseMutex(hMutex);
	}
	return 0;
}
DWORD WINAPI _C_SCAN_INSERT(LPVOID lpParameter)  //C_SCAN算法 --- 插入
{
	while(1)
	{
		WaitForSingleObject(hMutex,INFINITE);
		if(C_SCAN_request.empty())
			break;
		else
		{
			++ v_c_scan[C_SCAN_request.back()]; //该点的待访问次数加1
			++ num_C_SCAN;
			C_SCAN_request.pop_back();
		}
		ReleaseMutex(hMutex);
	}
	return 0;
}
/************************************************************/
/***********************************************************/
void FCFS()
{
	 int temp=pos;
	 for(int i=0;i!=request.size();++i)
	 {
		 ans_FCFS += abs(request[i] - temp);
		 temp = request[i];
	 }
}
void SSTF()
{
	HANDLE hThread1;
	HANDLE hThread2;
	//创建线程
	hThread1 = CreateThread(NULL,0,_SSTF_INSERT,NULL,0,NULL); //插入
	hThread2 = CreateThread(NULL,0,_SSTF_FIND,NULL,0,NULL); //寻道
	CloseHandle(hThread1);
	CloseHandle(hThread2);
	while(que.size() || SSTF_request.size()); //直到处理完所有访问
}
void SCAN()
{
	HANDLE hThread1;
	HANDLE hThread2;
	//创建线程
	hThread1 = CreateThread(NULL,0,_SCAN_INSERT,NULL,0,NULL); //插入
	hThread2 = CreateThread(NULL,0,_SCAN_FIND,NULL,0,NULL); //寻道
	CloseHandle(hThread1);
	CloseHandle(hThread2);
	while(num_SCAN>0 || SCAN_request.size()); //直到处理完所有访问
}
void C_SCAN()
{
	HANDLE hThread1;
	HANDLE hThread2;
	//创建线程
	hThread1 = CreateThread(NULL,0,_C_SCAN_INSERT,NULL,0,NULL); //插入
	hThread2 = CreateThread(NULL,0,_C_SCAN_FIND,NULL,0,NULL); //寻道
	CloseHandle(hThread1);
	CloseHandle(hThread2);
	while(num_C_SCAN>0 || C_SCAN_request.size()); //直到处理完所有访问
}
/***********************************************************/
//输出请求队列
void output(const vector<int>&request)
{
	for(int i=0;i!=request.size();++i)
	{
		cout<<request[i]<<" ";
		if( (i+1) % 20 == 0 )
			cout<<endl;
	}
}
void solve()
{
	 cout<<"结果如下:"<<endl;
	 cout<<"磁头初始位置为: "<<pos<<endl;
	 cout<<"请求队列为:"<<endl;
	 output(request);
	 cout<<endl;
	 FCFS();
	 SSTF();
	 SCAN();
	 C_SCAN();
	 cout<<"算法	--------------寻道次数"<<endl;
	 cout<<"FCFS	---------------  "<<ans_FCFS<<endl;
	 cout<<"SSTF	---------------  "<<ans_SSTF<<endl;
	 cout<<"SCAN	---------------  "<<ans_SCAN<<endl;
	 cout<<"C-SCAN  ---------------  "<<ans_C_SCAN<<endl;
	 cout<<endl;
}
int main()
{
	for(int i=0;i<5;++i)
	{
		init();
		solve();
	}
	return 0;
}

Post a Comment

Your email is kept private. Required fields are marked *