README.md

OS

• Process vs Thread
  • Process + PCB
    • IPC
  • Thread
  • Multi-Thread vs Multi-Process
• 스케쥴러
• CPU 스케쥴러
  • FCFS
  • SJF
  • SRTF
  • Priority Scheduling
  • Round Robin(RR)
    • 시분할 처리 시스템
• Synchronization
  • 뮤텍스
  • 세마포어
  • 스핀락
  • 모니터
  • 어토믹
• DeadLock
• 메모리 관리 기법
  • 페이징
  • 세그멘테이션
• 가상 메모리
  • 가상 주소 공간
  • Demand paging
  • Page Fault
  • Page Replacement 알고리즘
    • FIFO
    • OPT
    • LRU
    • LFU/MFU

Process VS Thread

프로세스 + PCB

• 프로그램을 구동하여 프로그램이 메모리 상에서 실행되는 작업 단위
• OS로부터 주소 공간, 파일, 메모리 등을 할당받음
• Process 당 최소 1개의 Thread를 가짐
• 다른 Process 자원에 접근하려면 **IPC(프로세스 간 통신)**을 사용해야 한다.

IPC

• 프로세스들 사이에 서로 데이터를 주고받는 행위 또는 그에 대한 방법이나 경로

1. 공유 메모리: 다수의 프로세스에 의해 공유되는 메모리 영역

• OS의 관여가 없어 속도가 빠름
• 보안 및 동기화 문제

2. 메세지 전달: 프로세스 사이 데이터 송수신 또는 동기화 작업

• 분산 시스템 환경에서 주로 사용
• 데이터 교환 개수가 적을 때 유용

프로세스 구조

• Code: 실행 프로그램의 코드 영역 및 Program Counter(다음번 실행될 명령어의 주소를 가지고 있는 레지스터) 저장
• Data: 프로그램 전역변수 & 정적변수 저장
• Heap: 동적으로 메모리 공간을 할당했을 시 저장되는 부분
  • 낮은 주소 -> 높은 주소(FIFO)
• Stack: 매개변수, 복귀 주소 및 로컬 변수 같은 임시 자료를 저장하는 부분
  • 높은 주소 -> 낮은 주소(LIFO)

PCB(Process Control Block)

• 특정 프로세스에 대한 중요 정보를 저장하고 있는 운영 체제의 자료 구조

• 프로세스 생성과 동시에 고유한 PCB 생성

• 프로세스 전환 발생 시 작업 내용을 PCB에 저장, 이후 다시 CPU 할당 시 PCB에 저장된 내용을 불러와 다시 작업 수행

• PCB 저장 내용

  1. 프로그램 식별자(PID): 프로세스 식별번호
  2. 프로세스 상태: new, ready, running, waiting, terminated 등의 상태 저장
  3. 프로그램 카운터: 프로세스가 다음에 실행할 명령어 주소
  4. CPU 레지스터
  5. CPU 스케쥴링 정보: 프로세스 우선순위, 스케쥴 큐에 대한 포인터 등
  6. 메모리 관리 정보: 페이지 테이블 또는 세그먼트 테이블 같은 정보 포함
  7. 입출력 상태 정보: 프로세스에 할당된 입출력 장치들 및 열린 파일 목록
  8. 어카운팅 정보: 사용된 CPI 시간, 시간 제한, 계정 정보 포함

Context Switching

• 문맥 교환
• 이전 프로세스 상태를 PCB에 저장하고 또 다른 프로세스 정보를 메모리에 적재하는 과정

스레드(Thread)

• 프로세스 내에서 실행되는 여러 흐름의 단위

• PC(Program Counter) 및 Stack만 따로 할당받고 Code, Data, Heap 영역은 공유

• 다른 Thread의 Heap 영역 공유

• Stack을 독립적으로 가지는 이유: 독립적인 함수 호출을 통해 독립적인 실행 흐름 추가를 위해

• PC 레지스터를 독립적으로 가지는 이유: 스레드 명령어가 어디까지 수행됐는지 나타내며, 스레드는 스케쥴러에 의해 선점당하는 경우가 있기 때문에 어디까지 수행했는지 기억할 필요가 있다.

