OS 깨끗하게 리뷰하기 (1)

지금까지 Network, DB를 리뷰했다. OS도 빼먹을 수 없다고 생각한 필자는 OS의 기본 상식에 대해서 빠르게 훑고자 한다.

스케줄러

프로세스를 스케줄링하기 위한 Queue는 크게 Job Queue, Ready Queue, Device Queue가 있다. Job Queue는 시스템에 있는 모든 프로세스의 집합, Ready Queue는 메모리 내에 있으면서 CPU에서 실행되길 대기하는 프로세스의 집합, Device Queue는 Device I/O의 작업을 대기하는 프로세스의 집합이다. 장기 스케줄러는 ready queue로 어떤 프로세스를 보낼지 정하며 new -> ready의 역할을, 단기 스케줄러는 ready -> running -> waiting -> ready를 하며 프로세스에 CPU 할당을 하는 역할을 한다. 중기 스케줄러는 ready->suspended되며 프로세스 전체로 메모리에 디스크로 swapping하며 여유 공간을 마련한다.

swapping에서 내보내는건 swap-out, 다시 불러오는건 swap-in이다. 메모리 공간이 부족할때 swapping이 일어난다.

CPU 스케줄링

CPU 스케줄링은 CPU를 잘 사용하기 위해 프로세스를 배정하는 것이다 (Ready Queue에 있는 친구들..). CPU 스케줄링에는 크게 preemptive (선점)과 Non-preemtive(비선점) 2가지가 있다. 선점의 경우에는 작업이 다 끝나지 않았는데 다른 프로세스가 강제로 CPU를 점유할 수 있고, 비선점의 경우에는 프로세스 종료나 I/O의 경우가 될때까지 다른 프로세스가 CPU를 점유할 수 없다. 선점은 빠른 응답이 필요할때 좋고, 비선점은 응답시간 예측에 용이하다. 프로세스 상태를 간략하게 포함하면 다음과 같다.

CPU 스케줄링의 알고리즘은 비선점과 선점에 따라 다르다. 먼저 비선점의 경우,

  • FCFS (First Come First Service): 큐에 도착한 순서대로 CPU 할당
  • SJF (Shortest Job First): 수행시간이 짧을 것이라 판단되는 일부터 처리
  • HRN (Highest Response-ratio Next): SJF의 단점을 보완하여 우선순위를 계산한다. 우선순위 = (대기시간 + 실행시간) / 실행시간. 결과값이 높은것에 우선순위를 보완한다.

선점의 경우,

  • Priority Scheduling: 우선순위가 높은 순서대로 처리. 우선순위가 낮으면 무한히 기다릴 수 있음. 기다린 시간에 비례해 우선순위를 한단계씩 높이는 aging방법으로 해결 가능
  • Round Robin: FCFS와 비슷하게 프로세스에 CPU 할당하지만 특정 time slice이내에 실행이 완료되지않으면 다음 순번에게 CPU 자원을 넘겨주고 뒤로 배치됨
  • Multi Level Queue: 그룹을 나눠서 (최고 우선순위, 낮은 우선순위) 그룹마다 다른 큐를 사용
  • Multi Level Feedback Queue: 자신의 Time Slice를 다쓰면 다른 큐로 이동

CPU 스케줄링의 척도에는 Response Time (입력에 대한 반응 시간), Turnaround Time (처음 시작부터 끝까지 걸린 시간), CPU Utilization 등이 있다.

페이징과 세그멘테이션

메모리 관리는 필요하다! 이유인 즉슨 각 프로세스는 다른 메모리에 접근할 수 없고 오직 운영체제만이 접근할 수 있으며, 멀티 프로그래밍 환경에서 한정된 메모리를 효율적으로 활용해야했기에 메모리를 관리하는 것은 필요했다. 이를 이해서 여러가지 기법이 있다.

  1. 연속 메모리 관리
    이것은 프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되는 것이다. 고정 분할 기법과 동적 분할 기법이 있는데, 고정 분할 기법은 고정된 파티션으로 나누는 것이나 내부 단편화가 발생하고, 동적 분할 기법은 파티션들이 동적으로 생성되며 프로세스의 크기와 같은 파티션에 넣는 것이나 외부 단편화가 발생한다.

단편화란? 단편화는 메모리가 생성되고 제거 되면서 메모리 사이 사용하지 못하는 틈이 생기는데, 이것이 단편화다. 외부 단편화는 메모리 공간중 사용하지 못하게 되는 일부분이고, 내부 단편화는 프로세스가 사용하는 메모리 공간 중 남는 부분을 의미한다.

  1. 페이징
    페이징과 세그멘테이션은 불연속 메모리 관리로, 프로그램의 일부가 다른 주소 공간에 할당 될 수 있다. 여기서 페이지란 고정 사이즈의 작은 프로세스 조각이다. 그러나 페이징은 일부 내부 단편화가 발생할 수 있다.

  2. 세그멘테이션
    세그먼트는 서로 다른 크기의 논리적 블록이 연속된 공간에 배치되는 것을 의미한다. 일부 외부 단편화가 발생 될 수 있다.

