기술면접을 위한 OS 개념정리 01 - CPU 스케쥴링, 입출력 관리, 디스크 관리

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.
• 기술면접만을 준비하기보다 비전공자 입장에서 OS의 기본적인 내용을 짚기 위해 작성되었습니다.

중요도 - 하: 기술 면접에 나올 가능성은 적으나 워낙 기초라 1독은 해야 안심이 될 듯

CPU, 프로세서, 코어

• 프로세서 : 컴퓨터 운용을 위해 명령을 처리하고 반응하기 위한 논리 회로
  • control unit(신호를 보내는 제어장치) + ALU (사칙 연산, 논리 연산)
• CPU : 장치가 해야할 일을 총 지휘하는 프로세서
• 코어 : 각종 연산을 수행하는 CPU의 핵심 요소

CPU 스케쥴링

• CPU 버스트 : 사용자 프로그램의 CPU를 직접 가지고 빠른 명령을 수행하는 과정
  • Add/Store/Load : 레지스터의 두 값을 더함(속도 매우 빠름)/CPU의 계산된 값을 메모리에 저장/메모리의 데이터를 CPU로 읽어들임
• I/O 버스트 : 커널에 의해 입출력 작업을 진행하는 느린 단계의 수행 과정
• I/O 바운드 프로세스 : I/O 버스트가 빈번하여 CPU 버스트가 짧음. 사용자에게 입출력을 받아 처리해가는 대화형 프로그램이 해당됨
• CPU 바운드 프로세스 : 입출력이 드물게 동작하는 계산 위주의 프로세스
• 바운드 프로세스의 스케쥴링 : 일반적으로 I/O 바운드 프로세스가 많다. 따라서 I/O 바운드 프로세스 위주로 먼저 처리하여 I/O 작업을 수행하게 두고 CPU 바운드 프로세스를 처리하면 전체 시스템의 가용률을 높일 수 있다.

CPU 스케쥴러/디스패처

• CPU 스케쥴러 : 준비 큐에서 어떤 프로세스에 CPU를 할당할 지 결정하는 운영체제의 코드다. 그 외 몇 가지 필요한 상황이 있다.
• 비선점형 방식 : 프로세스가 스스로 반납 전까지 CPU를 빼앗지 않음 - FCFS
• 선점형 방식 : CPU로 처리할 작업이 있음에도 강제로 빼앗을 수 있는 방식 - 시분할

1. 실행 상태의 프로세스가 I/O작업을 요청하여 봉쇄상태로 전환
2. 실행 중인 프로세스가 타이머 인터럽트 발생으로 인해 준비상태로 전환
3. I/O 작업 요청했던 프로세스의 I/O 작업 종료로 인터럽트 발생, 준비 상태로 전환
4. CPU에서 실행 상태에 있는 프로세스가 종료

위의 경우 중 1, 4는 스스로 반납하여 비선점형, 2는 선점형 방식이다. 3은 I/O 작업 완료한 프로세스의 우선순위가 높아 CPU를 빼앗을 경우 선점형에 해당한다.

• 디스패처 : 새로 CPU를 할당받은 프로세스가 작업을 수행할 수 있도록 환경설정하는 코드. 문맥교환 동작을 수행한다.
  • 디스패치 지연시간(latency) : 디스패치 동작에 걸리는 시간, 문맥교환 오버헤드에 해당

스케쥴링의 성능 평가

• 시스템 관점 지표 : CPU 이용률과 처리량 등 시스템 가용 정도 관련 지표
  • CPU 이용률 : 전체 시간 중 CPU 가용 시간
  • 처리량 : 주어진 시간 내 준비 상태의 프로세스 중 CPU 버스트를 완료한 프로세스 개수
  • 처리량을 제고하려면 CPU 버스트가 짧은 I/O 바운드 프로세스를 우선 할당하면 된다.
