Operating System Concepts 정리 (1)

2022년 04월 27일
제작기간 2022년 03월 22일 ~ 04월 27일
태그 CS

운영체제 (Operating System)

  • 컴퓨터 하드웨어를 관리하는 소프트웨어
  • 자원 할당제, 제어 프로그램 (사용자 수행을 제어) 역할을 수행

운영체제 구조

서비스

  • GUI, 프로그램 적재 및 종료, I/O 연산, 파일 시스템 조작, 통신, error detection
  • Resources allocation(다수의 프로세스나 작업 대상), logging, protection과 security

사용자와 운영체제 Interface

사용자가 운영체제와 접촉하는 방법을 설명함

  • Command Interpreter: Shell(일종의 해석기)에게 제공받을 수 있음
  • GUI, Touch-Screen Interface

System Call

  • OS에 의해 사용 가능하게 된 서비스에 대한 Interface 제공
  • RTE(실행시간 환경)
    • 컴파일러/인터프리터를 포함. 특정 언어로 작성된 Application을 실행하는 데 필요한 전체 소프트웨어 제품 + 라이브러리/로더 등의 타 소프트웨어
    • OS가 제공하는 시스템과의 System Call Interface 제공 → API 함수 호출로부터 Systm Call 호출
    • 프로세스 제어, 파일 조작, 장치 조작, 정보 유지/보수, 통신/보호
  • API(Application programming interface): 프로그래머가 사용 가능한 함수의 집합 명시
    • System Call 보다 사용이 편함
    • API를 지원하는 모든 시스템에서의 컴파일/실행을 기대할 수 있음

System Services

프로그램 개발 및 실행을 위한 환경(System Utility)을 제공

  • System Call Interface부터 복잡한 것까지 포함
  • 파일 관리, 상태 정보, 파일 변경, 프로그래밍 언어 지원, 프로그램 적재/수행, 통신, 백그라운드 서비스(상시 시행되는 서비스로, 서비스, 서브 시스템, 디먼이라고도 함)

Linkers와 Loaders

Disk에 저장된 이진 실행 파일을 컴파일하고 메모리에 배치하여 적절한 CPU 코어에서 실행하는 과정을 설명함

  • 재배치 가능 Object file: 임의의 물리 메모리 위치에 적재되도록 설계된 파일
    • 소스 파일을 위와 같은 오브젝트 파일로 컴파일함
  • Linker: 재배치 가능 오브젝트 파일을 하나의 이진 실행 파일로 결합
    • 타 오브젝트 파일/라이브러리가 실행 파일에 포함될 수 있음
  • Loader: 이진 실행 파일을 적재하는 데 사용
  • 재배치: 프로그램에 최종 주소를 할당, 프로그램 코드와 데이터를 해당 주소와 일치하게 조정, 프로그램 실행 시, 코드가 라이브러리 함수를 호출하고 변수에 접근할 수 있게 함

위 과정을 거치면 CPU 코어에서 실행 가능한 프로세스가 됨

동적으로 라이브러리 Linking

  • 위 설명과는 다르게 동적으로 라이브러리를 링크할 수 있음 (ex. Dynamically linked library)
  • 실행 파일에서 사용하지 않으면 로드하지 않음

운영체제 구조

  1. 모놀리식 구조 (Monolithic Structure)
    1. 커널의 모든 기능을 단일 주소 공간에서 실행되는 단일 정적 이진 파일에 넣음
    2. 구현 및 확장이 어렵고, 한 부분의 변경이 주는 영향이 큼
    3. 성능이 뛰어남
  2. 계층적 접근 (Layered Approach)
    1. 기능이 나뉨
    2. 운영체제의 층은 데이터와 조작 연산으로 구상된 추상적 객체의 구현임
    3. 순차적으로 디버깅 되고, 해당 층은 하위 층의 기능을 사용하기 때문에 디버깅이 쉬움
  3. 마이크로커널 (Microkernels)
    1. 모든 중요하지 않은 구성요소를 커널에서 제거 → 별도의 주소 공간의 사용자 수준 프로그램으로 구현 → 결과적으로 커널의 크기가 줄어듦
    2. 서버를 두고 통신을 제공하는 방식임
    3. 새로운 서비스는 사용자 공간에 추가 → 확장이 쉬움
    4. 다른 하드웨어로의 이식이 쉬움
    5. 서비스 대부분이 사용자 프로세스(커널X)로 수행 → 보안성과 신뢰성
    6. ex. Mach, Darwin(macOS, iOS)
  4. LKM(loadable kernel modules)
    1. 커널은 핵심 구성요소 집합을 가지고 있고, 부팅/실행 중에 부가 서비스를 모듈을 통해 링크 가능
    2. 커널은 핵심 서비스 제공, 다른 서비스는 동적으로 구현하는 것이 설계 방향성
  5. 하이브리드 시스템 (Hybrid Systems)

