[과제] 운영체제_프로세스 우선순위 큐_C언어, 최대힙 이용해서 구현하기

[코드 설명]

<Node 구조체>

우선순위 큐에 삽입, 삭제될 Node 속에는

             [프로세스 id, 우선순위, 수행시간, 도착시간] 묶음이 포함되어야 한다.

             따라서, Node 속에 포함되어야 할 정보들을 구조체로 묶어 정의해두었다,

typedef struct Node { //Node 구조체

             int pid; //프로세스 id

             int inputT; //도착시간(>0)

             int prior; //우선순위 (1~10)

             int runT; //실행시간 (5~100)

}Node;

<우선순위 큐 구조체>

노드가 삽입 삭제될 ‘우선순위 큐’를 최대힙을 이용해 구현했다.

실질적으로 노드가 삽입 삭제될 노드타입의 힙 배열과 size는 묶어서 구조체로 정의했다.

typedef struct priorQueue{ //우선순위 큐 구조체
	Node heap[MAX_ELEMENT]; 
	int size; 
} priorQueue;

<공백 우선순위 큐 생성 연산>

위에서 선언한 ‘우선순위 큐’ 구조체 크기에 맞게 메모리에 동적으로 할당해온 뒤,

             별도의 공백 우선순위 큐 생성 연산 함수를 만들어두었다.

priorQueue* createPriorQueue() { //공백 우선순위 큐 생성

             priorQueue* pQ = (priorQueue*)malloc(sizeof(priorQueue));

             pQ->size = 0; //내부 사이즈 0 초기화

             return pQ;

}

<노드 생성 연산>

노드 속에 포함되어야 할 정보들을 인수로 받아서, 노드 구조체 각 멤버에 값을 넣은 뒤

생성한 노드를 반환할 수 있도록 함수를 만들어두었다.

Node *createNode(int pid, int inputT, int prior, int runT) { //pid, inputT, prior, runT 값 받아서 
	Node* node = (Node*)malloc(sizeof(Node)); //Node타입 크기로 동적 할당해놓은 메모리 주소 얻음
	//노드 구조체 멤버에 노드 데이터들 삽입시킴
	node->pid = pid;
	node->inputT = inputT;
	node->prior = prior;
	node->runT = runT;
	return node; //생성한 노드 반환 
}

(1) 큐의 내용을 모두 보여주는 showAll()

-상/하위 노드 우선순위 관계가 깨지지 않도록 삽입, 삭제 처리했기 때문에

힙 배열에 저장된 노드들은 모두 우선순위 순으로 정리되어있을 것이다.

따라서 큐의 내용을 모두 보일 때는 힙 배열 내부를 for문으로 차례로 돌면서 출력했다

- Node [pid, inputT, (prior), runT] 꼴로 출력

void showAll(priorQueue* pQ) { //큐의 내용을 모두 보여주는 showAll() 함수 
	int i;
	printf("priorityQueue : \n");
	for (i = 1; i <= pQ->size; i++) 
	 printf("[ P%d, %d, (%d), %d ] -> ", pQ->heap[i].pid, pQ->heap[i].inputT, pQ->heap[i].prior, pQ->heap[i].runT);

}

(2) 큐에 노드 단위로 삽입하는 기능 insert(Node)

: (마지막 위치+1 ) 에 노드 임시로 삽입해둔 뒤 ,

상향식으로 부모노드 우선순위와 비교해가며 노드의 삽입 위치 찾을 것이다.

-노드 삽입받을 큐의 내부 size를 +1 확장 처리해둔다.

-인수로 받은 Node가 삽입될 위치를 임시로 확장해둔 마지막 위치로 지정해둔 뒤,

while문을 돌면서 상향식으로 부모의 우선순위와 비교해가며 노드가 삽입될 위치를 찾는다.

-찾은 삽입 위치에 인수로 들어온 Node의 데이터들을 삽입한다.

void insert(priorQueue* pQ, Node* node) { 
	int i;
	pQ->size = pQ->size + 1; //노드 삽입될 size + 1처리 
	i = pQ->size; //i에 가장 마지막 위치 노드 지칭 
	
	//노드의 삽입 위치 찾기 위해, 삽입노드의 우선순위 > 부모의 우선순위보다 높은 동안 반복하면서 
	부모노드와 자리 맞바꿔가며 삽입 위치를 찾는다. 

	while ((i != 1) && (node->prior > pQ->heap[i / 2].prior)) {
		pQ->heap[i] = pQ->heap[i / 2]; // 자식 <-> 부모
		i /= 2; //자식 인덱스는 부모노드 위치로 업데이트 후 다시 반복 
	}

	//while탈출된 i는 '우선순위'에 따라 삽입노드의 삽입위치 i를 찾은 상태. 
	//찾은 i위치에 삽입노드의 모든 데이터들을 저장 
	pQ->heap[i].inputT = node->inputT;
	pQ->heap[i].pid = node->pid;
	pQ->heap[i].prior = node->prior;
	pQ->heap[i].runT = node->runT;

}

