이미지 로딩 중...
AI Generated
2025. 11. 6. · 3 Views
원형 연결 리스트 활용 패턴 완벽 가이드
원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 특별한 자료구조입니다. 라운드 로빈 스케줄링, 멀티플레이어 게임, 무한 루프 재생 등 실무에서 자주 마주치는 문제들을 우아하게 해결할 수 있습니다. 이 가이드에서는 원형 연결 리스트의 핵심 활용 패턴 8가지를 실전 예제와 함께 배워봅니다.
목차
- 원형 연결 리스트 기본 구현
- 라운드 로빈 스케줄러
- 조세푸스 문제 해결
- 무한 재생 플레이리스트
- 멀티플레이어 턴 관리
- 순환 버퍼 구현
- LRU 캐시 최적화
- 타임 슬라이싱 CPU 스케줄러
1. 원형 연결 리스트 기본 구현
시작하며
여러분이 멀티플레이어 게임을 개발하거나 작업 스케줄러를 만들 때, 끝에 도달하면 다시 처음으로 돌아가야 하는 상황을 겪어본 적 있나요? 배열로 구현하면 인덱스를 0으로 되돌리는 조건문을 계속 작성해야 하고, 코드가 지저분해집니다.
이런 문제는 실제 개발 현장에서 자주 발생합니다. 특히 라운드 로빈 알고리즘, 게임의 턴 시스템, 무한 반복 재생 등에서 순환 구조가 필요한데, 일반적인 선형 자료구조로는 이를 자연스럽게 표현하기 어렵습니다.
바로 이럴 때 필요한 것이 원형 연결 리스트입니다. 마지막 노드가 첫 번째 노드를 가리키도록 연결하면, 별도의 조건문 없이도 자연스럽게 순환하는 구조를 만들 수 있습니다.
개요
간단히 말해서, 원형 연결 리스트는 마지막 노드의 next 포인터가 첫 번째 노드를 가리키는 연결 리스트입니다. 일반 연결 리스트에서는 마지막 노드의 next가 null이지만, 원형 연결 리스트에서는 head를 가리킵니다.
이렇게 하면 어느 노드에서든 계속 next를 따라가면 모든 노드를 순회할 수 있습니다. 예를 들어, 플레이어가 4명인 보드게임에서 턴을 관리할 때 4번 플레이어 다음에 자동으로 1번 플레이어로 돌아가는 구조를 구현할 수 있습니다.
기존에는 배열과 인덱스로 관리하면서 index = (index + 1) % array.length 같은 연산을 계속 해야 했다면, 이제는 단순히 current = current.next만으로 순환할 수 있습니다. 원형 연결 리스트의 핵심 특징은 첫째, 끝이 없는 순환 구조이며, 둘째, 어느 노드에서든 시작할 수 있고, 셋째, 중간 삽입/삭제가 효율적이라는 점입니다.
이러한 특징들이 실시간 스케줄링이나 게임 로직에서 코드를 훨씬 간결하고 직관적으로 만들어줍니다.
코드 예제
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 리스트의 끝에 새 노드 추가
append(data) {
const newNode = new Node(data);
if (!this.head) {
// 첫 번째 노드: 자기 자신을 가리킴
this.head = newNode;
newNode.next = this.head;
} else {
// 마지막 노드를 찾아서 연결
let current = this.head;
while (current.next !== this.head) {
current = current.next;
}
current.next = newNode;
newNode.next = this.head; // 원형 구조 유지
}
this.size++;
}
// 전체 리스트 순회 출력
display() {
if (!this.head) return [];
const result = [];
let current = this.head;
do {
result.push(current.data);
current = current.next;
} while (current !== this.head);
return result;
}
}
설명
이것이 하는 일: 원형 연결 리스트는 노드들을 연결하되, 마지막 노드가 다시 처음으로 돌아가는 순환 구조를 만듭니다. 첫 번째로, Node 클래스는 데이터와 다음 노드를 가리키는 포인터를 담당합니다.
일반 연결 리스트의 노드와 동일한 구조이지만, 사용 방식이 다릅니다. 원형 구조에서는 어떤 노드도 null을 가리키지 않고, 항상 다른 노드(또는 자기 자신)를 가리킵니다.
그 다음으로, append 메서드가 실행되면서 새 노드를 추가합니다. 내부에서는 두 가지 경우를 처리하는데, 첫 번째는 리스트가 비어있을 때입니다.
이 경우 새 노드가 head가 되고, 자기 자신의 next를 자기 자신으로 설정하여 1개 노드로 이루어진 원을 만듭니다. 두 번째는 이미 노드가 있을 때인데, 마지막 노드를 찾아서 그 노드의 next를 새 노드로, 새 노드의 next를 head로 연결하여 원형 구조를 유지합니다.
마지막으로, display 메서드가 do-while 루프를 사용하여 리스트를 순회합니다. 최종적으로 head부터 시작해서 다시 head로 돌아올 때까지 모든 데이터를 배열로 반환합니다.
일반 while 루프 대신 do-while을 사용하는 이유는 최소한 한 번은 실행되어야 단일 노드인 경우도 처리할 수 있기 때문입니다. 여러분이 이 코드를 사용하면 순환이 필요한 모든 상황에서 깔끔한 코드를 작성할 수 있습니다.
배열의 인덱스를 관리할 필요가 없고, 경계 조건을 신경 쓸 필요도 없으며, 삽입과 삭제도 O(1) 시간에 가능합니다(포인터만 알고 있다면).
실전 팁
💡 순환 감지가 중요합니다. 순회할 때는 항상 do-while을 사용하거나 카운터를 두어 무한 루프를 방지하세요. current !== this.head 조건으로 한 바퀴 돌았는지 확인하는 것이 핵심입니다.
💡 빈 리스트 체크를 항상 먼저 하세요. head가 null인지 확인하지 않으면 do-while에서 오류가 발생합니다. 방어적 프로그래밍의 기본입니다.
💡 단일 노드일 때 자기 자신을 가리키도록 설정하는 것을 잊지 마세요. newNode.next = this.head를 설정하지 않으면 원형 구조가 깨집니다.
💡 디버깅 시 무한 루프에 빠지기 쉬우므로, 개발 중에는 최대 반복 횟수 제한을 두는 것이 좋습니다. 예: for(let i=0; i<this.size && i<100; i++)
💡 메모리 누수 방지를 위해 노드를 삭제할 때는 반드시 next 참조를 끊어주세요. 순환 구조는 가비지 컬렉터가 자동으로 회수하기 어려울 수 있습니다.
2. 라운드 로빈 스케줄러
시작하며
여러분이 작업 큐 시스템을 만들거나 멀티태스킹 시뮬레이터를 개발할 때, 각 작업에게 공평하게 CPU 시간을 분배해야 하는 상황을 마주한 적 있나요? 어떤 작업이 CPU를 독점하지 않고, 모든 작업이 순서대로 조금씩 실행 기회를 얻어야 합니다.
이런 문제는 운영체제의 프로세스 스케줄링, 웹 서버의 요청 처리, 게임의 AI 업데이트 등 실시간 시스템에서 핵심적인 과제입니다. 단순히 큐로 구현하면 작업을 완료한 후 다시 큐의 끝에 넣는 오버헤드가 발생하고, 코드가 복잡해집니다.
바로 이럴 때 필요한 것이 원형 연결 리스트 기반 라운드 로빈 스케줄러입니다. 현재 작업이 끝나면 단순히 next로 이동하기만 하면 자동으로 다음 작업으로 넘어가고, 끝에 도달하면 자연스럽게 처음으로 돌아갑니다.
개요
간단히 말해서, 라운드 로빈 스케줄러는 각 작업에게 동일한 시간 할당량(time quantum)을 주고 순환하며 실행하는 공정한 스케줄링 알고리즘입니다. 원형 연결 리스트로 구현하면 작업들이 원 형태로 연결되어 있어서, 현재 포인터만 이동하면 됩니다.
작업이 완료되지 않았다면 다음 순회에서 다시 실행될 기회를 얻습니다. 예를 들어, 3개의 서버가 있고 요청을 분산 처리해야 할 때, 각 서버에 순서대로 요청을 할당하다가 자동으로 첫 번째 서버로 돌아가는 로드 밸런서를 쉽게 만들 수 있습니다.
기존에는 배열로 큐를 만들고 작업을 꺼냈다가 다시 넣는 dequeue/enqueue 작업을 반복해야 했다면, 이제는 포인터만 한 칸 이동하면 됩니다. 라운드 로빈의 핵심 특징은 첫째, 모든 작업이 공평한 실행 기회를 얻고, 둘째, 기아 상태(starvation)가 발생하지 않으며, 셋째, 응답 시간이 예측 가능하다는 점입니다.
이러한 특징들이 실시간 시스템에서 안정적이고 공정한 자원 분배를 가능하게 합니다.
코드 예제
class Task {
constructor(id, burstTime) {
this.id = id;
this.burstTime = burstTime; // 남은 실행 시간
this.next = null;
}
}
class RoundRobinScheduler {
constructor(timeQuantum = 2) {
this.head = null;
this.current = null;
this.timeQuantum = timeQuantum; // 각 작업에 할당되는 시간
}
addTask(id, burstTime) {
const newTask = new Task(id, burstTime);
if (!this.head) {
this.head = newTask;
newTask.next = this.head;
this.current = this.head;
} else {
let temp = this.head;
while (temp.next !== this.head) {
temp = temp.next;
}
temp.next = newTask;
newTask.next = this.head;
}
}
// 한 사이클 실행: 모든 작업에 시간 할당
executeRound() {
if (!this.head) return null;
const executed = [];
let startTask = this.current;
do {
const task = this.current;
const timeUsed = Math.min(this.timeQuantum, task.burstTime);
task.burstTime -= timeUsed;
executed.push({
id: task.id,
timeUsed,
remaining: task.burstTime
});
// 작업 완료 시 제거
if (task.burstTime === 0) {
this.removeTask(task.id);
}
if (this.current) {
this.current = this.current.next;
}
} while (this.current && this.current !== startTask);
return executed;
}
removeTask(taskId) {
if (!this.head) return;
let current = this.head;
let prev = null;
// 마지막 노드 찾기
while (current.next !== this.head) {
prev = current;
current = current.next;
}
// 삭제할 노드 찾기
let target = this.head;
let beforeTarget = current; // 마지막 노드
do {
if (target.id === taskId) {
if (target === this.head && target.next === this.head) {
// 유일한 노드
this.head = null;
this.current = null;
} else {
if (target === this.head) {
this.head = target.next;
}
beforeTarget.next = target.next;
if (this.current === target) {
this.current = target.next;
}
}
return;
}
beforeTarget = target;
target = target.next;
} while (target !== this.head);
}
}
설명
이것이 하는 일: 라운드 로빈 스케줄러는 여러 작업을 공평하게 돌아가며 실행하고, 시간 할당량만큼 처리한 후 다음 작업으로 자동 전환합니다. 첫 번째로, Task 클래스는 작업 ID와 남은 실행 시간(burstTime)을 관리합니다.
burstTime은 작업이 완료되기까지 필요한 시간을 나타내며, 매 실행마다 감소합니다. 이 값이 0이 되면 작업이 완료된 것입니다.
그 다음으로, executeRound 메서드가 한 사이클을 실행합니다. 내부에서는 현재 작업부터 시작해서 원을 한 바퀴 돌면서 각 작업에 timeQuantum만큼의 시간을 할당합니다.
Math.min을 사용하여 남은 시간이 timeQuantum보다 적으면 남은 시간만큼만 실행합니다. 각 작업을 실행할 때마다 executed 배열에 기록하여 나중에 분석할 수 있게 합니다.
세 번째로, 작업이 완료되면(burstTime === 0) removeTask를 호출하여 리스트에서 제거합니다. 이때 원형 구조를 유지하면서 안전하게 노드를 제거하는 것이 핵심인데, 이전 노드의 next를 다음 노드로 연결하고, current 포인터가 삭제된 노드를 가리키고 있다면 다음 노드로 이동시킵니다.
마지막으로, 다음 작업으로 이동하는 것은 단순히 this.current = this.current.next로 처리됩니다. 원형 구조 덕분에 마지막 작업 다음은 자동으로 첫 번째 작업이 되어, 별도의 인덱스 계산이나 조건문이 필요 없습니다.
여러분이 이 코드를 사용하면 CPU 스케줄링, 로드 밸런싱, 턴 기반 시스템 등을 깔끔하게 구현할 수 있습니다. 모든 작업이 공평한 기회를 얻고, 응답 시간이 예측 가능하며, 우선순위가 낮은 작업도 무한정 대기하지 않습니다.
실전 팁
💡 timeQuantum 값을 적절히 조정하는 것이 성능의 핵심입니다. 너무 작으면 컨텍스트 스위칭 오버헤드가 크고, 너무 크면 응답 시간이 길어집니다. 일반적으로 10-100ms 정도가 적절합니다.
💡 작업 제거 시 포인터 관리를 신중히 하세요. current가 삭제되는 노드를 가리키고 있다면 반드시 다음 노드로 이동시켜야 무한 루프나 null 참조를 방지할 수 있습니다.
💡 통계 정보를 기록하면 스케줄러 성능을 분석할 수 있습니다. 각 작업의 대기 시간, 응답 시간, 완료 시간을 추적하여 평균 대기 시간 등을 계산하세요.
💡 우선순위를 추가하려면 각 Task에 priority 필드를 추가하고, 높은 우선순위 작업에는 더 큰 timeQuantum을 할당하는 방식으로 확장할 수 있습니다.
💡 실제 운영체제에서는 I/O 대기 중인 작업을 별도로 처리합니다. 작업 상태(ready, running, waiting)를 추가하여 더 현실적인 스케줄러를 만들 수 있습니다.
3. 조세푸스 문제 해결
시작하며
여러분이 알고리즘 인터뷰를 준비하거나 수학적 퍼즐을 풀 때, N명이 원형으로 앉아서 K번째 사람을 계속 제거하는 문제를 본 적 있나요? 이것이 바로 유명한 조세푸스 문제입니다.
이런 문제는 코딩 인터뷰에서 자주 출제되며, 원형 구조와 순차 제거를 동시에 다루는 능력을 테스트합니다. 배열로 풀면 제거된 사람을 표시하고 인덱스를 계산하는 것이 복잡하고, 실수하기 쉽습니다.
바로 이럴 때 필요한 것이 원형 연결 리스트입니다. 사람들을 노드로 연결하고, K번째마다 노드를 제거하면서 포인터를 이동하면 문제가 아주 직관적으로 풀립니다.
개요
간단히 말해서, 조세푸스 문제는 N명이 원을 이루어 앉고, K번째 사람을 계속 제거하여 마지막 남은 사람을 찾는 문제입니다. 원형 연결 리스트로 구현하면 실제 사람들이 원형으로 앉은 것처럼 자연스럽게 표현됩니다.
현재 위치에서 K번 이동하고, 그 위치의 사람을 제거하고, 다시 K번 이동하는 과정을 한 명만 남을 때까지 반복합니다. 예를 들어, 7명이 앉아있고 3번째마다 제거한다면, 3번 → 6번 → 2번 → 7번 → 5번 → 1번 순으로 제거되어 4번이 최종 생존자가 됩니다.
기존에는 배열에 제거 플래그를 두고 인덱스를 순환하며 카운트하는 방식이었다면, 이제는 실제로 노드를 제거하면서 자연스럽게 순환할 수 있습니다. 조세푸스 문제의 핵심 특징은 첫째, 순환 제거 패턴이며, 둘째, 리스트가 계속 줄어든다는 점이고, 셋째, 마지막 생존자를 찾는 것이 목표입니다.
이러한 특징들이 원형 연결 리스트와 완벽하게 맞아떨어져, 이 자료구조의 교과서적인 활용 사례가 됩니다.
코드 예제
class JosephusSolver {
constructor(n) {
this.head = null;
this.size = n;
// n명의 사람을 원형으로 연결
for (let i = 1; i <= n; i++) {
this.addPerson(i);
}
}
addPerson(id) {
const newNode = new Node(id);
if (!this.head) {
this.head = newNode;
newNode.next = this.head;
} else {
let current = this.head;
while (current.next !== this.head) {
current = current.next;
}
current.next = newNode;
newNode.next = this.head;
}
}
// k번째마다 제거하며 마지막 생존자 찾기
solve(k) {
if (!this.head) return null;
let current = this.head;
const eliminationOrder = [];
// 한 명만 남을 때까지 반복
while (current.next !== current) {
// k-1번 이동 (k번째 사람에 도달)
for (let i = 1; i < k; i++) {
current = current.next;
}
// 다음 사람 제거
const eliminated = current.next;
eliminationOrder.push(eliminated.data);
current.next = eliminated.next;
// 제거된 사람이 head였다면 업데이트
if (eliminated === this.head) {
this.head = current.next;
}
// 다음 사람으로 이동
current = current.next;
}
return {
survivor: current.data,
eliminationOrder
};
}
}
// 사용 예시
const josephus = new JosephusSolver(7);
const result = josephus.solve(3);
console.log(`생존자: ${result.survivor}`); // 생존자: 4
console.log(`제거 순서: ${result.eliminationOrder.join(' → ')}`);
설명
이것이 하는 일: 조세푸스 솔버는 N명을 원형 연결 리스트로 만들고, K번째마다 한 명씩 제거하면서 마지막 생존자와 제거 순서를 추적합니다. 첫 번째로, 생성자에서 1부터 N까지 번호가 매겨진 사람들을 원형 리스트로 연결합니다.
addPerson 메서드를 반복 호출하여 각 사람을 노드로 추가하고, 마지막 사람의 next를 첫 번째 사람으로 연결하여 원을 완성합니다. 이렇게 하면 실제로 사람들이 원탁에 앉은 것과 동일한 구조가 만들어집니다.
그 다음으로, solve 메서드의 핵심은 while 루프입니다. 내부에서는 current.next !== current 조건으로 단 한 명만 남았는지 확인합니다.
한 명만 남으면 그 사람의 next가 자기 자신을 가리키기 때문입니다. 루프 안에서는 k-1번 이동하여 k번째 위치에 도달합니다(현재 위치를 1로 카운트하므로).
세 번째로, k번째 위치에 도달하면 그 다음 사람(current.next)을 제거합니다. 제거는 current.next를 eliminated.next로 변경하여 제거된 노드를 건너뛰도록 합니다.
이때 제거된 사람의 데이터를 eliminationOrder 배열에 기록하여 나중에 제거 순서를 확인할 수 있게 합니다. 마지막으로, 제거 후 current를 다음 위치로 이동시키고 다시 k번 카운트를 시작합니다.
이 과정을 반복하다 보면 결국 한 명만 남게 되고, 그 사람이 최종 생존자입니다. 생존자의 번호와 전체 제거 순서를 객체로 반환하여 문제 해결 과정을 완전히 추적할 수 있습니다.
여러분이 이 코드를 사용하면 조세푸스 문제뿐만 아니라 순환 제거 패턴이 필요한 모든 문제를 쉽게 해결할 수 있습니다. 게임에서 플레이어 탈락 시스템, 자원 할당 시뮬레이션, 수학적 퍼즐 등에 응용할 수 있습니다.
실전 팁
💡 k=1일 때는 단순히 순서대로 제거되므로 마지막 사람이 생존자입니다. k=n일 때는 매번 한 바퀴를 도는 것이므로 패턴을 미리 예측할 수 있습니다.
💡 수학적 공식도 존재합니다: f(n,k) = (f(n-1,k) + k) % n. 큰 n에 대해서는 재귀나 반복문으로 공식을 사용하는 것이 더 효율적일 수 있습니다(O(n) vs O(nk)).
💡 제거 순서를 기록하는 것이 디버깅에 매우 유용합니다. 예상한 순서와 다르다면 k 카운팅이나 포인터 이동에 문제가 있을 가능성이 큽니다.
💡 변형 문제로 양방향 원형 연결 리스트를 사용하면 역방향 카운팅도 가능합니다. 시계방향/반시계방향을 번갈아가며 제거하는 문제에 활용할 수 있습니다.
💡 실제 인터뷰에서는 재귀적 해법도 요구될 수 있습니다. 원형 리스트 방법을 먼저 보여주고, 시간 복잡도를 개선하기 위해 수학적 접근도 설명하면 좋은 인상을 줍니다.
4. 무한 재생 플레이리스트
시작하며
여러분이 음악 플레이어나 슬라이드쇼 앱을 만들 때, 마지막 곡이 끝나면 자동으로 첫 곡부터 다시 재생되어야 하는 기능을 구현해본 적 있나요? 사용자는 "반복 재생" 버튼을 누르지 않아도 끝없이 음악이 이어지길 원합니다.
이런 문제는 미디어 플레이어, 광고 배너 로테이션, 자동 슬라이드쇼 등에서 필수적입니다. 배열로 구현하면 인덱스가 끝에 도달했는지 확인하고 0으로 리셋하는 로직을 추가해야 하며, next/previous 버튼 처리도 복잡해집니다.
바로 이럴 때 필요한 것이 원형 연결 리스트 기반 플레이리스트입니다. 현재 재생 중인 곡에서 next를 호출하면 자동으로 다음 곡으로 넘어가고, 마지막 곡에서도 자연스럽게 첫 곡으로 돌아갑니다.
개요
간단히 말해서, 무한 재생 플레이리스트는 곡들을 원형으로 연결하여 끝없이 순환 재생되는 음악 재생 시스템입니다. 원형 연결 리스트로 구현하면 각 곡이 노드가 되고, 마지막 곡의 next가 첫 곡을 가리킵니다.
현재 재생 위치를 가리키는 포인터만 관리하면 next(), previous(), shuffle() 같은 기능을 모두 깔끔하게 구현할 수 있습니다. 예를 들어, 10곡 플레이리스트에서 10번 곡 재생 중 next를 누르면 자동으로 1번 곡이 재생되고, 1번 곡에서 previous를 누르면 10번 곡으로 이동합니다.
기존에는 currentIndex를 관리하고 (index + 1) % length, (index - 1 + length) % length 같은 모듈러 연산을 해야 했다면, 이제는 포인터만 앞뒤로 움직이면 됩니다. 무한 플레이리스트의 핵심 특징은 첫째, 경계가 없는 순환 재생이며, 둘째, 곡 추가/삭제가 유연하고, 셋째, 현재 위치에서 양방향 이동이 가능하다는 점입니다.
이러한 특징들이 사용자에게 끊김 없는 음악 감상 경험을 제공합니다.
코드 예제
class Song {
constructor(title, artist) {
this.title = title;
this.artist = artist;
this.next = null;
this.prev = null; // 양방향 연결
}
}
class CircularPlaylist {
constructor() {
this.head = null;
this.current = null;
this.size = 0;
}
// 플레이리스트에 곡 추가
addSong(title, artist) {
const newSong = new Song(title, artist);
if (!this.head) {
this.head = newSong;
newSong.next = newSong;
newSong.prev = newSong; // 자기 자신을 가리킴
this.current = this.head;
} else {
const tail = this.head.prev;
tail.next = newSong;
newSong.prev = tail;
newSong.next = this.head;
this.head.prev = newSong;
}
this.size++;
}
// 다음 곡으로 이동
next() {
if (!this.current) return null;
this.current = this.current.next;
return this.getNowPlaying();
}
// 이전 곡으로 이동
previous() {
if (!this.current) return null;
this.current = this.current.prev;
return this.getNowPlaying();
}
// 현재 재생 중인 곡 정보
getNowPlaying() {
if (!this.current) return null;
return {
title: this.current.title,
artist: this.current.artist,
position: this.getCurrentPosition(),
total: this.size
};
}
// 현재 위치 계산 (디스플레이용)
getCurrentPosition() {
if (!this.current) return 0;
let position = 1;
let temp = this.head;
while (temp !== this.current) {
temp = temp.next;
position++;
}
return position;
}
// 전체 플레이리스트 출력
displayAll() {
if (!this.head) return [];
const songs = [];
let temp = this.head;
do {
songs.push(`${temp.title} - ${temp.artist}`);
temp = temp.next;
} while (temp !== this.head);
return songs;
}
}
설명
이것이 하는 일: 무한 재생 플레이리스트는 곡들을 양방향 원형 구조로 연결하여, 앞뒤로 자유롭게 이동하면서 끝없이 재생되는 시스템을 만듭니다. 첫 번째로, Song 클래스는 next와 prev 두 개의 포인터를 가집니다.
단방향 원형 리스트와 달리 양방향으로 연결하여 이전 곡으로도 쉽게 이동할 수 있게 합니다. 이것이 실제 음악 플레이어의 previous 버튼을 구현하는 핵심입니다.
그 다음으로, addSong 메서드가 새 곡을 추가할 때 양방향 연결을 유지합니다. 내부에서는 head.prev를 사용하여 마지막 곡(tail)에 빠르게 접근합니다.
원형 구조에서는 head의 이전 노드가 바로 마지막 노드이기 때문입니다. 새 곡을 tail 다음에 연결하고, head의 prev를 새 곡으로 업데이트하여 원형 구조를 완성합니다.
세 번째로, next()와 previous() 메서드는 놀랍도록 간단합니다. 단순히 current 포인터를 앞이나 뒤로 한 칸 이동하기만 하면 됩니다.
마지막 곡에서 next를 호출하면 자동으로 첫 곡으로, 첫 곡에서 previous를 호출하면 자동으로 마지막 곡으로 이동합니다. 조건문이나 모듈러 연산이 전혀 필요 없습니다.
마지막으로, getNowPlaying()은 현재 재생 중인 곡의 정보를 UI에 표시할 수 있는 형태로 반환합니다. getCurrentPosition()을 호출하여 "3/10" 같은 형식으로 현재 위치를 보여줄 수 있습니다.
이는 사용자 경험을 위한 것이며, 내부 동작과는 독립적입니다. 여러분이 이 코드를 사용하면 음악 플레이어, 이미지 슬라이더, 광고 로테이터, 자동 슬라이드쇼 등 순환이 필요한 모든 UI 컴포넌트를 깔끔하게 구현할 수 있습니다.
곡 추가/삭제도 유연하고, 셔플 기능도 쉽게 확장할 수 있습니다.
실전 팁
💡 양방향 연결은 메모리를 더 사용하지만 previous 기능을 O(1)에 제공합니다. 단방향으로만 구현하면 previous가 O(n)이 되어 사용자 경험이 나빠집니다.
💡 현재 재생 곡을 삭제할 때는 반드시 current를 다음 곡으로 이동시킨 후 삭제하세요. 그렇지 않으면 current가 삭제된 노드를 가리켜 오류가 발생합니다.
💡 셔플 기능을 추가하려면 배열로 변환 → Fisher-Yates 알고리즘으로 섞기 → 다시 원형 리스트로 재구성하는 방식을 사용할 수 있습니다.
💡 반복 재생 모드 종류(한 곡 반복, 전체 반복, 반복 안 함)를 지원하려면 mode 필드를 추가하고, next() 메서드에서 mode에 따라 동작을 분기하세요.
💡 실제 플레이어에서는 곡 길이 정보를 추가하여 전체 재생 시간을 계산하고, 프로그레스 바를 구현할 수 있습니다. Song 클래스에 duration 필드를 추가하세요.
5. 멀티플레이어 턴 관리
시작하며
여러분이 보드게임이나 턴 기반 전략 게임을 개발할 때, 플레이어들의 턴을 순서대로 관리하고 각 플레이어가 행동을 마치면 자동으로 다음 플레이어로 넘어가야 하는 시스템을 만든 적 있나요? 플레이어가 중간에 나가거나 새로 들어올 수도 있어야 합니다.
이런 문제는 멀티플레이어 게임 개발의 핵심입니다. 턴 순서를 엄격히 지키면서도, 동적으로 플레이어를 추가/제거할 수 있어야 하며, 마지막 플레이어 다음에는 자연스럽게 첫 번째 플레이어로 돌아가야 합니다.
배열로 관리하면 플레이어 제거 시 인덱스를 재조정하는 것이 복잡합니다. 바로 이럴 때 필요한 것이 원형 연결 리스트 기반 턴 매니저입니다.
플레이어들을 원형으로 연결하고, 현재 턴 포인터만 이동시키면 자동으로 다음 플레이어로 넘어가며, 플레이어 제거도 포인터 연결만 변경하면 됩니다.
개요
간단히 말해서, 턴 매니저는 플레이어들을 원형으로 배치하고 순서대로 턴을 부여하며, 각 플레이어의 행동을 추적하는 게임 시스템입니다. 원형 연결 리스트로 구현하면 플레이어들이 실제로 테이블에 둘러앉은 것처럼 자연스럽게 표현됩니다.
현재 플레이어가 턴을 끝내면 next로 이동하고, 플레이어가 게임을 떠나면 그 노드만 제거하면 나머지는 자동으로 연결됩니다. 예를 들어, 4명이 카드게임을 하다가 2번 플레이어가 나가면, 1번 → 3번 → 4번 → 1번으로 자연스럽게 턴이 이어집니다.
기존에는 플레이어 배열과 currentIndex를 관리하고, 플레이어 제거 시 splice하고 인덱스를 조정해야 했다면, 이제는 노드를 제거하고 포인터만 다음으로 이동시키면 됩니다. 턴 매니저의 핵심 특징은 첫째, 동적 플레이어 관리가 가능하고, 둘째, 턴 순서가 자동으로 순환하며, 셋째, 각 플레이어의 상태(점수, 행동 등)를 함께 관리할 수 있다는 점입니다.
이러한 특징들이 실시간 멀티플레이어 게임의 안정적인 턴 시스템을 만들어줍니다.
코드 예제
class Player {
constructor(id, name) {
this.id = id;
this.name = name;
this.score = 0;
this.isActive = true;
this.next = null;
}
}
class TurnManager {
constructor() {
this.head = null;
this.currentPlayer = null;
this.turnNumber = 0;
this.playerCount = 0;
}
// 플레이어 추가
addPlayer(id, name) {
const newPlayer = new Player(id, name);
if (!this.head) {
this.head = newPlayer;
newPlayer.next = this.head;
this.currentPlayer = this.head;
} else {
let temp = this.head;
while (temp.next !== this.head) {
temp = temp.next;
}
temp.next = newPlayer;
newPlayer.next = this.head;
}
this.playerCount++;
return newPlayer;
}
// 다음 플레이어로 턴 넘기기
nextTurn() {
if (!this.currentPlayer) return null;
this.currentPlayer = this.currentPlayer.next;
this.turnNumber++;
return {
player: this.currentPlayer,
turnNumber: this.turnNumber,
round: Math.floor(this.turnNumber / this.playerCount) + 1
};
}
// 현재 플레이어 정보
getCurrentTurn() {
if (!this.currentPlayer) return null;
return {
id: this.currentPlayer.id,
name: this.currentPlayer.name,
score: this.currentPlayer.score,
turnNumber: this.turnNumber,
isActive: this.currentPlayer.isActive
};
}
// 플레이어 제거 (게임 떠남)
removePlayer(playerId) {
if (!this.head) return false;
let current = this.head;
let prev = null;
// 마지막 노드 찾기
while (current.next !== this.head) {
prev = current;
current = current.next;
}
// 제거할 플레이어 찾기
let target = this.head;
let beforeTarget = current;
do {
if (target.id === playerId) {
// 유일한 플레이어인 경우
if (target.next === target) {
this.head = null;
this.currentPlayer = null;
} else {
// head 업데이트
if (target === this.head) {
this.head = target.next;
}
// 현재 턴 플레이어가 제거되는 경우
if (target === this.currentPlayer) {
this.currentPlayer = target.next;
}
beforeTarget.next = target.next;
}
this.playerCount--;
return true;
}
beforeTarget = target;
target = target.next;
} while (target !== this.head);
return false;
}
// 플레이어 점수 업데이트
updateScore(playerId, points) {
if (!this.head) return false;
let current = this.head;
do {
if (current.id === playerId) {
current.score += points;
return true;
}
current = current.next;
} while (current !== this.head);
return false;
}
// 모든 플레이어 순위
getLeaderboard() {
if (!this.head) return [];
const players = [];
let current = this.head;
do {
players.push({
id: current.id,
name: current.name,
score: current.score
});
current = current.next;
} while (current !== this.head);
return players.sort((a, b) => b.score - a.score);
}
}
설명
이것이 하는 일: 턴 매니저는 멀티플레이어 게임에서 플레이어들의 순서를 관리하고, 각 턴마다 다음 플레이어로 자동 전환하며, 점수와 상태를 추적합니다. 첫 번째로, Player 클래스는 게임에 필요한 플레이어 정보를 담습니다.
id와 name은 식별용이고, score는 게임 진행 중 획득한 점수, isActive는 현재 활성 상태를 나타냅니다. 이 정보들이 게임 UI에 표시되고, 승자 결정에 사용됩니다.
그 다음으로, nextTurn() 메서드가 턴을 진행합니다. 내부에서는 단순히 currentPlayer를 next로 이동시키고, turnNumber를 증가시킵니다.
turnNumber와 playerCount를 사용하여 현재 몇 번째 라운드인지도 계산할 수 있습니다. 예를 들어, 4명이 게임하고 turnNumber가 9라면 3번째 라운드(9 / 4 = 2, 0부터 시작하므로 +1)입니다.
세 번째로, removePlayer() 메서드가 중요합니다. 플레이어가 게임을 떠날 때 호출되는데, 제거되는 플레이어가 현재 턴을 가진 플레이어라면 currentPlayer를 다음 플레이어로 이동시킨 후 제거합니다.
이렇게 하면 턴이 끊기지 않고 자연스럽게 다음 플레이어로 넘어갑니다. 마지막 한 명만 남았을 때도 올바르게 처리합니다.
네 번째로, updateScore()는 플레이어의 행동에 따라 점수를 업데이트합니다. 플레이어 ID로 해당 노드를 찾아서 score를 증가시킵니다.
getLeaderboard()는 모든 플레이어를 배열로 변환하고 점수 순으로 정렬하여 순위표를 만듭니다. 여러분이 이 코드를 사용하면 보드게임, 카드게임, 턴 기반 RPG, 퀴즈쇼 등 턴 시스템이 필요한 모든 게임을 만들 수 있습니다.
플레이어가 중간에 나가거나 들어와도 게임이 중단되지 않고, 턴 순서가 자동으로 유지됩니다.
실전 팁
💡 플레이어가 모두 나가서 playerCount가 0이 되면 게임을 종료하는 로직을 추가하세요. removePlayer 후 playerCount를 체크하여 게임 종료 이벤트를 발생시킬 수 있습니다.
💡 타임아웃 기능을 추가하면 더 현실적입니다. 각 턴마다 setTimeout을 설정하고, 시간 내에 행동하지 않으면 자동으로 nextTurn()을 호출하세요.
💡 플레이어 상태에 'spectator' 모드를 추가하면 게임에서 나갔지만 구경은 하는 플레이어를 표현할 수 있습니다. isActive를 false로 설정하고 turnNumber를 건너뛰는 방식입니다.
💡 특수 아이템으로 턴 순서를 역전시키려면 양방향 원형 리스트로 확장하고, nextTurn() 대신 previousTurn()을 호출하도록 게임 로직을 변경하세요.
💡 멀티스레드 환경에서는 동시성 문제를 고려해야 합니다. nextTurn()과 removePlayer()가 동시에 호출되면 문제가 생길 수 있으므로, 뮤텍스나 락을 사용하세요.
6. 순환 버퍼 구현
시작하며
여러분이 실시간 로그 시스템이나 스트리밍 데이터 처리를 구현할 때, 최근 N개의 데이터만 유지하고 오래된 데이터는 자동으로 덮어쓰는 구조가 필요한 적 있나요? 메모리를 고정 크기로 유지하면서 끊임없이 들어오는 데이터를 효율적으로 관리해야 합니다.
이런 문제는 임베디드 시스템, 로그 버퍼, 오디오/비디오 스트리밍, 센서 데이터 수집 등에서 매우 중요합니다. 일반 배열이나 큐로 구현하면 오래된 데이터를 삭제하고 새 데이터를 추가하는 오버헤드가 발생하며, 메모리 재할당이 빈번해집니다.
바로 이럴 때 필요한 것이 원형 버퍼(Circular Buffer, Ring Buffer)입니다. 고정된 크기의 원형 구조에서 쓰기 포인터만 이동시키면, 자동으로 가장 오래된 데이터를 덮어쓰며 메모리 효율성이 극대화됩니다.
개요
간단히 말해서, 순환 버퍼는 고정 크기의 버퍼를 원형으로 사용하여, 버퍼가 가득 차면 가장 오래된 데이터부터 덮어쓰는 FIFO 자료구조입니다. 원형 연결 리스트로 구현하면 미리 정해진 개수의 노드를 원형으로 연결하고, 쓰기 포인터와 읽기 포인터를 관리합니다.
쓰기 포인터가 계속 이동하며 데이터를 덮어쓰고, 읽기 포인터는 아직 읽지 않은 데이터를 가리킵니다. 예를 들어, 크기 5의 버퍼에 6번째 데이터가 들어오면 첫 번째 데이터가 자동으로 사라지고 새 데이터로 대체됩니다.
기존에는 배열과 head/tail 인덱스로 관리하면서 모듈러 연산을 해야 했다면, 이제는 포인터만 순환시키면 됩니다. 순환 버퍼의 핵심 특징은 첫째, 메모리 크기가 고정되어 있고, 둘째, 오래된 데이터가 자동으로 제거되며, 셋째, 삽입/삭제가 O(1)로 매우 빠르다는 점입니다.
이러한 특징들이 실시간 시스템에서 예측 가능한 성능과 안정적인 메모리 사용을 보장합니다.
코드 예제
class BufferNode {
constructor() {
this.data = null;
this.timestamp = null;
this.next = null;
}
}
class CircularBuffer {
constructor(capacity) {
this.capacity = capacity;
this.size = 0;
this.head = null;
this.writePointer = null;
this.readPointer = null;
// 고정 크기의 원형 버퍼 초기화
this.initializeBuffer();
}
initializeBuffer() {
// capacity만큼의 노드를 미리 생성
for (let i = 0; i < this.capacity; i++) {
const node = new BufferNode();
if (!this.head) {
this.head = node;
node.next = this.head;
this.writePointer = this.head;
this.readPointer = this.head;
} else {
let temp = this.head;
while (temp.next !== this.head) {
temp = temp.next;
}
temp.next = node;
node.next = this.head;
}
}
}
// 데이터 쓰기 (가장 오래된 데이터 덮어쓰기)
write(data) {
this.writePointer.data = data;
this.writePointer.timestamp = Date.now();
// 버퍼가 가득 찬 경우 읽기 포인터도 이동
if (this.size === this.capacity) {
this.readPointer = this.readPointer.next;
} else {
this.size++;
}
this.writePointer = this.writePointer.next;
return true;
}
// 데이터 읽기 (가장 오래된 데이터부터)
read() {
if (this.size === 0) return null;
const data = {
value: this.readPointer.data,
timestamp: this.readPointer.timestamp
};
// 읽은 데이터 초기화
this.readPointer.data = null;
this.readPointer.timestamp = null;
this.readPointer = this.readPointer.next;
this.size--;
return data;
}
// 최근 N개 데이터 가져오기 (읽지 않고 조회만)
peek(count = this.size) {
if (this.size === 0) return [];
const result = [];
let current = this.readPointer;
const itemsToRead = Math.min(count, this.size);
for (let i = 0; i < itemsToRead; i++) {
if (current.data !== null) {
result.push({
value: current.data,
timestamp: current.timestamp
});
}
current = current.next;
}
return result;
}
// 버퍼 상태 정보
getStatus() {
return {
capacity: this.capacity,
size: this.size,
available: this.capacity - this.size,
utilizationPercent: ((this.size / this.capacity) * 100).toFixed(1)
};
}
// 버퍼 비우기
clear() {
let current = this.head;
do {
current.data = null;
current.timestamp = null;
current = current.next;
} while (current !== this.head);
this.size = 0;
this.writePointer = this.head;
this.readPointer = this.head;
}
}
설명
이것이 하는 일: 순환 버퍼는 메모리를 고정 크기로 유지하면서 끊임없이 들어오는 데이터를 처리하고, 버퍼가 가득 차면 가장 오래된 데이터를 자동으로 제거합니다. 첫 번째로, initializeBuffer()에서 미리 capacity만큼의 노드를 생성하여 원형으로 연결합니다.
일반 원형 리스트와 달리 노드를 미리 만들어두는 이유는, 런타임에 메모리 할당/해제를 하지 않아 성능이 예측 가능하고 실시간 시스템에 적합하기 때문입니다. 모든 노드의 data는 null로 초기화됩니다.
그 다음으로, write() 메서드가 데이터를 씁니다. 내부에서는 현재 writePointer가 가리키는 노드에 데이터와 타임스탬프를 저장하고, writePointer를 다음 노드로 이동시킵니다.
중요한 부분은 버퍼가 가득 찬 경우(size === capacity) 읽기 포인터도 함께 이동시킨다는 것입니다. 이렇게 하면 아직 읽지 않은 데이터가 덮어써지는 것을 방지하고, 항상 가장 최근 capacity개의 데이터만 유지됩니다.
세 번째로, read() 메서드는 readPointer가 가리키는 가장 오래된 데이터를 반환하고 포인터를 이동시킵니다. 읽은 후 해당 노드의 data를 null로 초기화하여 메모리를 정리하고, size를 감소시킵니다.
이는 소비자가 데이터를 처리하는 속도를 제어할 수 있게 합니다. 네 번째로, peek() 메서드는 데이터를 읽지 않고 조회만 합니다.
최근 N개의 데이터를 확인하고 싶을 때 유용하며, readPointer를 이동시키지 않아 원본 데이터가 보존됩니다. getStatus()는 버퍼의 현재 상태를 모니터링할 수 있게 해줍니다.
여러분이 이 코드를 사용하면 로그 시스템, 센서 데이터 수집, 오디오 버퍼링, 네트워크 패킷 버퍼 등 실시간 데이터 처리가 필요한 모든 상황에서 안정적이고 효율적인 시스템을 만들 수 있습니다. 메모리 사용량이 일정하고, 가비지 컬렉션 부담이 없으며, 성능이 예측 가능합니다.
실전 팁
💡 버퍼 크기는 2의 거듭제곱으로 설정하면 모듈러 연산을 비트 AND로 최적화할 수 있습니다. 예: capacity = 1024이면 index % 1024 대신 index & 1023을 사용하여 더 빠릅니다.
💡 멀티스레드 환경에서는 Lock-Free 알고리즘을 적용해야 합니다. writePointer와 readPointer를 atomic 변수로 만들고, CAS(Compare-And-Swap) 연산을 사용하세요.
💡 버퍼 오버플로우를 감지하려면 write() 전에 조건을 체크하세요. 만약 덮어쓰기를 허용하지 않는다면 size === capacity일 때 false를 반환하도록 수정할 수 있습니다.
💡 실시간 시스템에서는 타임스탬프가 매우 중요합니다. 데이터가 얼마나 오래되었는지 확인하여 유효성을 판단하고, 만료된 데이터는 처리하지 않도록 할 수 있습니다.
💡 메모리 매핑된 파일로 순환 버퍼를 구현하면 프로세스 간 공유가 가능합니다. 공유 메모리에 버퍼를 배치하면 여러 프로세스가 동시에 읽고 쓸 수 있습니다.
7. LRU 캐시 최적화
시작하며
여러분이 API 응답을 캐싱하거나 이미지 로딩을 최적화할 때, 자주 사용하는 데이터는 메모리에 유지하고 오랫동안 사용하지 않은 데이터는 제거해야 하는 상황을 마주한 적 있나요? 제한된 메모리로 최대한의 히트율(hit rate)을 얻어야 합니다.
이런 문제는 캐시 시스템, 페이지 교체 알고리즘, 데이터베이스 버퍼 관리 등에서 핵심적입니다. 단순히 오래된 것부터 제거하는 FIFO는 자주 사용하는 데이터도 제거할 수 있고, 모든 접근 시간을 기록하면 메모리와 성능 오버헤드가 큽니다.
바로 이럴 때 필요한 것이 LRU(Least Recently Used) 캐시입니다. 원형 연결 리스트와 해시맵을 결합하면 O(1) 시간에 get과 put을 수행하면서, 가장 오랫동안 사용하지 않은 데이터를 자동으로 제거할 수 있습니다.
개요
간단히 말해서, LRU 캐시는 최근에 사용한 데이터를 빠르게 접근할 수 있게 하고, 용량이 가득 차면 가장 오래 사용하지 않은 데이터를 제거하는 캐싱 전략입니다. 원형 연결 리스트로 구현하면 최근 사용한 항목을 head 근처에 배치하고, 오래된 항목은 tail 쪽에 위치시킵니다.
데이터를 접근할 때마다 해당 노드를 head로 이동시키고, 새 데이터 삽입 시 용량이 초과되면 tail(가장 오래된 항목)을 제거합니다. 예를 들어, 용량 3인 캐시에 [A, B, C]가 있고 B를 접근하면 [B, A, C]가 되며, 새로운 D를 넣으면 C가 제거되고 [D, B, A]가 됩니다.
기존에는 리스트를 순회하며 타임스탬프를 비교해야 했다면, 이제는 포인터만 조작하면 됩니다. 해시맵을 함께 사용하면 O(1) 접근도 가능합니다.
LRU 캐시의 핵심 특징은 첫째, 최근 사용 패턴을 자동으로 반영하고, 둘째, get과 put이 모두 O(1)이며, 셋째, 메모리 사용량이 예측 가능하다는 점입니다. 이러한 특징들이 웹 애플리케이션, 운영체제, 데이터베이스 등에서 필수적인 성능 최적화 기법이 되게 합니다.
코드 예제
class CacheNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
this.prev = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.size = 0;
this.cache = new Map(); // 빠른 조회를 위한 해시맵
// 더미 head와 tail 노드 (경계 처리 단순화)
this.head = new CacheNode(0, 0);
this.tail = new CacheNode(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 캐시에서 값 가져오기
get(key) {
if (!this.cache.has(key)) {
return -1; // 캐시 미스
}
const node = this.cache.get(key);
// 최근 사용으로 이동 (head 다음으로)
this.removeNode(node);
this.addToHead(node);
return node.value;
}
// 캐시에 값 저장
put(key, value) {
if (this.cache.has(key)) {
// 이미 존재하면 값 업데이트 및 최근 사용으로 이동
const node = this.cache.get(key);
node.value = value;
this.removeNode(node);
this.addToHead(node);
} else {
// 새 항목 추가
const newNode = new CacheNode(key, value);
this.cache.set(key, newNode);
this.addToHead(newNode);
this.size++;
// 용량 초과 시 LRU 항목 제거
if (this.size > this.capacity) {
const lru = this.tail.prev;
this.removeNode(lru);
this.cache.delete(lru.key);
this.size--;
}
}
}
// 노드를 리스트에서 제거 (연결 끊기)
removeNode(node) {
const prev = node.prev;
const next = node.next;
prev.next = next;
next.prev = prev;
}
// 노드를 head 바로 다음에 추가 (최근 사용)
addToHead(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
// 캐시 상태 확인
getStats() {
const items = [];
let current = this.head.next;
while (current !== this.tail) {
items.push({ key: current.key, value: current.value });
current = current.next;
}
return {
size: this.size,
capacity: this.capacity,
items: items, // 최근 사용 순서
utilizationPercent: ((this.size / this.capacity) * 100).toFixed(1)
};
}
// 캐시 비우기
clear() {
this.cache.clear();
this.head.next = this.tail;
this.tail.prev = this.head;
this.size = 0;
}
}
설명
이것이 하는 일: LRU 캐시는 최근에 사용한 데이터를 빠르게 접근하고, 메모리가 가득 차면 가장 오래 사용하지 않은 데이터를 제거하여 항상 최적의 데이터 집합을 유지합니다. 첫 번째로, 더미 head와 tail 노드를 사용하는 것이 핵심 트릭입니다.
실제 데이터 노드들은 head와 tail 사이에 위치하며, head 바로 다음이 가장 최근에 사용한 항목, tail 바로 앞이 가장 오래 사용하지 않은 항목입니다. 더미 노드를 사용하면 경계 조건(빈 리스트, 단일 노드 등)을 체크할 필요가 없어 코드가 간결해집니다.
그 다음으로, get() 메서드는 Map에서 O(1)로 노드를 찾고, 해당 노드를 리스트에서 제거한 후 head 다음에 다시 추가합니다. 이 작업이 "이 데이터를 방금 사용했다"는 것을 표시하는 방법입니다.
removeNode()와 addToHead()는 양방향 포인터를 조작하여 O(1)에 수행됩니다. 세 번째로, put() 메서드는 두 가지 경우를 처리합니다.
첫째, 키가 이미 존재하면 값만 업데이트하고 최근 사용 위치로 이동합니다. 둘째, 새 키라면 노드를 생성하여 head 다음에 추가하고, 용량을 초과하면 tail 바로 앞의 노드(가장 오래된 항목)를 제거합니다.
Map에서도 함께 삭제하여 일관성을 유지합니다. 네 번째로, 양방향 연결 리스트를 사용하는 이유는 노드를 중간에서 제거할 때 이전 노드를 찾기 위해 순회할 필요가 없기 때문입니다.
node.prev로 즉시 접근할 수 있어 O(1)이 보장됩니다. 단방향 리스트로는 불가능합니다.
여러분이 이 코드를 사용하면 API 응답 캐싱, 계산 결과 메모이제이션, 데이터베이스 쿼리 캐싱, 이미지/파일 캐싱 등 모든 종류의 캐시 시스템을 구현할 수 있습니다. Redis나 Memcached 같은 전문 캐시 서버도 내부적으로 LRU 전략을 사용합니다.
실전 팁
💡 더미 노드를 사용하는 패턴을 꼭 기억하세요. 링크드 리스트 문제에서 경계 조건을 처리하는 가장 우아한 방법이며, 코드 복잡도를 크게 줄여줍니다.
💡 실제 프로덕션에서는 TTL(Time To Live)을 추가하세요. 각 노드에 만료 시간을 저장하고, get() 시 확인하여 만료된 항목은 자동으로 제거합니다.
💡 히트율(hit rate)을 모니터링하면 캐시 성능을 평가할 수 있습니다. get() 호출 횟수와 캐시 미스 횟수를 카운터로 추적하여 hit_rate = hits / (hits + misses)를 계산하세요.
💡 LRU의 변형인 LFU(Least Frequently Used)도 유용합니다. 접근 횟수를 기준으로 제거하려면 각 노드에 frequency 카운터를 추가하고 우선순위 큐를 사용하세요.
💡 대규모 시스템에서는 분산 캐시가 필요합니다. Consistent Hashing을 사용하여 여러 캐시 서버에 데이터를 분산시키고, 각 서버가 독립적으로 LRU를 관리하도록 하세요.
8. 타임 슬라이싱 CPU 스케줄러
시작하며
여러분이 운영체제 시뮬레이터를 만들거나 멀티태스킹 시스템을 설계할 때, 여러 프로세스가 CPU를 공유하면서 각자 일정 시간씩 실행되고 컨텍스트 스위칭되는 구조를 구현한 적 있나요? 실시간으로 프로세스 상태를 관리하고, I/O 대기와 실행을 구분해야 합니다.
이런 문제는 실제 운영체제의 프로세스 스케줄러, 가상화 시스템, 컨테이너 런타임 등에서 핵심 알고리즘입니다. 단순한 라운드 로빈보다 더 현실적인 모델이 필요하며, 프로세스 상태(ready, running, waiting)를 정확히 관리해야 합니다.
바로 이럴 때 필요한 것이 타임 슬라이싱 기반 CPU 스케줄러입니다. 원형 연결 리스트로 ready 큐를 관리하고, 각 프로세스에 시간 할당량을 주며, I/O 완료 시 자동으로 ready 큐에 복귀시키는 완전한 스케줄링 시스템을 만들 수 있습니다.
개요
간단히 말해서, 타임 슬라이싱 CPU 스케줄러는 여러 프로세스를 시분할 방식으로 실행하고, 각 프로세스의 상태를 추적하며, 공정한 CPU 시간 배분을 보장하는 운영체제 핵심 컴포넌트입니다. 원형 연결 리스트로 ready 큐를 구현하면 실행 준비가 된 프로세스들이 원형으로 대기하고, 스케줄러가 순차적으로 CPU를 할당합니다.
각 프로세스는 timeQuantum 동안 실행되고, 완료되지 않았으면 다시 큐의 끝으로 이동합니다. I/O를 요청하면 waiting 상태로 전환되고, I/O가 완료되면 다시 ready 큐에 추가됩니다.
예를 들어, 3개 프로세스가 각각 10ms씩 실행되고, 그중 하나가 I/O를 요청하면 나머지 2개가 계속 실행되다가 I/O 완료 후 다시 3개가 순환합니다. 기존에는 여러 개의 큐와 복잡한 상태 전환 로직이 필요했다면, 이제는 원형 구조와 상태 플래그만으로 깔끔하게 구현할 수 있습니다.
타임 슬라이싱 스케줄러의 핵심 특징은 첫째, 프로세스 상태를 명확히 관리하고, 둘째, 공정한 CPU 시간 분배를 보장하며, 셋째, I/O와 CPU 사용을 효율적으로 조율한다는 점입니다. 이러한 특징들이 현대 운영체제의 멀티태스킹을 가능하게 합니다.
코드 예제
class Process {
constructor(pid, name, burstTime, priority = 0) {
this.pid = pid;
this.name = name;
this.burstTime = burstTime; // 총 실행 시간
this.remainingTime = burstTime;
this.priority = priority;
this.state = 'ready'; // ready, running, waiting, terminated
this.waitTime = 0;
this.turnaroundTime = 0;
this.ioRequests = 0;
this.next = null;
}
}
class CPUScheduler {
constructor(timeQuantum = 10) {
this.timeQuantum = timeQuantum;
this.readyQueue = null; // 원형 연결 리스트
this.currentProcess = null;
this.waitingQueue = [];
this.completedProcesses = [];
this.currentTime = 0;
this.processCount = 0;
}
// 새 프로세스 추가
addProcess(pid, name, burstTime, priority = 0) {
const process = new Process(pid, name, burstTime, priority);
if (!this.readyQueue) {
this.readyQueue = process;
process.next = this.readyQueue;
} else {
let temp = this.readyQueue;
while (temp.next !== this.readyQueue) {
temp = temp.next;
}
temp.next = process;
process.next = this.readyQueue;
}
this.processCount++;
}
// CPU 사이클 실행
executeTimeslice() {
if (!this.readyQueue) {
return { event: 'idle', time: this.currentTime };
}
// 현재 프로세스 선택
this.currentProcess = this.readyQueue;
this.currentProcess.state = 'running';
// 실제 실행 시간 계산
const executionTime = Math.min(
this.timeQuantum,
this.currentProcess.remainingTime
);
this.currentProcess.remainingTime -= executionTime;
this.currentTime += executionTime;
const event = {
type: 'execution',
pid: this.currentProcess.pid,
name: this.currentProcess.name,
executedTime: executionTime,
remainingTime: this.currentProcess.remainingTime,
currentTime: this.currentTime
};
// 프로세스 완료
if (this.currentProcess.remainingTime === 0) {
this.currentProcess.state = 'terminated';
this.currentProcess.turnaroundTime = this.currentTime;
this.completedProcesses.push(this.currentProcess);
this.removeFromReadyQueue(this.currentProcess.pid);
event.type = 'completed';
}
// I/O 요청 시뮬레이션 (30% 확률)
else if (Math.random() < 0.3) {
this.currentProcess.state = 'waiting';
this.currentProcess.ioRequests++;
this.waitingQueue.push({
process: this.currentProcess,
ioCompletionTime: this.currentTime + 20
});
this.removeFromReadyQueue(this.currentProcess.pid);
event.type = 'io_request';
}
// 다음 프로세스로 이동
else {
this.currentProcess.state = 'ready';
this.readyQueue = this.readyQueue.next;
event.type = 'context_switch';
}
// I/O 완료 체크
this.checkIOCompletion();
return event;
}
// I/O 완료된 프로세스를 ready 큐에 복귀
checkIOCompletion() {
this.waitingQueue = this.waitingQueue.filter(item => {
if (this.currentTime >= item.ioCompletionTime) {
item.process.state = 'ready';
this.addToReadyQueue(item.process);
return false; // 큐에서 제거
}
return true; // 계속 대기
});
}
// ready 큐에 프로세스 추가
addToReadyQueue(process) {
if (!this.readyQueue) {
this.readyQueue = process;
process.next = this.readyQueue;
} else {
let temp = this.readyQueue;
while (temp.next !== this.readyQueue) {
temp = temp.next;
}
temp.next = process;
process.next = this.readyQueue;
}
}
// ready 큐에서 프로세스 제거
removeFromReadyQueue(pid) {
if (!this.readyQueue) return;
// 단일 프로세스
if (this.readyQueue.next === this.readyQueue) {
if (this.readyQueue.pid === pid) {
this.readyQueue = null;
}
return;
}
// 여러 프로세스
let current = this.readyQueue;
let prev = null;
while (current.next !== this.readyQueue) {
prev = current;
current = current.next;
}
let target = this.readyQueue;
let beforeTarget = current;
do {
if (target.pid === pid) {
if (target === this.readyQueue) {
this.readyQueue = target.next;
}
beforeTarget.next = target.next;
return;
}
beforeTarget = target;
target = target.next;
} while (target !== this.readyQueue);
}
// 스케줄러 통계
getStatistics() {
const avgTurnaround = this.completedProcesses.length > 0
? this.completedProcesses.reduce((sum, p) => sum + p.turnaroundTime, 0) /
this.completedProcesses.length
: 0;
return {
totalTime: this.currentTime,
completedCount: this.completedProcesses.length,
readyCount: this.countReadyProcesses(),
waitingCount: this.waitingQueue.length,
avgTurnaroundTime: avgTurnaround.toFixed(2),
cpuUtilization: '95%' // 단순화
};
}
countReadyProcesses() {
if (!this.readyQueue) return 0;
let count = 1;
let current = this.readyQueue.next;
while (current !== this.readyQueue) {
count++;
current = current.next;
}
return count;
}
}
설명
이것이 하는 일: CPU 스케줄러는 여러 프로세스를 동시에 실행하는 것처럼 보이게 하기 위해 각 프로세스를 빠르게 번갈아가며 실행하고, 상태를 추적하며, CPU와 I/O 자원을 효율적으로 분배합니다. 첫 번째로, Process 클래스는 실제 운영체제의 PCB(Process Control Block)를 단순화한 것입니다.
pid(프로세스 ID), burstTime(총 실행 시간), remainingTime(남은 실행 시간), state(현재 상태), waitTime(대기 시간), turnaroundTime(완료 시간) 등 스케줄링에 필요한 모든 정보를 담고 있습니다. 이 정보들이 스케줄링 알고리즘의 의사결정에 사용됩니다.
그 다음으로, executeTimeslice()가 한 번의 CPU 사이클을 시뮬레이션합니다. 내부에서는 현재 프로세스를 선택하고(readyQueue의 head), timeQuantum과 remainingTime 중 작은 값만큼 실행합니다.
실행 후 remainingTime이 0이 되면 프로세스가 완료된 것이므로 terminated 상태로 전환하고 completedProcesses에 추가합니다. 세 번째로, I/O 요청 처리가 현실감을 더합니다.
30% 확률로 프로세스가 I/O를 요청한다고 가정하고(디스크 읽기, 네트워크 요청 등), 해당 프로세스를 waiting 상태로 전환하여 waitingQueue에 넣습니다. I/O 완료 시간을 기록하고, 매 사이클마다 checkIOCompletion()으로 완료된 I/O를 확인하여 프로세스를 다시 ready 큐에 추가합니다.
네 번째로, 컨텍스트 스위칭이 일어납니다. 프로세스가 완료되지도 않고 I/O를 요청하지도 않았지만 timeQuantum을 다 사용했다면, 해당 프로세스는 다시 ready 상태가 되고 readyQueue 포인터가 다음 프로세스로 이동합니다.
이것이 바로 "시분할"입니다. 마지막으로, getStatistics()는 스케줄러의 성능 지표를 계산합니다.
평균 반환 시간(turnaround time)은 프로세스가 시작부터 완료까지 걸린 시간의 평균으로, 스케줄러 효율성의 핵심 지표입니다. CPU 이용률, 처리량, 평균 대기 시간 등도 추가할 수 있습니다.
여러분이 이 코드를 사용하면 운영체제 교육, 시뮬레이터 개발, 성능 벤치마킹, 컨테이너 스케줄러 프로토타입 등을 만들 수 있습니다. 실제 Linux나 Windows의 스케줄러는 훨씬 복잡하지만, 기본 원리는 동일합니다.
실전 팁
💡 우선순위 스케줄링을 추가하려면 priority 필드를 활용하세요. 높은 우선순위 프로세스에게 더 긴 timeQuantum을 주거나, 별도의 high-priority 큐를 만들어 먼저 처리할 수 있습니다.
💡 컨텍스트 스위칭 오버헤드를 시뮬레이션하려면 각 스위칭마다 1-2ms의 추가 시간을 더하세요. 이렇게 하면 timeQuantum이 너무 작을 때 성능이 저하되는 것을 관찰할 수 있습니다.
💡 실제 운영체제는 CFS(Completely Fair Scheduler) 같은 더 정교한 알고리즘을 사용합니다. 각 프로세스의 "virtual runtime"을 추적하여 공정성을 보장하는 방식입니다.
💡 멀티코어 CPU를 시뮬레이션하려면 여러 개의 currentProcess 포인터를 유지하고, 각 코어가 독립적으로 스케줄링하도록 확장할 수 있습니다.
💡 NUMA(Non-Uniform Memory Access) 환경에서는 프로세스를 특정 코어에 고정(affinity)시키는 것이 캐시 효율성을 높입니다. Process 클래스에 preferredCore 필드를 추가하세요.