• 사용자 관점 지표 : 소요시간, 대기시간, 응답시간 등 사용자가 체감하는 대기시간 관련 지표
  • 소요시간 : 준비 큐 대기시간 + CPU 사용 시간(I/O 요청으로 자진 반납 시 반납 때까지)
  • 대기시간 : 이번 CPU 버스트가 끝나기까지 준비큐에서 대기한 시간(시분할 시 여러 번 발생 가능)
  • 응답시간 : 첫 번째 CPU 할당받기까지 준비큐에서의 대기시간. 사용자에겐 가장 중요

스케쥴링 알고리즘

• FCFS(First Come First Served) : 준비 큐 진입 순서대로 CPU 할당. 비선점형 방식이다. 먼저 도착한 프로세스에 따라 평균 대기시간이 가변적이다.
  • 콘보이(Convoy) 효과 : 버스트가 긴 프로세스가 먼저 도착해 짧은 프로세스가 오래 대기해야 하는 현상
• 최단 작업 우선(Shortest-Job-First, SJF) : 버스트가 가장 짧은 프로세스에 제일 먼저 CPU를 할당, 평균 대기 시간이 가장 짧다.
  • 비선점형 방식 : 더 짧은 프로세스가 와도 빼앗지 않음
  • 선점형 방식(Shortest Remaining Time First, SRTF) : 더 짧은 프로세스 진입 시 빼앗음
  • 현실적으로 프로세스의 CPU 버스트 시간을 알기 어렵다.(중간에 뺏기 때문)
  • CPU 버스트 예측 : 예측시간 T, 매개변수 α, 실제시간 t에 대해 $T_{n + 1}=\alpha t_n+(1-\alpha)T_n$으로 산출한다. α가 0이면 $T_{n + 1} = T_n$으로 고정값이다. $T_n$을 풀어쓰면 과거의 실제시간으로 치환되어 $(1-\alpha)^j\alpha t_{n-j}$의 꼴로 표현되어 과거로 갈 수록 영향을 줄여나간다.
  • 기아 현상(starvation) : CPU 버스트가 긴 프로세스는 준비 큐에 무한정 대기하게 된다.
  • 전체 시스템 성능 향상을 위해 CPU 버스트가 긴 프로세스를 희생하여 형평성을 간과함
• 우선순위 : 큐에 대기 중인 프로세스에 우선순위를 부여한다. CPU 버스트가 기준이면 SJF가 된다. 각 프로세스마다 중요도는 다를 수밖에 없으므로 기아 현상 발생 여지가 있으며 대기 시간이 길어질수록 순위를 높이는 노화(aging) 기법을 사용하여 해결한다.
• 라운드 로빈(RR) : CPU 할당 시간(time quantum)을 정해 할당한다. 수행시간이 긴 프로세스가 CPU를 점유하더라도 일정 시간 뒤에 CPU 점유를 해제하고 대기열 맨 뒤에 가게 된다.
  • 프로세스의 context를 저장할 수 있기에 가능한 스케쥴링 기법
  • CPU 사용시간이 랜덤한 프로세스가 같이 실행되는 환경에 효과적이다.
  • CPU 버스트 시간에 따라 소요시한이 일정한 비율로 비례하기 때문에 공정하다.
  • 응답시간이 빨라진다. n개의 프로세스에 대해 할당 시간이 q일 경우 최소 $(n - 1)q$시간 내로 첫 할당을 받는다.
• 할당시간이 길면 FCFS가 되고 너무 짧으면 문맥교환 오버헤드가 커진다.
• 멀티레벨 큐 : 준비 큐를 여러 개로 분리해 관리하는 방식.
  • 전위(foreground) 큐 : 대화형 작업을 담는 큐. 빠른 응답 시간을 위해 RR 사용
  • 후위(background) 큐 : 계산 위주 작업을 담는 큐. 응답시간이 중요하지 않아 FCFS 사용
  • 큐에 대한 스케쥴링 : 전위 큐 작업이 모두 끝나면 후위 큐 작업하는 고정 우선순위 방식과(starvation 발생 가능) RR처럼 시간 제약을 일정 비율로 나누는 타임 슬라이스 방식이 있음.