• 구성 요소

  1. 스레드 ID
  2. 프로그램 카운터(PC): 프로세스가 다음에 실행할 명령어 주소 저장
  3. 레지스터 집합들
  4. 스택: 함수 내 선언 변수, 복귀 주소, 매개변수 등 임시 변수 저장

Multi-Threading vs Multi-Processing

Multi-Threading

• 장점

  • 스레드 간의 통신이 필요한 경우 별도 자원을 사용하지 않고 공유하는 Heap 영역 을 통해 데이터를 주고 받을 수 있어 통신 방법이 훨씬 간단함.
    • 공유 데이터가 많아 지금까지 쌓아둔 캐시 데이터가 의미가 있음
  • 프로세스 생성을 통한 자원 할당 시스템 콜이 줄어들어 자원을 효율적으로 관리가 가능

• 단점

  • 다른 Thread가 사용 중인 자원에 접근해 엉뚱한 값을 읽거나 수정 가능
  • 이 때문에 동기화 작업 필요, 하지만 이로 인해 병목 현상 발생
  • 오류로 하나의 스레드가 종료 시 전체 스레드에 영향

Multi-Processing

• 장점
  • 서로 독립된 프로세스에서 실행되므로 하나가 죽더라도 다른 프로세스에 영향을 끼치지 않음.
• 단점
  • 많은 메모리 공간 및 CPU 시간 차지
  • Context Switching시 공유 데이터가 없으므로 캐시 메모리를 비워야 해 시간이 오래 걸림

결론

• 속도가 빠른 것이 중요시될 시 멀티스레딩 이 더 좋지만 공유 자원에 여러 스레드가 접근하는 경우가 많은 경우 오류가 발생할 가능성이 높아지므로 멀티 프로세스를 사용하는 것이 더 나을 수도 있음.
• 상황에 따라(안전 vs 속도) 적절한 동작 방식을 선택할 필요.

스케쥴러

• 프로세스를 스케쥴링하기 위한 Queue
  • Job Queue(Pool): 현재 시스템 내에 있는 모든 프로세스 집합
  • Ready Queue: 현재 메모리 내에 있으면서 CPU를 잡아 실행되기를 기다리는 프로세스 집합
  • Device Queue(I/O Waiting queue): Device I/O 작업을 기다리는 프로세스 집합
• 이러한 Queue들에 프로세스를 넣고 빼는 작업을 스케쥴러가 담당

• 스케쥴러 종류

1. Long-Term Scheduler

• 메모리에 비해 많은 프로세스가 한꺼번에 올라올 경우 Job Queue에 저장한 후, 어떤 프로세스에 메모리를 할당해 Ready Queue에 보낼지 결정하는 역할

2. Short-Term Scheduler

• CPU와 메모리 사이 스케쥴링 담당
• Ready Queuedp 있는 프로세스 중 어떤 프로세스를 running시킬지 결정
• 프로세스에 CPU 할당

3. Medium-term Scheduler

• 여유 공간을 마련하기 위해 프로세스를 통째로 메모리에서 디스크로 쫓아내는 것 담당
• 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절

CPU 스케쥴러

• 위의 단기 프로세스의 다른 이름
• 스케쥴링 대상: Ready Queue에 있는 프로세스
• 선점형(프로세스 CPU 강제로 뺏음)/비선점형(CPU를 획득한 프로세스가 스스로 반납할때 까지 CPU 안 뺏김)으로 나뉜다.
• 디스패쳐: CPU 코어의 제어권을 CPU 스케쥴러가 선택한 프로세스에게 주는 모듈
  • 한 프로세스에서 다른 프로세스로 Context Switching
  • 사용자 모드로 전환

스케쥴링 기준

• 최대화: CPU Utilization(CPU 이용률) 및 Throughput(시간당 완료 프로세스 개수)을 최대화
• 최소화: Turnaround Time(프로세스 실행 시간), Waiting Time(큐 대기 시간), Response Time(큐에 들어간 후 프로세스 종료까지 걸린 시간)
• 위 기준이 제일 이상적이지만 대부분 알고리즘에 Trade-off가 존재.

스케쥴링 알고리즘

