[CS 정리] 운영체제 (2)

스케줄러

프로세스를 스케줄링하기 위한 Queue

• Job Queue : 시스템에 들어올 때 진입하는 큐, 현재 시스템 내에 있는 모든 프로세스의 집합
• Ready Queue : 현재 메모리 내에 있으면서 CPU를 잡아 실행되기를 기다리는 프로세스의 집합
• Device Queue : 특정 입출력 장치를 대기하는 프로세스의 집합

Process 스케줄러

각각의 Queue에 프로세스들을 넣고 빼주는 스케줄러

장기 스케줄러(Long-term scheduler, Job scheduler)

메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장. 대용량 메모리(일반적으로 디스크)에 임시로 저장

저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 Ready Queue로 보낼지 결정하는 역할

• 메모리와 디스크 사이의 스케줄링을 담당
• 프로세스에 memory(및 각종 리소스)를 할당(admit)
• degree of Multiprogramming 제어(실행중인 프로세스의 제어)
• 프로세스의 상태(new → ready(in memory))
• 시스템에서 새로운 프로세스를 생성하는 간격은 길기 때문에 실행 빈도수가 적다

단기 스케줄러(Short-term scheduler, CPU scheduler)

• CPU와 메모리 사이의 스케줄링을 담당
• Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
  • 어느 프로세스에게 CPU를 할당할지 결정
• 프로세스의 상태(ready → running → waiting → ready)
• 단기 스케줄러는 실행 간격이 짧기 때문에 매우 빨라야하며, 실행 빈도가 잦다

중기 스케줄러(Medium-term scheduler, Swapper)

• 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄(Swapping)
• 프로세스에게서 Memory를 deallocate(반납)
• degree of Multiprogramming 제어
• 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러
• 프로세스의 상태(ready → suspended)

CPU 스케줄러

CPU가 유휴상태가 될 때마다 Ready Queue에 있는 프로세스를 대상으로 실행될 프로세스를 선택

디스패치(Dispatch) : 운영체제가 프로세스를 프로세서에 할당하는 것. 프로세스 상태가 ready → running 으로 바뀜. 

 

큐에 있는 레코드들은 일반적으로 프로세스들의 PCB

 

스케줄링이 발생하는 상황

1. 프로세스가 실행 상태에서 대기 상태로 전환
2. 프로세스가 실행 상태에서 준비 완료 상태로 전환
3. 프로세스가 대기 상태에서 준비 완료 상태로 전환
4. 프로세스 종료

1, 4에서만 스케줄링이 발생하면 비선점. 아니라면 선점형 스케줄링

 

비선점 스케줄링

• 프로세스가 할당된 뒤 CPU를 방출할 때까지 점유
• 일괄 처리 방식에 적합
• 중요한 작업이 중요하지 않은 작업을 기다리는 경우 발생 가능

 

선점형 스케줄링

• 프로세스가 CPU를 할당받아 실행하고 있을 때, 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 올 수 있다
• 우선순위가 높은 프로세스를 빠르게 처리 가능
• 주로 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용

평가 기준

• CPU 사용량(CPU Utilization)
• 처리량(Throughput) : 단위 시간당 완료된 작업의 개수
• 소요 시간(Turnaround Time) : 작업이 요청되고 완료되기까지 걸린 시간
  • 수행 시간(Burst Time) : 쉬지않고 CPU를 할당했을 때 예상 처리시간. 선점 등에 의해 Turnaround time이 더 길어질 수 있다
• 대기 시간(Waiting Time) : 대기 큐에서 기다린 시간
• 응답 시간(Response Time) : 요청이 도착된 시간부터 응답이 발생한 시점까지 걸린 시간

FCFS(First Come First Served)

특징

• 먼저 온 고객을 먼저 서비스 해주는 방식, 즉 먼저 온 순서대로 처리
• 비 선점형(Non-Preemptive) 스케줄링
• 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않음
• 할당되었던 CPU가 반환될 때만 스케줄링이 이루어짐

 

문제점

• convoy effect : 소요 시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상

SJF(Short Job First)

특징

• 다른 프로세스가 먼저 도착했어도 CPU burst time이 짧은 프로세스에게 선 할당
• CPU 버스트가 같다면 FCFS를 적용
• 주어진 프로세스 집합에 대해 최소 평균 대기시간을 가진다는 점에서 최적임이 증명 가능
  • 다음 CPU 버스트의 길이를 파악하기 어려워 단기 CPU 스케줄링 수준에서 구현불가 
