2026-04-12 TIL (Weekend)
CS
공유자원
멀티스레드 환경에서는 여러 스레드가 메모리를 공유하기 때문에 필연적으로 ‘충돌’ 문제가 발생합니다.
- 공유 자원
- 여러 프로세스나 스레드가 공동으로 접근해서 사용하는 변수, 메모리, 파일 등을 말합니다.
- 임계 영역
- 공유 자원에 접근하여 값을 변경하는 코드의 일부분을 말합니다.
- 문제점: 두 개 이상의 스레드가 동시에 임계 영역에 뛰어들면 데이터가 꼬이는 현상이 발생합니다. 따라서 임계 영역에는 오직 한 번에 하나의 스레드만 접근하도록 통제해야 합니다.
해결책: 뮤텍스, 세마포어, 모니터
이 세 가지의 관계를 한 줄로 요약하자면, 임계 영역에 스레드들이 함부로 들어오지 못하게 막는 동기화 도구들입니다.
| 개념 | 핵심 정의 |
|---|---|
| 뮤텍스 (Mutex) | 오직 1개의 스레드만 임계 영역에 접근할 수 있게 하는 잠금 메커니즘입니다. (내가 열쇠를 쥐고 들어가서 문을 잠그고, 볼일이 끝나면 내가 직접 문을 열고 나옵니다.) |
| 세마포어 (Semaphore) | 설정된 개수(N개)의 스레드가 동시에 임계 영역에 접근할 수 있게 하는 메커니즘입니다. (카운팅 변수가 있어서, 3자리 빈 공간이 있으면 3명까지는 동시에 들어갈 수 있습니다.) |
| 모니터 (Monitor) | 프로그래밍 언어 차원에서 제공하는 가장 안전한 동기화 도구입니다. (개발자가 직접 열쇠(Lock) 코드를 짤 필요 없이, synchronized 같은 키워드 하나만 붙이면 알아서 뮤텍스처럼 작동하며 임계 영역을 보호해 줍니다.) |
교착 상태
임계 영역을 지키기 위해 Lock를 엄격하게 걸다 보면, 스레드들이 영원히 멈춰버리는 부작용이 발생하는데 이를 교착 상태라고 합니다.
교착 상태 두 개 이상의 프로세스나 스레드가 서로 상대방이 쥐고 있는 열쇠(자원)를 내놓기만을 무한정 기다리며 멈춰있는 상태입니다.
요약
여러 스레드가 같이 쓰는 [공유 자원]을 건드리는 위험한 코드 구역이 [임계 영역]이다. 이곳을 지키기 위해 [뮤텍스/세마포어/모니터]라는 자물쇠를 채운다. 하지만 자물쇠를 잘못 채우면 서로를 영원히 기다리는 [교착 상태(Deadlock)]에 빠지게 됩니다.
CPU 스케줄링 알고리즘
컴퓨터에서 CPU는 가장 비싸고 귀중한 자원입니다. CPU가 단 1초라도 놀고 있는 것은 엄청난 손해입니다.
따라서 메모리에 올라와 있는 수많은 프로세스들 중에서 당장 누구에게 CPU를 할당해 줄 것인가를 결정하여, CPU가 쉬지 않고 효율적으로 일하게 만드는 지휘자 역할이 바로 CPU 스케줄링입니다.
- 목표: CPU 이용률 극대화, 처리량 증가, 대기 시간 및 응답 시간 최소화
비선점형 방식
한 프로세스가 CPU를 할당받으면, 그 프로세스가 스스로 작업을 마치거나 I/O 작업 때문에 잠시 대기 상태로 빠질 때까지 운영체제가 강제로 CPU를 빼앗을 수 없는 방식입니다.
- 장점: 문맥 교환(Context Switching) 비용이 적어 오버헤드가 낮습니다.
- 단점: 하나의 긴 프로세스가 CPU를 독점하면 나머지 프로세스들이 기다려야 합니다.
1. FCFS (First Come First Served)
- 핵심: 큐(Queue)처럼 먼저 도착한 놈이 먼저 처리받는 가장 단순한 방식.
- 치명적 단점 (호위 효과, Convoy Effect): 실행 시간이 100시간인 프로세스가 먼저 도착하면, 실행 시간이 1초인 프로세스는 100시간을 꼼짝없이 기다려야 합니다.
2. SJF (Shortest Job First)
- 핵심: 큐에 있는 녀석들 중 실행 시간이 가장 짧은 놈부터 먼저 처리하는 방식. (평균 대기 시간을 가장 짧게 만들어 줍니다.)
- 치명적 단점 (기아 상태, Starvation): 실행 시간이 긴 프로세스는 짧은 프로세스들이 계속 들어오면 영원히 CPU를 할당받지 못합니다.
3. 우선순위 (Priority)
- 핵심: 프로세스마다 우선순위(숫자)를 부여하여 가장 높은 순위부터 처리하는 방식.
- 해결책 (에이징, Aging): 이 방식도 우선순위가 낮은 녀석은 기아 상태(Starvation)에 빠질 수 있습니다. 그래서 기다린 시간에 비례해 우선순위를 조금씩 높여주는 ‘에이징’ 기법을 사용해 해결합니다.
선점형 방식
하나의 프로세스가 CPU를 사용하고 있더라도, 운영체제가 강제로 CPU를 빼앗아 다른 프로세스에게 넘겨줄 수 있는 방식입니다. 현대의 스마트폰과 윈도우/맥OS는 모두 이 방식을 사용합니다.
- 장점: 우선순위가 높은 급한 작업을 빠르게 처리할 수 있고, 사용자 응답성이 매우 좋습니다.
- 단점: Context Switching으로 인해 오버헤드가 발생합니다.
1. 라운드 로빈 (Round Robin, RR)
- 핵심: 현대 OS의 근간, 모든 프로세스에게 ‘타임 퀀텀(Time Quantum, 할당 시간)’을 동일하게 주고, 시간이 다 되면 강제로 CPU를 뺏은 뒤 큐의 맨 뒤로 쫓아냅니다.
- 특징: 할당 시간이 너무 길면 FCFS와 다를 바 없어지고, 너무 짧으면 문맥 교환 오버헤드 때문에 컴퓨터가 버벅거립니다.
2. SRF / SRTF (Shortest Remaining Time First)
- 핵심: SJF의 선점형 버전입니다. 현재 실행 중인 프로세스의 ‘남은 시간’보다, 방금 새로 도착한 프로세스의 ‘실행 시간’이 더 짧으면 CPU를 뺏어버립니다.
3. 다단계 큐 (Multilevel Queue)
- 핵심: 프로세스의 중요도에 따라 큐를 여러 개로 쪼개는 방식입니다.
- 특징: 예를 들어 1번 큐(시스템 작업), 2번 큐(사용자 상호작용), 3번 큐(백그라운드 작업)로 나누고, 각 큐마다 ‘라운드 로빈’, ‘FCFS’ 등 서로 다른 스케줄링 알고리즘을 섞어서 적용합니다.
요약
- 비선점형: 은행 창구 (앞사람 볼일 끝날 때까지 무조건 대기)
- 선점형: 응급실 (감기 환자 진료 중이라도, 피 흘리는 응급 환자 오면 의사 뺏김)
코딩테스트
길찾기 알고리즘의 자료구조
코딩 테스트에서 탐색(길찾기) 문제가 나오면, 알고리즘에 따라 다음에 탐색할 곳을 어디에 저장해 둘 것인가에 대한 자료구조 선택이 문제의 핵심이 됩니다.
1. BFS (너비 우선 탐색) 큐 (Queue)
“먼저 온 놈이 먼저 간다! (가까운 곳부터 공평하게)”
- 동작 방식 (선입선출 - FIFO): 새로운 노드를 발견하면 큐의 뒤에 줄을 세우고, 탐색은 항상 맨 앞사람부터 꺼내서 처리합니다.
- 특징 (공평한 물결): 시작점에서 1보 거리인 곳을 ‘모두’ 확인한 후에야 2보 거리로 넘어갑니다. 물결이 퍼져나가는 것과 같습니다.
- 코테 핵심 용도:
- 가중치가 없는(모든 칸의 이동 비용이 1로 동일한) 맵에서의 ‘최단 거리’, ‘최소 이동 횟수’ 찾기.
- 키워드: “토마토가 익는 최소 일수”, “미로 탈출 최소 칸 수”
2. DFS (깊이 우선 탐색) 스택 (Stack) / 재귀
“나중에 온 놈부터 처리한다! (한 우물만 끝까지 파기)”
- 동작 방식 (후입선출 - LIFO): 갈림길에서 새로운 길을 발견하면, 기존 길들은 스택의 밑에 깔아두고 방금 찾은 맨 위의 새로운 길부터 끝을 볼 때까지 파고듭니다.
- 특징 (직진 본능): 실무나 코테에서는 스택(Stack) 자료구조를 직접 선언해서 쓰기보다, 컴퓨터의 ‘콜 스택(Call Stack)’을 이용하는 재귀 함수(Recursion) 방식을 압도적으로 많이 사용합니다.
- 코테 핵심 용도:
- 최단 거리는 보장하지 않습니다! (우연히 먼저 파고든 길이 빙 돌아가는 길일 수 있음)
- 경로의 ‘특징’을 저장해야 할 때, ‘모든 경우의 수(완전 탐색)’를 다 뒤져봐야 할 때 사용합니다.
- 키워드: “바이러스가 퍼진 영역의 총 개수”, “N-Queen 문제”
3. 다익스트라 (Dijkstra) 우선순위 큐 (Priority Queue)
“거리가 가장 짧은(싼) 놈부터 처리한다! (구두쇠의 내비게이션)”
- 일반 큐(BFS)를 쓰면 안 되는 이유?: 맵에 ‘비용(가중치)’이 존재하기 때문입니다. 일반 큐는 비용이 100이든 1000이든 먼저 발견한 길을 먼저 가버립니다.
- 동작 방식 (최소 힙 - Min Heap): 들어온 순서와는 아무런 상관이 없습니다. 큐 안에 데이터가 들어오면, 내부적으로 가장 비용이 싼(거리가 짧은) 녀석이 알아서 맨 앞으로 새치기를 합니다!
- 코테 핵심 용도:
- 톨게이트 비용, 늪지대 체력 소모 등 ‘가중치가 다른(음수는 없는) 그래프’에서 최단 거리를 찾을 때 무조건 사용합니다.
- 키워드: “특정 도시로 가는 최소 배달 시간”, “가장 저렴한 비행기 티켓 경로”
요약 노트
- 비용이 없다 + 최단 거리 = BFS (큐)
- 모든 경우의 수 다 보기 = DFS (재귀)
- 비용이 다르다 + 최단 거리 = 다익스트라 (우선순위 큐)