개요

해당 포스팅은 PintOS 1주차에 배운 PintOS에 관련된 핵심적인 내용, OS의 동작 원리를 핵심적으로 다룰 생각이다.(코드는 최대한 지양하고 CS에 관련된 내용)

OS란?

OS(Operrating System)은 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어를 말하며, 컴퓨터의 하드웨어를 동작시키기 위한 기본적인 역할들을 추상화 시킨다.

OS의 역할

1. User Interface(유저 인터페이스)
2. File Management(파일 관리)
3. Management of H/W and peripherals(하드웨어 및 주변장치 관리)
4. Processor Management(프로세서 관리)
5. Running of S/W(소프트웨어 실행)
6. Interrupt and error handing(인터럽트와 에러 관리)
7. Security(보안)
8. Memory Management(메모리 관리)
9. Network Communication(네트워크 소통)

qemu란?

Pintos를 가동시키는 가상 에뮬레이터를 말함

Common bugs

1. Memory leak

   불필요한 Memory가 해제되지 않고 점유하는 상황

   -> Allocation한 Memory는 사용한 후 접근이 없을 때 해제해줘야 함

2. DeadLock(교착상태)

   두 프로세스가 서로 점유하고 있는 자원을 서로 필요료 할때 두 프로세스 모두 사용하지 못하고 교착상태에 빠지는 것을 말함

3. Starvation

   Threads에게 우선순위를 부여해 공유자원에 접근할 때, 우선순위들이 낮은 Thread가 Running을 하지 못하는 상태

   -> 이러한 문제를 해결하기 위해 스케줄링 방법들이 존재 함
   

4. Use after free

   Heap에서 동적할당된 공간을 Free한 후 재사용할 때 일어날 수 있는 취약점

   
   
   
   

Context Switching

하나의 User Thread에서 다른 User Thread로 CPU의 제어권이 이양되는 과정
Kernel에 의해 일어나며, 이전 Thread의 Status를 보관하고
새 Thread의 Status를 적재하는 작업

Context Swiching은 System Call에 의해 Kernel Mode 상에서 기존에 Running중인 Process의 상태를 저장한 후 Block(or Ready)하고,
Ready중인 Process를 Running상태로 바꿔준다.

Alarm Clock

• tick

  Program에서 시간을 재는 단위
  PintOS상에서는 TIMER_FREQ의 값이 100으로 저장되어 있어 10ms = 1tick

• timer

  컴퓨터에 내장되어 있는 H/W
  tick을 세고, 그 단위마다 CPU에 Interrupt를 날린다.

Busy Waiting 방식

time_interrupt가 발생할 때마다 Ready List를 순회하여
Thread들이 사용해야할 타이밍인지를 체킹함

이러한 Busy Waiting 방식은 즉각적으로 Feedback이 필요한 마우스, 키보드 입력과 같은 작업에는 효율적이나, 정해진 tick에 실행되는 Thread의 경우 매 tick마다 확인해야하므로 효율성이 떨어진다.

-> PIntOS Project 1-1 : 이러한 Busy Waiting 방식을 Sleep/Awake방식으로 개선

Sleep/Awake

Sleep Statue에 있는 Thread들을 Ready List에 넣지않고 Sleep List라는 List에 저장시키는 방식(이때 Thread들의 Status는 BLOCK)

time_interrupt가 일어날 때마다 sleep_list에 존재하는 thread들 중 깨워야할 tick이 된 thread를 ready_list에 넣고 상태를 READY상태로 바꿔준다.

Scheduler(스케줄러)

시분할 System에서 OS는 CPU와 같은 컴퓨터 자원들을 적절히 Process에 배분함으로써 효울적으로 Process들을 동시에 실행할 수 있다.
Scheduler는 Process들의 상태, 순서들을 관리하는 Process를 말한다.

Process Scheduling Queues

OS는 모든 PCB를 Process Scheduling Queues에 저장한다.
각각의 Process의 Status에 따라 다른 종류의 Queue에 보관하는데 한 Process의 Status가 다른 Status로 변경되면 기존의 Queue에서 다른 Queue로 넘어간다.