• 선점형, 비선점형 모두 가능
  • 프로세스가 실행되는 동안 새로운 프로세스가 더 짧은 CPU 버스트를 가질 때, 실행하는 프로세스를 선점한다면 선점형 프로세스. 선점형 SJF 알고리즘(Shortest Remaing Time First)

 

문제점

• 기아 상태(starvation) 
  효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것.
  극단적으로 CPU 사용이 짧은 Job을 선호. 따라서 사용 시간이 긴 프로세스는 거의 영원히 CPU 할당을 받지 못함

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링
• 우선순위가 같다면 FCFS
• 선점형 스케줄링(Preemptive) 방식
  • 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점
• 비선점형 스케줄링(Non-Preemptive) 방식
  • 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다

 

문제점

• 기아 상태(starvation)
• 무기한 봉쇄(Indefinite blocking)
  실행할 준비는 되어있지만 CPU를 사용하지 못하는 프로세스를 CPU가 무기한 대기하는 상태

 

해결책

• 노화(aging)
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높임

Round Robin

특징

• 시분할 시스템을 위해 설계
• 각 프로세스는 동일한 크기의 할당 시간(time quantum, 시간 할당량)을 갖는다
• 할당 시간이 지나면 프로세스는 선점당하고 Ready Queue의 제일 뒤에가서 다시 줄을 선다
• Round Robin 은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을경우 효과적
• 가능한 이유는 프로세스의 context를 save할 수 있기 때문

 

장점

• Response time이 빨라진다
  • N개의 프로세스가 Ready Queue에 있고 할당 시간이 Q(time quantum)인 경우 프로세스는 Q단위로 CPU 시간의 1/N을 얻는다. 즉 어떤 프로세스도 (N-1)Q time unit 이상 기다리지 않는다
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가. 공정한 스케줄링

 

주의할 점

• 설정한 time quantum이 너무 커지게 되면 FCFS와 같아진다
• 너무 작게 되면 스케줄링 알고리즘의 목적에는 이상적이지만 context switching이 작아 overhead가 발생하기 때문에 적당한 time quantum이 중요

 

---

 

메모리 관리 전략

메모리 관리 배경

각각의 프로세스는 독립된 메모리 공간을 가지고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. 단지, 운영체제 만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제한을 받지 않는다

Swapping

운영체제가 정한 주기마다 스케줄링 정채에 따라 프로세스를 주 메모리에서 보조 메모리로, 다시 보조 메모리에서 주 메모리로 이동시키는 것

메모리 관리를 위해 사용되는 기법

표준 Swapping 방식으로는 Round Robin과 같은 스케줄링의 다중 프로그래밍 환경에서 CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억장치(하드디스크)로 내보내고(Swap Out) 다른 프로세스의 메모리를 불러 들일 수 있다(Swap In)

단편화(Fregmentation)

프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할만큼의 작은 자유 공간들이 늘어나게 되는데 이를 단편화라고 한다

외부 단편화

메모리 공간 중 사용하지 못하게 되는 일부분. 물리 메모리(RAM)에서 사이사이 남는 공간들을 모두 합치면 충분한 공간이 되는 부분들이 분산되어 있을 때 발생

 

해결방법

• 압축(compaction) : 메모리의 모든 내용을 한군데로 몰고 모든 자유 공간들을 다른 한 군데로 몰아 클 블록으로 만드는 것
  • 재배치가 정적으로 이루어진다면 불가능. 동적으로 재배치가 가능한 경우에만 사용 가능
  • 압축 작업 중 시스템은 다른 작업을 할 수 없다
• 통합(Coalescing) : 인접한 단편화 영역을 하나의 영역으로 통합하는 작업

내부 단편화

프로세스가 사용하는 공간에 포함된 남는 부분

예) 메모장을 켰는데 4KB만큼 할당해 주었지만 실제 1KB만 사용하고 있을 때 필요 이상으로 메모리를 할당받아 내부 단편화가 3KB만큼 발생

페이징(Paging)

가상 메모리를 사용. 외부 단편화를 해결