• 멀티레벨 피드백 큐 : 멀티레벨 큐와 유사하나 프로세스가 다른 큐로 이동이 가능함
  • CPU 버스트 짦음 : RR 할당시간이 짧은 상위 큐에서 빨리 처리. 미완료 시 중간 큐 이동
  • CPU 버스트 중간 : RR 할당시간이 긴 중간 큐에서 처리. 미완료 시 하위 큐로 이동
  • CPU 버스트 김 : RR에서 처리가 안될 경우 계산 위주로 간주. FCFS인 하위 큐에서 처리
• 다중처리기 : CPU가 여러 개인 다중처리 시스템에서의 스케쥴링
  • CPU별로 줄세울 때 프로세스의 편중을 막기 위해 부하균형 매커니즘 필요
  • 대칭형 다중처리 : 각 CPU가 알아서 스케쥴링 결정
  • 비대칭형 다중처리 : 한 CPU가 다른 CPU들의 스케쥴을 책임지고 나머지가 한 CPU에 맞춰 움직임
• 실시간 : 주어진 데드라인이 있어 정해진 시간 내로 처리가 중요함
  • 경성(Hard) 실시간 시스템 : 원자로/미사일 등 데드라인이 반드시 지켜져야 함
  • 연성(Soft) 실시간 시스템 : 실시간 스트리밍 등 데드라인이 지켜지지 않더라도 시스템의 붕괴는 발생하지 않음
  • EDF(Early Deadline Fist) : 데드라인에 임박한 요청부터 처리

스케쥴링의 평가

• 큐잉모델 : 이론적 측정 방식, 수학적으로 계산하여 처리량, 평균 대기시간 산출
• 구현 및 실측 : 실제 코드 기반으로 실측값을 기준으로 측정
• 시뮬레이션 : 가상 스케쥴링 프로그램 작성 후 산출

주변 장치 및 입출력 장치 관리 - 인터럽트

• 인터럽트(interrupt) : CPU의 서비스가 필요할 때나 주변 기기가 서비스를 요청할 때 발생시키는 신호이다. CPU는 인터럽트를 받으면 작업 상태를 저장해두고 인터럽트를 처리한다.
• 인터럽트 처리 루틴(interrupt service routine) / 인터럽트 핸들러 (interrupt handler) : 인터럽트는 장치 종류나 상황에 따라 종류가 다양하므로 그에 따라 해야 할 작업을 정의한 프로그램 코드이다. 커널에 존재하는 CPU 스케쥴링, 메모리 관리 루틴과 마찬가지로 커널코드의 일부이다.
• 인터럽트 핸들링 : 인터럽트가 발생한 경우 처리해야할 일들의 절차, 인터럽트 처리 루틴 / 인터럽트 핸들러에 정의된 내용을 말한다.
  • A 프로그램이 실행 중 인터럽트가 발생하면 A의 현재 상태(CPU에서 실행 중인 명령의 메모리 주소 등)를 저장해야 한다. 프로그램 실행 시 CPU의 임시 기억장치인 레지스터에 읽기 / 쓰기 작업을 하는데 인터럽트로 인해 새로운 명령이 실행되면 기존 레지스터를 비워버리기 때문에 이러한 상태를 저장한 뒤에야 인터럽트 처리를 시작한다.
• 프로세스 제어 블록(process control block, PCB) : OS가 현재 시스템 내에서 실행되는 프로그램들을 관리하기 위해 사용하는 자료구조이다. 프로그램마다 하나씩 존재하며 프로그램이 실행 중인 코드의 메모리 주소, 레지스터 값, 하드웨어 상태등을 저장하여 프로그램의 어느 부분이 실행 중이였는 지 알 수 있다.
  • 프로그램이 실행되는 중 인터럽트가 발생하면 PCB에 저장 후 CPU의 제어권이 인터럽트 처리 루틴으로 넘어간다. 인터럽트 처리가 끝나면 PCB에서 상태를 CPU에 복원해 인터럽트되기 직전의 상태에서 실행을 이어간다.
