[스터디3] 운영체제 - 04. CPU 스케줄링 알고리즘

목차

 

이번에는 3.4 섹션 위주로 운영체제에 대해 정리하겠습니다. 스케줄링 알고리즘은 공부를 계속 해도 어렵게 느껴지는 것 같습니다. 추가적으로 책 하나를 더 참고해서 공부를 진행했습니다.

3장 운영체제

3.2 메모리

3.2.1 메모리 계층

• 메모리 계층: 레지스터, 캐시, 메모리, 저장장치로 구성됨.
  • 메모리 계층은 경제성과 캐시 때문에 존재함.

▲ 메모리 계층

구분	휘발성 여부	속도	기억 용량	설명	예시
레지스터	휘발성	가장 빠름	가장 적음	CPU 내부에 위치하여 연산에 필요한 데이터를 가장 빠르게 제공함.	-
캐시	휘발성	빠름	적음	CPU와 주기억장치 사이의 데이터 전송 속도 차이를 줄이기 위해 사용됨.	L1, L2, L3 캐시
주기억장치	휘발성	보통	보통	시스템이 실행 중인 프로그램의 데이터와 명령어를 저장, 접근 속도가 캐시보다 느리지만 HDD보다 빠름.	RAM
보조기억장치	비휘발성	낮음	많음	시스템의 전원이 꺼져도 데이터가 유지되며, 대량의 데이터를 저장할 수 있음.	HDD, SSD

▲ 메모리 계층 표

• 캐시(cache): 빠른 장치와 느린 장치 간의 속도 차이에 따른 병목 현상을 줄이기 위해서 데이터를 미리 복사해 놓는 임시 저장소(메모리)
  • 데이터 접근 시간과 계산 시간을 줄일 수 있음.
  • 계층 간 속도 차이를 해결하기 위해서 계층과 계층 사이에 캐싱 계층을 배치함.
  • 캐시를 직접 설정할 때는 지역성을 기반으로 자주 사용하는 데이터를 저장해야 함.
    
    • 시간 지역성(temporal locality): 최근 사용한 데이터에 다시 접근하려는 특성
    • 공간 지역성(spatial locality): 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성
  • 캐시히트: 캐시에서 원하는 데이터를 찾은 경우 → 속도 빠름
  • 캐시미스: 캐시에서 원하는 데이터가 없어 주 메모리로 가서 데이터를 찾아오는 경우 → 속도 느림
  • 캐시매핑: 캐시가 히트되기 위해 매핑하는 방법
    1. 직접 매핑(direct mapping): 메모리가 1~100이 있고, 캐시가 1~10이 있음. 1:1~10, 2:1~10... 으로 매핑하는 방법. 처리가 빠르지만, 충돌 발생이 잦음.
    2. 연관 매핑(associative mapping): 순서를 일치시키지 않고, 관련 있는 캐시와 메모리를 매핑함. 모든 블록을 탐색해야 해서 속도가 느리지만, 충돌이 적음.
    3. 집합 연관 매핑(set associative mapping): 직접 매핑 + 연관 매핑. 순서는 일치시키지만, 집합으로 저장하여 블록화되어 있음. 메모리가 1~100이 있고 캐시가 1~10이 있다면, 캐시 1~5에는 1~50의 데이터를 무작위로 저장하는 방법.
• 쿠키: 만료기한이 있는 키-값 저장소. 4KB까지 데이터를 저장할 수 있음.
• 로컬 스토리지: 만료기한이 없는 키-값 저장소. 웹 브라우저를 닫아도 유지됨.
• 세션 스토리지: 만료기한이 없는 키-값 저장소. 탭을 닫을 때 데이터가 삭제됨. 클라이언트에서만 수정 가능함.

3.2.2 메모리 관리