• 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애는 메모리 기법
• 외부 단편화를 방지하고 압축 작업을 불필요하게 함
• 보조 기억장치를 이용한 가상 메모리(논리 메모리)를 같은 크기의 블록으로 나눈 것(페이지), RAM(물리 메모리)을 페이지와 같은 크기로 나눈 것(프레임)
• 사용하지 않는 프레임을 페이지에 옮기고 필요한 메모리를 페이지 단위로 프레임에 옮기는 기법
• 페이지와 프레임을 대응시키기 위해 page mapping 과정이 필요해 paging table을 만든다
• 페이징 기법을 사용하면 연속적이지 않은 공간도 활용할 수 있어 외부 단편화 문제를 해결 가능
• 코드가 reentrant code라면 공유가 가능(Shared Page)

 

단점 : 내부 단편화 문제의 비중이 증가

페이지를 너무 작게하면 내부 단편화 문제를 해결할 수 있지만 page mapping table이 많아져 효율이 감소

세그멘테이션(Segmentation)

가상 메모리 사용, 내부 단편화 해결, 외부 단편화 존재

• 페이징에서 논리 메모리와 물리 메모리를 같은 크기의 블록이 아닌 서로 다른 크기의 논리적 단위(Segment)로 분할
  • main, function, method, object 등 인간적인 관점으로 나누는 것
• 연속적인 공간에 저장되어 있다
• 세그먼트 테이블에는 각 세그먼트 별 세그먼트 시작주소와 세그먼트 길이정보를 가지고 있다

 

단점 : 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 자유 공간들이 많은 수의 작은 조각들로 나누어져 못 쓰게 될 수도 있다(외부 단편화)

 

 

---

               

가상 메모리

메모리로서 실제 존재하지는 않지만 사용자에게 있어 메모리로서 역할을 하는 메모리

가상 메모리에 수용된 프로그램이 실행될 때에는 실제 메모리를 필요로한다

프로세스들이 연속된 물리적 메모리 공간처럼 여기게 만듦

필요한 부분만 메모리에 올림으로써 메인 메모리에 올라가는 프로세스의 크기를 줄인다

 

개발 배경

이전에는 실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 따라서 메모리 용량보다 큰 프로그램은 실행불가

또한, 여러 프로그램을 동시에 메모리에 올리면 용량의 한계와 페이지 교체 등의 성능 이슈가 발생

가끔 사용되는 코드가 차지하는 메모리들을 확인할 수 있다는 점에서 불필요하게 전체가 메모리에 올라와 있어야하는게 아님을 알게됨

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려야한다

가상메모리는 프로세스 전체가 메모리 내에 올리지 않더라도 실행 가능하도록 하는 기법

프로그램이 물리 메모리보다 커도 된다는 장점

하는 일

가상 메모리는 실제 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것

작은 메모리를 가지고 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공

 

💡 가상 주소 공간
한 프로세스가 메모리에 저장되는 논리적인 모습을 가상 메모리에 구현한 공간
프로세스가 요구하는 메모리 공간을 가상 메모리에서 제공함으로 현재 직접적으로 필요하지 않은 메모리 공간은 실제 물리 메모리에 올리지 않는 것으로 메모리 절약 가능

ex) 프로그램이 실행되며 논리 메모리로 100kb가 요구되지만 실행까지 필요한 메모리 공간(heap, stack, code, data)의 합이 40kb라면 실제 물리 메모리에는 40kb만 올라가고 나머지 60kb만큼은 필요시 물리 메모리(보조기억장치 등)에 요구

 

CPU가 생성하는 주소 = 논리 주소(logical address) = 가상주소(virtual address)
메모리 상에서 유효한 주소(MAR, 메모리 주소 레지스터에 주어지는 주소) = 물리 주소(pysical address)

 

💡 Mapping

가상 메모리에 프로그램이 실행될 경우 어떤 과정을 통해 실제 메모리로 옮기는 것
매핑은 MMU(메모리 관리 장치, Memory Management Unit)라는 하드웨어에 의해 지원

요구 페이징(Demand Paging)

프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신 초기에 필요한 것들만 적재하는 전략

가상 메모리 스세템에서 많이 사용되며 가상 메모리는 대게 페이지로 관리

요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재

한 번도 실행되지 않은 페이지는 물리 메모리에 적재❌

 