운영체제 Building과 Booting

  1. 생성
    1. 운영체제 소스 코드 → 운영체제가 실행될 시스템의 운영체제 구성 → 컴파일(시스템 빌드) → 설치 → 컴퓨터와 OS 부팅
  2. 시스템 부트
    1. Booting: 커널을 적재하여 컴퓨터를 시작하는 과정
    2. 부트스트랩 프로그램(부트 로더)가 커널의 위치 찾음 → 커널이 메모리에 적재되고 시작됨 → 커널이 하드웨어를 초기화 → 루트 파일 시스템이 마운트 됨
    3. 다단계 부팅: BIOS (비휘발성 펌웨어에 있는 소형 부트 로더) 실행 → 부트 블록 (2번째 부트 로더) 적재 → 전체 OS를 메모리에 적재

운영체제 디버깅

디버깅은 하드위어와 소프트웨어의 시스템의 오류를 발견하고 수정하는 행위를 말함. 여기서는 소프트웨어 측면에서 살펴봄.

  • 장애 분석
    • 오류 정보를 로그 파일에 기록
    • core dump(프로세스가 사용하던 메모리를 캡쳐한 것)를 취하고 저장
    • crash(커널 장애)도 오류 정보가 log 파일에 저장되고, memory의 상태가 crash dump에 저장됨
  • 성능 관찰 및 조정 (Performance Monitoring and Tuning)
    • Counters: 호출된 시스템 콜 횟수, 네트워크 장치 또는 디스크에 수행된 작업 수 등의 시스템 활동을 추적 (통계)
    • Tracing: 시스템 콜과 관련된 단계와 같은 특정 이벤트에 대한 데이터 수집
  • BCC (BPF Compiler Collection)
    • Linux 동적 커널 추적을 위한 툴킷
    • 검증기(명령어가 시스템 성능이나 보안에 영향을 주는 지 확인함)를 통과해야 작동 보장

프로세스 관리

Process는 실행 중인 프로그램임. 대부분의 시스템에서 작업의 단위임. 최신 운영체제는 여러 하드웨어 처리 코어가 있는 시스템에서 여러 제어 스레드를 병렬로 실행함.

Process 개념

실행 중인 프로그램. 현재 활동의 상태는 프로그램 카운터 값과 프로세서 레지스터 내용으로 나타냄.

  • 프로세스 메모리는 섹션으로 구분됨
  • 이러한 섹션은 다음과 같은 구성임
    • 텍스트 섹션 (실행 코드), 데이터 섹션 (전역 변수), 힙 섹션 (동적으로 할당되는 메모리), 스택 섹션 (함수에서 사용하는 임시 데이터. 복귀 주소, 매개 변수, 지역 변수 등)
  • 함수 호출 시, 활성화 레코드(activation record)가 Stack에 푸쉬됨. 함수에서 제어가 돌아오면 Pop됨.
  • 메모리가 동적으로 할당되면, Heap이 커지고, 메모리가 반환되면 축소됨
  • 스택과 힙은 서로의 방향을 향해 확대되지만 겹치면 안 됨.
  • 프로세스 상태는 new, running, waiting, ready, terminated로 구분
  • PCB (Process Control Block): 프로세스 상태, 프로그램 카운터, CPU 레지스터, CPU 스케줄링 정보, 메모리 관리 정보, accounting 정보, I/O 상태 정보
  • Thread: 현대 운영체제는 한 프로세스가 다수의 실행 스레드를 가질 수 있도록 하며, 이 정보는 PCB에 포함됨

Process Scheduling

프로세스 스케줄러는 코어에서 실행 가능한 여러 프로세스 중에서 하나의 프로세스를 선택함. 한 번에 하나의 프로세스만 실행 가능한 코어에 배치

  • 다중 프로그래밍 정도: 현재 메모리에 있는 프로세스 수
  • 스케줄링 큐(Queue): 프로세스가 시스템에 들어가면 준비 큐에 들어가 준비 상태가 되고 코어에서 실행되기를 기다림
  • wait queue: I/O 완료와 같은 특정 이벤트가 발생하기를 기다리는 프로세스가 삽입됨
  • 새 프로세스는 준비 큐에 놓임 → 실행을 위해 선택되거나 디스패치 될 때까지 기다임 → CPU core가 할당되고 실행
    • → I/O 요청 공표 or 자식 프로세스 생성 후 종료를 대기 → 대기 큐
    • → 인터럽트나 타임 슬라이스 만료로 코어에서 제거됨 → 준비 큐
  • Context Switch (문맥 교환)
    • 이전의 프로세스 상태를 보관 후, 새 프로세스의 보관된 상태를 복구. PCB에 표현됨
    • 문맥 교환은 순수히 오버헤드임

