HRRN 스케줄링
1. 개요
HRRN 스케줄링은 연결 리스트를 활용하여 구현할 수 있는 알고리즘이다. 연결 리스트 큐의 각 요소를 순회하며 기준값을 비교하고, 가장 높은 기준값을 가진 요소를 찾아 큐에서 제거한다. 요소의 비율을 비교하여 가장 높은 비율을 가진 요소를 선택하며, 이 과정을 통해 우선순위 큐를 구현할 수 있다.
-
스케줄링 알고리즘 -
스케줄링 (컴퓨팅)
스케줄링은 운영 체제가 시스템의 목적과 환경에 맞춰 작업을 관리하는 기법으로, 장기, 중기, 단기 스케줄러를 통해 프로세스를 선택하며, CPU 사용률, 처리량 등을 기준으로 평가하고, FCFS, SJF, RR 등의 알고리즘을 사용한다. -
스케줄링 알고리즘 -
선입 선출
선입 선출(FIFO)은 먼저 들어온 데이터가 먼저 나가는 큐(Queue) 형태의 자료 구조로, 컴퓨터 과학, 전자 공학, 네트워크 장비 등에서 널리 활용된다.
2. 알고리즘
HRRN 스케줄링 알고리즘은 주어진 연결 리스트 큐에서 특정 기준(비율)에 따라 요소를 제거하는 방식으로 작동한다. 큐 내의 각 요소를 순회하며 비율을 비교하고, 가장 높은 비율을 가진 요소를 찾는다. 만약 어떤 요소 N의 비율이 현재까지 찾은 가장 높은 비율을 가진 요소 M보다 높다면, M을 N으로 교체한다. 순회가 끝나면 가장 높은 비율을 가진 요소를 큐에서 제거한다.
제거할 요소가 큐의 맨 앞에 있다면, 해당 요소를 제거하고 다음 요소를 큐의 맨 앞으로 설정하여 반환한다. 제거할 요소가 큐의 맨 앞이 아니라면, 해당 요소 N의 이전 요소와 다음 요소가 서로 연결되도록 재설정하고, N을 반환한다.
2.1. 기본 원리
HRRN 스케줄링에서 사용되는 기본 원리는 다음과 같다. 연결 리스트로 구현된 큐(Queue)를 순회하며 각 요소의 우선순위를 비교한다. 이 때, 가장 높은 우선순위를 가진 요소를 찾는다. 만약 어떤 요소 N의 우선순위가 현재까지 찾은 가장 높은 우선순위를 가진 요소 M보다 높다면, M을 N으로 교체한다. 순회가 끝나면 가장 높은 우선순위를 가진 요소를 큐에서 제거한다.
제거할 요소가 큐의 맨 앞에 있다면, 해당 요소를 제거하고 다음 요소를 큐의 맨 앞으로 설정한다. 제거된 요소는 반환된다. 만약 제거할 요소가 큐의 맨 앞이 아니라면, 해당 요소 N의 이전 요소와 다음 요소가 서로 연결되도록 재설정하고, N을 반환한다.
2.2. 단계별 설명
연결 리스트 Q가 주어지면, 큐 내의 각 비율을 비교하여 가장 높은 비율을 찾기 위해 Q를 반복한다. 요소 N의 비율이 가장 높은 비율을 가진 요소 M의 비율보다 크면, 목록에서 가장 높은 비율 요소인 요소 M을 요소 N으로 교체한다. 목록의 끝에 도달하면 가장 높은 비율의 요소를 큐에서 제거한다. 요소가 목록의 시작 부분에 있으면 큐에서 제거하고 목록을 다음 요소로 설정하여 요소를 반환한다. 그렇지 않으면 N의 이웃이 서로를 다음 및 이전 이웃으로 재할당하여 N의 결과를 반환한다.