ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • 디스크 스케줄링 알고리즘
      IT Tech/PS 2020. 8. 14. 13:51

      운영체제가 디스크를 읽거나 쓰려는 요청을 받았을 때, 우선순위를 정해 관리하는 기법..

       

      Operating System Concepts 한국어판을 보고도 설명에 대해 이해하기가 힘들어서

      인터넷을 찾아보다가 나름 좋은 자료인 것 같아서 공부하기로 함.

       

       

      참고자료

      www.geeksforgeeks.org/disk-scheduling-algorithms/

       

      Disk Scheduling Algorithms - GeeksforGeeks

      A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

      www.geeksforgeeks.org

      코드는 직접 짠 건 아니고 위 사이트에 올라온 것을 퍼와서 분석해보는 정도로 해보았다.

       

      FCFS ( First Come First Serve ) 스케줄링

      먼저 들어온 것을 먼저 처리하는 알고리즘이다.

      Input: 
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50

Output:
Total number of seek operations = 510
Seek Sequence is
176
79
34
60
92
11
41
114

      176, 79, 34, 60, 92,11, 42, 114 순서대로 들어온다고 보고 초기 헤드 값은 50을 보고 있다.

      다음과 같은 시퀀스 결과

      C++ 코드

      // C++ program to demonstrate 
// FCFS Disk Scheduling algorithm 

#include <bits/stdc++.h> 
using namespace std; 

int size = 8; 

void FCFS(int arr[], int head) 
{ 
	int seek_count = 0; 
	int distance, cur_track; 

	for (int i = 0; i < size; i++) { 
		cur_track = arr[i]; 

		// calculate absolute distance 
		distance = abs(cur_track - head); 

		// increase the total count 
		seek_count += distance; 

		// accessed track is now new head 
		head = cur_track; 
	} 

	cout << "Total number of seek operations = "
		<< seek_count << endl; 

	// Seek sequence would be the same 
	// as request array sequence 
	cout << "Seek Sequence is" << endl; 

	for (int i = 0; i < size; i++) { 
		cout << arr[i] << endl; 
	} 
} 

// Driver code 
int main() 
{ 

	// request array 
	int arr[size] = { 176, 79, 34, 60, 92, 11, 41, 114 }; 
	int head = 50; 

	FCFS(arr, head); 

	return 0; 
}

       

      Python 코드

      # Python program to demonstrate 
# FCFS Disk Scheduling algorithm 

size = 8; 

def FCFS(arr, head): 

	seek_count = 0; 
	distance, cur_track = 0, 0; 

	for i in range(size): 
		cur_track = arr[i]; 

		# calculate absolute distance 
		distance = abs(cur_track - head); 

		# increase the total count 
		seek_count += distance; 

		# accessed track is now new head 
		head = cur_track; 
	
	print("Total number of seek operations = ", seek_count); 

	# Seek sequence would be the same 
	# as request array sequence 
	print("Seek Sequence is"); 

	for i in range(size): 
		print(arr[i]); 
	
# Driver code 
if __name__ == '__main__': 

	# request array 
	arr = [ 176, 79, 34, 60, 92, 11, 41, 114 ]; 
	head = 50; 

	FCFS(arr, head); 

# This code contributed by Rajput-Ji

       

      SSTF 스케줄링

      큐 값들 중에서 헤드에서 가장 가까운 요청부터 처리해주는 기법이다.

      다음과 같은 큐가 있다고 생각하자.

      Input
Request sequence = { 98, 183, 40, 122, 10, 124, 65 }
Initial head position = 53

      이것을 스케줄링 표현하면

      헤드에서 오른쪽 방향을 가는 이유는 53에서 가장 가까운 요청이 65이라서 그런 것.

       

      # Python3 program for implementation of 
# SSTF disk scheduling 

# Calculates difference of each 
# track number with the head position 
def calculateDifference(queue, head, diff): 
	for i in range(len(diff)): 
		diff[i][0] = abs(queue[i] - head) 
	
# find unaccessed track which is 
# at minimum distance from head 
def findMin(diff): 

	index = -1
	minimum = 999999999

	for i in range(len(diff)): 
		if (not diff[i][1] and
				minimum > diff[i][0]): 
			minimum = diff[i][0] 
			index = i 
	return index 
	
