큐 Queue

학습목표

1. 큐의 추상 자료형을 이해한다.

2. 큐의 삭제 연산과 삽입 연산에 대해서 이해한다

3. 큐를 이용한 CPU 할당 방법을 이해한다.

4. 만원 상태를 늦출 수 있는 원형 큐를 이해한다.

 

주요용어

큐 : 

한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out: FIFO) 또는 선착순 서브(First-Come-First-Serve: FCFS) 알고리즘을 갖는 순서 리스트

큐의 앞(front) : 

원소의 삭제연산이 이루어지는 곳

큐의 뒤(rear) : 

원소의 삽입연산이 이루어지는 곳

FCFS(First-Come First-Served) 스케줄링(또는 FIFO 스케줄링) : 

작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해 주는 기법

RR(Round Robin) 스케줄링 기법 : 

작업이 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받으며, 일정한 크기의 시간 할당량을 모든 작업에게 주고 그 시간동안 작업이 완료되지 못하면 준비 큐의 맨 뒤에 다시 배치되는 기법

원형 큐 : 

파이프의 입구와 출구 부분을 연결시킨 형태이며, 큐의 양 끝을 연결시켜서 원으로 만든 형태의 큐

 

 

1. 큐의 개념

큐의 의미

- 한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관

- 한쪽에서는 삽입연산 : 서비스를 받기 위한 기다림

- 다른 한쪽에서는 삭제연산 : 서비스를 받는 중

 

 

2. 큐의 추상 자료형

큐의 삽입(Add_q)연산

QueueAdd_q(queue,item)::=
	if(IsFull_q(queue))
	then{‘queueFull’을 출력한다;}
	else{큐의 rear에서 item을 삽입하고,
	큐를 반환한다; }

큐의 삭제(Delete_q)연산

ElementDelete_q(queue)::=
	if(IsEmpty_q(queue))
		then{‘queueEmpty’를 출력한다;}
	else{큐의 front에 있는
		원소를 반환한다; }

빈 큐 검사(IsEmpty_q)연산

BooleanIsEmpty_q(queue)::=
	if(rear==front)
	  then{‘TRUE’값을 반환한다;}
	else{‘FALSE’값을 반환한다;}

큐의 만원 검사(IsFull_q)연산

BooleanIsFull_q(queue,maxQueueSize)::=
	if((queue의 elements의 개수)==maxQueueSize
	  then{‘TRUE’값을 반환한다;}
	else{‘FALSE’값을 반환한다; } 

 

Add/Delete연산의 실행

① Create_q(4);

 

② Add_q(queue,‘A’);

③ Add_q(queue,‘B’);

④ Add_q(queue,‘C’);

 

⑤ Delete_q(queue);

⑥ Delete_q(queue);

⑦ Delete_q(queue);

 

⑧ Add_q(queue,‘D’);

 

 

 

3. 큐의 응용

CPU의 관리 방법

- FCFS(First-ComeFirst-Served) 스케줄링 (FIFO스케줄링)기법은

  작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해 주는 기법

 

CPU의 관리 방법

RR(RoundRobin)스케줄링 기법은

대화형 시스템에 사용되는 스케줄링 방식