운영체제 정리

 

---

운영체제 정리

본 글은 Youtube ‘HPC Lab. KOREATECH’의 "[Course] Operating System (CPA310)-운영체제 강의" 의 ppt 내용을 요약한 정리본 입니다.

강의 Instructor: Duksu Kim

(1) 운영체제 구분 — 작업 수행 방식

1. Personal Computing

개인이 시스템 전체 독점, CPU 활용률(utilization)이 고려의 대상이 아님, OS가 상대적으로 단순함. 하지만, 다양한 사용자 지원 기능 지원

장점: 빠른 응답시간

단점: 성능이 낮음

2. Parallel Processing System

• 단일 시스템 내에서 둘 이상의 프로세서 사용
• 메모리 등의 자원 공유(Tightly-coupled system)
• 사용 목적: 성능 향상, 신뢰성 향상(하나가 고장나도 정상 동작 가능)

3. Distributed Processing Systems

• 네트워크를 기반으로 구축된 병렬처리 시스템(Loosely-coupled system)
• 물리적인 분산, 통신망 이용한 상호 연결
• 각각 운영체제 탑재한 다수의 범용 시스템으로 구성
• 사용자는 분산운영체제를 통해 하나의 프로그램, 자원처럼 사용 가능(은폐성, transparency)
• 각 구성 요소들간의 독립성유지, 공동작업 가능
• Cluster system(ex. super computer), client-server system, P2P 등

장점: 자원 공유를 통한 높은 성능, 고 신뢰성, 높은 확정성

단점: 구축 및 관리가 어려움

4. Real-time Systems

• 작업 처리에 제한 시간(deadline)을 갖는 시스템
• 작업(task)의 종류:

Hard real-time task(ex. 발전소 제어, 무기 제어 등), Soft real-time task(ex. 동영상 재생), Non real-time task

(2) 운영체제의 구조

1. Kernel

• OS 의 핵심 부분(메모리 상주): 가장 빈번하게 사용되는 기능들 담당

2. Utility

• 비상주 프로그램
• UI등 서비스 프로그램

(( HW -Kernel-System calls-Utilities-applications ))

운영체제의 구조:

1. 단일구조: 커널 내 모듈간 직접 통신, 커널의 거대화
2. 계층 구조: 모듈화, 설계 및 구현의 단순화, 단일구조 대비 성능 저하

3. 마이크로 커널 구조: 커널의 크기 최소화(필수 기능만 포함), 기타 기능은 사용자 영역에서 수행

(3) 운영체제의 기능

• Process 관리:

커널에 등록된 실행 단위(실행 중인 프로그램)

사용자 요청/프로그램의 수행 주체(entity)

• Processor(CPU)관리
• Memory 관리
• File 관리
• 입출력(I/O)관리
• 보조 기억 장치 및 기타 주변장치 관리 등

---

(4) Process Management

1. Job VS Process

Job: 실행 할 프로그램 + 데이터, 컴퓨터 시스템에 실행 요청 전의 상태

Process: 실행을 위해 커널에 등록된 작업, 시스템 성능 향상을 위해 커널에 의해 관리 됨, 실행 중인 프로그램, 각종 자원들을 할당 받을 수 있음.

커널은 프로세스에게 Resource를 할당/반납.

2. Process Control Block(PCB)

OS가 프로세스 관리에 필요한 정보 저장, 각 프로세스들에 대한 상태정보 저장

프로세스 생성 시, 커널에 생성 됨

관리하는 정보: PID, 스케쥴링 정보, 프로세스 상태, 메모리 관리 정보(Page table, segment table), 입출력 상태 정보, 문맥저장 영역, 계정 정보

• PCB는 OS별로 서로 다름. PCB 참조 및 갱신 속도는 OS의 성능을 결정 짓는 중요한 요소 중 하나.

3. Process States

• Created State: Job을 커널에 등록, PCB 할당 및 프로세스 생성, 가용 메모리 공간 체크 및 프로세스 상태 전이
• Ready State: 프로세서 외에 다른 모든 자원을 할당 받은 상태, 즉시 실행 가능 상태, Processor(CPU) 기다리다가 할당받으면 → running state
• Running State: 프로세서와 필요한 자원을 모두 할당 받은 상태, Preemption( →ready state), Block/sleep( →asleep state, I/O 등 자원 할당 요청)
• Blocked/Asleep State: 프로세서 외에 다른 자원을 기다리는 상태, 자원 할당은 system call에 의해 이루어 짐. ( → ready state)
• Suspended State: 메모리를 할당 받지 못한(빼앗긴) 상태, 커널 또는 사용자에 의해 발생, swap-out, swap-in, memory image를 swap device에 보관.
• Terminated/Zombie State: 프로세스 수행이 끝난 상태, 모든 자원 반납 후, 커널 내에 일부 PCB 정보만 남아 있는 상태