def shortestSeekTimeFirst(request, head):			 
		if (len(request) == 0): 
			return
		
		l = len(request) 
		diff = [0] * l 
		
		# initialize array 
		for i in range(l): 
			diff[i] = [0, 0] 
		
		# count total number of seek operation	 
		seek_count = 0
		
		# stores sequence in which disk 
		# access is done 
		seek_sequence = [0] * (l + 1) 
		
		for i in range(l): 
			seek_sequence[i] = head 
			calculateDifference(request, head, diff) 
			index = findMin(diff) 
			
			diff[index][1] = True
			
			# increase the total count 
			seek_count += diff[index][0] 
			
			# accessed track is now new head 
			head = request[index] 
	
		# for last accessed track 
		seek_sequence[len(seek_sequence) - 1] = head 
		
		print("Total number of seek operations =", seek_count) 
														
		print("Seek Sequence is") 
		
		# print the sequence 
		for i in range(l + 1): 
			print(seek_sequence[i]) 
	
# Driver code 
if __name__ =="__main__": 
	
	# request array 
	proc = [176, 79, 34, 60, 
			92, 11, 41, 114] 
	shortestSeekTimeFirst(proc, 50) 
	
# This code is contributed by 
# Shubham Singh(SHUBHAMSINGH10)

       

      SCAN 스케줄링 ( 엘레베이터 스케줄링 )

      SCAN 스케줄링은 한 끝에서 시작해서 다른 끝으로 이동하며, 가는 길의 요청을 모두 처리하게 되는 스케줄링 기법이다.

      헤드 위치에서부터 다음 진행 방향이 정해져 있다고 하기 때문에 그 방향으로만 계속 가며 끝에 다다르면 방향을 전환하여 끝까지 진행하는 스케줄링이다.

      Input: 
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = left (We are moving from right to left)

Output:
Total number of seek operations = 226
Seek Sequence is
41
34
11
0
60
79
92
114
176

      처음 방향이 왼쪽으로 진행되고 끝(0)에 다다르면 오른쪽으로 방향을 전환하여 헤드에서 나머지 가장 가까운 값을 찾아서 진행해준다.

      코드를 보면 처음에 오른쪽 방향으로 진행이 되었다면 끝인 199를 넣고 왼쪽으로 방향 전환 후, 41부터 진행할 것으로 보인다.

      0까지 다다르면 방향을 전환.

      // C++ program to demonstrate 
// SCAN Disk Scheduling algorithm 

#include <bits/stdc++.h> 
using namespace std; 

int size = 8; 
int disk_size = 200; 

void SCAN(int arr[], int head, string direction) 
{ 
	int seek_count = 0; 
	int distance, cur_track; 
	vector<int> left, right; 
	vector<int> seek_sequence; 

	// appending end values 
	// which has to be visited 
	// before reversing the direction 
	if (direction == "left") 
		left.push_back(0); 
	else if (direction == "right") 
		right.push_back(disk_size - 1); 

	for (int i = 0; i < size; i++) { 
		if (arr[i] < head) 
			left.push_back(arr[i]); 
		if (arr[i] > head) 
			right.push_back(arr[i]); 
	} 

	// sorting left and right vectors 
	std::sort(left.begin(), left.end()); 
	std::sort(right.begin(), right.end()); 

	// run the while loop two times. 
	// one by one scanning right 
	// and left of the head 
	int run = 2; 
	while (run--) { 
		if (direction == "left") { 
			for (int i = left.size() - 1; i >= 0; i--) { 
				cur_track = left[i]; 

				// appending current track to seek sequence 
				seek_sequence.push_back(cur_track); 

				// calculate absolute distance 
				distance = abs(cur_track - head); 

				// increase the total count 
				seek_count += distance; 

				// accessed track is now the new head 
				head = cur_track; 
			} 
			direction = "right"; 
		} 
		else if (direction == "right") { 
			for (int i = 0; i < right.size(); i++) { 
				cur_track = right[i]; 
				// appending current track to seek sequence 
				seek_sequence.push_back(cur_track); 

				// calculate absolute distance 
				distance = abs(cur_track - head); 

				// increase the total count 
				seek_count += distance; 

				// accessed track is now new head 
				head = cur_track; 
			} 
			direction = "left"; 
		} 
	} 

	cout << "Total number of seek operations = "
		<< seek_count << endl; 

	cout << "Seek Sequence is" << endl; 

	for (int i = 0; i < seek_sequence.size(); i++) { 
		cout << seek_sequence[i] << endl; 
	} 
} 

// Driver code 
int main() 
{ 

	// request array 
	int arr[size] = { 176, 79, 34, 60, 92, 11, 41, 114 }; 
	int head = 50; 
	string direction = "left"; 

	SCAN(arr, head, direction); 

	return 0; 
}

       

       

      C-SCAN 스케줄링

      C-SCAN은 SCAN과 처음에 시작할 방향을 지정을 해주지 않으며, 한 방향으로만 가는 것이 특징이다.

      끝에 다다르게 되어도 처음부터 시작되며 오른쪽 방향으로만 서비스 요청이 이루어지는 것을 볼 수 있다.

      참고 자료에 보면 only Right Direction 이라고 나와있는데, 헤드에서부터 오직 오른쪽 방향으로만 가는 듯하다. ( 올바른 방향으로 해석하는 건 아닌 것 같다... )

      Input:  
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50