Process에 대한 연산

  • 자식 프로세스 생성 시, 자식은 자원(CPU 시간, 메모리, I/O 장치, file)이 필요
  • 이 자원은 OS나 부모 프로세스에게 받을 수 있음
  • 부모 프로세스는 자식 프로세스가 자신의 자원의 부분 집합을 사용하게 제한할 수 있음
  • cascading termination: 부모 프로세스 종료 시, 자식 프로세스도 잇따라 종료
  • 좀비: 종료 되었지만 부모가 wait()을 호출하기 전 상태
  • 고아: 부모가 wait()을 호출하지 않고 종료

Process 간 통신 (Interprocess Communication)

IPC라고 부름. 협력적(서로 영향을 주는) 프로세스 관계에서 통신이 필요하기에 나온 개념.

  • 정보 공유, 계산 가속화, 모듈성을 보장하기 위함
  • shared memory와 message passing으로 구분 가능함

1. 공유 메모리

  • 공유 메모리 영역이 구축되며, 각 프로세스는 해당 영역에 쓰고 읽기를 반복함
  • 공유 메모리 영역 구축 시에만 시스템 콜이 필요 → 빠름
  • 메모리에 접근 금지한다는 제약 조건이 해제됨 → 동일 시간, 동일 위치에 쓰지 않도록 책임
  • 동시에 읽고 쓰기가 진행되기 위하여 버퍼(buffer) 사용
    • 무한 버퍼(unbounded buffer): 한계가 없기 때문에, 생산자에게 제약이 없음
    • 유한 버퍼(bounded buffer): 버퍼가 가득 찬 경우 생산자가 대기해야 함

2. 메세지 전달 모델

  • 협력 프로세스들 사이에 메세지를 교환함
  • 충돌 회피의 필요성이 없음. 적은 양의 데이터를 교환하는 데 용이
  • 통상 시스템 콜을 사용하여 구현. 커널 간섭 등의 부가적인 소비 시간 필요 → 느림
  • 분산 환경(통신하는 프로세스들이 네트워크에 의해 연결된 타 컴퓨터에 존재할 수 있음)에서 용이
  • 직접 통신
    • 각 프로세스는 통신의 수신자 or 송신자 명시
    • 프로세스 각 쌍 사이에는 딱 하나의 연결만 존재
  • 간접 통신
    • mailbox 또는 port로 메세지가 송수신
    • 두 프로세스가 공유 mailbox를 가져야 통신 가능
  • OS가 소유한 메일박스는 자체적으로 존재함
  • 일반적으로 송신자의 포트에서 수신자의 포트로 메세지를 복사하는 데에서 성능 저하가 발생

동기화

메세지 전달은 blocking, unblocking(비봉쇄형) 방식으로 전달됨

  • blocking: 수신할 때까지 보냄
  • unblocking: 송신 후 원래 작업 재개

버퍼링

  • 교환되는 메세지는 임시 큐에 들어가있음
  • 임시 큐는 무용량(큐 최대 길이 0 → 반드시 기다려야 수신), 유한 용량, 무한 용량으로 구현 가능

IPC 시스템의 사례

1. POSIX 공유 메모리

  • 메모리-사상 파일을 사용하여 구현됨
  • 메모리-사상 파일은 공유 메모리의 특정 영역을 파일과 연관시킴

2. Mach 운영체제

  • 분산시스템 용으로 설계되었으나 macOS, iOS 등의 데스크톱/모바일 시스템에도 적합함
  • Mach 커널은 프로세스와 유사하지만 다중 태스크(제어 스레드가 많고 관련 자원이 적음) 생성 및 제거를 지원
  • 대부분의 통신은 ‘메세지’로 수행. 복잡한 메세지의 경우, 데이터가 저장된 메모리 위치를 가리키는 포인터를 전달(Out-of-line)
  • port(Mach의 메일박스)로 메세지 주고 받음
  • 각 태스크는 부트스트랩 포트에 액세스 할 수 있음 → 태스크가 생성한 포트를 시스템 전체의 부트스트랩 서버에 등록 가능 → 다른 태스크가 포트를 검색하고 메세지를 보낼 수 있게 됨
  • 복사 연산(메세지 전달)
    • 이를 피하기 위한 가상 메모리 관리 기술 채택
    • 수신자의 주소 공간에 송신자의 메세지가 포함된 주소 공간을 매핑함 → 복사가 일어나지 않음 (단, 같은 시스템에서만 사용 가능)