1. FCFS(First-Come-First-Served) 알고리즘

• 먼저 온 순서대로 처리
• 비선점형
• 문제점: Convoy Effect, 소요시간이 긴 프로세스가 먼저 도달할 시 효율성이 낮음

2. SJF(Shortest-Job-First) 알고리즘

• 비선점형
• 프로세스 종료 시 도착한 프로세스 중에서 CPU Burst Time이 가장 짧은 프로세스에 선 할당
• 문제점: Startvation, 사용 시간이 긴 프로세스는 거의 영원히 CPU 할당 불가능

3. SRTF(Shortest Remaining Time First) 알고리즘

• 새로운 프로세스가 도착할 때마다 새로운 스케쥴링
• 선점형, 현재 수행중인 프로세스의 남은 시간보다 더 짧은 CPU burst time을 가진 프로세스가 들어올 시 CPU를 뺏음
• 문제점: Starvation 및 계속 스케쥴링을 하기 때문에 CPU 사용시간 측정이 힘듦

4. Priority Scheduling

• 우선순위가 가장 높은 프로세스에 CPU 할당
• 작은 숫자가 우선순위가 높음
• 선점형/비선점형 존재
• 문제점: Starvation 및 무기한 봉쇄(실행 준비는 되어있으나 CPU를 사용 못하는 CPU가 무기한 대기)
• 이에 대한 해결책: Aging - 우선순위가 낮은 프로세스도 시간이 지남에 따라 우선순위를 높임

5. Round Robin

• 현대적인 CPU 스케쥴링
• 각 프로세스는 동일 크기의 할당시간을 가짐
• 할당 시간이 지나면 프로세스는 선점 당하고 Ready Queue 맨 뒤로 이동
• CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 경우 효율 적
• 프로세스는 Context를 save할 수 있어 가능
• 장점
  • Response Time이 빨라짐
  • 모든 프로세스가 공정하게 받을 수 있음
• 단점
  • 할당 시간이 너무 길 시 FCFS와 같아짐
  • Context Switching 비용 존재
• 시분할 처리 시스템: 각각의 작업들에게 일정한 CPU 시간만큼을 차례로 할당하는 RR 스케쥴링 사용하는 방식, 각 사용자에게 독립된 컴퓨터를 사용하는 느낌 제공

Synchronization

정의

• 여러 프로세스 or 스레드가 공유하는 자원의 일관성을 유지하기 위한 활동
• 동기화가 없다면 Race Condition(2개 이상의 프로세스가 공통 자원을 병행하면서 읽을 시 순서에 따라 결과가 달라지는 현상)이 발생해 일관성이 깨진다.

비동기 vs 동기

• 동기(Synchronous)
  • 요청과 결과가 동시에 일어남.
  • 요청과 결과가 한 자리에서 동시에 일어나며, 요청 시 결과를 받을 때까지 대기
• 비동기(Asynchronous)
  • 요청과 결과가 동시에 일어나지 않음
  • 노드 사이 작업 처리 단위를 동시에 맞추지 않아도 됨.

임계 영역

• Critical Section: 실행 코드 중에 공유 데이터로 접근하는 코드
• 이 부분을 동기화를 통해 일관성을 유지시켜야 한다
• 임계 영역 문제 해결 충족 조건
  1. Mutual Exclusion(상호 배제): 하나의 프로세스가 임계 영역에 있으면 다른 프로세스는 못 들어간다
  2. Progress(진행): 임계 영역을 차지하는 프로세스가 없을 시 새로운 프로세스가 접근하면 들여보내준다
  3. Bounded Waiting(유한 대기): 임계 영역에 접근 요청 후 이가 받아들여질 때 까지의 시간은 유한해야 함

뮤텍스

• MUTual EXclusion(상호 배제)의 약자
• 오직 하나의 프로세스(스레드)만이 동일 시점에서 뮤텍스를 얻어 임계 영역 입장
• 임계 영역에 들어온 스레드만 락 해제 가능

세마포어

• Lock을 걸지 않은 스레드도 Signal을 보내 락 해제 가능
• Wait & Signal 사용
  • wait 호출 시 세마포어 카운트 1 내림
  • signal 호출 시 카운트 1 증가
  • 카운트가 0보다 작아질 시 lock 실행
