임베디드 스터디 - 다단계 큐, 다단계 피드백 큐, 멀티프로세서 스케줄링

다단계 큐 (Multilevel Queue)

• 프로세스를 성격에 따라 여러 큐로 분리하고 각 큐마다 다른 알고리즘 적용

큐 1 (최상위) : 시스템 프로세스    → Priority 스케줄링
큐 2          : 인터랙티브 앱      → Round Robin
큐 3 (최하위) : 배치 작업         → FCFS

• 단점 : 프로세스가 한 번 배정된 큐에 고정 → 상황 변화에 대응 불가
• 단점 : 상위 큐에 프로세스가 계속 들어오면 하위 큐는 기아 현상 (Starvation) 발생

다단계 피드백 큐 (Multilevel Feedback Queue)

• 다단계 큐와의 차이 : 프로세스가 동작 패턴에 따라 큐 간 이동 가능
• 현대 OS에서 가장 널리 쓰이는 방식

큐 1 (타임퀀텀 8ms)  : 새 프로세스 진입
        ↓ 타임퀀텀 내 완료 못하면 강등
큐 2 (타임퀀텀 16ms) : 더 긴 시간 할당
        ↓ 또 완료 못하면 강등
큐 3 (FCFS)         : CPU를 오래 쓰는 배치 작업
        ↑ 오래 기다리면 상위 큐로 승급 (Aging 적용)

• CPU를 금방 쓰고 나가는 짧은 프로세스 → 상위 큐에서 처리
• CPU를 오래 쓰는 프로세스 → 자동으로 하위 큐로 강등

멀티프로세서 스케줄링

로드 밸런싱 (Load Balancing)

• 모든 CPU 코어가 균등하게 일하도록 작업을 분배하는 것

방식	설명
Push 방식	과부하 코어가 다른 코어로 프로세스를 밀어냄
Pull 방식	한가한 코어가 바쁜 코어에서 프로세스를 가져옴

캐시 친화성 (Cache Affinity)

• 프로세스를 이전에 실행했던 CPU 코어에 계속 배정하여 캐시를 재활용하는 원칙
• 코어 이동 시 캐시 미스 발생 → 메모리에서 데이터를 다시 불러와야 하므로 성능 저하

로드 밸런싱 vs 캐시 친화성

로드 밸런싱 : 프로세스를 자유롭게 이동 → 균등한 부하
캐시 친화성 : 프로세스를 같은 코어에 고정 → 캐시 재활용
→ OS는 두 가지를 적절히 타협하면서 스케줄링

Gang 스케줄링

• 서로 긴밀하게 협력하는 스레드들을 같은 타임 슬롯에 여러 코어에 함께 배정
• 스레드들이 서로 다른 시간에 실행되면 동기화 문제 발생
• HPC(고성능 컴퓨팅), 병렬 과학 계산 등에서 주로 사용

일반 스케줄링          Gang 스케줄링

코어1: T1 | T3 |      코어1: T1 | T1 |
코어2: T2 | T4 |      코어2: T2 | T2 |
코어3: T4 | T1 |      코어3: T3 | T3 |
코어4: T3 | T2 |      코어4: T4 | T4 |
           ↑                     ↑
      T1~T4가 뿔뿔이       T1~T4가 항상 같은
      다른 시간에 실행       슬롯에 함께 실행

비교 요약

개념	핵심
다단계 큐	프로세스를 성격별 큐로 분리, 큐 고정
다단계 피드백 큐	동작 패턴에 따라 큐 간 이동 가능
로드 밸런싱	코어 간 부하 균등 분배 (Push/Pull)
캐시 친화성	같은 코어에 고정하여 캐시 미스 방지
Gang 스케줄링	협력 스레드를 같은 타임 슬롯에 함께 배정