• Job Queue : 현재 System에 존재하는 모든 Process들의 집합
• Ready Queue : 현재 Memory에서 CPU에서 Running되기를 기다리는 Process들의 집합
• Device Queue : Device I/O 작업을 Ready하고 있는 Process들의 집합

통상 Ready Queue에 올려진 Proces들 중 실행시킬 Process들을 선택하는 작업을 Scheduling(스케줄링)이라고 한다.

Scheduler의 종류

• 장기 스케줄러(Job Scheduler)

  많은 Procee들이 Memory에 올라와 일부가 Disk에 임시로 저장된 경우, Disk의 Process 중 어떤 Process를 Memory에 할당해 Ready Queue로 보낼지를 정하는 역할을 함

  -> Virtual Memory의 발달로 실행 준비가 된 Process들은 모두 Memory에 담아 Ready Queue에 넣을 수 있어 잘 사용하지 않음
  
  
  

• 단기 스케줄러(CPU Scheduler)

  CPU와 Memory 사이의 Scheduling을 담당함.
  Ready Queue에 존재하는 Process 중 어떤 Process를 할당할 지를 결정

• 중기 스케줄러(Swapper)

  Memory에 너무 많은 Program들이 동시에 올라가는 것을 조절하는 Scheduler
  여유 공간을 위해 Process를 통째로 Memory에서 Disk로 쫒아낸다.

비선점형 스케줄링(Non-Preemptive Scheduling)

이미 Allocated된 CPU를 다른 Process가 강제로 빼앗아 사용할 수 없는 Scheduling방식
어떤 Process가 CPU를 Allocated하면 그 Process가 종료되거나 I/O Interrupt가 발생하여 자발적으로 중지되지 않으면 계속 실행되도록 보장함

• FCFS(First Come First Served)
• SJF(Shortest Job First)
• HRRN(Highest Response Ratio Next)

선점형 스케줄링(Preemptive Scheduling)

어떤 Process가 CPU를 Allocated해 실행 중에 있어도 다른 Process가 실행 중인 Process를 중지하고 CPU를 강제로 점유가 가능한 방식

• Round Robin
• SRTF(Shortest Remaining-Time First)
• MQS(Multilevel Queue)
• MFQS(Multilevel Feedback Queue)

Round Robin(RR)

선점형 스케줄링의 하나, Process 사이에 우선순위를 두지 않고 순서대로 Time Slice(Pintos기준 4ms)로 CPU를 할당하는 방식

Process에게 균등하게 컴퓨터 자원을 부여할 수 있다.
(TIme Slice가 끝난 후 미완료된 Process들은 Ready리스트로 돌아간다.)

Priority

Ready Queue에 있는 Process들에게 Priority를 부여해 Priority가 높은 Process부터 Scheduling하는 방식

FCFS(Ready Queue에 먼저 들어간 순서부터 CPU에 할당되는 방식), SJF(CPU가 명령을 실행하는 시간이 짧은 Process가 먼저 할당하는 방식) 등이 있음

Stavation과 Priority Inversion의 문제가 발생할 수 있음

• Priority Inversion : High Priority Process가 낮은 Low Priority Process로 인해 Block이 되는 상태
  (Low Priority Process가 끝날 때까지 실행되지 못하는 상태)

Priority Donation

Priority Inversion상황이 발생했을 때, High Priority Process가 Low Priority Process에게 일시적으로 Priority를 양도하는 방법으로,
이를 통해 Low Priority Process가 실행된 후 Semaphore를 사용한 뒤 반납핧 수 있고, 그것을 High Priority Process가 받아 실행할 수 있다.

• Multiple Donation
  

• Nested Donation
  

MLQS(Multi-Level Queue Scheduler)

Process의 유형에 따라 여러 개의 Queue로 나누고 각각에 다양한 알고리즘을 적용하는 방식. 우선순위가 높은 Queue의 Process가 먼저 실행된다.
(Process가 다른 Queue로 이동될 수도 있다)

• 4BSD
• nice