• 만약 초기 세마포어 카운트는 1로 설정 했을 시 뮤텍스와 같음, 즉 세마포어는 뮤텍스가 될 수 있음

스핀락

• 다른 스레드가 Lock 소유 시 Sleep 하는 대신 lock가 반환될 때까지 계속 확인
• 보통 sleep하는 과정에서 context switching이 발생하므로 스핀락은 아주 작업에 대해 효율적이라 할 수 있음
• 하지만 얻을 때 까지 계속 돌리므로 Busy Waiting 문제로 CPU 오버헤드가 발생할 수 있는 문제점

모니터

• 현재 많이 사용되고 있는 동기화 도구로, 세마포어보어 고수준 개념으로 알려져 있고 주로 Java에 사용됨
• 배타 동기, 조건 동기 이 2가지 Queue를 가짐
• 배타동기 Queue는 Synchronized 키워드를 통해 호출
• 조건동기 Queue는 wait(), notify(), notifyAll()로 호출
• 세마포어보다 코딩이 훨씬 쉬운데, 이는 항상 스레드가 들어오고 나가는 걸 명시해줘야하는 세마포어와 다르게 Synchronized 키워드만 붙이면 알아서 조절해준다.

Atomic operation

• 결코 분해할 수 없는 물리적인 작업을 일컫는 말
• 경쟁 상태를 해결(동기화)하기 위한 하나의 방법
• 조건
  1. 모든 조작이 완료할 때 까지 어떤 프로세스도 변경을 알지 못하게 해야함
  2. 조작 중 하나라도 실패하면 이전 상태로 복구.

DeadLock

• 프로세스가 자원을 얻지 못해 다음 처리를 못하는 상태
• 시스템이 한정된 자원을 여러 곳에서 사용하려고 시도 시 발생

발생 조건

1. 상호 배제(Mutual Exclusion): 자원은 한 번에 한 프로세스에만 사용 가능
2. 점유 대기(Hold and Wait): 프로세스는 최소한 하나의 자원을 점유함, 다른 프로세스에 할당되어 사용하는 자원을 추가로 점유하기 위해 대기하는 프로세스 존재
3. 비선점(No Preemption): 프로세스에 할당된 자원은 사용이 종료될 때까지 강제로 못 뺏음
4. 순환 대기(Circular Wait): 프로세스 집합에서 순환 형태로 자원 대기

-> 이 4가지 조건이 모두 만족해야 데드락 발생, 하나라도 성립하지 않는다면 해결 가능

해결 방법

• 예방(Prevention): 교착 상태 중 하나를 제거해 해결하는 방법, 이는 자원 낭비가 매우 심하다고 한다

• 회피(Avoidance): 교착 발생 시 피하는 방법으로, 대표적으로 은행원 알고리즘이 존재

  • 은행원 알고리즘
    • 프로세스가 자원을 요구할 시 자원 할당 후에도 안정 상태가 유지되는지를 확인하며 이것이 유지되면 할당되고 아니면 거절 및 대기
    • 수행되기 위한 3가지 도구
    1. Max: 각 프로세스가 자원을 얼마나 요청 가능한지
    2. Allocated: 각 프로세스가 현재 보유하고 있는 자원은 얼마인지
    3. Available: 시스템이 얼마나 자원을 보유하고 있는지
    • 여기서 자원을 할당 요청받았을 시 그 요청을 받을 시 안정 상태 및 불안정 상태를 확인하고 여부에 따라 할당해줄지 거절할지 결정

• 탐지 및 회복(Detection): 자원 할당 그래프를 통해 교착 상태를 탐지

  • 자원 할당 그래프

    

    • 동그라미는 프로세스, 네모는 리소스
    • 프로세스 -> 리소스: 리소스 할당 요청
    • 리소스 -> 프로세스: 리소스 할당된 상태
    • 이 상태에서 사이클이 일어나고 자원의 유형이 하나밖에 없다면 교착 상태