4. 프로세스 관리르 위한 자료구조

Ready Queue, I/O Queue, Device Queue

(5) Interrupt

예상치 못한, 외부에서 발생한 이벤트

프로세스 중단 (커널 개입) --> 인터럽트 처리 --> 1. Interrupt handling 2, Interrupt Service

인터럽트를 처리하는 프로세스를 커널에 넣어줘

6. Context Switching

커널의 개입으로 이루어져, PCB

Context: 프로세스와 관련된 정보들의 집합

불필요한 Context switching을 줄이는 것: thread 사용

(6) Thread Management

1. Thread --> 자원은 공유하지만, 각각의 자신만의 제어요소를 갖고 있음 --> 작업을 효율적으로, cpu 처리 병렬가능

프로세스는 자원을 할당받고 자원을 제어함.

Resource 제어 = Thread, 제어는 여러개 있을 수 있음.

같은 프로세스의 Thread들은 동일한 주소 공간 공유

Light Weight Process(LWP)

프로세서(CPU) 활용의 기본 단위

Thread가 여러개면 동시에 여러개의 CPU를 사용할 수 있음

제어 요소 외 코드, 데이터 및 자원들은 프로세스 내 다른 스레드들과 공유

전통적 프로세스 = 단일 스레드 프로세스

2. Thread의 장점

• Responsiveness: 일부 스레드의 처리가 지연되어도, 다른 스레드는 작업을 계쏙 처리 가능
• Resource sharing
• Economy
• multi-processor 활용

3. 스레드의 구현

- User thread: 사용자 영역의 스레드 라이브러리로 구현됨

                        커널은 스레드의 존재를 모름

                       커널 수준 스레드는 하나인데, 사용자 수준 스레드는 여러개라서 다대일(n:1) 매핑

                       커널은 프로세스 단위로 자원을 할당하기에 하나의 스레드가 block 상태가 되면, 모든 스레드가 대기한다.

                       (single-threaded kernel의 경우)

- Kernel thread: OS(kernel)이 스레드 직접 관리, 일대일(1:1) 매핑

                         커널 영역에서 스레드의 생성, 관리 수행(Context switching 등 overhead가 큼)

                         커널이 각 스레드를 개별적으로 관리 --> 프로세스 내 스레드들이 병행 수행 가능

                         하나의 스레드가 block 상태가 되어도, 다른 스레드는 계속 작업 수행 가능

- Multi-threading model: 다대다(n:m) 모델

                                       n>m, 혼합형 스레드

                                       n개 사용자 수준 스레드, m개 커널 스레드

                                       사용자는 원하는 수만큼 스레드 사용

                                       커널 스레드는 자신에게 할당된 하나의 사용자 스레드가 block 상태가 되어도, 다른 스레드 수행 가능

                                       (병행 처리 가능)

                                       효율적이면서 유연함

                                       사용자는 사용자 수준 스레드 처럼 자유롭게 사용, 관리는 스레드 라이브러리가. 커널에서는 사용자 수준                                         스레드가 동적으로 자원을 쓸 수 있게 해줌

(7) 프로세스 스케줄링

- Multi-programming

- 여러개의 프로세스

- 자원 할당 --> Scheduling

- 자원 관리: time sharing 관리(e.g. process scheduling), space sharing 관리

- 목적: 시스템의 성능향상

- 대표적 시스템 성능 지표(index): response time, throughput, resource utilization

1) CPU burst VS I/O burst

- 프로세스 수행 = CPu 사용 + I/O 대기

- CPU burst: CPU 사용 시간 --> compute bounded process

- I/O burst: I/O 대기 시간 --> I/O bounded process

burst time은 스케줄링의 중요한 기준 중 하나

2) 스케줄링의 단계

발생하는 빈도 및 할당 자원에 따른 구분

• Long-term scheduling:
  • job scheduling(시스템에 제출 할(Kernel에 등록할) 작업(job)결정)
  • 다중프로그래밍 정도(degree) 조절: 시스템 내에 프로세스 수 조절
  • I/O-bounded와 compute-bounded 프로세스들을 잘 섞어서 선택해야 함
  • 시분할 시스템에서는 모든 작업을 시스템에 등록(Long-term scheduling이 불필요)
•  Mid-term scheduling:
  • memory allocation(swapping(swap-in/out))
•  Short-term scheduling:
  • 자주 일어남
  • Process scheduling(low-level scheduling): 프로세서를 할당할 프로세스를 결정
  • 매우 빨라야함

3) 스케줄링 정책(Policy)

 

1. 선점 vs 비선점: Preemptive scheduling, Non-preemptive scheduling

2. 우선순위: priority

 

• Non-preemptive scheduling: 할당 받을 자원을 스스로 반납할 때까지 사용
  • context switch overhead가 적음
  • 잦은 우선순위 역전, 평균 응답 시간 증가