프로세스 내의 개별 페이지들은 페이저(Pager)에 의해 관리

페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어와 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 감소

 

 

페이지 폴트(Page Fault)

프로그램이 자신의 주소공간에는 존재하지만 시스템의 RAM에는 현재 없는 데이터나 코드에 접근을 시도했을 때 발생하는 현상

프로세스에 필요한 데이터만 적재하기때문에 적재되지 않은 페이지를 요구하는 경우가 발생

 

과정

CPU가 원하는 주소를 MMU에 전송

→ MMU는 주소 변환 과정에서 페이지 테이블(table)에 주소에 대한 항목이 없다고 표시

→ MMU는 CPU를 인터럽트한 후 페이지 폴트 처리기라는 소프트웨어가 실행

→ 페이지 폴트 처리기가 원하는 페이지를 디스크 상 어디에 위치하는지 찾은 후 읽어옴

 

💡 페이지 테이블(Page Table)

프로세스의 페이지 정보를 저장. 하나의 프로세스는 하나의 페이지 테이블 소유
테이블은 색인(페이지 번호)와 내용(해당 페이지에 할랑된 물리 메모리)으로 구성

TLB(Translation Look-aside Buffer, 변환 우선 참조 버퍼)

MMU에서 사용하는 특정한 소형 하드웨어 캐시, 일종의 page cache

페이지 테이블은 메인 메모리(주 기억장치)에 저장되기 때문에 메모리를 액세스 할 때마다 물리 기억장치의 주소를 얻기 위해 테이블을 조회와 가상 기억장치에 필요한 데이터를 얻기 위한 접근, 총 두번을 접근해야 하기 때문에 액세스 시간이 길어져 문제를 해결하기 위해 프로세서 내장 캐시인 TLB를 사용

 

key(Page 번호), value(Frame 번호)로 구성

페이지 를 키와 비교해 발견되면 프레임 번호를 반환해 주고, 메모리의 페이지 테이블에서 찾아 TLB에 추가된다

페이지 교체

프로그램 실행시 모든 항목이 물리 메모리에 올라오지 않기 때문에 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재)가 발생하면 원하는 페이지를 보조 기억장치에서 가져옴

하지만 물리 메모리가 모두 사용중인 상황이라면 페이지 교체가 발생해야 함!

 

기본적인 방법

1. 디스크에서 필요한 페이지의 위치를 찾는다
2. 빈 페이지 프레임을 찾는다
   1. 페이지 교체 알고리즘을 통해 희생(victim)될 페이지를 고른다
   2. 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정
3. 새롭게 비워진 페이지 테이블 내 프레임 새 페이지를 읽어오고, 프레임 테이블을 수정
4. 사용자 프로세스 재시작

 

💡 전역 교체(global replacement)와 지역 교체(local replacement)

전역 교체 방법은 모든 페이지 프레임이 교체 대상이 될 수 있는 것이고, 지역 교체는 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법

지역 교체는 프로세스마다 프레임을 미리 할당하는 것을 전재. 반면 전역 교체는 전체 메모리를 각 프로세스가 공유해 사용하고, 교체 알고리즘에 근거해 할당되는 메모리량이 가변적으로 변하는 방법 

FIFO 페이지 교체

First In First Out

가장 간단한 페이지 교체 알고리즘, 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 나가게 된다

큐를 만들어 구현이 가능하다

 

장점

• 이해하기 쉽고, 프로그램하기 쉬움

 

단점

• 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있음
• 처음부터 활발하게 사용되는 페이지를 교체해 페이지 부재율을 높이는 부작용 초래
• Belady의 모순 : 페이지를 저장할 수 있는 페이지 프레임의 개수를 늘려도 페이지 부재가 더 많이 발생하게 되는 모순이 존재

최적 페이지 교체(Optimal Page Replacement, MIN)

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체, 가장 낮은 페이지 부재율을 보장

비교 연구 목적을 위해 사용

 

장점

• 알고리즘 중 가장 낮은 페이지 부재율을 보장
• Belady의 모순 현상을 야기하지 않음 ⇒ 스택 알고리즘

 

단점

• 구현의 어려움
• 모든 프로세스의 메모리 참조 계획을 파악할 방법 없음