• 회복: 교착 상태가 일어난 프로세스를 종료하거나 교착 상태의 프로세스들을 자원 선점해 회복 시도

  • 종료 방법
  1. 모두 종료
  2. 교착 상태가 제거될 때까지 하나씩 종료
  • 자원 선점 방법
  1. 해당 프로세스를 일시 정지한 후 자원을 선점해 다른 프로세스에 할당
  2. 우선순위가 낮거나 수행 횟수가 적은 프로세스 위주로 선점

메모리 관리 기법

• 각각의 프로세스는 독립된 메모리 공간을 가지며, 다른 프로세스 및 OS의 메모리 공간에 단독 접근 불가, OS는 예외적으로 이러한 제약이 없음

메모리 낭비 방지 방법

1. 동적 적재(Dynamic Loading): 프로그램 실행에 반드시 필요한 루틴 및 데이터만 적재하고, 필요 시에 해당 부분을 동적으로 메모리에 적재
2. 동적 연결(Dynamic Linking): 라이브러리 루틴 연결을 컴파일 시점이 아닌 실행 시점까지 미루는 기법, DLL 사용

단편화

• 프로세스들이 메모리에 적재되고 제거되는 일이 반복되면 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼 작은 자유공간들이 늘어나는 것

  • 내부 단편화

    • 프로세스가 hole 안에 들어가면서 사용하지 못하게 되는 용량 부분

    

  • 외부 단편화

    • 메모리 공간 중 사용하지 못하게 되는 부분 발생

    

  • 압축

    • 위 공간들을 합치면 충분한 공간이 생기는 경우 이것들을 한 쪽으로 몰아 자유 공간을 확보하는 방법론, 효율이 좋지 않음

메모리 관리 전략

• 연속 메모리 할당(Continuous Memory Allocation)
  • 프로세스를 메모리에 연속적으로 할당
  • 할당 및 제거를 반복하다보면 Scattered Holes가 발생해 외부 단편화가 발생, 매우 비효율적
  • 단일
    1. 스와핑(Swapping): CPU에서 실행되지 않는 프로세스 전체 저장장치의 Swap 영역으로 이동해 메모리 확보, 이 과정에서 큰 전송시간이 필요하기 때문에 메모리 공간이 부족할 때 사용
    2. 오버레이(Overlay): 주기억장치보다 큰 프로그램을 실행하기 위한 기법, 프로그램을 여러 조각으로 나눔
  • 다중
    1. 고정 분할 할당: 사용자 영역을 여러 개 고정된 크기로 분할, 준비상태 큐에서 프로그램 영역에 할당
    2. 가변 분할 할당: 필요한 만큼의 크기를 영역으로 분할
• 분산 할당 기법: 가상 기억장치를 사용해 프로그램을 주기억장치에 적재, 보조 기억 장치의 일부를 주 기억장치로 사용해 불연속 적으로 사용

페이징

• 외부 단편화를 예방하는 방법
• 프로세스를 일정 크기인 페이지로 잘라서 메모리 프레임에 적재하는 방식
• 하나의 프로세스는 연속 동작을 수행하므로 물리 주소를 이용해 쪼개져 있는 페이지를 CPU로 하여금 연속적이라고 인지하게 해야한다.
• CPU는 논리 주소를 이용해 연속적인 주소값으로 명령을 내리지만, 실제 메모리 주소가 저장되어 있는 페이지 테이블을 이용해 물리 주소로 변환
  • 페이지 테이블에 프레임 숫자 저장, 이롤 통해 물리 주소를 찾음, 이를 연속적으로 이어서 메모리 할당

세그멘테이션

• 내부 단편화를 예방하는 방법
• 프로세스를 세그먼트(ex - data + code + stack)라는 논리적 집합으로 나눠서 메모리에 저장, 세그먼트의 크기는 일정하지 않음
• 세그먼트 테이블에는 시작 주소(base) 및 세그먼트 크기(limit)를 저장, 만약 CPU에서 크기를 넘어가는 주소를 부르면 인터럽트가 발생, 강제 종료

페이징/세그멘테이션 비교