3. Windows

  • 모듈화를 이용한 기능 향상 및 확장성 강화
  • ALPC(advanced local procedure call facility): 고급 로컬 프로시저 호출 설비: 메세지 전달 설비
  • connection port와 communication port 두 가지의 포트를 사용함
  • 서버 프로세스가 모든 프로세스가 접근 가능한 연결 포트 객체 공표 → 클라이언트가 서비스를 원하는 경우, 서버의 연결 포트 객체 핸들러를 열어 요청을 보냄 → 서버는 채널을 생성하고 핸들을 반환함
    • 여기서 채널은 한 쌍의 사적인 통신 포트로 구성됨 (클라이언트→서버, 서버→클라이언트)

4. Pipes

  • 두 프로세스가 통신할 수 있게 하는 전달자
  • 단방향 통신 / 양방향 통신 (반이중/전이중)
  • Anonymous pipe: 단방향, 두 프로세스는 부모-자식의 관계 → 동일한 기계상의 두 프로세스만 통신 가능함을 의미
  • Named pipe: 양방향도 가능, 관계 제약 X, 지명 파이프는 다수의 writer를 가짐
    • FIFO: UNIX에서의 지명 파이프. 양방향을 지원하지만, 반이중 전송만 가능하고, 양방향을 위해서는 2개의 FIFO를 사용함
    • 동일하지 않은 기계상의 통신에서는 소켓을 사용함

클라이언트 서버 환경 통신

  • Socket: 통신의 endpoint를 뜻함
    • 양 프로세스마다 하나씩, 총 2개의 소켓이 필요
    • 각 소켓은 IP주소, 포트 번호를 접합하여 구별
    • 포트
      • well-known포트: 전 세계적으로 표준으로 사용. Telnet, ftp, http가 있음
      • 127.0.0.1: 자신의 기계
    • 클라이언트 프로세스가 연결을 요청 → 호스트 컴퓨터가 포트 번호(>1024)를 부여
    • TCP(연결 기반), UDP(비연결성)
    • 구조화되지 않은 바이트 스트림만을 통신하도록 함
  • 원격 프로시저 호출 (RPC: Remote Procedure Calls)
    • 네트워크에 연결된 두 시스템 사이의 통신에 사용하기 위하여 프로시저 호출 기법을 추상화하는 방법으로 설계
    • 메세지 기반 통신. 메세지는 구조화되어 있고, 데이터의 패킷 수준을 넘어섬
    • 포트: 메세지 패키지의 시작 부분에 포함되는 정수. 서비스를 구분하기 위해 여러 개 가질 수 있음 (단, 네트워크 주소는 하나)
    • 클라이언트가 원격 호스트의 프로시저 호출하는 것을 마치 자신의 프로시저 호출하는 것처럼 해줌
    • 클라이언트에 스텁을 제공하여 통신 → 필요한 자세한 사항들을 숨겨 줌
    • 클라이언트가 원격 프로시저 호출 → RPC는 그에 대응하는 스텁을 호출 → 원격 프로시저가 필요로 하는 매개변수 건넴 → 스텁이 원격 서버의 포트를 찾음 → 매개변수를 정돈(marshall)함
      • parameter marshalling: 클라이언트와 서버 사이의 데이터 표현 방식 차이를 해결
    • 기종 중립적인 데이터 표현 방식을 정의 (ex. XDR)
    • 정확히 한 번 호출을 보장: RPC 요청 수신 후에, ACK 메세지를 보냄. ACK를 받을 때까지 RPC 호출 재전송

스레드와 병행성 (Threads & Concurrency)

스레드는 CPU 이용의 기본 단위. 스레드는 ID, PC(프로그램 카운터), 레지스터 집합, 스택으로 구성됨. 같은 프로세스에 속한 다른 스레드와 운영체제 자원(코드, Data Section, 열린 file, 신호)을 공유함.

  • 프로세스 생성은 시간과 자원을 필요로 하기 때문에, 프로세스 안에 여러 스레드를 만드는 것이 효율적
  • 각 스레드는 장치 관리, 메모리 관리, 인터럽트 처리 같은 작업 수행

Multicore Programming

단일 컴퓨터 칩에 여러 컴퓨팅 코어(OS에 별도의 CPU로 인식됨)를 배치하는 시스템

  • 각 코어에 별도의 스레드를 할당할 수 있음 → 스레드가 병렬로 실행될 수 있음
  • 데이터 병렬 실행(데이터의 부분집합을 다수의 계산 코어에 분배), 태스크 병렬 실행 (태스크/스레드를 다수의 코어에 분배)기법이 있으며 혼합 가능

Multithreading Models