💡 스택 알고리즘(stack algorithm)
n개의 프레임에 적재되는 페이지의 집합이 항상 n+1개의 프레임에 적재되는 페이지 집합의 부분집합이 되는 알고리즘

LRU 페이지 교체(Least Recently Used)

최적 알고리즘의 근사 알고리즘. 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체

대체적으로 FIFO보다 우수하고 OPT보다는 그렇지 않은 모습

Belady의 모순 현상을 야기하지 않음(스택 알고리즘)

 

지원할 수 있는 컴퓨터 시스템은 거의 없고, 대부분 참조 비트(reference bit)형태로 지원

 

❓ LRU를 구현할 수 있는 자료구조는? ⇒ LinkedHashMap (LinkedList + HashMap)

LFU 페이지 교체(Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체하는 방법. 활발하게 사용되는 페이지는 참조 횟수가 많아질 것이라는 가정에서 만들어진 알고리즘

집중적으로 사용됨으로 참조 횟수가 커지지만 이후 사용되지 않더라도 계속 메모리에 머뭄

최적 페이지 교체(OPT)를 제대로 근사하지 못해 잘 사용하지 않는다

MFU 페이지 교체(Most Frequently Used)

참조 횟수가 가장 적은 페이지가 최근 메모리에 올라왔고 앞으로 계속 사용될 것이라는 가정에 기반

최적 페이지 교체를 제대로 근사하지 못해 잘 사용하지 않는다

NUR(Not Used Recently)

최근 사용되지 않은 페이지를 교체하는 것

최근 사용된 메모리 페이지를 유지하는 것을 선호하는 것이다

 

스레싱(Thrashing)

프로세스의 처리시간보다 페이지 교체 시간이 더 많아지는 현상

원인

프로세스가 원활하게 수행되기 위해서는 일정수준 이상의 페이지 프레임을 할당받아야 하는데, 다중 프로그래밍의 정도가 너무 높아(= 너무 많은 프로세스가 적재되어) 프로세스가 프레임을 충분히 할당받지 못해 페이지 부재가 발생.

활발하게 사용되는 페이지들을 모두 적재하지 못해 교체되는 즉시 바로 필요해지게 되고, 곧바로 읽어 들어야 할 페이지를 연속적으로 교체하게 되며 발생

 

해결 방법

• 다중 프로그래밍 정도를 적정 수준으로 유지한다
• 페이지 부재율(page fault rate)을 조절한다
• working set(작업 집합)을 유지한다
• 프로세스가 필요로 하는 만큼 프레임을 제공
• 일부 프로세스를 종료

 

💡 woking set(작업 집합)
지역성을 토대로 프로세스가 일정시간동안 원활하게 수행되기 위해 메모리에 한꺼번에 올라가야하는 페이지들의 집합

페이지 부재율과 직접적인 연관 존재
페이지 부재율이 증가 → 다음 지역성으로 진입, 작업집합의 변화, 상승하는 시점이 다음 지역성의 시작점
페이지 부재율이 감소 → 자주 사용하는 페이지가 거의 적재, 작업집합의 안정화

 

캐시의 지역성

원리

캐시 메모리는  속도가 빠른 장치와 느린 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리

CPU가 어느 데이터를 원할 것인가를 어느정도 예측할 수 있어야한다

캐시의 성능은 작은 용량의 캐시 메모리에 CPU가 이후 참조할 쓸모 있는 정보가 어느정도 들어있느냐에 좌우됨

 

이 때 적중률(Hit race)을 극대화 시키기 위해 데이터의 지역성(Locality)의 원리를 사용

지역성의 전제 조건으로 프로그램은 모든 코드나 데이터를 균등하게 access하지 않는다는 특성을 기본으로 함

즉, Locality란 기억 장치 내의 정보를 균등하게 access하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성

• 시간 지역성(Temporal Locality) : 최근에 참조된 주소는 가까운 시간 내에 계속 참조할 가능성이 높다는 특성
• 공간 지역성(Spatial Locality) : 대부분의 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

 

 

 

---

📚 Reference

Abraham Silberschatz, 『Operating System Concepts』, 조유근, 홍릉과학출판사(2013)
https://github.com/JaeYeopHan/Interview_Question_for_Beginner
https://github.com/WeareSoft/tech-interview
https://github.com/gyoogle/tech-interview-for-developer