(3) 큐의 제일 첫 번째 요소를 삭제하는 Node getFirst()

: 루트노드 위치의 데이터를 삭제하면 전체 size는 –1 처리 될 것이므로

기존 (마지막 위치)에 있던 temp 노드를 삭제할 루트노드 위치로 올려보낸 뒤,

하향식으로 자식노드 우선순위와 비교해가며 자신의 자리를 찾을 것이다.

Node getFirst(priorQueue* pQ) { 
	int parent, child; 
	Node item, temp;

	item = pQ->heap[1]; //삭제할 루트 노드를 임시 저장 
	temp = pQ->heap[pQ->size]; //삭제될 마지막 위치에 있던 노드를 temp에 임시 저장 

	pQ->size = pQ->size - 1; //기존의 마지막 위치 공간 삭제 처리 (size -1) 

	//(temp가 루트노드에서부터 아래의 자식노드와 비교해가며 자기 위치 찾을 예정)
	
	parent = 1; //부모인덱스 1 
	child = 2; //왼쪽 자식 인덱스 2 
	while (child <= pQ->size) { 

		//temp와 비교될 더 큰 자식 노드(왼 vs 오) 정함
		//자식 인덱스가 size보다 작으면서, (왼쪽 자식 우선순위 < 오른쪽 자식 우선순위) 인 경우,
		if ((child < pQ->size) && (pQ->heap[child].prior) < pQ->heap[child + 1].prior)
			 
			child++; //child값 ++ 해주고 오른쪽 자식 지칭하게 만듬 

		//temp의 우선순위가 비교할 자식 우선순위보다 큰 경우, (위치 찾은 상태) -> 탈출 
		if (temp.prior >= pQ->heap[child].prior) break;
		
		//temp의 우선순위가 자식의 우선순위보다 작은 경우, (부모 <-> 자식 위치 맞바꿈)
		else {
			pQ->heap[parent] = pQ->heap[child]; //부모 <-> 자식 맞바꿈
			parent = child; 
			child = child * 2; //자식인덱스는 더 밑으로 내려가고 계속 반복 진행
		}
	}
	pQ->heap[parent] = temp; //while 탈출 후 찾은 위치에 temp 삽입 

	return item; //삭제 노드 반환
}

<실행 main>

-공백 우선순위 큐 동적 할당해놓고, 그 위치에 20개의 노드를 삽입한 뒤,

Node [pid, inputT, (prior), runT] 꼴로 출력하고,

for문 돌면서 첫 요소 삭제 처리함

void main() {
	int i, n;
	priorQueue* pQ = createPriorQueue();
	//(pid, inputT, prior, runT)s
	
	//우선순위큐에 노드 20개 삽입 
	insert(pQ, createNode(1, 0, 6, 9));
	insert(pQ, createNode(2, 3, 7, 7));
	insert(pQ, createNode(3, 2, 8, 90));
	insert(pQ, createNode(4, 2, 10, 5));
	insert(pQ, createNode(5, 5, 9, 11));
	insert(pQ, createNode(6, 7, 1, 13));
	insert(pQ, createNode(7, 4, 2, 19));
	insert(pQ, createNode(8, 1, 3, 21));
	insert(pQ, createNode(9, 2, 4, 11));
	insert(pQ, createNode(10, 9, 5, 8));
	insert(pQ, createNode(11, 3, 8, 10));
	insert(pQ, createNode(12, 5, 7, 31));
	insert(pQ, createNode(13, 6, 10, 20));
	insert(pQ, createNode(14, 5, 3, 21));
	insert(pQ, createNode(15, 3, 7, 19));
	insert(pQ, createNode(16, 4, 2, 20));
	insert(pQ, createNode(17, 5, 8, 11));
	insert(pQ, createNode(18, 6, 1, 12));
	insert(pQ, createNode(19, 2, 8, 24));
	insert(pQ, createNode(20, 6, 3, 13));

	printf("우선순위 큐에 삽입된 노드 출력\n\n ");
	showAll(pQ);
	printf("\n\n");
	
	n = pQ->size; 
	for (i = 1; i <= n; i++) {
	 Node item = getFirst(pQ);
	 printf("\n 큐의 첫 요소 삭제 [P%d, %d, (%d), %d] ", item.pid, item.inputT, item.prior, item.runT);
	}

	getchar();
}

 

[실행결과화면]