• 가상 메모리(virtual memory): 컴퓨터가 실제 메모리 자원을 추상화하여 매우 큰 메모리로 보이게 만드는 것. 가상 주소와 실제 주소가 매핑하고, 프로세스의 주소 정보가 있는 페이지 테이블로 관리됨. 속도 향상을 위해 TLB를 사용함.
  • 가상 주소(logical address): 가상적으로 주어진 주소
  • 실제 주소(physical address): 실제 메모리상에 있는 주소
• 스와핑(swapping): 가상 메모리에는 존재하지만 RAM에는 현재 없는 데이터나 코드에 접근할 경우, 메모리에서 당장 사용하지 않는 영역을 하드디스크로 옮기고 하드디스크의 일부분을 메모리처럼 불러와 쓰는 것.
• 페이지 폴트(page fault): 프로세스의 주소 공간에는 존재하지만, 지금 컴퓨터의 RAM에는 없는 데이터에 접근했을 경우에 발생함.
• 스레딩(thrashing): 메모리의 페이지 폴트율이 높은 것. 메모리에 너무 많은 프로세스가 동시에 올라가게 되면 발생하며, 컴퓨터의 성능 저하를 초래함.
  
  • 해결 방법
    1. 작업 세트(working set): 프로세스의 과거 사용 이력인 지역성을 통해 결정된 페이지 집합을 만들어서 미리 메모리에 로드하는 것
    2. PFF(Fage Falut Frequency): 페이지 폴트 빈도를 조절하는 방법으로 상한선과 하한선을 만드는 방법
• 연속 할당: 메모리에 연속적으로 공간을 할당하는 것
  1. 고정 분할 방식(fixed partition allocation): 메모리를 고정된 크기로 미리 나누어 관리하는 방식. 내부 단편화가 발생함.
     • 내부 단편화(internal fragmentation): 메모리를 나눈 크기보다 프로그램이 작아서 들어가지 못하는 공간이 많이 발생하는 현상
     • 외부 단편화(external fragmentation): 메모리를 나눈 크기보다 프로그램이 커서 들어가지 못하는 공간이 많이 발생하는 현상
     • 홀(hole): 할당할 수 있는 빈 메모리 공간
  2. 가변 분할 방식(variable partition allocation): 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용함. 외부 단편화가 발생함.
     
     • 최초적합(first fit): 위쪽이나 아래쪽부터 시작해서 홀을 찾으면 바로 할당함.
     • 최적적합(best fit): 프로세스의 크기 이상인 공간 중 가장 작은 홀부터 할당함.
     • 최악적합(worst fit): 프로세스의 크기와 가장 많이 차이가 나는 홀에 할당함.
• 불연속 할당: 메모리를 연속적으로 할당하지 않는 것
  1. 페이징(paging): 동일한 크기의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당하는 방식
  2. 세그멘테이션(segmentation): 페이지 단위가 아닌 의미 단위인 세그먼트로 나누는 방식. 홀 크기가 균일하지 않음.
• 페이지 교체 알고리즘
  • 오프라인 알고리즘(offline algorithm): 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘
  • FIFO(First In First Out): 가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법
  • LRU(Least Recently Used): 참조가 가장 오래된 페이지를 바꾸는 방법
  • NUR(Not Used Recently): LRU에서 발전하였음. 0과 1을 가진 비트를 두어 시계 방향으로 돌면서 0을 찾은 순간 해당 프로세스를 교체하는 방법
  • LFU(Least Frequently Used): 가장 참조 횟수가 적은 페이지를 교체하는 방법

3.4 CPU 스케줄링 알고리즘

• 기본적으로 스케줄링은 기본적으로 프로세스의 실행이 끝나면 이루어짐. 실행 도중 스케줄링이 이루어지는 시점이 두 가지 있음. 1에서만 수행되는 비선점형 스케줄링, 1과 1 모두에서 수행되는 선점형 스케줄링이 있음.
  1. 실행 상태에서 입출력 작업을 위해 대기 상태로 전환될 때
  2. 실행 상태에서 타이머 인터럽트가 발생해 준비 상태로 변경될 때

