Jump to:
Navigation

01. OS의 단권화

in Study / Computer Science / Operating System on Blog

컴퓨터 구성요소

  1. Processor
  2. Main Memory
  3. IO Module
  4. System bus

System Bus 종류

  1. Address Bus : 소스, 목적지 지정
  2. Data Bus : 데이터 전송
  3. Control Bus : R/W 같은 명령

Program이란

Instruction과 Data의 집합

Process란

프로그램이 메모리로 적재되어 구동되는 것

레지스터 존재 이유

IO 처리 시간이 느리기 때문에 Memory Bus로의 접근을 최소화 하기 위해서

Memory 종류

  1. SRAM : Static RAM, 6개의 트랜지스터가 1bit를 구성, 가성비 비쌈, 매우 빠르고 refresh 필요 X

  2. DRAM : Dynamic RAM, 1개의 트랜지스터, 1개의 캐퍼시터로 1bit을 구성, 가성비 쌈, SRAM에 비해 느리고 refresh 필요

  3. FLASH MEMORY : Floating gate를 이용해서 구현, 읽고 쓰는 속도 비대칭, No in-place update (쓰려고 하는 섹터에 이미 데이터가 있었다면 수정 불가 => 지우고 써야 함), Non volatile( 전원 공급이 끊겨도 데이터 유지 )

SRAM, DRAM 차이

구분SRAMDRAM
1Bit 구성6개 트랜지스터1개 트랜지스터와 1개 캐퍼시터
용량 대비 가격비쌈쌈(상대적으로)
속도빠름느림(상대적으로)
refresh 필요 유무XO
휘발성 유무OO

Flash Memory 특징

  • Floating gate를 이용해서 구현
  • 읽고 쓰는 속도 비대칭
  • No in-place update (쓰려고 하는 섹터에 이미 데이터가 있었다면 수정 불가 => 지우고 써야 함)
  • 내구성 한계 (블럭마다 지우고 쓸 수 있는 횟수가 존재, 다 쓰면 해당 블럭 사용 불가 => 모든 블럭이 균등하게 유지되는게 좋음 => wear leveling)
  • Non-Volatile (전원이 꺼져도 데이터가 유지됨)

Memory

flowchart TD; A(Memory) --> B(Non Volatile); A(Memory) --> C(Volatile); C(Volatile) --> D(SRAM); C(Volatile) --> E(DRAM); B(Non Volatile) --> F(Flash Memory);

HDD 특징

Hard Disk Drive

  • 용량이 크다
  • 충격에 약하다
  • 느리다

SSD란

Flash Memory 기반으로 HDD처럼 사용하기 위해 FTL(Flash Translation Layer)로 Interface화 함 읽기 쓰기는 page 단위, 삭제는 block단위

Write amplication

FTL이란

host의 논리 주소를 ssd의 물리 주소로 변환

Processor 구성 요소

  1. Algebra : Operator와 Operand의 집합 (연산자와 피연산자)
  2. ALU : Arithmetic and Logical Unit : 수학적 계산을 처리하는 것
  3. 기타 레지스터들

CPU란

ALU를 포함한 Register와 Control Unit, Cache 등으로 instruction을 수행하는 것 Memory에 올라온 Instruction을 처리하는 것

특수 목적 레지스터

  1. PC

    Program Counter 다음 실행할 명령어의 주소를 가리킴

  2. IR

    Instruction Register 불러온 Instruction을 저장

  3. PSW

    Program Status Word 프로그램의 상태 저장( kernel 모드인지, user 모드인지 등)

  4. MAR

    Memory Address Register 불러올 메모리의 주소 저장

  5. MBR

    Memory Buffer Register 메모리에서 가져온 값 저장

ISA

Instrction Set Architecture Instruction과 Machine State(Register, Memory)를 관리하는 프로그램에서 최하위 레벨의 API, 명령어 집합 구조 ISA마다 OPCode(명령어)와 Operand(피연산자)가 다르다

CPU 처리 단계

Fetch -> Execution -> Interrupt 체크의 반복 Fetch : 메모리로부터 IR 레지스터로 명령어를 가져다 놓는 것

Instruction 종류

  1. Data Processing

    데이터를 처리하는 것

  2. Control

    if 문 등 분기 처리 하는 것

  3. Processor-Memory

    메모리에 접근하는 것

  4. Processor-I/O

    I/O에 접근하는 것

Interrupt란

IO 입출력이나 각종 예외 상황을 처리하기 위해 프로세서에게 알리는 신호 CPU와는 별도로 비동기적으로 발생

Interrupt 목적

CPU Utilization을 위해 I/O 처리가 Processor보다 속도가 현저하게 느리기 때문에 CPU를 효율적으로 쓰기 위해서 I/O 처리 등을 시키면 그게 끝날 때까지 기다리지 않고 다른 작업을 수행하다가, 신호가 오면 처리한다 항상 Kernel 모드에서 실행된다

Interrupt 처리 과정

  1. I/O Devidce가 Interrupt 발생

  2. CPU가 Instruction 처리 후 Interrupt 왔는지 체크

  3. 있다면, 있는걸 확인했다고 ACK을 보냄

  4. 기존의 PC와 PSW 상태를 저장 (Memory의 Stack에 보냄)

  5. PC를 Interrupt를 처리하기 위한 Interrupt Handler 주소로 설정, PSW를 커널 모드로 설정

  6. 레지스터 내부 값들을 저장 (Memory의 Stack에 보냄)

  7. Interrupt를 잠시 받지 않음(Disable 처리)

  8. Interrupt Handler로 들어가서 ISR 실행 (Interrupt Service Routine : 인터럽트에 특화된 Operation, Interrupt Handler의 부분집합)

  9. ISR에는 어떤 Interrupt가 왔을 때 어떤 함수를 실행할지 명세하는 Table인 IDT가 존재

  10. 처리 끝나면 다시 원래 상태로 복원

PIC