• 컨트롤러 : CPU에 인터럽트를 송신하기 위한 주변기기의 작은 CPU
• 로컬 버퍼(local buffer) : 메모리에 데이터를 보내기 전 작업을 완료할 때까지 저장하는 공간
• 인터럽트 라인(interrupt line) : 인터럽트 수신 시 CPU에 신호를 전달하는 장치
• 인터럽트 벡터(interrupt vector) : 인터럽트 종류마다 번호를 정해서 그에 맞는 인터럽트 처리 루틴과 매칭시키는 자료 구조
• 소프트웨어 인터럽트(software interrupt) : 하드웨어로부터가 아니라 소프트웨어로부터 발생된 인터럽트이다. 주로, 트랩(trap)이라 불러서 구분한다. 예외 상황(Exception)과 시스템 콜(System Call)이 있다.
  • 예외 상황(Exception) : 사용자 프로그램이 0으로 나누는 시도를 하거나 자신의 할당 메모리 바깥에 접근하는 등 권한 없는 작업 시도에 대한 처리를 발생시키는 인터럽트이다.
  • 시스템 콜 : 사용자 프로그램이 운영체제 내부에 정의된 코드를 실행하고 싶을 때 OS에 전달하는 서비스 요청이다.
    • 프로그램 동작 중 키보드 입력 / 화면 출력 등이 필요할 때 이미 커널에 적재된 코드를 요청한다.

입출력 관리

• 동기식 입출력(Synchronous I/O) : 어떤 프로그램이 입출력 요청을 했을 때 입출력 작업을 완료해야 그 후속작업을 진행하는 방식
  • 예시 :
    1. A 프로그램이 디스크를 읽는 트랩을 발생시킨다.
    2. 입출력 작업이 끝날 때까지 A 프로세스를 봉쇄 상태(blocked state)로 전환시켜 입출력 작업 완료 전까지 CPU를 할당하지 않는다.
    3. 그 동안 다음 대기열의 B 프로그램에 할당하여 작업을 계속 진행한다.
    4. 이후 A 프로세스가 호출한 디스크 입출력 과정이 끝나 CPU에 인터럽트가 수신되면 A 프로그램의 봉쇄 상태를 해제하여 CPU 대기열 큐에 적재한다.
    5. 자신의 차례가 되면 입출력 이후의 작업을 진행한다.동기성 보장 : 입출력 트랩을 발생시킨 A가 봉쇄 상태로 전환되고 다음에 CPU를 할당받은 B 프로그램 또한 동일한 곳에 접근하고자 입출력 트랩을 발생시킨 경우 입출력 장치가 A에서 B가 아닌 B에서 A 순서대로 처리하여 발생하는 문제를 방지하고자 장치 별로 큐를 두고 요청한 순서대로 처리하게끔 보장한다.
• 비동기식 입출력(Asynchronous I/O) : 입출력 작업이 끝날 때까지 기다리지 않고 입출력 작업으로 가져온 데이터가 필요한 경우는 입출력이 끝나고 수행하되 굳이 필요없는 작업은 그대로 이어서 진행한다. 이를테면, 디스크 쓰기는 쓰기 명령을 내린 뒤에 다음 작업을 처리해도 되므로 비동기식 입출력을 사용할 수 있다. 물론 비동기식 입출력의 경우에도 입출력 작업이 끝난 뒤에도 CPU로 작업이 완료되었다는 인터럽트를 전송한다.

• DMA(Direct Memory Access) : 원칙적으로 메모리는 CPU만 접근할 수 있어 CPU를 제외한 장치가 메모리 데이터에 접근하기 위해서는 CPU에 인터럽트를 발생시켜 CPU가 대행해야만 한다. 그러나 매번 CPU가 대행할 경우 기존 업무를 방해받을 수 있어 중간에 CPU말고도 접근이 가능한 장치인 DMA를 둬서 입출력 장치의 메모리 접근 요청에 의한 CPU로의 인터럽트 빈도를 줄여준다.
• 즉, 로컬 버퍼에서 메모리로 데이터를 읽는 작업은 DMA가 수행하며 단위는 byte가 아니라 block 단위로 크게 읽어온다.

