✅ 멀티프로그래밍
프로세스의 실행은 CPU burst와 I/O burst의 반복이라고 볼 수 있다.
- CPU burst: 프로세스가 CPU를 사용해 연산 작업을 수행
- I/O burst: CPU가 입출력 작업을 기다림
만약 I/O 작업이 진행되는 동안 CPU가 해당 프로세스의 완료를 기다리기만 한다면, 이 시간 동안 CPU는 아무 일도 하지 않고 낭비된다.
이러한 비효율을 줄이기 위해 운영체제는 CPU를 항상 바쁘게 유지하려고 한다.
즉, 어떤 프로세스가 I/O 요청으로 대기 상태에 들어가면 CPU는 즉시 다른 준비된 프로세스에게 할당된다.
이렇게 CPU를 효율적으로 사용하기 위해 여러 프로세스를 메모리에 올려두고, 실행 가능한 프로세스끼리 번갈아가며 CPU를 사용하는 방식을 멀티프로그래밍(multiprogramming)이라고 한다.
특히 단일 CPU 코어에서는 한 번에 하나의 프로세스만 실행할 수 있기 때문에
어느 프로세스를 실행할지를 결정하는 CPU 스케줄링이 필수적이다.
✅ 스케줄링이 필요한 경우
프로세스의 상태를 기준으로 봤을 때, 스케줄링이 필요한 경우는 다음과 같다.
- `running -> waiting` : 이벤트 발생
- `running -> ready` : interrupt 발생
- `waiting -> ready`: 이벤트 처리 완료
- `terminated` : 프로세스가 종료
그리고 스케줄링은 선점과 비선점으로 나눌 수 있다.
✅ 선점/비선점 스케줄링
📍비선점 스케줄링 (NonPreemptive Scheduling)
: CPU가 한 프로세스에 할당되면 , 프로세스가 종료되거나 이벤트가 발생하기 전까지 CPU를 뺏을 수 없음
- 적용 경우: `running → waiting`(1), `terminated`(4)
- Context Switching이 적어 Overhead가 작음
- 응답 시간 예측 가능
- 짧은 작업이라도 긴 작업이 끝나야 실행될 수 있어 비효율적일 수 있음
📍선점 스케줄링 (Preemptive Scheduliing)
: 더 높은 우선순위 프로세스가 발생하면, 현재 실행 중인 프로세스로부터 강제로 CPU를 회수
- 적용 경우: `running → waiting`(1), `running → ready`(2), `waiting → ready`(3), `terminated`(4)
- 빠른 응답이 필요한 시분할 시스템(Time-sharing)에 적합
- CPU 처리 시간이 매우 긴 프로세스의 사용 독점을 막을 수 있어 효율적
- 높은 우선순위를 가진 프로세스들만 들어오는 경우, Context Switching이 많아져 오버헤드 발생 가능
✅ 스케줄링 알고리즘
📍FCFS (First Come First Served)
: 먼저 도착한 프로세스를 먼저 실행하는 비선점형 스케줄링
- 구현이 간단하고 이해하기 쉬움
💡 언제 사용?
- 작업 시간이 비슷한 프로세스들이 모여 있을 때 효율적
- 단순성과 예측 가능성 덕분에 간단한 데이터 처리 시스템에서 유용
🛠️ 문제점
- Convoy Effect: 긴 작업이 먼저 오면 짧은 작업들이 대기하게 되어 전체 시스템 효율 저하
- 즉, 평균 대기 시간이 매우 길어질 수 있음
- Interactive 시스템(사용자 상호작용 중심)에 부적절
- 모든 프로세스가 주기적으로 CPU를 조금씩 가져야 하는데 그러지 못함
🔖 예시
| 프로세스 | CPU burst time |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
[ex. P1, P2, P3 순서로 도착]
=> 평균 대기 시간은 (0+24+27)/3
[ex. P2, P3, P1 순서로 도착]
=> 평균 대기 시간은 (0+3+6)/3
📍SJF (Shortest Job First)
: CPU burst time(예상 실행 시간)이 가장 짧은 프로세스를 먼저 실행하는 스케줄링
- 주어진 프로세스에 대해 최소의 평균 대기시간 보장 -> Convey effect 해결
- 시스템 내 프로세스 수를 최소화할 수 있음
- 선점형/비선점형 모두 가능
- 비선점형 SJF : SPN
- 선점형 SJF : SRTN
💡 언제 사용?
- 작업 시간이 비슷한 프로세스들이 모여 있을 때 효율적
- 단순성과 예측 가능성 덕분에 간단한 데이터 처리 시스템에서 유용
🛠️ 문제점
- Starvation(기아): CPU burst time이 긴 프로세스는 계속 뒤로 밀려 거의 실행되지 못할 수 있음
📍SRTF (Shortest Remaining Time First)
: 남은 CPU burst time이 가장 짧은 프로세스를 우선 실행하는 선점형 스케줄링
- 선점형 스케줄링 방식
- SJF의 선점형 버전
💡 언제 사용?
- 짧은 작업이 많은 시스템
- CPU burst time을 정확히 알 수 있다면 최적의 평균 대기 시간을 보장할 수 있음
- 평균 대기 시간을 최소화해야 할 때
🛠️ 문제점
- Starvation: CPU burst time이 긴 프로세스는 계속 뒤로 밀려 거의 실행되지 못할 수 있음
📍Priority Scheduling
: 우선순위(priority)가 높은 프로세스를 먼저 실행
- 우선순위는 일반적으로 숫자로 표현되며, 숫자가 작을수록 높은 우선순위
- 선점형/비선점형 모두 가능
- 선점형: 더 높은 우선순위 프로세스가 오면 CPU를 빼앗음
- 비선점형: 높은 우선순위 프로세스를 Ready Queue 맨 앞에 추가
🛠️ 문제점
- Starvation: 우선순위가 낮은 프로세스는 계속 뒤로 밀려 거의 실행되지 못할 수 있음
- 무기한 봉쇄(Indefinite Blocking): 실행 준비는 되어 있지만, 계속해서 CPU를 할당받지 못해 무기한 대기하는 상태
📍RR (Round Robin)
: 프로세스마다 동일한 시간량(Time Quantum)만큼 CPU를 할당하는 선점형 스케줄링
- 시간이 지나면 강제로 CPU를 회수하고 다음 프로세스에 할당 (선점형)
- 현대적인 시분할 시스템에 적합
- 짧은 응답시간을 보장
- 적절한 시간량을 설정하는 것이 중요
- 너무 크면 FCFS처럼 동작하여 응답 시간이 나빠질 수 있음
- 너무 작으면 Context Switching 오버헤드가 커짐
💡 언제 사용?
- 다수의 사용자나 프로세스가 공평하게 CPU를 사용해야 하는 경우
- 사용자 응답 시간이 중요한 시스템
🛠️ 문제점
- Time Quantum 설정이 민감
- CPU 버스트가 매우 짧은 프로세스가 많은 경우에도 Time Quantum에 의해 불필요하게 전환될 수 있음
📍MLQ (Multi Level Queue)
: 여러 개의 Ready Queue를 만들어 각 큐마다 서로 다른 스케줄링 정책을 적용하는 방식
- 여러 개의 큐를 가지며, 각각의 큐는 자신만의 스케줄링 기법 사용
- 큐 사이에는 우선순위 기반 스케줄링 적용
- 우선순위가 높은 큐는 응답시간이 빠름
💡 언제 사용?
- 고정된 우선순위로도 충분한 시스템(단순한 서버, 임베디드 시스템)에서 적합
🛠️ 문제점
- 여러 개의 큐 관리로 인해 오버헤드 발생
- 우선순위가 낮은 큐는 Starvation 발생 가능
- 최초 배정된 큐를 벗어나지 못하므로 시스템 변화에 적응하기 힘듦
📍MLFQ (Multi Level Feedback Queue)
: MLQ의 발전된 형태로, 프로세스가 큐 간에 이동할 수 있도록 허용한 선점형 스케줄링
- 큐 간 이동이 허용된 MLQ
- Time Slice를 짧게 설정해 동시성이 높은 느낌을 줄 수 있음
- 기존 스케줄러들의 "긴 작업 독점", "고정 우선순위" 문제를 해결
💡 언제 사용?
- 다양한 성격의 프로세스(짧은 작업, 긴 작업, I/O 중심 작업 등)가 혼재된 상황
- 시스템 반응성과 공정성을 모두 고려해야 하는 다중 사용자 시스템이나 시분할 시스템
🛠️ 문제점
- 설계 및 구현이 복잡
- 여러 개의 큐 관리로 인해 오버헤드 발생
- 우선순위가 낮은 큐는 Starvation 발생 가능
✨ 추가 질문
싱글 스레드 CPU에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까?
MLFQ(Multi-Level Feedback Queue)가 적절하다.
싱글 스레드 CPU에서는 상시로 동작해야 하는 프로세스가 있더라도, 다른 중요한 프로세스들도 함께 처리해야 한다.
이를 위해 우선순위를 기반으로 CPU를 할당하는 MLFQ가 적합하다고 생각한다.
MLFQ는 상시로 돌아가는 프로세스에 높은 우선순위를 부여해 지속적으로 CPU를 사용할 수 있도록 하면서도
그보다 더 우선순위가 높은 다른 프로세스들도 짧은 Time Slice를 활용해 빠르게 대응할 수 있게 해 준다.
프로세스 스케줄링 vs 스레드 스케줄링
우리가 일반적으로 이야기하는 스케줄링 알고리즘은 주로 프로세스(Process)를 대상으로 한다.
하지만 오늘날 시스템에서는 스레드(Thread)도 독립적으로 실행되기 때문에, 스레드 역시 스케줄링의 대상이 될 수 있다.
✅ 동시성과 병렬성
📍동시성 (Concurrency)
: 하나의 코어에서 여러 스레드가 번갈아가며 실행
- CPU가 작업마다 시간을 분할해 적절한 context switching을 통해 동시에 실행되는 것처럼 보이게 함
- 유휴시간을 최소화하는 것이 목표
유휴 시간: 컴퓨터가 작동가능한 상태인데 작업을 하고 있지 않은 시간
🛠️ 문제점
- Race Condition: 여러 프로세스가 하나의 자원에 접근에 실행 결과에 영향을 줄 수 있음
- DeadLock: 여러 프로세스가 서로의 작업이 끝나기를 무한히 대기할 수 있음
- Starvation: 우선순위가 낮은 프로세스는 원하는 자원을 계속 할당받지 못함
📍병렬성 (Parallelism)
: 멀티 코어에서 여러 스레드가 동시에 실행
- 동일한 시간에 독립적인 작업을 실행할 수 있음을 의미
🛠️ 문제점
- 메모리 손상 및 누수: 여러 작업이 같은 메모리 공간에 접근할 경우 충돌 위
- 스레드 간 동기화 문제: 병렬 작업 간 정확한 데이터 일관성 관리 필요
'⚙️ CS > 운영체제' 카테고리의 다른 글
| [운영체제] 프로그램 실행 과정 (0) | 2025.04.29 |
|---|---|
| [운영체제] 동기화 (0) | 2025.04.29 |
| [운영체제] 스레드 (1) | 2025.04.16 |
| [운영체제] 프로세스 (1) | 2025.04.16 |