사용자 수준에서는 사용자 스레드, 커널 수준(OS 위)에서는 커널 스레드를 위한 지원이 제공됨. 두 종류의 스레드에는 일종의 연관관계가 있음.

  • 다대일: 다수의 사용자 스레드를 하나의 커널 스레드로 사상
    • 개발자가 원하는 만큼의 사용자 수준 스레드 생성을 허용
    • 커널은 한 번에 하나의 커널 스레드만 스케줄 → 병렬 실행 X
  • 일대일: 하나의 사용자 스레드에는 하나의 커널 스레드로 사상
    • 더 많은 병렬 실행은 가능
    • 개발자가 한 응용 내에 만들 수 있는 스레드를 제한하거나 양을 주의해야함
  • 다대다: 다수의 사용자 스레드를 그 이하의 커널 스레드로 멀티플랙스
    • 위 두 단점을 어느 정도 해결
    • 두 수준 모델(two-level model): 다대다 모델 + 한 사용자 스레드가 하나의 커널 스레드에만 연관되는 것을 허용
  • 처리 코어 수가 증가하며 커널 스레드 제한의 중요성 감소 → 일대일로 처리해도 됨

Thread Library

프로그래머에게 스레드를 생성하고 관리하기 위한 API를 제공함.

  • 구현 방법
    • 사용자 공간에서만 라이브러리 제공: 코드와 자료구조는 사용자 공간에 존재. 커널의 지원 X. 라이브러리 함수 호출은 사용자 공간의 지역 함수 호출을 의미
    • 커널 수준 라이브러리를 구현: 코드와 자료구조는 커널 공간에 존재. 라이브러리 API 호출은 System Call을 의미
  • 비동기 스레딩: 다중 스레드 서버에서 사용되는 전략. 반응형 사용자 인터페이스를 설계하는 데에 흔히 사용
  • 동기 스레딩: 부모 스레드가 하나 이상의 자식 스레드를 생성, 상당한 양의 데이터 공유를 수반

Implicit Threading (암묵적 스레딩)

스레딩의 생성과 관리 책임을 응용 개발자로부터 컴파일러와 실행시간 라이브러리에게 넘기는 전략

  • 작업은 일반적으로 함수로 작성됨
  • 런타임 라이브러리는 일반적으로 다대다 모델 사용, 별도의 스레드에 매핑
  • 개발자가 병렬 작업만 식별만 하면 됨 → 라이브러리가 스레드 생성 및 관리에 대한 특정 세부 사항을 결정함
  • 스레드 풀
    • 스레드 생성 소요 시간을 절약하기 위함
    • 최대 스레드 수의 한계를 지정하기 위함
    • 태스크 생성 방법을 태스크로부터 분리하면, 태스크 실행을 다르게 할 수 있음 (ex. 태스크 실행 전 딜레이를 넣어 스케줄, 주기적 실행…)
  • Fork Join
    • 스레드 생성 전략 모델
    • fork 단계에서 스레드 구축 X → 병렬 작업만 식별
    • 라이브러리가 생성할 실제 스레드 수를 결정하는 동기 버전의 스레드 풀임
    • 문제가 직접 해결할 만큼 작은 상태의 기준 결정이 필요
    • fork된 작업의 큐를 유지 관리하며, 스레드 큐가 비어있으면 다른 스레드 큐에서 작업을 가져올 수 있음 (work stealing 알고리즘) → 스레드 간의 부하 분산

Threading Issues

  • System Call: fork와 exec 호출에 따른 스레드 복제 범위(해당 스레드 or 전체) 결정
  • 신호 처리(Signal Handling): 모든 신호마다 커널이 실행시키는 디폴트 신호 처리기가 존재. 이는 신호 처리를 위해 호출되는 사용자 정의 처리기로 대체 가능
  • Thread Cancellation: 스레드가 끝나기 전에 강제 종료시키는 작업
    • 취소되어야 할 스레드를 target thread(목적 스레드)라고 칭함
    • 취소는 비동기식 취소(한 스레드가 목적스레드를 강제 종료), 지연 취소(목적 스레드가 주기적으로 자신의 종료 필요성을 점검)로 발생 가능
  • Thread-Local Storage(TLS)
    • 한 프로세스에 속한 스레드는 데이터를 공유하기 때문에 자신만이 액세스 가능한 데이터 공간이 필요
    • 정적 데이터와 유사함
  • Scheduler Activations
    • 스레드 라이브러리와 커널의 통신 방법 중 하나
    • 커널은 응용에 LWP 집합 제공 → 응용은 사용자 스레드를 가용한 가상 처리기로 스케줄 → 커널은 응용에게 특정 이벤트를 알림(upcall이라는 프로시저)
    • upcall은 응용 스레드가 봉쇄하려고 할 때 발생
      • upcall 발생 → 커널은 새로운 가상 처리기를 응용에 할당
      • → 응용은 새로운 가상 처리기상에서 upcall 처리기를 수행 → upcall 처리기는 봉쇄 스레드의 상태를 저장 + 스레드가 실행 중이던 가상 처리기를 반환
      • → upcall 처리기는 새로운 가상 처리기에서 실행 가능한 다른 스레드 스케줄
    • LWP(경량 프로세스): 다대다/두 수준 모델은 사용자와 커널 스레드 사이의 중간 자료구조. 하나의 커널 스레드에 부속되어 있음