가상 메모리

가상 메모리는 프로세스 전체가 메모리 위에 올라오지 않아도 실행이 가능하도록 하는 기법이다. 즉, 프로그램이 물리 메모리보다 클 수 있다. 이러한 방식은 필요한 부분만 메모리에 올리는 것으로, 보통 페이지 단위를 자주 쓴다. 이것을 Demanding Paging이라 한다. 프로세스의 개별 페이지들은 페이저에 의해 관리되며 실제로 필요한 페이지만 메모리로 읽어온다.

Page fault의 경우 CPU가 접근하려는 페이지가 메모리에 없는 경우를 뜻한다. 이 경우 missing page를 가져오고 다시 배치함으로서 아무일도 일어나지않은 것처럼 한다.

페이지 교체 알고리즘

메모리가 가득차게 되면 어떤 페이지를 교체시켜야할지 정해야한다. 이때 out될 페이지를 victim page라 한다. 이러한 victim page를 정하게 되면 해당 페이지는 디스크에 기록하고, 페이지 테이블을 수정하여 새 페이지를 읽어오게 된다. Victim page를 정하는 알고리즘을 페이지 교체 알고리즘이라 한다. 몇가지 교체 알고리즘이 있다.

  1. First in First Out (FIFO)
    메모리에 먼저 올라온 페이지를 가장 먼저 내보내는 알고리즘. 초기화 코드에는 적절하다 (프로세스가 실행될때 최초 초기화 이후 다른 역할을 수행하지 않는 코드)
  2. Optimal Page Replacement (OPT)
    앞으로 가장 사용하지 않을 페이지를 우선적으로 내보내는 알고리즘. 구현의 어려움이 좀 있다.
  3. Least Recently Used (LRU)
    최근에 사용하지 않은 페이지를 우선적으로 내보내는 알고리즘. 가장 좋은 방법 중 하나.
  4. Least Frequently Used (LFU)
    참조 횟수가 가장적은 페이지를 우선적으로 내보내는 알고리즘. 어떤 프로세스가 특정 페이지를 집중적으로 사용하다가 다른 기능을 사용하게 되면 더 이상 사용하지 않아도 메모리에 머물게 되어 자주 쓰이지 않음

캐시

캐시란 Main Memory에 저장된 내용의 일부를 임시로 저장해두는 것을 의미한다. CPU와 Main Memory의 속도 차이로 인한 성능 저하를 막는다. 적중률을 극대화 시키기 위해 (hit-miss ratio) 지역성의 원리를 사용한다. 지역성이란 메모리에서 정보를 균일하게 액세스하는게 아닌 특정부분을 집중적으로 참조하는 것으로 시간 지역성 (최근에 참조된 주소가 다음에도 참조됨)과 공간 지역성 (실제 프로그램이 참조된 주소와 인접한 주소가 참조됨)이 있다. 캐시에 목적 데이터가 저장되어 있을때 바로 접근하여 출력할 수 있게 자료구조를 묶어서 저장하는 캐시라인이라는 방법이 쓰인다. 종류는 대표적으로 Full Associative, Set Associative, Direct Map이 있다.

Direct Map은 여러주소가 캐시 메모리의 한 주소에 매핑된다. 이러면 conflict miss가 일어날 수 있다. Full Associative는 비어 있는 캐시 메모리에 마음대로 주소를 저장한다. 찾을때가 문제이다. Set Associative는 특정 행을 지정하고 그 행 안의 열이 비어있으면 저장한다. 둘을 섞은 방식이라 생각하면 편하다.

캐시 미스는 처음 불러서 나는 cold miss, A와 B데이터가 같은 캐시 메모리 주소에 할당되어서 나는 conflict miss, 캐시 메모리 공간이 부족해서 나는 capacity miss가 있다.

파일 시스템

파일이나 자료를 쉽게 발견하기 위해 유지 및 관리하는 방법이다. 커널 영역에서 동작하며 계층적 디렉토리 형태를 가진다. 파일을 빠르게 읽고 쓰고 삭제할 수 있게 해준다. 파일시스템은 파일의 데이터인 데이터 영역과 데이터 영역에 기록된 파일의 위치, 이름등이 적힌 메타 영역으로 나뉘어 있다.

Reference

https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-6.-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS
https://technote-mezza.tistory.com/92
https://gyoogle.dev/blog/computer-science/operating-system