Interrupt

Synchronization(동기화)

Multi Process System에서 Process(Thread)들이 같은 공유 자원을 사용할 때,
동시에 동일한 공유 자원이 접근하지 못하게 막는 것.

가장 쉬운 방법은 한 Thread가 CPU를 점유할 때 일시적으로 CPU에 들어오는 Interrupt를 막는 것이다.(= Interrupt Disable)

Interrupt Disable을 사용한는 경우

• Scheduling에 직접적으로 연관된 함수들
• LOCK이나 Semaphore를 사용하지 못할 때
• Kernel Thread와 외부 Interrupt Handler의 동기화를 진행해야 할 때

but, 왠만한 상황에서는 세마포어, LOCK, Condition Variables 등의 Synchronization Primitive를 사용하여 동기화를 하고, OS 자체의 response time을 증가시키므로 Interrupt Disable을 남발하는 것은 좋은 프로그램 디자인이 아니다.

Syncronization Primitives

OS 등의 플랫폼에서 동기화를 보조하기 위해 제공하는 매커니즘

Semaphore(깃발)

한 Process가 임계 영역에 해당하는 코드를 실행하고 있을 때 다른 Process가 임계영역으로 진입하지 못하게 하는 것

• Binary Semaphre : 0과 1의 값만 가지는 Semaphore
• Counting Semaphre : 여러 값을 가질 수 있는(Domain의 제한이 없는) Semaphore
  
  

접근

sema_down (깃발을 꽂는 행위) = wait() (value : 0)
sema_up (깃발을 뽑는 행위) = signal() (value : 1)

Lock(잠금)

lock일때는 value가 0. unlock일 때는 value가 1인 Binary Semaphore의 일종

접근

lock (잠금을 거는 행위) = wait() (value : 0)
unlock (잠금을 푸는 행위) = signal() (value : 1)

Conditional Variable(컨디션 변수)

동기화 도구 중의 하나로, Semaphore나 Lock 보다 더 높은 레벨의 동기화이다.

Conditional Variable는 일종의 Queue Struct로서, 어떤 실행의 Status가 원하는 것과 다를 때 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐이다.
(마치 세마포어의 값을 0으로 초기화한 뒤 sema_up을 기다리는 경우와 같다.)

접근

wait() : Thread 스스로를 잠재우기 위한 연산
signal() : Thread가 무언가를 변경해 Sleep Thread를 깨우기 위해 사용하는 연산

PintOS 1주차 회고

clone하자마자 압도적인 코드량에 "내가 이거 다 볼 수 있을려나"라는 두려움이 먼저 들었다.
주말이 되기 전에 "OS와 관련된 기본적인 개념에 대해 이해하고, 일요일부터 본격적으로 문제를 풀어보자"라는 것이 내 계획이었는데, OS관련 이론은 너무 방대하기도 하고 내가 직면하고 해결해야할 문제에 필요 없는 내용들을 공부하기도 하기에 비효율적이었다고 생각한다.

공부로 도망가지 마시고 이번 주에 해야 할 과제에 집중하시기를 권장 드립니다. -코치님-

5주라는 기간이 OS의 모든것을 이해하기는 사실 상 불가능하고 필수적인 기능만 PintOS라는 매게체를 통해 배워나가는 것이 과정의 핵심이라는 것을 다시 상기가 된 것 같다.

Alarm clock,Priority Scheduling의 경우 조원분들과 머리를 맞대고 개선을 해나가다보니 어찌어찌 통과는 했지만, 우리 조가 구현한 코드에 대해서 "왜 이렇게 돌아가야 pass가 될까?"라는 질문에 대한 답은 완전하게 해결하지 못한 상태인 것 같다.

알고리즘주차 이후로 신체적으로 아픈 주간이 있었고, 정신적으로는 많이 헤이해졌다는 느낌을 많이 받았고, 그로 인해 미룬 공부들이 직격타를 맞은 느낌이다.

내가 얼마나 노력하는가에 따라 output이 달라지는 교육이라는 것을 잊지말고 최선을 다하자.