CPU 스케줄링

다중 프로그래밍은 CPU 이용률 최대화를 위해, 항상 실행 중인 프로세스를 가지게 하는 데 있음. 특정 프로세스가 대기해야 할 경우, 운영체제는 CPU를 해당 프로세스로부터 회수, 다른 프로세스에 할당함.

최신 운영체제는 프로세스가 아니라 커널 수준의 스레드를 스케줄링함.

  • CPU-I/O 버스트 사이클
    • 프로세스 실행은 CPU 실행과 I/O 대기로 사이클로 구성
    • CPU burst → I/O burst → CPU burst → …
    • I/O 중심의 프로그램의 CPU 버스트는 짧고, CPU 중심의 프로그램의 CPU 버스트는 긺
  • CPU 스케줄러: 프로세스는 CPU 에서 실행되기 전까지 준비 큐에서 대기하며, 큐에 있는 레코드들은 PCB임
  • Preemptive and Nonpreemptive Scheduling(선점 및 비선점 스케줄링)
    • 비선점(협조적) 스케줄링 방법: 대기 전환, 종료 전환에서만 스케줄링이 발생 → 실시간 컴퓨팅에 불리
    • 선점 스케줄링 방법: 모든 상황에서 가능. 경쟁 조건을 만들 수 있음
  • Dispatcher (디스패처)
    • CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈
    • 문맥 교환, 사용자 모드로 전환, 프로그램 재개를 위해 프로그램의 적절한 위치로 이동하는 일
    • 디스패치 지연(latency): 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간
    • 자발적 문맥 교환: 현재 사용 불가능한 자원을 요청했기에 프로세스가 CPU 제어를 포기
    • 비자발적 문맥 교환: 타임 슬라이스가 만료 or 우선순위가 더 높은 프로세스에 의해 선점됨… CPU 빼앗김

스케줄링 기준

  • CPU 이용률
  • 처리량: 단위 시간당 완료된 프로세스의 개수
  • 총처리 시간: 프로세스를 실행하는 데 소요된 시간 (준비큐 대기 시간, CPU에서 실행한 시간, I/O 시간)
  • 대기 시간: 준비 큐에서 대기하는 시간의 합
  • 응답 시간: 요구를 제출한 후, 응답이 나올 때까지의 시간. 총처리 시간은 최선의 기준이 아닐 수도 있기 때문에 생긴 기준

스케줄링 알고리즘

  • 선입 선처리 (FCFS)
    • CPU 버스트 시간이 크게 변할 경우, 평균대기 시간도 상당히 변할 수 있음
    • Convoy effect(호위 효과): 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU 양도하기를 기다리는 현상
  • 최단 작업 우선 스케줄링 (SJF)
    • 다음 CPU 버스트의 길이를 알 방법이 없음 → CPU 스케줄링 수준에서 구현X → 근삿값을 계산하여 짧은 정도를 예상
    • 선점형의 경우, 남은 시간에 의해 작업의 길이가 정해짐 → 최소 잔여 시간 우선 스케줄링이라고도 부름
  • 라운드 로빈 스케줄링 (Round-Robin Scheduling)
    • 선입 선처리와 유사 + 선점
    • 시간 할당량(time quantum), 타임 슬라이스(time slice)라는 작은 단위의 시간을 정의
    • CPU는 준비 큐(원형 큐)를 돌면서 한 번에 하나의 프로세스에 한 번의 시간 할당량 동안 CPU를 할당(timer가 인터럽트를 걸도록 설정)함
    • CPU 버스트의 80%는 시간 할당량보다 짧아야 이득 (10~100 밀리초의 시간 할당량이 평균)
  • 우선순위 스케줄링
    • 무한 봉쇄(indefinite blocking) / 기아 상태(starvation)이 발생할 수 있음
    • 노화(Aging)으로 방지. 주기적으로 대기 중인 프로세스의 우선순위를 증가시킬 수 있음
  • 다단계 큐 스케줄링 (Multilevel Queue Scheduling)
    • 우선순위마다 별도의 큐를 갖는 것이 좋을 때가 있음 (우선순위 검색을 위해 O(n)의 검색이 필요할 수 있음)
    • 우선순위가 정적으로 할당되며, 프로세스는 실행시간 동안 동일한 큐에 남아 있음
    • 각 큐는 절대적인 우선순위를 가지고 있음
  • 다단계 피드백 큐 스케줄링
    • 다단계 큐 + 프로세스가 큐들 사이를 이동하는 것을 허용
    • 정의 요소: 큐의 개수, 각 큐의 스케줄링 알고리즘, 노화(높은 우선순위로 이동) 시기 결정 방식, 강등 시기 결정 방식, 프로세스에 큐 배정하는 방식