▲ 스케줄링 유형

• CPU 스케줄링 알고리즘: 운영체제가 프로세스에 CPU를 배분하는 방법. CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것이 목표임.

▲ CPU 스케줄링 알고리즘

분류	알고리즘	특징	장점	단점
비선점형	FCFS(First Come, First Served)	가장 먼저 도착한 프로세스를 가장 먼저 처리	간단하고 공정	긴 작업 앞에 짧은 작업이 대기할 수 있음(convoy effect)
	SJF(Shortest Job First)	실행 시간이 가장 짧은 프로세스부터 처리	평균 대기 시간 최소화	긴 작업은 계속 대기할 수 있음(기아 현상)
	우선순위(Priority)	우선순위가 높은 작업을 먼저 처리, 나이 들수록 우선순위 증가(aging) 사용으로 보완	우선순위 기반 작업 처리	낮은 우선순위 작업이 계속 대기할 수 있음
선점형	라운드 로빈(Round Robin)	각 프로세스에 동일한 시간 할당, 시간 내에 끝나지 않으면 준비 큐 뒤로 이동	공정하고 응답 시간 단축	시간 할당량에 매우 민감하며 설정이 중요
	SRF(Shortest Remaining Time First)	현재 실행 중인 작업보다 짧은 잔여 시간을 가진 새 작업이 도착하면 즉시 교체	최소 대기 시간 보장	빈번한 컨텍스트 스위칭 가능성
	다단계 큐(Multi-level Queue)	우선순위에 따라 여러 큐 사용, 각 큐는 독립적 스케줄링 정책 적용	우선순위별 효율적 처리 가능	큐 간 이동 제한으로 유연성 저하

▲ CPU 스케줄링 알고리즘 표

3.4.1 비선점형 방식

• 비선점형 방식(non-preemptive): 프로세스가 스스로 CPU 소유권을 포기하는 방식. CPU 자원을 사용하는 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없음. 컨텍스트 스위칭으로 인한 부하가 적음.
  1. FCFS(First Come, First Served): 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘. 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect)이 발생함.
  2. SJF(Shortest Job First): 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘. 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 발생함. 평균 대기 시간이 가장 짧음. 과거의 실행했던 시간을 추측함.
  3. 우선순위: 오래된 작업일수록 우선순위를 높이는 방법(aging)을 사용해 보완한 알고리즘. 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 방식.

3.4.2 선점형 방식

• 선점형 방식(preemptive): 현대 운영체제가 사용함. 운영체제가 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고, 강제로 다른 프로세스에 CPU 자원을 할당하는 방식. 컨텍스트 스위칭 과정에서 오버헤드가 발생할 수 있음.
  • 라운드 로빈(RR: Round Robin): 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘. 로드밸런서에서 트래픽 분산 알고리즘으로도 사용함. FCFS+타임 슬라이스(프로세스가 CPU를 사용하도록 정해진 시간)라고 볼 수 있음.
  • SRT/SRF(Shortest Remaining Time First): SJF를 확장한 형태로, 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘. SJF+RR이라고 볼 수 있음.
  • 다단계 큐: 우선순위에 따른 준비 큐를 여러 개 사용하는 방식. 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용함. 큐 간 프로세스 이동이 안 되므로 스케줄링 부담이 적지만, 유연성이 떨어짐.
  • 다단계 피드백 큐(multilevel feedback queue): 다단계 큐 스케줄링과 비슷하지만, 프로세스들이 큐 사이를 이동할 수 있다는 차이가 있음.

 

⭐ 참고자료

 

1) 강민철, 『이것이 취업을 위한 컴퓨터 과학이다 with CS 기술 면접』, 한빛미디어(2024), p198-201.

 

이 글은 『 면접을 위한 CS 전공지식 노트 』 책을 학습한 내용을 정리한 것입니다.