• 세그멘테이션은 페이징과 다르게 논리적으로 나누기 때문에 해당 비트를 보호하고 공유하기 쉬움, 그러나 외부 단편화가 자주 일어나며, 이에 대한 최적화 알고리즘이 존재하지 않음
• 페이징은 물리적으로 나누기 때문에 외부 단편화를 효과적으로 방지할 수 있으나 보호 및 공유가 힘듦.

Paged segmentation

• 페이징/세그멘테이션 장점을 합친 메모리 할당 기법
• 세그멘테이션을 먼저 진행한 후 페이징 기법을 통해 메모리 할당
• 세그먼트 테이블에 Base 대신 페이지 테이블 위치를, limit 대신 페이지 개수를 저장
• 페이지의 크기를 축소 가능
• 메모리 참조가 한번 더 증가하여 속도 저하의 문제점

가상 메모리

• 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법
• 프로그램 전체가 아닌 필요한 일부분만 실제 메모리에 올리는 기법

가상 주소 공간

• 한 프로세스가 메모리에 저장되는 논리적인 모습을 가상 메모리에 구현한 공간
• 프로세스 중 핵심 부분(Code/Data/Stack/Heap) 부분만 따로 실제 메모리에 올림

Demand paging

• 기본 컨셉: 가상 메모리가 추구하는 방식을 구현, 사용하는 부분만 메모리에 올리는 방법 중 하나
• 가상 메모리는 페이지로 관리, 실행과정에서 필요해질 때 물리 메모리에 적재.
• 페이지는 페이저로 관리, 실제 필요한 페이지들만 메모리로 읽어 옮으로서 사용되지 않을 페이지를 가져오는 시간 낭비/메모리 낭비를 줄일 수 있음, 페이저는 캐시이기도 함.
• 페이저는 Valid-Invalid Bit를 가지며 이는 메모리에 올리는 것이 현재 메모리에 존재하는지 아니면 Disk에 있는지 확인

Page Fault

• 지금 실행시켜야할 Page가 실제 메모리에 올라와 있지 않는 경우

• Page Fault 일어날 시 과정

  1. CPU가 OS에 이를 알리고 잠시 CPU 작업 멈춤
  2. OS는 Disk에서 해당 부분을 찾아서 물리 메모리의 비어있는 Frame에 올림
  3. Page Table의 해당 부분 Bit를 Valid로 전환
  4. Page fault가 일어난 명령어를 다시 실행

  

Page Replacement 알고리즘

• 현재 자신이 차지하고 있는 Frame을 지금 당장 실행해야 할 Page에게 넘겨줄 Victim Frame을 찾는 과정

• Modify Bit를 통해 Victim Frame을 찾게 도와줌

  • Page 중 내부 데이터가 바뀌었는지 알려주는 Bit, 내부 데이터가 바뀌었을 시 Swap-out 필요
  • 이는 많은 비용 발생, Modify Bit가 0인 Frame 우선 탐색

• Page Replacement 기본 과정

  1. 원하는 Page를 Disk에서 찾는다.
  2. 비어있는 Frame 확인, 있으면 사용하고 없으면 Page Replacement 알고리즘 통해 Victim Frame 찾기
  3. Disk에서 가져온 Page를 2번 과정서 찾은 Frame에 넣고 갱신
  4. 프로세스 재실행

알고리즘 종류

1. FIFO(First-in First-out) 페이지 교체

• 실제 메모리에 올라온지 가장 오래된 Frame 선택
• Frame 수가 많아도 Page Fault가 많이 발생하는 모순

2. 최적(Optimal) 페이지 교체

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체
• 가장 낮은 페이지 부재율을 보장하지만 구현이 어려움.

3. LRU(Least-Recently-Used)

• 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체
• 대체적으로 FIFO 알고리즘보다 우수하고 OPT 알고리즘보단 못함
• 보통 구현은 Queue처럼 사용되는 Linked-List에 list의 Node를 map과 연결시켜서 사용

4. LFU(Least Frequently Used) 페이지 교체

• 참조 횟수가 가장 적은 페이지 교체
• 특정 페이지에 집중하다가 다른 기능을 사용해도 계속 메모리에 머무는 문제 발생

5. MFU(Most Frequently Used) 페이지 교체

• 참조 횟수가 많은 페이지를 교체