Output:
Initial position of head: 50
Total number of seek operations = 190
Seek Sequence is
60
79
92
114
176
199
0
11
34
41

      스케줄링표를 참고하면 끝에 다다르게 되면 끝(199)에서 처음(0)부터 시작하는 것을 볼 수 있으며, 진행방향은 여전히 오른쪽이다.

      #include <bits/stdc++.h> 
using namespace std; 

// Code by Vikram Chaurasia 

// C++ program to demonstrate 
// C-SCAN Disk Scheduling algorithm 

int size = 8; 
int disk_size = 200; 

void CSCAN(int arr[], int head) 
{ 
	int seek_count = 0; 
	int distance, cur_track; 
	vector<int> left, right; 
	vector<int> seek_sequence; 

	// appending end values 
	// which has to be visited 
	// before reversing the direction 
	left.push_back(0); 
	right.push_back(disk_size - 1); 

	// tracks on the left of the 
	// head will be serviced when 
	// once the head comes back 
	// to the beggining (left end). 
	for (int i = 0; i < size; i++) { 
		if (arr[i] < head) 
			left.push_back(arr[i]); 
		if (arr[i] > head) 
			right.push_back(arr[i]); 
	} 

	// sorting left and right vectors 
	std::sort(left.begin(), left.end()); 
	std::sort(right.begin(), right.end()); 

	// first service the requests 
	// on the right side of the 
	// head. 
	for (int i = 0; i < right.size(); i++) { 
		cur_track = right[i]; 
		// appending current track to seek sequence 
		seek_sequence.push_back(cur_track); 

		// calculate absolute distance 
		distance = abs(cur_track - head); 

		// increase the total count 
		seek_count += distance; 

		// accessed track is now new head 
		head = cur_track; 
	} 

	// once reached the right end 
	// jump to the beggining. 
	head = 0; 

	// Now service the requests again 
	// which are left. 
	for (int i = 0; i < left.size(); i++) { 
		cur_track = left[i]; 

		// appending current track to seek sequence 
		seek_sequence.push_back(cur_track); 

		// calculate absolute distance 
		distance = abs(cur_track - head); 

		// increase the total count 
		seek_count += distance; 

		// accessed track is now the new head 
		head = cur_track; 
	} 

	cout << "Total number of seek operations = " 
		<< seek_count << endl; 

	cout << "Seek Sequence is" << endl; 

	for (int i = 0; i < seek_sequence.size(); i++) { 
		cout << seek_sequence[i] << endl; 
	} 
} 

// Driver code 
int main() 
{ 

	// request array 
	int arr[size] = { 176, 79, 34, 60, 
					92, 11, 41, 114 }; 
	int head = 50; 

	cout << "Initial position of head: " << head << endl; 
	CSCAN(arr, head); 

	return 0; 
}

       

       

      LOOK 스케줄링

      SCAN과 마찬가지로 방향이 지정되어 있으나 시퀀스의 끝에 다다르면 가장 가까운 값을 찾고 방향을 전환하여 진행한다.

      실제로 이런 방식으론 구현되진 않는다고 한다. ( Operating system Concepts 참고 )

      Input:  
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = right (We are moving from left to right)

Output:
Initial position of head: 50
Total number of seek operations = 291
Seek Sequence is
60
79
92
114
176
41
34
11

      이번엔 오른쪽 방향으로 진행되고 있으며 시퀀스의 가장 큰 값에 도달하면 방향을 전환하고 나머지 헤드에서 가장 가까운 값을 찾아 진행한다.

      #include <bits/stdc++.h> 
using namespace std; 

// Code by Vikram Chaurasia 

// C++ program to demonstrate 
// SCAN Disk Scheduling algorithm 

int size = 8; 
int disk_size = 200; 