스레드 스케줄링

최신 운영체제에서 스케줄 되는 대상은 프로세스가 아니라 커널 수준의 스레드임

  • 경쟁 범위 (Contention Scope)
    • PCS (프로세스 경쟁 범위): 동일한 프로세스에 속한 스레드들 사이에서 CPU 경쟁
    • SCS (시스템 경쟁 범위): 실제로 CPU 상에서 실행되기 위해서, 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄 하는 것이 필요, 어느 커널 스레드를 스케줄 할 것인지 SCS 필요
  • Pthread Scheduling
    • 다대다 모델을 구현하는 시스템에서, PTHREAD-SCOPE-PROCESS 정책이 사용자 수준 스레드를 가용한 LWP로 스케줄함
    • Linux, macOS 시스템은 PCS를 사용하지 않고, 일대일 스레드 시스템을 사용

멀티 프로세서 스케줄링

여러 개의 CPU가 사용 가능하면, 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(load sharing)가 가능함. 다중 처리기(multiple processor)는 여러 개의 물리 프로세서를 제공하는 시스템을 말함

  • 비대칭 다중 처리: 마스터 서버(프로세서 중 하나)가 모든 스케줄링 결정과 I/O 처리, 다른 시스템 활동을 취급하게 하는 것
  • 대칭 다중 처리(SMP): 각 프로세서는 스스로 스케줄링 할 수 있음. 각 프로세서의 스케줄러가 준비 큐 검사 및 실행할 스레드 선택
    • 모든 스레드를 공동 준비 큐에서 관리: 공유 준비 큐에 경쟁 조건이 생길 수 있음
    • 각 프로세서가 자신만의 스레드 큐 관리: 경쟁 이슈가 없음 + 캐시 메모리 사용이 효율적 → 일반적으로 사용함
  • 다중 코어 프로세서
    • 동일한 물리 칩 안에 여러 처리 코어를 장착 → 각 코어는 구조적인 상태 유지 → 각 코어가 개별적인 논리적 CPU로 보여짐
    • memory stall: 프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리며 시간을 허비하는 현상. 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 발생함
    • 메모리 스톨을 막기 위해, 하나의 코어에 2개 이상의 하드웨어 스레드를 할당 → 메모리를 기다리는 동안 코어가 스레드를 전환할 수 있음 (칩 다중 스레딩)
    • coarse-grained(거친): 메모리 스톨과 같은 긴 지연시간의 이벤트가 발생할 때까지 한 코어에서 실행 → 명령어 파이프라인이 타 스레드 수행 전에 완전히 정리 되어야 함 → 교환 비용 큼
    • fine-grained(세밀한): 명령어 주기의 경계와 같이 좀 더 세밀한 정밀도를 가진 시점에 스레드 교환 발생 → 구조적 설계는 스레드 교환을 위한 회로를 포함 → 스레드 간 교환 비용 작음
  • 부하 균등화 (load balancing)
    • push migration: 특정 태스크가 주기적으로 각 처리기의 부하를 검사 + 불균형 상태에서는 과부하인 처리기에서 덜 바쁜 처리기로 스레드를 이동(push)
    • pull migration: 쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 pull 받음
    • 모든 큐에 대략 같은 수의 스레드가 있는 것을 목표
  • 처리기 선호도 (Processor Affinity)
    • 스레드에 의해, 가장 최근에 접근한 데이터가 해당 처리기의 캐시를 채움. 스레드에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족 (warm cache)
    • 그러나, 스레드가 이주하면, 캐시 메모리 내용은 무효화 되며, 이주한 프로세서의 캐시는 다시 채워야 함 → 비용 큼 → SMP를 지원하는 OS에서는 스레드 이주 X + 같은 프로세서에서 계속 실행 : 프로세서 선호도
    • 약한 선호도: 노력하는 정책은 있지만 보장은 하지 않음
    • 강한 선호도: 프로세스는 자신이 실행될 처리기 집합을 명시할 수 있음
    • NUMA(non-uniform memory access): 모든 CPU가 하나의 물리적 주소 공간을 공유할 수 있지만, CPU는 자신의 로컬 메모리에 더 빠르게 액세스 할 수 있음
  • 이기종 다중 처리 (Heterogeneous Multiprocessing)
    • 다중 코어 아키텍처를 전력 소비를 유휴 수준으로 조정하는 기능을 포함하여, 클록 속도 및 전력 관리 측면에서 차이가 나는 코어를 사용하여 설계
    • 고성능 big 코어와 에너지 효율적인 LITTLE 코어를 결합
    • ex. 고성능 요구 X + 긴 작업 → little 코어에 할당 / 반대 → big 코어에 할당