Programmable Interrupt Controller Interrupt가 왔는지(INTR 핀), 어디에서 왔는지 알려주고(IRQ# 핀), CPU와 통신(ACK 핀, Interrupt 확인 등) Interrupt의 우선순위 조정 및 Masking 처리

Blocking/Non-Blocking, Sync/Async

  • 차이

    Blocking/Non-BlockingSync/Async
    A 함수가 B 함수를 실행시켰을 때
    주도권이 어디 있는가    		A 함수가 B 함수를 실행시켰을 때
    B 함수의 결과에 종속되어 처리되는가

  • Blocking/Non-Blocking

    BlockingNon-Blocking
    A함수가 B함수를 실행시키면
    실행 흐름이 B함수로 넘어감    		A 함수가 B 함수를 실행시켰을 때
    B 함수와 별도로 여전히 실행 흐름이 A에게 있음

  • Sync/Async

    SyncAsync
    A함수가 B함수의 결과에 종속적임A 함수가 B 함수의 결과에 비종속적(상관없음)

  • 경우의 수

    경우의 수SyncAsync
    BlockingA함수가 B함수로 넘어가고, return되면
    그제서야 A함수로 실행 흐름이 다시 돌아오고
    A함수에서 바로 return 값을 받아서 처리    		B 결과에 비 종속적이지만
    Blocking이므로 B함수 실행 시 B함수로 제어권이 넘어가, A는 Block됐다가 B가 다 처리되고 return되면
    그제서야 다시 진행
    Non-BlockingA 함수가 B 함수 실행과 상관없이 계속 주도권을 가지고 있지만
    B의 결과에 종속적이기 때문에
    B의 return 유무를 계속 체크하면서 확인하다가 끝나면 그 값 바로 받아서 진행    		B함수가 실행된 것과 상관없이 주도권을 가지고 있으면서 B의 결과에 비종속적이므로
    B가 return 했는지 확인하지 않고 그냥 다른 거 계속 하다가
    언젠가 return 된 것 확인해서 처리

Interrupt와 Exception 차이

구분InterruptException
발생 위치외부내부
(시스템 콜 포함)
동기AsyncSync
실행 중이었던 Instruction 처리항상 Interrupt 처리를 완료하고 나서실행 중 완료되지 않은 채로 처리될 수 있음

IO Controller

IO Controller는 IO Devices에게 IO관련 Operation을 control할 수 있는 시스템 SW를 허용하여 Communication함

IO Controller는 적어도 3개의 Address(Port) 가 버스에 존재하는데, 각각이 Controller의 register에 대응되며 이를 IO Port Register라고 함

IO Port Register

 역할
Status디바이스의 현재 상태를 확인
Control
Command		디바이스에게 작업 명령
Data디바이스와 데이터 송수신

I/O Address Space 구현 방식

참고 링크

  • Port mapped IO

    IO Controller가 시스템 버스에 연결되고, 이때 내부의 Port들이 메모리처럼 별도의 주소로 매핑되고, I/O Instruction Trigger로 접근

  • Memory mapped IO

    기존의 Memory Address 내에 IO Address 공간을 할당해서 사용하는 것 => 메모리 내에 위치하므로 메모리의 load, store Instruction으로도 IO에 접근할 수 있다 (I/O를 위한 Address로 Physical Memory에는 접근 불가)

I/O 통신 방법 ( Processor가 I/O 처리를 보낸 후 Interrupt가 오기 전까지 )

  • Programmed I/O(Polling I/O)

    CPU가 I/O Controller에게 명령을 내린 뒤 계속해서 Status를 확인하며 끝날 때까지 기다리는 방식 (Busy-Wait, Non-Block - Async)

  • Interrupt Driven I/O

    I/O Controller에게 명령을 내리고, Interrupt가 올 때까지 다른 일을 처리하는 방식 (Non-Block - Async)

  • DMA(Direct Message Access)

    대용량의 I/O를 word 단위로 왔다 갔다 하면서 Interrupt를 보내긴 비효율적임

    기존까지는 word 연산 단위였다면, Block 단위 대용량 I/O를 처리할 필요 있음

    => DMA에게 I/O 커맨드 블럭을 보내면, DMA가 직접 메모리로 접근해 I/O 처리를 한 뒤 CPU에게 Interrupt 보냄

    I/O Controller와 분리된 방식, 통합된 방식 다 구현 가능

APIC

Advanced Programmable Interrupt Controller 어떤 프로세스에게 어떤 Interrupt를 줄 것인지도 결정하는 Controller

SMP

Symmetric Multi-Processor 대칭 멀티 프로세서

한 시스템에 여러개의 프로세서가 있을 때, APIC을 이용해서, 공유 Device에서 발생하는 Interrupt를 프로세서별로 처리할 수 있다, 또한, 각 프로세서 별로 가지고 있는 Local Device에 대한 Interrupt 관련 처리를 위한 Local APIC이 존재한다

Mutiple Interrupts 처리 방법

  • Sequential Interrupt Processing

    인터럽트가 처리되는 동안 다른 인터럽트들은 disable 했다가 끝나면 re enable해서 pending되었던 다른 인터럽트들을 처리

    • 장점

      구현이 단순함

    • 단점

      우선순위를 고려하지 않음

  • Nested Interrupt Processing

    인터럽트 간 우선순위를 설정하고, 인터럽트를 처리하고 있었더라도 더 높은 우선순위의 인터럽트가 발생하면 그것 먼저 처리한 뒤 이어서 진행

    • 장점

      우선순위를 고려하여 처리할 수 있음

    • 단점

      구현이 복잡함

Interrupt 장단점

  • 장점

    I/O를 처리하려고 기다리지 않아도 되서 CPU를 효율적으로 활용 가능

  • 단점

    Interrupt를 처리하기 위해 register를 Memory에 저장했다가 복구하는 작업 필요

Memory 계층

Memory 계층이 높을 수록 빠르지만 비쌈

Memory 속도

Cache > Main Memory > Disk Memory 순으로 빠름

Memory Locality

  • Temporal Locality (시간적)

    한번 접근한 것은 다시 접근하게 될 확률이 높음

  • Spatial Locality (공간적)

    한번 접근한 것의 주위 공간에 접근하게 될 확률이 높음

Memory 계층 목표

가장 낮은 수준의 메모리의 크기와 비용으로, 가장 높은 수준의 메모리의 속도를 가지는 것처럼 작동하는 가상 메모리를 제공하는 것

이를 달성하기 위해 Memory Locality를 잘 활용해야 함

Cache

SRam의 속도와 DRam의 크기와 비용을 가지는 가상 메모리를 제공하는 것

  • Mapping Function

    • Direct Mapping Mapping

      % 연산 등을 통해서 불러올 Memory 블럭마다 캐시의 어느 곳으로 갈 지 결정해서 할당하는 방식

      • 장점

        구현이 쉬움

      • 단점

        블럭이 들어가는 곳이 정해져 있기 때문에 우연히 같은 위치로 들어가는 Memory Load 연산이 반복된다면 Temporal Locality를 따르지 않을 수 있음 (Hit rate이 떨어지는 이슈)

    • N-Way Set Associative Mapping

      한 세트당 저장하는 블록 수를 N개로 조정 이때 각 세트의 블럭 별로 사용하고 있는 값인지를 확인하는 Valid와 메모리의 나머지 부분을 저장하는 Tag 비트가 있음

      예를 들어 뒷자리 두비트로 하나의 Set를 만든다면 경우의 수는 00, 01, 10, 11 이렇게 네 경우가 있고, 앞으로 불러올 메모리의 하위 2bit를 보고서 저 4개 중 일치하는 곳의 Set 내의 블럭에 Load 함

      만약 블럭이 Valid한 곳이라면 Valid 하지 않은 블럭을 찾고 다 Valid하면 한 개를 비우고 넣음

      • 장점

        하나의 Set당 들어갈 수 있는 블록이 n개가 되므로 Hit rate이 늘어남

      • 단점

        탐색할 때 n개의 블럭을 다 찾아봐야 하므로 탐색 오버헤드가 발생함

    • Fully Associative Mapping

      N-Way Associative Mapping의 경우에서 한 세트에 모든 블럭을 넣는 것

  • Cache 읽는 과정

    1. CPU로부터 읽을 메모리 주소 가져옴
    2. 메모리 블럭이 Cache에 담겨져 있는지 확인
    3. 있으면 바로 CPU에게 전달
    4. 없으면 메모리에서 블럭과 값을 값을 가져와서 Cache에 넣고, CPU에게 전달

  • Cache 쓰는 방법

    • Write Through

      항상 데이터와 메모리 양쪽에 data를 write 함

      • 장점

        단순함

      • 단점

        느리고 메모리 트래픽 증가

    • Write Back

      Dirty Bit로 수정됐는지를 확인하고, 데이터를 캐시에만 Write 했다가 교체되어질 때, Write함

      • 장점

        빠름

      • 단점

        일관성을 검증하기가 까다로움

OS의 목적

  1. 편리성 2. 효율성 3. 발전성

OS의 역할

  1. 중재자 프로그래머에게 시스템을 사용하기 위한 편리한 Interface를 제공
  2. 자원 관리자

OS 발전

  1. Serial Processing

    OS 존재 X

    사람이 직접 Job 적재

    => Job to Job Transition : 스케쥴링 어떻게 할 것인지 문제 존재

    문제점

    1. 고가의 자원을 비효율적으로 사용
    2. 셋업시간(컴파일러 세팅 등)의 장기화
    3. 스케쥴링 문제

  2. Simple batch System

    비슷한 일들끼리 묶어서 셋업 시간을 단축

    Monitor

    최초의 OS, 항상 Memory에 load되어 상주해 있음

    JCL

    Job Control Language

    일들을 관리하기 위한 언어

    JCL을 통해 Job to Job Transition 자동화

    요구사항

    1. Memory Protection OS인 Monitor가 점유하고 있는 공간을 침범하는 것을 막아야 함
    2. System Timer 한 개의 작업이 독점하지 못하도록 System Timer가 필요함

    3. 특권 Instructions 오직 Monitor를 통해서만 실행될 수 있는 명령어들이 있어야 함

      I/O Instruction들은 특권 Instruction임

    4. I/O Device Controller
    5. Interrupt 처리
      • Synchronous I/O : 프로그램이 I/O의 결과에 종속되어 기다림

      • Asynchronous I/O : 프로그램이 I/O에 종속되지 않음

        => Asynchronous I/O는 Interrupt를 이용해 병렬적으로 처리 가능하나 Synchronous I/O는 기다려야 함

        문제점

    6. Card 읽는게 느림
    7. CPU가 자주 놀았음 (Synchronous한 I/O 때문)

  3. Multiprogrammed Batch System

    이전까지는 Uni-Programming이었음

    => 메모리에 하나의 Program만 적재

    이제 메모리에 여러개의 Program을 올려서 Idle한 시간을 줄여 CPU 활용을 높이는 것이 목표

    Multi Processing으로 CPU관점에서 여러개의 작업이 병행적으로 처리됨

    요구사항

    1. Relocation 여러 프로그램이 올라옴에 따라 Boundary가 없어짐

      => 프로그램이 어디서 실행될 지 알 수가 없음

      => Disk에 Swap Area 확보해두고, 다른 프로그램을 메모리에 올릴 때 안쓰는 걸 Swap Area로 넣음

    2. Memory Protection 프로그램들 간 메모리 영역 침범이 생기지 않도록 해야 함

    3. MMU Memory Management Unit

      Logical 주소를 Main Memory의 Physical 주소로 Instruction 실행 시에 변환하는 것이 필요함 이를 처리하는 Unit

  4. Time Sharing

    인적 자원을 보다 효율적으로 사용하고자 하며, 다수의 상호작용하는 Job들을 다룰 수 있어야 함

    Processor 사용 시간을 여러 User들끼리 나눔

    같은 Machine을 여러 User들끼리 나누므로 Switching이 빈번하게 일어날 것이며, Job별로 Time Slice가 할당되어야 함

    문제점

    시스템 시간을 계속 체크하면서, Time Slice를 다 썼는지 확인해야 함

    구분Batch Multi ProgrammingTime Sharing
    목적Processor 사용률 극대화Response Time 최소화
    OS 접근JCLTerminal의 Command

OS 진화하면서 생긴 변화

  1. Process CPU를 나눠쓰기 시작함
  2. Memory Management MMU 등을 이용하면서 메모리 침범을 하지 않는 등
  3. Information Protection and Security 특권 모드 등
  4. Schedulig and Resource Management
  5. System Structure

OS 범주

  • Kernel

    Memory에 항상 상주하고 있는 OS의 일부분 함수들의 집합으로 구성됨

    함수들은 근본적인 메커니즘을 제공

    (ex : Process 관리, 동기화, CPU 스케쥴링, 메모리 관리 등)

    이러한 제공되는 Service들을 System Call이라고 함

  • Utility

    디스크에 있는 OS의 일부분 커널을 제외한 부분 필요에 따라 disk에서 load됨

    • System Utility

      System이 만듦

      컴퓨터 프로그램에 필요한 핵심적인 것

    • User Utility

      사용자가 만든 것

  • Shell

    System Utility 중 Special한 Utility

    사용자의 명령어를 실행하는 것

    사용자와 커널을 이어줌

Mode

Modeop-codeMemoryCPU Register
KernelExecute any op-codeAccess any placeAcess Any Register
UserNo Privileged op-codeOnly my memory areaNo Speacial Register

Dual Mode 필요성

User가 I/O 등에 Direct로 접근하지 못하게 막기 위해서

Mode Switch 발생하는 상황

  1. Interrupt
  2. Exception
  3. System Call

CPU Protection

  • 목적

    CPU를 독점하는 것을 방지하기 위함 => User Program을 실행하는데 아무 Interrupt나 System Call이 없다면 소유권이 OS에게 돌아가지 않고 계속해서 UserProgram만 실행되는 등의 문제가 생길 것 => System Timer가 필요함

  • System Timer

    특정 시간마다 Interrupt를 발생시키는 것 일단 Interrupt가 발생하면 Control이 OS로 넘어감 오직 OS만 load 할 수 있음

  • Absolute Time & Relative Time

  • Absolute Time

    정확한 날짜

  • Relative Time

    오늘부터 이틀 뒤 같은 상대적인 날짜 OS에선 Relative Time이 중요하게 사용됨

Memory Protection

  • Memory Management Unit

    논리적 Memory 주소를 물리적 Memory 주소로 변환 동시에 Memory Protection, Cache Control 등 관리 => HW로 구축됨

I/O Protection

  • Privileged I/O Instructions

    모든 I/O Instructions는 Privileged Instructions User는 I/O에 Direct Access 불가 반드시 OS procedure를 호출해서 접근 가능 System Call을 통해 User-mode의 Program이 Kernel-mode의 Service를 호출

  • System Call

    Process가 Kernel Service를 요청하는 수단 Application이 OS와 Communication 하기 위한 방법

    • 호출 목적

      • System Resource 보호
      • 신뢰성 무한 루프 돌 때 중단 함수 호출 등
      • 보안 권한 없이 OS나 다른 Resource 접근

    • System Call 대신 API를 사용하는 이유

      • OS에게 약간의 유연성 제공
      • System Call보다 API가 사용하기 쉬움
      • OS마다 System Call이 다르기 때문에 일관적인 기능을 제공하는 API 사용

    • System Call 호출 과정

      1. Library에서 System Call 함수 호출
      2. EAX 레지스터에서 System Call 번호 가져감
      3. PC에 System Call 주소 넘김
      4. Kernel 들어가서 넘겨받은 정보를 바탕으로 System Call Table 호출

    • System Call Parameter 전달 방법

      1. 레지스터

        레지스터 안에 파라미터를 넘김

      2. Memory 블럭

        메모리 블럭 안에 파라미터를 저장하고 block의 시작 주소를 넘김

      3. 스택

        파라미터를 Stack에 push하고 OS에 의해 Stack에서 Pop함 Block과 Stack 방식은 파라미터의 길이, 갯수 제한이 없음

Process

  • 정의

    • 실행 가능한 Program이 Memory에 올라와서 실행시킬 수 있는 것

    • 실행 시퀀스이자 Active Entity

    • 현재 상태(Program + stack)와 자원을 얼마나 사용하고 있는지, 명령을 실행하고 관리하는 Activity의 단위

  • 기본 구성 요소

    • Program Code
    • 코드와 연관된 Data 집합

  • 특성

    • 실행 단위 ( Thread, Light Weight Process )
    • 자원 소유권 단위 ( Process, Task )

Program

Disk에 Text와 Data가 저장되어 있는 이진 시퀀스이자 Passive Entity Program이 실행될 때 비로소 Process 하나의 Program은 여러 개의 Process가 될 수 있음 (여러 User들이 같은 Program을 실행할 때)

Stack

프로그램을 실행시키면 Return Address를 Stack에 Push하고 종료되면 Pop 함 프로그램의 Excution Sequence를 관리하기 위함 Stack의 Top을 관리하기 위한 StakPointer가 존재 보호하기 위해 base와 limit 레지스터 존재 Stack은 높은 주소에서 낮은 주소로 자람 => base의 주소가 limit 보다 높음 Process를 실행시키기 위해선 반드시 Stack 필요

  • Stack Frame

    아래의 정보들을 모아서 Stack Frame이라고 함

    • Return Address
    • Parameter
    • Return Parameter

  • Call Stack

    Stack Frame들의 집합 그때 당시의 Stack Frame을 보여줌

Program Description

  • User Level Context (memory context)

    프로그램을 수행하기 위한 기본적인 구성요소

    • 구성요소

      • User text
      • User data
      • User Stack

  • System Level Context

    • 구성요소

      Process Control Block

    • Process Control Block

      OS가 Process를 관리하기 위한 정보들의 집합

      • 구성요소

        • Process Identification

          식별자 정보 PID, UID 등

        • Process Control Information Process 간 Relation 정보(부모, 자식, 형제), 등
        • ProcessorState Information Process가 현재 어떤 상태인지, Priority 등

  • Hardware Context (register)

    PC, PSW 등 레지스터의 Content

Process Control Block

OS에서 가장 중요한 Data Sturcture OS가 Process 관리하기 위해 필요한 모든 정보를 저장 관리하는 Structure Multiprocessing을 가능하게 하며 각각의 Process가 각각의 PCB를 가짐

  • 구성요소

    • Process Identification

      식별자 정보 PID, UID 등

    • Process Control Information

      Process 간 Relation 정보

      • Process간 관계 (부모 자식)
      • Process 상태 (Run, Ready, Block)
      • 메모리 정보 (Segment, Page)
    • Processor State Information

      Processor의 레지스터 정보 Register와 Priority 등 정보

      • User level Register
      • Control and State Register

Process Image

Process Image란 OS가 어떤 Process를 관리하고 제어하기 위해 알아야 할 정보들의 집합 OS가 관리하는 각 Process별 Description Process가 어디에 위치해 있는지, Process를 관리하기 위한 속성들에 대한 정보 User Level Context + PCB Process의 식별 정보, 상태 정보 뿐만 아니라 해당 Process의

  • 구성 요소

    • User Text
    • User Data
    • Stack
    • PCB
    • Kernel Stack

Process State Model

Process의 상태가 변화되는 과정을 모델화 한 것

  • Two State Process Model

    • 상태 종류

      • Not Running

        Queue에서 대기 중인 상태

      • Running

        Dispatcher에 의해 선택되어 CPU에서 Running 중인 상태

    • 과정

    1. Process가 Queue에 적재됨

    2. Queue에 들어있는 Process 중 하나를 Dispatcher가 Scheduiling 기법에 따라서 골라서 Processor에서 수행 => Running 상태

    3. 만약 끝나면 그대로 Exit

    4. Time Slicing을 다 사용하면 Pause 되어 다시 Queue로 돌아감 => Not Running 상태

    • 문제점

      사용자로부터 Input 입력 등 IO Request가 필요할 때 Event가 올 때까지 대기해야 하기 때문에 IO 입력 대기 중인 Process를 다시 Running 상태로 올리는 비효율적인 문제 존재

  • Five State Process Model

    Not Running 상태를 Ready와 Blocked로 세부화함

    • 상태 종류

      • New

        프로세스 생성

      • Ready
      • Running
      • Blocked

        프로세스가 I/O관련 작업을 처리할 때 전환되는 상태 I/O 작업이 끝나면 다시 Ready 상태로 돌아가 선택되길 기다림 Time out은 여기로 안옴

      • Exit

  • Seven State Process Model

    메모리의 공간이 부족해지면 Process를 잠시 Disk로 옮겨야 함 => Suspend

    => 우선순위에 따라 Blocked 상태의 Process를 옮길 수도, Ready 상태의 Process를 옮길 수도 있음, 심지어 Running 상태에 있던 것도 Suspend될 수 있음

    => Five State Process Model에서 Ready Suspended, Block Suspended 상태가 추가됨

    • 상태 종류

      • New
      • Ready
      • Running
      • Blocked

        Running 중 I/O 작업 발생했을 때 전환되는 상태 Event가 발생하면 다시 Ready 상태로 전환됨

      • Blocked Suspend

        Block 상태에서 Suspend 된 상태 다시 공간이 생겨 Activate 될 때 Blocked 상태로 전환 만약 Suspend된 상태에서 Event가 발생하면 Ready Suspend 상태로 전환

      • Ready Suspend

        New or Ready or Running 상태에서 공간 부족으로 Suspend된 상태 다시 공간이 생겨 Activate 될 때 Ready 상태로 전환

      • Exit

Swapping

프로세스를 Main memory에서 Disk로 옮기는 것 OS에서 낮은 우선순위의 Process를 우선적으로 Swapping해서 Suspended queue에 적재

Process List Structures

PCB에서는 각 Process의 정보를 가지고 있고, 이 Process들의 상태 별로 PCB들을 리스트처럼 관리하는 구조

Mode Switch

User Mode에서 Kernel Mode, Kernel Mode에서 User Mode로 Mode를 전환하는 것 Process는 바뀌는 것 X

Process Switch

Process가 다른 것으로 바뀌는 것

  • 과정
    1. Current Process의 Processor의 context(pc, sp, psw )를 저장
    2. Current Process의 PCB를 Update (Ready, Blocked 등)
    3. Current Process의 PCB를 적절한 Queue로 이동
    4. 다음으로 실행시킬 Process를 결정
    5. 결정한 Process의 PCB를 Update (Running 상태로)
    6. TLB를 Update
    7. Process의 Processor의 context를 복원

Process Switch가 Mode Switch가 훨씬 Cost가 높음

Kernel Model 종류 (OS 실행 모델)

  • Nonprocess Kernel

    전통적인 방식 Kernel이 분리된 Entity로서 실행됨 => User Process에서 Kernel로 들어가는 것이 Process Switch와 대등

  • Execution within User Processes (Common in OS)

    User Processes 내부에서 커널 작동

    Kernerl 내에서 실행되는 함수들의 Execution Sequence를 관리하기 위한 Kernel Stack이 필요 각 Process Image가 Kernel Stack도 포함함

    => Timer등 간단한 작업을 위해 Kernel로 들어가는 것은 Process 내 Kernel에서 처리하고 이는 Mode Switch에 해당

  • Process-Based Operating System (Modular OS)

    Kernel을 아주 핵심적인 Code로 구성하고, 나머지 Kernel 기능들을 User Process Level로 올려서 마치 사용자들이 Module처럼 유연한 설계가 가능한 OS Kernel 방식

    Non Critical한 OS Function을 Process Level로 분리

Kernel Stack

하나의 Process에는 일반 Stack과 Kernel에서 Kernel 함수를 수행하기 위한 Kernel Stack으로 2가지의 Stack이 존재

  • 장점

    • 자원을 보호할 수 있음 (user stack이 더렵혀졌을 때도 Kernel을 실행시킬 수 있음)

COW (Copy On Write)

프로세스 생성 시간 줄이기 위함 Fork를 해서 효율적으로 Process를 생성할 때, 최초에는 자식 부모가 같은 Shared Page를 가리킴 그러나 부모 혹은 자식이 Write을 하여 값이 바뀌는 상황이 생길 때, 그제서야 Page를 복사하여 별도의 구분되는 Page를 가짐

  • Zero Fill On Demand

  • Fork , VFork

    • VFork 는 새로운 프로세스를 만들 때 부모 프로세스가 일시적으로 중단이 되고 자식 프로세스랑 메모리를 공유 결정적인 차이점은 fork는 자식 만든다고 부모가 중단되지 않음 vfork는 부모 프로세스가 일시적으로 중단 됨, 자식이 exit or execute 되기 전까지는 부모가 block됨

Process Termination

  • 자발적 종료 (exit)

    exit()로 우리가 직접 프로세스를 종료하는 것 종료하면 프로세스 자원 deallocated 됨

  • 비자발적 종료 (kill, abort)

    OS나 부모 등 다른 Process에 의해 종료 Kill이나 Abort 명령어 통해 실행

Zombie

프로세스는 종료됐지만 커널이 PCB나 일부 자원들을 제거할 수 없는 어정쩡한 상태

Child 프로세스가 Exit 된 후 부모 프로세스에게 (wait 등) 상태가 전달될 때까지의 어정쩡한 상태

  • Reaping

    자식의 exit 값이 부모에게 전달되는 과정

    종료 상태가 부모에게 전달되어야 함 => 부모가 wait을 통해서 수신함으로써 마무리됨

  • Zombie 상태 기간

    • wait, waitPID로 거두어질 때까지
    • 부모 Process가 Terminate될 때까지

  • Wait, WaitPid

    Parent Process가 fork를 하고 wait을 하면 Child Process의 종료 상태 값이 wait의 인자로 즉각적으로 전달이 됨 인자가 오기를 기다리는 동안 parent는 Block 상태가 됨 => 이렇게 Child Process의 상태 값을 수신함으로써 Zombie Process가 나타나는 것을 막을 수 있음

Orphan

만약 Child Process보다 Parent Process가 먼저 종료되면 Child Process의 부모를 init 으로 옮긴다

  • Process Termination 과정

    1. cleanup handler 호출
    2. Zombie 상태로 설정 및 종료 상태를 Kernel에 저장
    3. 자원 해제
    4. 부모에게 시그널 보냄
    5. 자식 프로세스들을 init으로 옮김

Demon

Multi Tasking OS에서 사용자가 직접 제어하지 않고, Background에서 돌면서 여러 작업을 하는 Program 윈도우의 서비스 같은 개념

데몬은 어떤 운영체제든 시스템적으로 별개로 돌아가는 특성이 강하고, 윈도우의 서비스는 시스템의 어떤 status를 측정하는 등 system과의 연관성에 좀 더 초점이 맞춰져 있음

  • 특징

    • 시스템의 첫 프로세스인 init의 바로 하위에 위치

  • Fork off and Die

    Demon은 자식 프로세스를 Fork해서 자신을 복사한 후 자기 자신을 삭제하여, 해당 프로세스를 의도적으로 고아 프로세스로 만든 후 이를 init이 받아들이도록 하여 만들어짐

Init Process

리눅스 Kernel이 부팅 완료된 뒤 실행되는 첫 번째 프로세스 Kernel이 직접 실행하는 유일한 Process 부모 프로세스를 가지지 않는 유일한 프로세스

  • 역할

    • 시스템의 초기화와 관리
    • 데몬 프로세스나, 고아 프로세스의 부모

Process Scheduling Types

  • Long Term Scheduling (job scheduler)

    프로세스가 생성되서 시스템에 들어갈지 말지 결정

  • Mid Term Scheduling (swapper)

    디스크에 있는 어떤 Process를 다시 메모리에 적재 시킬 것인가 (Suspend Queue에서 ReadyQueue 이동 판단)

  • Short term Scheduling

    CPU 스케쥴러 ( Processor에 올릴 것인가 판단, 어떤 Process를 실행 시킬 것인가 )

    • IO Scheduling

      Pending된 IO 요청들을 관리

Schedule 함수 종류

  • Selection function

    Ready Process에 있는 것 중 어떤 것이 다음 번에 실행될 지 결정

    • 기준

      • w : 시스템에 상주해 있던 시간
      • e : 실행을 위해 쓴 시간
      • s : 예상되는 처리 시간

    • Decesion mode

      Selection 함수가 실행되는 시간적 순간을 지정

      • 종류
        • Non Preemptive

          종료되거나 블럭될 때까지 내버려둠

        • Preemptive

          새 프로세스가 도착하거나, 블럭된 Process의 Interrupt가 생기거나, 시간이 다 되는 등의 이슈가 생기면 Process Switch 발생

  • FIFO (FCFS)

    가장 오래 기다린 것 먼저 실행 First-Come-First-Served

    • Selection Function

      MAX[W] : 가장 오래 System에 상주해 있는 Process

    • Decesion Mode

      Non-Preemption

    • 장점

      • 간단한 Schedule 정책

    • 단점

      • 오래된 프로세스 위주
      • Convoy Effect 발생

    • Convoy Effect

      별로 안 걸리는 새 작업이 있지만 CPU 사용 시간이 긴 무거운 긴 작업을 처리하느라 응답이 느려짐

  • Shortest-Process-Next (SPN)

    예상 처리 시간이 가장 짧은 Process 먼저 선택

    • Selection Function

      MIN[S] : 최소로 예상되는 처리 시간의 Process

    • Decision Mode

      Non-Preemption

    • 장점

      • Turn Around Time 개선

    • 단점

      • 오래 걸리는 Process는 계속해서 선택받지 못할 수 있음 (Starvation)
      • 구현하기 어려움 (예상 처리 시간 계산 등)

    • Turn Around Time

      프로세스가 완료된 시각 - 프로세스가 도착한 시간

  • Round-Robin

    Time Slicing Running 중이던 Process가 Ready Queue로 들어가게 됐을 때, FCFS를 기반으로 동작

    Quantum Time을 기반으로 Process 별 Time Slice를 할당해서, 주기적으로 Process Switch가 일어나 Convoy Effect를 해결해보고자 함

    • Selection Function

      Constant

    • Decision Mode

      Preemption

    • 주의점

      Quantum Time을 어떻게 설정하는지가 중요함 너무 길게 설정하면 FIFO랑 다를 것이 없고 너무 짧게 설정하면 SPN과 유사하며, Context Switch가 많아져 Overhead가 많이 생김 => 작업을 처리하는데 걸리는 시간보다 조금 더 크게 Quantum Time을 두면 좋음

  • Shortest-Remaning-Time (SRT)

    SPN과 동일, Decision Mode만 Preemption 예상되는 처리 시간에서 현재까지 실행된 시간을 뺀 나머지 시간이 최소인 프로세스 => 금방 종료될 것이라 기대되는 프로세스

    • Selection Function

      MIN[S-E]

    • Decision Mode

      Preemption

    • 장점

      • SPN 보다 Turn Around 시간 짧음

    • 단점

      • OverHead가 높음

  • Highest-Response-Ratio-Next (HRRN)

    Response Ratio ( R ) 가 높은 Process를 선택하는 것

    • Response Ratio

      q는 기다린 시간 R = (q + s)/s

    • Selection Function

      MAX[(q+s)/s]

    • Decision Mode

      Non-Preemption

    • 장점

      오래 걸리는 Process도 대기 시간에 따라 선택 받을 수 있는 기회가 있음 (Starvation 방지)

    • 단점

      프로세스 총 실행 시간 추정 필요

Burst

  • CPU Burst

    CPU가 Operation을 실행하기 위한 시간

  • I/O Burst

    CPU가 I/O를 기다리는 시간

Bound

  • CPU Bound

    CPU Burst 시간이 길고 I/O Burst 시간이 짧은 Cycle

  • I/O Bound

    I/O Burst 시간이 길고 CPU Burst 시간이 짧은 Cycle

  • Bound 파악하는 법

    Time Quantum을 다 쓰면 CPU Bound 프로세서 아니면 I/O Bound 프로세서

Scheduling 기준

  • CPU Utilization

    시간 당 CPU를 얼마나 활용하는가

  • Throughput

    시간당 Process를 몇개나 처리하는가

  • Turnaround Time

    Process가 들어와서 작업을 완료되기까지의 시간

  • Response Time

    Process가 들어와서 처음으로 응답되기까지 걸린 시간

  • Deadline

    Process가 특정 시간 내에는 끝내주길 바라는 Deadline을 제출했을 때 이것을 얼마나 만족시키는가

  • Fairness

    작업 처리 요구량에 비례해서 CPU 시간 할당을 얼마나 잘하는가 요구량이 3:1이면 CPU 할당도 3:1로 => 모든 것을 만족하기 힘들기에 상황에 맞춰 최적화 해야 함

Virtual Round Robin

CPU Bound Process의 유리함을 막음 I/O 리퀘스트가 있는 Process의 경우 지정된 quantum을 다 못쓰고 I/O 리퀘스트를 수행하러 Blocked Queue로 가면, 처리가 끝난 뒤에 Ready Queue가 아니라 보조 Queue로 가서 Ready Queue보다 먼저 실행되며, 남은 Quantum Time 만큼을 보충해줌

Multi Level Feedback Queue (MLFQ)

다단계의 Queue 존재 우선 순위 존재 및 우선순위가 높을수록 더 자주 실행

처음에는 Quantum Time이 짧은 SPN queue RR, 뒤로 갈 수록 Quantum Time이 긴 Round Robin이나 FIFO 방식을 사용 처음 단계에서 끝나지 않았다면 CPU Bound Process일 확룔이 높으므로 Overhead를 최소화하기 위해 Quantum Time이 높은 Queue로 보내서 처리 여러개의 Ready Queue로 나눠서 분할하는데, 우선적으로 작업이 짧은 Interactive한 Process에게 주며 시간이 오래 걸리는 Process는 QuantumTime을 늘려서 OverHead를 낮추는 방식 Foreground(높은 우선순위)는 Quantum Time이 짧은 Round Robin 방식 Background(낮은 우선순위)는 FIFO 방식 or Quantum Time을 크게 작업이 돌아가고 나서 결과를 보고 Time Slice를 다 쓰면 우선 순위가 낮아짐

  • Queue가 여러개가 있음
  • Queue마다 Scheduling 알고리즘이 다름
  • 승진, 강등 시키는 Method가 있음

시간에 따라서 Bound가 달라질 수 있으니 정확하지 않을 수 있음 interactive한게 많아지면 starvation 발생할 수 있음 모든 작업이 처음부터 끝까지 CPU Bound, I/O Bound는 아니기 때문에 중간에 Process의 Bound가 변할 수 있기에 정확하지 않을 수 있음 => Priority Boost로 일정 시간이 지나면 그 당시에 있던 모든 Job을 다시 최상위 Queue로 전부 옮겨서 실행하거나 하는 등의 보완책 존재

Multiprocessor Scheduling

  • Uniprocessor scheduling

    언제 어떤 Job을 실행시킬지 결정

  • Multiprocessor scheduling

    언제 어떤 Job을 어디서 실행 시킬 지 결정

    • 고려해야 할 점

      • 여러 개의 Queue를 유지
      • 캐쉬 활용
      • 어느 Processor에 할당할 것인지
      • 헤테로지니어스한 Processor 관리
      • Processor들 간 밸런스 관리

    • HW Issue : Cache Affinity

      • Cache Affinity (캐쉬 친화성)

        이전에 실행 시켰던 프로세서에서 수행하게 하면 캐쉬 성능을 통해 좀 더 성능을 향상 시킬 수 있음

        가능하다면 같은 프로세서에서 실행하게 하는 것이 좋음 캐쉬 일관성이라는 것도 있음 캐쉬가 물리적으로 분리되어 있어서 어느 한 쪽에 있는 cache에 있는 값이 변경되면 다른 곳에 있는 cache도 수정되어야 함 -=> bus snooping

    • SW Issue : Concurrency

      • Concurrency

        병행성 Queue는 Memory에 적재되고 공유됨 이를 동시에 접근해서 처리할 때 문제 발생 (Race Condition) 한번에 하나의 실행만 될 수 있도록 보장해줘야 함 -> Mutual Exclusion (상호배제)

Single Queue Multi Processor Scheduling

다중 프로세서 단일 큐 프로세서들이 공유하는 하나의 Queue가 존재 Queue의 맨 앞에 있는 Job을 각자 가져가서 처리함

  • 장점

    단순함

  • 단점

    Cache Affinity 불만족 CPU가 늘어날수록 연산이 느려지게 됨 Cache Affinity를 만족하려면 할 수는 있으나 동시성을 해결하기 위해 Lock을 사용 => 확장성 저하

Multi Queue Multi Processor

멀티 프로세서 멀티 큐 각 CPU 마다 별도의 Queue 존재 Process는 하나의 Queue에만 들어가게 함 실행 끝나면 같은 Queue에서 대기

  • 장점

    • Cache Affinity 만족 ( 같은 Processor 에게 실행되므로 )
    • 확장성 향상
    • 각 Queue마다 별도의 Scheduling 기법 적용 가능

  • 단점

    • Load imbalance (부하 불균등) 프로세스 실행 시간 예측 어려워 한쪽은 비어서 놀고 있을 수 있음 => Migration : 불균등할 때 작업을 다른 프로세서로 옮김 => Cache Affinity와 Trade Off

    • Work Stealing

      바쁜 Queue에서 여유로운 Queue로 작업을 옮김 부하를 검사해서 한쪽이 비어있다면, busy한 Queue에서 작업을 가져오는 것 자주하면 Overhead, 너무 적으면 Load Imbalance 발생 => Threshold를 넘으면 migration 진행

O(1) 스케쥴러

여러개의 Queue가 있고 각 Queue마다 우선순위를 가짐 각 Queue가 Priority를 가지고 있고, 작업들은 각 Queue에 Linked List로 연결됨 그래서 우선 순위가 가장 높은 Task를 먼저 선택

두개의 Queue가 존재 Active run Queue, Expired run Queue Time Slice를 다 쓰면 Expired Queue로 이동함 다 안썼으면 유지 or 돌아옴 그렇게 다 Expired Queue로 가면 다시 Expired를 Active로 Active를 Expired로 바꿔서 반복 프로세스의 수와 상관없이 고정된 배열 크기 만큼 순회하면 되므로 O(1)의 시간을 가짐(탐색, 삽입, 삭제 모두) 코어마다 멀티Queue가 존재 (SMP)

  • 단점

    • 정확한 수행 시간 보장 어려움, 확장성 한계 (고정된 우선순위 존재)

Proportional Share Scheduling

프로세스의 weight value에 비례해서 CPU를 할당

  • 사용처

    • Fair Queueing(Network, packet scheduling)
    • Proportional share : Process Scheduling

  • 최적화 기준

    얼마나 공정하게 CPU 사용시간을 보장할 수 있을 지

  • 종류

    • Completely Fair Scheduler (CFS)

      가상 runtime이 가장 적은 일을 고름

    • Weighted Fair Queueing (WFQ)

    • Lottery and Stride Scheduling(정리 필요)

      각 프로세스의 우선순위에 따라서 일종의 티켓을 비율만큼 부여하고 Select시 랜덤하게 뽑아서 실행 랜덤하게 실행되기 때문에 프로세스 실행, Lottery는 Non deterministic Stride는 각 프로세스마다 우선순위에 따라서 stride라는 우선순위 값을 부여하고 shcduling이 실행될 때마다 passvalue에stride를 더해서 진행, 초기에는 전부다 passvalue가 0이었다가 우선순위에 따라서 부여된 우선순위를 기준으로 scheduling 진행 시 가장 낮은 passvalue를 가진 process를 실행 => 중간에 새로운 잡이 들어왔을 때 passvalue를 0으로 해버리면 중간에 들어온 job이 process를 독점하기 때문에 pass value에 stride를 더하면서 가장 낮은 것을 실행시키는 것 둘다 비율, 가중치에 초점을 뒀는데 stride는 수치에 초점을 둠. 그 중에서 어떻게 Fair하게 할 것이냐가 WFQ 정리 필요

MultiThreading

단일 Process 내에 다수의 실행 흐름을 가지도록 OS가 지원 하나의 Process에는 하나 이상의 Thread가 존재

Concurrency and Parallelism

  • Concurrency

    동시성 여러 개를 왔다갔다하면서 같이 처리함 -> 병행

  • Parallelism

    병렬성 동시, 같은 시간에 여러개를 처리함 -> 병렬

싱글 프로세서는 병행성이 있음(병렬 X)

Thread

ThreadSafe : 어떤 함수, 변수들이 여러 Thread에서 동시에 접근해도 Program이 돌아가는데 문제가 없는 것

실행 단위로써의 프로세스, Light Weight Process Thread는 자원을 공유함 => Communication 비용이 적음 => 그래서 LWP

  • 탄생 동기

    작업을 처리할 때 Lengthy한 Operation 때문에 나머지 Concurrent한 작업들이 Delay가 되는 것을 해결하기 위해 => fork()를 통해 Process를 만들어서 해결하기에는 Cost가 높음 => Thread를 만들어서 분할

  • 장점

    • 응답성

      Thread의 일부가 Block되는 Lengthy한 Operation이어도 Program이 진행되도록 함

    • 효율성

      PCB를 만들 필요 없어 fork()보다 효율적, PCB 대신 TCB 생성 => Process Switch보다 빠름

    • 자원 공유

      별도의 System Call 없이 전역 변수를 공유할 수 있음

    • 확장성

      하나의 Process를 여러개의 thread로 나누어서 여러 CPU에 할당해 병렬적으로 처리할 수 있게 함 Parallel하게 처리할 수 있게 함

  • MultiCore에서 효율성

    • 암달의 법칙

      코어 수가 N개이고, Concurrent하게 실행 불가능한 순차 실행 비율을 S라고 할 때,
**개선 비율 <= ( 1 / ( S + ( 1 - S ) / N )** **Thread가 너무 많아져도 Rescheduling 횟수가 늘어나기 때문에 효율이 떨어지게 됨** => Optimal한 Thread 수가 존재

  • MultiCore에서 MultiThreading 할 때 고려할 점

    • Parallel하게 처리가 가능한지 확인
    • 크기를 동등하게 나누기
    • 데이터 의존적인지 확인 (Task가 병렬적으로 가능해도 Data가 Parallel하지 않을 때 동시에 접근하면 문제 발생할 수 있음)

  • Multicore에서 Parallelism의 종류

    • Data parallelism

      데이터를 부분 부분 쪼개어서 같은 작업들을 수행하게 함 ex : 30명의 평균을 10명씩 나누어서 구함

    • Task parallelism

      같은 데이터를 가지고서 다른 작업을 수행함 ex : 30명을 가지고 하나는 평균, 하나는 분산을 구함

  • Multithreaded Process Model ( Thread 구조 )

    각각의 Thread마다 Execution Stack, Kernel Stack, TCB( 공유할 수 없는 정보들을 저장한 블럭 )가 필요

    • User Stack
    • Kernel Stack
    • TCB

  • MultiThreading 구현 방법

    • Kernel Level Threads ( KLT )

      Kernel에서 Thread를 관리함 (생성, 삭제, 스위칭 등) 안정적

      • 단점

        SystemCall로 동작되어 Mode Switch가 발생하기 때문에 ULT에 비해 느림 ( fork() 보단 빠름 )

    • User Level Threads ( ULT )

      하나의 Process만 만든 뒤 라이브러리로 TCB를 만들고서 마치 Thread인 것 처럼 Multi flexing을 지원 (Kernel 쪽에서는 한개로만 인지) System Call 필요 X, 매우 빠름

      • 단점

        하나의 Thread라도 Block되면 모든 Thread가 Block됨 => Thread의 장점을 못가져감 가급적 Non Blocking 함수를 사용해서 해결

    • Combined

      KLT + ULT Kernel에서도 Thread를 관리하고, User Level에서도 Thread를 관리 한쪽이 Block되면 다른 Kernel의 Thread를 사용하면 됨

© 2025. Na2te All rights reserved.