void LOOK(int arr[], int head, string direction) 
{ 
	int seek_count = 0; 
	int distance, cur_track; 
	vector<int> left, right; 
	vector<int> seek_sequence; 

	// appending values which are 
	// currently at left and right 
	// direction from the head. 
	for (int i = 0; i < size; i++) { 
		if (arr[i] < head) 
			left.push_back(arr[i]); 
		if (arr[i] > head) 
			right.push_back(arr[i]); 
	} 

	// sorting left and right vectors 
	// for servicing tracks in the 
	// correct sequence. 
	std::sort(left.begin(), left.end()); 
	std::sort(right.begin(), right.end()); 

	// run the while loop two times. 
	// one by one scanning right 
	// and left side of the head 
	int run = 2; 
	while (run--) { 
		if (direction == "left") { 
			for (int i = left.size() - 1; i >= 0; i--) { 
				cur_track = left[i]; 

				// appending current track to seek sequence 
				seek_sequence.push_back(cur_track); 

				// calculate absolute distance 
				distance = abs(cur_track - head); 

				// increase the total count 
				seek_count += distance; 

				// accessed track is now the new head 
				head = cur_track; 
			} 
			// reversing the direction 
			direction = "right"; 
		} 
		else if (direction == "right") { 
			for (int i = 0; i < right.size(); i++) { 
				cur_track = right[i]; 
				// appending current track to seek sequence 
				seek_sequence.push_back(cur_track); 

				// calculate absolute distance 
				distance = abs(cur_track - head); 

				// increase the total count 
				seek_count += distance; 

				// accessed track is now new head 
				head = cur_track; 
			} 
			// reversing the direction 
			direction = "left"; 
		} 
	} 

	cout << "Total number of seek operations = " 
		<< seek_count << endl; 

	cout << "Seek Sequence is" << endl; 

	for (int i = 0; i < seek_sequence.size(); i++) { 
		cout << seek_sequence[i] << endl; 
	} 
} 

// Driver code 
int main() 
{ 

	// request array 
	int arr[size] = { 176, 79, 34, 60, 
					92, 11, 41, 114 }; 
	int head = 50; 
	string direction = "right"; 

	cout << "Initial position of head: " 
		<< head << endl; 

	LOOK(arr, head, direction); 

	return 0; 
}

       

       

      C-LOOK 스케줄링

      Input:
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = right (Moving from left to right)

Output:
Initial position of head: 50
Total number of seek operations = 156
Seek Sequence is
60
79
92
114
176
11
34
41

      끝에 다다르고 헤드의 왼쪽 부분으로 갈 때에서 LOOK 스케줄링과 차이가 보인다.

      // C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 
int size = 8; 
int disk_size = 200; 

// Function to perform C-LOOK on the request 
// array starting from the given head 
void CLOOK(int arr[], int head) 
{ 
	int seek_count = 0; 
	int distance, cur_track; 
	vector<int> left, right; 
	vector<int> seek_sequence; 

	// Tracks on the left of the 
	// head will be serviced when 
	// once the head comes back 
	// to the beggining (left end) 
	for (int i = 0; i < size; i++) { 
		if (arr[i] < head) 
			left.push_back(arr[i]); 
		if (arr[i] > head) 
			right.push_back(arr[i]); 
	} 

	// Sorting left and right vectors 
	std::sort(left.begin(), left.end()); 
	std::sort(right.begin(), right.end()); 

	// First service the requests 
	// on the right side of the 
	// head 
	for (int i = 0; i < right.size(); i++) { 
		cur_track = right[i]; 

		// Appending current track to seek sequence 
		seek_sequence.push_back(cur_track); 

		// Calculate absolute distance 
		distance = abs(cur_track - head); 

		// Increase the total count 
		seek_count += distance; 

		// Accessed track is now new head 
		head = cur_track; 
	} 

	// Once reached the right end 
	// jump to the last track that 
	// is needed to be serviced in 
	// left direction 
	seek_count += abs(head - left[0]); 
	head = left[0]; 

	// Now service the requests again 
	// which are left 
	for (int i = 0; i < left.size(); i++) { 
		cur_track = left[i]; 

		// Appending current track to seek sequence 
		seek_sequence.push_back(cur_track); 

		// Calculate absolute distance 
		distance = abs(cur_track - head); 

		// Increase the total count 
		seek_count += distance; 

		// Accessed track is now the new head 
		head = cur_track; 
	} 

	cout << "Total number of seek operations = " << seek_count << endl; 

	cout << "Seek Sequence is" << endl; 

	for (int i = 0; i < seek_sequence.size(); i++) { 
		cout << seek_sequence[i] << endl; 
	} 
} 

// Driver code 
int main() 
{ 
	// Request array 
	int arr[size] = { 176, 79, 34, 60, 92, 11, 41, 114 }; 
	int head = 50; 

	cout << "Initial position of head: " << head << endl; 

	CLOOK(arr, head); 

	return 0; 
}

       

       

       

       

      혹시 잘못된 내용이 있으면 댓글로 알려주세요..!

      반응형

      'IT Tech > PS' 카테고리의 다른 글

      11652번. 카드  (0) 2020.10.02
      1978번. 소수 찾기  (0) 2020.09.27
      10250번. ACM 호텔  (0) 2020.08.14
      2775번. 부녀회장이 될테야  (0) 2020.08.08
      2869번. 달팽이는 올라가고 싶다.  (0) 2020.08.03

      관련글 관련글 더보기

    Designed by Tistory.

    티스토리툴바