[자료구조] 우선순위 큐를 이용한 머신 스케줄링

 

머신 스케줄링

 

어떤 작업을 처리하는 동일한 기계가 m개 존재하고 처리해야 할 작업이 n개 있다고 하자.

이 기계를 풀가동하여 가장 최소의 시간에 작업들을 끝내고자 한다.

이것을 머신 스케줄링이라한다.

이 문제의 최적의 해를 찾는것은 어렵지만 LPT(longest processing time first) 방법을 통해 근사의 해를 찾을 수 있다.

 

 

LPT(Longest Processing Time first)

 

LPT는 가장 긴 작업을 우선적으로 가장 먼저 사용가능하게 되는 기계에 할당하는 것이다.

 

 

 

 

맨 위의 표는 각 작업의 기계 사용 시간이다. 미리 정렬되어 있다고 가정한다.

최소 힙은 모든 기계의 종료시간을 저장하고 있다.

초기의 모든 기계의 종료시간은 0이고, 힙에서 최소 종료시간을 가지는 기계를 삭제하여 작업을 할당한다.

그리고 선택된 기계의 종료시간을 업데이트하여 다시 힙에 저장한다.

 

 

 

LPT 구현 코드

#include <stdio.h>
#define MAX_ELEMENT 200

typedef struct {
	int id;
	int avail;
}element;

typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
}HeapType;

// 생성 함수
HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}

// 초기화 함수
void init(HeapType* h) {
	h->heap_size = 0;
}

// 삽입 함수
void insert_min_heap(HeapType* h, element item) {
	int i;
	i = ++(h->heap_size);

	// 트리를 거슬러 올라가며 부모 노드보다 작으면 교환
	while ((i != 1) && (item.avail < h->heap[i / 2].avail)){
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item; // 새로운 노드 삽입
}

// 삭제 함수
element delete_min_heap(HeapType* h) {
	int parent, child;
	element item, temp;

	item = h->heap[1];
	temp = h->heap[(h->heap_size)--];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		// 현재 노드의 자식노드 중 더 작은 자식노드를 찾음
		if ((child < h->heap_size) && (h->heap[child].avail) > (h->heap[child + 1].avail))
		child++;
		if (temp.avail < h->heap[child].avail)  break;

		// 한 단계 아래로 이동 
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

#define JOBS 7
#define MACHINES 3

int main(void) {
	int jobs[JOBS] = { 8, 7, 6, 5, 3, 2, 1 }; // 작업은 정렬되어 있다고 가정
	element m = { 0, 0 }; // id와 avail은 0으로 초기화
	HeapType* h;
	h = create();
	init(h);

	for (int i = 0; i < MACHINES; i++) {
		m.id = i + 1;
		m.avail = 0; // 기계가 사용 가능하게 되는 시간
		insert_min_heap(h, m);
	}


	for (int i = 0; i < JOBS; i++) {
		m = delete_min_heap(h); // 최소 히프에서 기계를 꺼내서 작업 할당

		printf("JOB %d을 시간=%d부터 시간=%d까지 기계 %d번에 할당\n", i, m.avail, m.avail + jobs[i] - 1, m.id);
		m.avail += jobs[i]; // 사용 가능 시간 증가
		insert_min_heap(h, m); // 다시 최소 힙에 추가
	}
	return 0;
}

 

JOB 0을 시간=0부터 시간=7까지 기계 1번에 할당
JOB 1을 시간=0부터 시간=6까지 기계 2번에 할당
JOB 2을 시간=0부터 시간=5까지 기계 3번에 할당
JOB 3을 시간=6부터 시간=10까지 기계 3번에 할당
JOB 4을 시간=7부터 시간=9까지 기계 2번에 할당
JOB 5을 시간=8부터 시간=9까지 기계 1번에 할당
JOB 6을 시간=10부터 시간=10까지 기계 1번에 할당