실시간 CPU 스케줄링

연성 실시간 시스템(중요한 실시간 프로세스 실행 보장 X)과 경성 실시간 시스템(엄격한 조건을 요구)으로 구분함

  • 지연시간 최소화
    • 인터럽트 지연시간: 인터럽트 발생 → 우선 수행 중이던 명령어 완수 → 인터럽트 종류를 결정 → 인터럽트 서비스 루틴(ISR) 사용하여, 수행 중인 프로세스 상태 저장
    • 디스패치 지연시간: 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간
  • 우선순위 기반 스케줄링
    • 단순 우선순위 기반으로는 경성 실시간 시스템 대응 불가능
    • 승인 제어 알고리즘: 프로세스가 자신의 마감시간을 스케줄러에게 알려야 할 수도 있음 → 마감시간 이내에 완수할 수 있는 프로세스만 허가
  • Rate-Monotonic 스케줄링
    • 선점 가능한 정적 우선순위 정책을 이용. 주기 태스크들을 스케줄 함 (주기에 따라서 우선순위 결정)
  • Earliest-Deadline-First 스케줄링
    • 마감시간에 따라서 우선순위를 동적으로 부여
  • 일정 비율 몫 스케줄링
    • 모든 응용에 T개의 시간 몫을 할당하여 동작
  • POSIX 실시간 스케줄링

사례

  • Linux
    • 완전 공평 스케줄러(CFS)가 디폴트
    • 각 클래스별로 우선순위를 부여받는 스케줄링 클래스에 기반
  • Window
    • 우선순위에 기반을 둔 선점 스케줄링 알고리즘 사용
    • 디스패처: 커널 중 스케줄링을 담당
    • UMS(사용자 모드 스케줄링) 도입: 응용 프로그램이 커널과는 독립적으로 스레드를 생성하고 관리할 수 있게 함
    • fiber: 많은 사용자 스레드가 하나의 커널 스레드에 사상되는 것이 가능하게 함. 그러나 TEB(스레드 환경 블록) 공유가 필요해서 API 호출이 불가했음
    • UMS가 모든 사용자 모드 스레드 스스로 각자의 문맥을 저장하게 하여 fiber 단점을 극복함
  • Solaris
    • 우선순위 기반 스레드 스케줄링
    • 다단계 피드백 큐를 사용하여 우선순위를 동적으로 바꾸고, 서로 다른 길이의 타임 슬라이스를 할당
    • 우선순위가 높을 수록 작은 타임 슬라이스를 할당 받음
    • 9에서 고정 우선순위와 공평 공유의 새로운 스케줄링 클래스를 도입

알고리즘 평가

  • CPU 이용률, 응답 시간, 처리량에 정의
  • 결정론적 모델링 (Deterministic Modeling)
    • 분석적 평가의 한 가지 유형
    • 사전에 정의된 특정한 작업 부하를 받아들여, 그 부하에 대한 알고리즘 성능 정의
    • 알고리즘 설명에 용이
  • 큐잉 모델
    • 도착률과 서비스율을 통해 이용률, 평균 큐의 길이, 평균 대기 시간등을 계산할 수 있음
    • 정확성 떨어짐
  • 모의 실험
    • 추적 파일(실제 시스템 관찰한 기록) 사용 가능
    • 비용이 큼(시간, 메모리) 그러나 정확함
  • 구현
    • 희귀 테스트를 통해서 특별한 상황 테스트 가능

토막지식

  • HADOOP: 클러스터형 시스템에서 빅데이터의 분산처리에 사용되는 Open source 프레임워크
  • Darwin
    • 커널환경. Mach 마이크로커널과 BSD UNIX 커널이 포함됨
    • Mach와 BSD, 2개의 시스템 콜 인터페이스를 제공
  • WSL (Windows 서브 시스템): Window에서 Linux 응용 프로그램을 실행할 수 있도록 지원
  • Kernighan의 법칙: 디버깅이 코드를 작성하는 것보다 어렵기 때문에, 코드를 영리하게 짰다면 정의에 따라 디버깅을 할 수 없다.