• Preemptive scheduling: 타의에 의해 자원을 빼앗길 수 있음
  • 할당 시간 종료, 우선순위가 높은 프로세스 등장
  • context switch overhead가 큼 --> process가 자주 바껴
  • Time-sharing system, real-time system등에 적합 --> 응답성이 높아져
• Priority: 프로세스의 중요도
  • Static priority: 프로세스 생성시 결정된 priority 유지
  • 구현이 쉽고, overhead가 적응
  • 시스템 환경 변화에 대한 대응이 어려움
• Dynamic priority(동적 우선수위):
  • 프로세스의 상태 변화에 따라 priority 변경
  • 구현이 복잡, priority 재계산 overhead가 큼
  • 시스템 하노경 변화에 유연한 대응 가능

4) 기본 스케줄링 알고리즘

 

FCFS(First-Come-First-Service)

RR(Round-Robin)

SPN(Shortest-Process-Next)

SRTN(Shortest Remaining Time Next)

HRRN(High-Response-Ratio-Next)

MLQ(Multi-level Queue)

MFQ(Multi-level Feedback Queue)

 

5) Case study

1. FCFS

• Non-preemptive scheduling
• 먼저 도착한 프로세스를 먼저 처리
• 자원을 효율적으로 사용 가능 --> 오는대로 프로세서에 던져주면 되니까, scheduling overhead 적어
• Batch system에 적합, interactive system에 부적합
• 단점: Convoy effect(하나의 수행시간이 긴 프로세스에 의해 다른 프로세스들이 긴 대기시간을 갖게되는 현상(대기시간>>실행시간), 긴 평균 응답시간(response time)

2. RR(Round-Robin)

• preemptive scheduling
• 먼저 도착한 프로세스(ready queue 기준)를 먼저 처리
• 자원 사용 제한 시간(time quantum)이 있음 --> 성능 결정
• 프로세스는 할당된 시간이 지나면 자원 반납(Timer-runout)
• 특정 프로세스의 자원 독점(monopoly)방지
• Context switch overhead가 큼
• 대화형, 시분할 시스템에 적합

3. SPN

• Non-preemptive scheduling
• burst time 가장 작은 프로세스를 먼저 처리
• 장점: 평균 대기시간(WT) 최소화, 시스템 내 프로세스 수 최소화(스케줄링 부하 감소, 메모리 절약 --> 시스템 효율 향상), 많은 포르세스들에게 빠른 응답 시간 제공
• 단점: Starvation(무한대기)현상 발생, BT가 긴 프로세스는 자원을 할당 받지 못할 수 있음, 정확한 실행시간을 알 수 없음

적

4. SRTN

• SPN의 변형
• Preemptive scheduling(뺏길 수 있어)
• 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선전됨.
• 장점: SPN의 장점 극대화
• 단점: 프로세스 생성시, 총 실행 시간 예측(BT)이 필요함, 잔여 실행을 계속 추적해야함(=overhead), Context switching overhead --> 구현 및 사용이 비현실적

5. HRRN

• SPN의 변형(SPN + Aging concepts, Non-preemptive scheduling)
• Aging concepts: 프로세스의 대기 시작(WT)을 고려하여 기회를 제공
• Response ratio가 높은 프로세스를 우선으로 스케줄링
• Response ratio = (WT+BT)/BT(응답률) --> "필요한 시간(BT) 대비, 얼마나 기다렸는가?"
• SPN의 장점 + Starvation 방지
• 실행 시간 예측 기법 필요(Overhead)

FCFS, RR ==> Fairness(공평성)

SPN, SRTN, HRRN ==> Efficiency/Performance(효율성, 성능), 문제점: 실행시간 예측 부하

-->

MLQ(multi-level queue)

MFO(multi-level feedback Queue)

 

7. MLQ

• 작업(or 우선순위)별 별도의 ready queue를 여러개 가짐
• 최초 배정된 Queue를 벗어나지 못함
• 각각의  queue는 자신만의 스케줄링 기법 사용
• queue 사이에는 우선순위 기반의 스케줄링 사용
• 장점: 중요한 애들은 빠른 응답시간
• 단점: 여러개의 Queue 관리 등 스케줄링 overhead, 우선순위가 낮은 queue는 starvation 현상 발생 가능

8. MFO

• 프로세스의 Queue간 이동이 허용된 MLQ
• feedback을 통해 우선 순위 조정 --> 현재까지의 프로세서 사용 정보(패턴) 활용
• 특성: Dynamic priority, preemptive scheduling, Favor short burst-time processes, Favoer I/O bounded processes, Imporve adaptability
• 프로세스에 대한 사전 정보(BT) 없이 SPN,SRTN,HRRN 기법의 효과를 볼 수 있음
• 단점: 설계 및 구현이 복잡, 스케줄링 overhead가 큼, Starvation 문제