자료구조 강의 4화 :: 큐, Round Robin, 원형큐

자료구조 4화를 듣고 배운내용

 

 

KEYWORDS

큐: 먼저 삽임된 원소가 먼저 삭제(First In First Out: FIFO)

스택과 유사하게 입출력 순서를 중심으로 자료간의 관계 성립되는 자료구조

줄을 서는 순서에 따라 공평하게 서비스를 해주는 경우에 많이 사용

큐의 앞(front): 원소의 삭제 연산이 이루어진다.

큐의 뒤(rear): 원소의 삽입 연산이 이루어진다

 

FCFS(First Come First Served) 스케줄링: 작업이 큐에 도착한 순서대로 CPU를 할당받도록 해주는 기법

RR(Round Robin) 스케줄링: 기본적으로 도착한 순서대로 CPU 할당되지만, CPU 시간 할당량, 시간 간격에 의해 제한, 일정한 크기의 시간 할당량을 모든 작업에 주고 그 시간동안 작업이 완료되지 못하면 큐의 맨 뒤에 다시 배치

원형 큐: 큐의 양 끝을 연결시켜서 원으로 만든 형태의 큐

 

 

큐

한쪽에서는 데이터 삽입연산만 발생, 다른 한쪽에는 삭제 연산만 발생하는 양쪽이 뚫린 관

삽입연산: 서비스를 받기 위한 기다림

삭제연산: 서비스를 받는 중

 

삽입시에는 rear가 front의 반대 반향으로 이동하고 값이 들어온다.

삭제시에는 front가 rear방향으로 이동되어 가르키게 되는거다

 

큐가 비어 있는 상태

삭제, 즉 front의 이동이 반복되면 front와 rear가 가르키는게 같아진다 이러면 큐가 비어있는 상태

 

큐의 예시

버스, 택시 타려고 서 있는 줄

 

Rround Robin 예시

가정: CPU 쓸 수 있는 시간을 10분으로 제한

A: 15

B: 7

 

그럼 A는 10분 쓰고 5분 남은 상태에서

B: 7

A: 5

뒤로 들어온다

 

원형큐

큐의 만원 상태를 해결하기 위한 방법

연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 '나머지 연산자'를 사용한다고 한다

 

어라? 비어있는 상태?

rear와 front가 같으면 full일수도, empty일수도

이 부분은 코드를 추가해서 찾아봐야 된다.

 

장단

장: 메모리를 효율적으로 사용할 수 있지만

단: 비어있는 상태때문에 프로그래밍이 조금 귀찮다.

선택은 개발자의 몫