보안

• 하드웨어 관점 : 커널 모드와 사용자 모드를 분리하여 실행할 수 있는 명령을 구분한다. 그리고 CPU는 모드 비트 0과 1을 둬서 0인 경우에만 커널 모드의 명령을 수행한다. 1은 사용자 프로그램이 CPU를 점유했을 때 마킹된다. 따라서, 프로그램이 시스템 콜을 하면 운영체제가 CPU를 점유하여 자동으로 모드 비트가 0으로 마킹되고 작업이 완료되면 사용자 프로그램에 CPU를 넘기면서 모드 비트를 1로 세팅한다.
• 메모리 관점 : 하나의 프로그램이 한 영역의 메모리에 적재될 경우 기준 레지스터와 한계 레지스터를 두어 참조값이 범위 내에 있는 지 확인한다. 벗어난 경우 예외상황이라는 트랩을 발생시켜서 종료시킨다.
• CPU 관점 : 타이머라는 장치를 둬서 CPU를 무한 점유하는 일이 없도록 한다. 시분할 시스템에도 사용된다.

디스크 관리

• 논리 블럭 : 데이터가 저장되는 단위
• 섹터 : 논리 블럭이 저장되는 디스크 내 물리적 위치
• 트랙 : 중심에서 거리가 같은 섹터 집합 (2차원 배열에서의 1개의 row와 유사 원판의 회전은 col을 옮긴다고 간주)
• 실린더 : 여러 개의 원판에서 중심으로부터 거리가 같은 트랙의 집합 (2차원 배열의 row와 유사)

디스크 스케쥴링

• 탐색시간 : 헤드를 데이터가 위치한 실린더까지 옮기는 시간
• 회전지연시간 : 디스크의 섹터가 헤드 위치로 도달하기까지의 시간
• 전송시간 : 섹터에서 데이터를 읽고 쓰는 시간
• 회전지연 시간과 전송 시간은 물리적 시간으로 OS는 탐색 시간을 통제하려 노력
• FCFS 스케쥴링 : 요청 순서대로 헤드를 이동
• SSTF(Shortest Seek Time First) : 헤드의 현재 위치에서 가장 가까운 요청부터 이동
  • starvation 문제 발생 가능
• SCAN : 헤드를 양 끝단으로 이동시키며 그 경로에 있는 요청 처리
  • 엘리베이터 스케쥴링 알고리즘이라고도 함
  • C-SCAN(Circular-SCAN) : 양 끝을 왕복하며 탐색하는 SCAN 알고리즘은 양 끝단의 경우 탐색 시간이 지연되기에 한쪽 끝으로 도달하면 방향을 바꾼 뒤엔 요청을 처리하지 않고 다시 출발점으로 회귀
• LOOK : SCAN 알고리즘의 개량 버전. 헤드가 이동하는 방향에 더 이상 요청이 없으면 방향 전환
  • C-LOOK : C-SCAN이 출발점으로 회귀하는 것과 달리 번호가 가장 낮은 요청으로 이동하여 처리 시작

다중디스크 스케쥴링

• 일부 디스크의 오류에도 지속적인 서비스가 가능하며 정보의 유실 방지 가능
• 작업을 수행할 디스크의 결정문제까지 포함, 디스크들의 부하 균형(load balancing) 고려해야 함.

관련 포스팅

1.기술면접을 위한 OS 개념정리 02 - 프로세스, 스레드

2.기술면접을 위한 OS 개념정리 03 - 메모리, 가상 메모리 관리, 웹캐싱 기법

3.기술면접을 위한 OS 개념정리 04 - 프로세스 동기화, 데드락