[WIL] 크래프톤 정글 8~9주차 - PintOS 키워드 정리

728x90

미완성 글입니다... 이후 내용 추가 및 수정 예정입니다.

Process, Thread

Process

- 프로세스란 운영체제로부터 시스템 자원을 할당받은 작업의 단위로, 쉽게 말하면 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램이라고 할 수 있다.

- 할당받는 자원의 예로는 CPU 시간, 운영되기 위해 필요한 주소 공간, Stack, Heap, Data, Code의 구조로 되어있는 독립된 메모리 영역 등이 있다.

- 프로세스는 각각 독립된 메모리 영역을 할당받는다.

- 기본적으로 프로세스는 각각 최소 1개의 스레드를 가지고 있다.

- 기본적으로 각 프로세스는 별도의 주소 공간에서 실행되기 때문에 다른 프로세스의 데이터에 접근할 수 없다.

다른 프로세스에 접근하려면 프로세스 간의 통신(IPC, inter-process communication)을 사용해야 한다.

ex) message passing, shared memory 등을 이용한 통신

· shared memory : 프로세스들이 메모리에서 공유하는 영역에서 read / write를 통해 통신을 수행하는 것을 말한다.

프로세스가 공유 메모리 할당을 커널에 요청하면 커널은 해당 프로세스에 메모리 공간을 할당해준다. 그 이후에는 커널의 도움없이 해당 영역에 자유롭게 접근이 가능하다.

shared memory(공유 메모리)는 프로세스 간의 통신을 수월하게 만들지만, 동시에 같은 메모리 위치에 접근하게 되면 동기화 문제가 발생할 수 있다.

· message passing : system call을 이용하여 커널 영역을 통해 send(message)와 receive(message)이라는 두 가지 연산을 통해 프로세스 간 통신을 하는 방식

shared memory 보다 속도는 느리지만, 동기화 문제가 발생하지 않아 적은 양의 데이터를 교환하는 데 유리하다.

(pipe, socket, message queue 등의 방식이 있다.)

Thread

- 스레드란 프로세스 내에서 실행되는 여러 흐름의 단위로, 프로세스가 할당받은 자원을 이용하는 실행 흐름의 단위라 할 수 있다.

- 스레드는 프로세스 내에서 각각 Stack만 따로 할당받고, Code, Data, Heap 영역을 공유한다.

이 때문에 프로세스 내에서 한 스레드가 오류로 인해 강제 종료된 경우, 다른 스레드가 모두 함께 종료 된다.

- 스레드들끼리는 프로세스 내의 주소 공간이나 자원들(힙 영역 등)을 서로 공유하면서 실행된다.

- 각각의 스레드는 별도의 레지스터와 스택을 가지고 있지만, 힙 메모리는 서로 읽고 쓸 수 있다.

- 한 스레드가 프로세스 자원을 변경하면, 다른 이웃 스레드도 그 변경 결과를 즉시 볼 수 있다.

Multi-Process & Multi-Thread

Multi-Process

- 멀티 프로세싱이란, 하나의 응용 프로그램을 여러 개의 프로세스로 구성하여 각 프로세스가 하나의 작업을 처리하도록 하는 것이다.

- 장점

· 여러 개의 자식 프로세스 중 하나에 문제가 발생하면 그 자식 프로세스만 죽는 것 이상으로 다른 영향이 확산되지 않는다.

- 단점

· Context Switching에서의 오버헤드 : 컨텍스트 스위칭 과정에서 캐시 메모리 초기화 등, 무거운 작업이 진행되고, 많은 시간이 소모되는 등의 오버헤드가 발생한다.

프로세스는 각각의 독립된 메모리 영역을 할당 받았기 때문에 프로세스 사이에 공유하는 메모리가 없어, 컨텍스트 스위칭이 발생하면 캐시에 있는 모든 데이터를 리셋하고 다른 프로세스의 캐시 정보를 불러와야 한다.

· 프로세스 사이의 어렵고 복잡한 통신 기법(IPC) : 프로세스는 각각의 독립된 메모리 영역을 할당받았기 때문에 하나의 프로그램에 속하는 프로세스들 사이에 변수를 공유할 수 없다.

Multi-Thread

- 멀티 스레딩이란, 하나의 응용 프로그램을 여러 개의 스레드로 구성하고, 각 스레드로 하여금 하나의 작업을 처리하도록 하는 것이다.

윈도우, 리눅스 등 많은 운영체제들이 멀티 프로세싱을 지원하고 있지만, 멀티 스레딩을 기본으로 하고 있다.

웹 서버는 대표적인 멀티 스레드 응용 프로그램이다.

- 장점

· 시스템 자원 소모 감소(자원의 효율성 증대) : 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어들어 자원을 효율적으로 관리할 수 있다.

· 시스템 처리량 증가(처리 비용 감소) : 스레드 간 데이터를 주고 받는 것이 간단해지고 시스템 자원 소모가 줄어들게 된다.

스레드 사이의 작업량이 작아 컨텍스트 스위칭이 빠르다.

· 간단한 통신 방법으로인한 프로그램 응답 시간 단축 : 스레드는 프로세스 내의 Stack 영역을 제외한 모든 메모리를 공유하기 때문에 통신의 부담이 적다.

- 단점

· 주의 깊은 설계가 필요하다.

· 디버깅이 까다롭다.

· 단일 프로세스 시스템의 경우, 효과를 기대하기 어렵다.

· 다른 프로세스에서 스레드를 제어할 수 없다.(프로세스 밖에서 스레드 각각을 제어할 수 없다.)

· 멀티 스레드의 경우 자원 공유의 문제가 생긴다.(동기화 문제)

· 하나의 스레드에 문제가 발생하면 전체 프로세스가 영향을 받는다.

Multi-Process vs Multi-Thread

선택하는 기준

· 안정성 vs 자원 사용 : 시스템의 안정성이 매우 중요한 경우, 멀티 프로세스가 선호된다. 리소스가 제한적인 환경에서는 멀티 스레드가 더 효율적일 수 있다.

· 구현의 복잡성 : 스레드는 공유 메모리로 인해 동기화 문제가 복잡해질 수 있으므로, 개발자의 동시성 제어에 대한 이해도가 중요하다.

· 응답 시간 : 멀티 스레드는 컨텍스트 스위칭이 빠르기 때문에, 더 빠른 응답 시간을 요구하는 경우 유리할 수 있다.

· 플랫폼 및 언어 지원 : 사용 중인 프로그래밍 언어나 플랫폼이 멀티 스레드 또는 멀티 프로세스 중 어느 쪽을 더 잘 지원하는지도 중요한 요소가 될 수 있다.

Context Switching

- Context Switching이란, 작업의 주체(Process, Thread)가 현재 Context를 잠시 중단하고, 다른 Context를 실행하는 것이다. 쉽게 말해 실행되는 프로세스나 스레드가 중단되고 다른 프로세스나 스레드가 실행되는 것을 말한다.

이 때, 이 작업은 kernel mode에서 실행된다.

- 프로세서가 지금까지 실행되던 프로세스(A)를 중지하고 다른 프로세스(B)의 PCB(Process Control Block) 정보를 바탕으로 프로세스(B)를 실행하는 것을 Process Context Switching이라고 한다.

- 동일한 프로세스 속에서 하나의 스레드(a)를 중지하고 다른 스레드(b)의 TCB(Thread Control Block) 정보를 바탕으로 스레드(b)를 실행하는 것을 Thread Context Switching이라고 한다.

- 프로세스는 하나 이상의 스레드로 동작하기 때문에 Context Switching의 최소 단위는 TCB이다.

참고)

	PCB(Process Control Block)	TCB(Thread Control Block)
정의	Process의 현재 상태를 저장하는 하나의 데이터 구조	하나의 Thread를 관리하는데 필요한 정보를 담고 있는 데이터 구조
특징	· PCB는 다른 프로세스들이 쉽게 접근할 수 없다. · Kernel 영역에 저장된다.	· 프로세스의 상태를 관리하는 PCB보다 적은 양의 정보가 담겨있다. · context switching을 할 때 CPU scheduling을 하는 최소 단위이다.
포함하는 정보	· 현재 프로세스 State(Ready, Wait, Running, Terminated 등) · Process Id, Parent Process Id · CPU registers(프로세스의 레지스터 상태를 저장하는 공간) · Program Counter(PC) : 프로세스에서 실행되어야할 다음 instruction의 주소 · CPU Scheduling 정보 : 스케줄링에 필요한 우선 순위 및 scheduling queue의 pointer · Memory 관리 정보 : 페이지 테이블, 세그먼트 테이블 등 프로세스 내부에서 사용되는 논리 메모리 주소를 물리 메모리 주소로 변환하는데 필요한 테이블 데이터 · Accounting 정보 : process를 실행한 user의 정보 · I/O 상태 정보 : process에 할당된 물리적 장치 및 프로세스가 읽고 있는 파일에 대한 정보	· Thread Identifier : 스레드를 구분하는 유일한 식별자 · Stack Pointer : 스레드 별로 고유한 stack의 pointer · program counter : 현재 instruction의 주소 · 스레드의 상태(Running, Ready, Waiting, Start, Done 등) · 스레드의 register values · 스레드가 속한 프로세스의 PCB 주소

CPU Scheduling 알고리즘

- CPU Scheduling 알고리즘은 CPU 코어가 하나라면 한번에 하나의 프로세스만 실행 가능하므로 어떤 순서로 프로세스들을 실행시킬 지 정해야하는데, 그 때 사용하는 방법이 CPU 스케줄링 알고리즘이다.

- CPU 스케줄링 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 하는 것을 목표로 한다.

CPU 스케줄러가 스케줄링을 결정하는 타이밍

1) 실행(running) 상태에서 대기(waiting) 상태로 전환(switching) 될 때

2) 실행(running) 상태에서 준비(ready) 상태로 전환(switching) 될 때

3) 대기(waiting) 상태에서 준비(ready) 상태로 전환(switching) 될 때

4) 종료(Terminated) 될 때

└> 1번과 4번 상황에서 스케줄링이 발생하는 것을 비선점형(nonpreemptive) 스케줄링이라 하고, 이외의 모든 상황에서

스케줄링이 발생하는 것을 선점형(preemptive) 스케줄링이라고 한다.

FCFS ( First Come First Served )

- Queue의 FIFO 방식과 유사한 방법으로, 먼저 온 프로세스를 먼저 처리하는 알고리즘이다.

다음과 같이 프로세스가 P1, P2, P3 순으로 왔다고 가정하고, 각각의 CPU 이용 시간을 24ms, 3ms, 3ms라고 하자.

이 때 프로세스가 처리되는 것을 포현한 Gantt Chart는 다음과 같다.

이 때의 평균 waiting time 은 (0 + 24 + 27) / 3 = 17ms가 된다.

프로세스가 P2, P3, P1 순으로 왔을 때의 Gantt Chart는 다음과 같고,

평균 waiting time은 (0 + 3 + 6) / 3 = 3ms가 된다.

SJF ( Shortest Job First )

- 실행 시간이 가장 짧은 프로세스를 먼저 수행하는 알고리즘이다.

- SJF는 preemptive, nonpreemptive 두 가지 방식 모두 가능하다.

· nonpreemptive 방식일 경우 : 현재 돌아가고 있는 프로세스가 끝나는 것을 허용한다.

· preemptive 방식일 경우 : 현재 돌아가고 있는 프로세스의 남은 시간보다 CPU 이용 시간이 적은 프로세스가 오면 CPU를 양보한다. 이 방식은 Shortest - Remaining - Time - First(SRTF)라 불리기도 한다.

- SJF는 평균 waiting time이 최소가 되므로 optimal하다고 볼 수 있다.

- 다음 프로세스의 CPU 이용 시간을 예측하는 것이 어려워 다음과 같은 공식을 사용하여 다음 프로세스의 CPU burst 시간을 예측한다.

· t_n : n번째 process의 실제 CPU burst 시간

· τ(타우)_n+1 : 다음 CPU burst 시간을 예측한 것

· 0 ≤ α ≤ 1

다음과 같은 순서로 프로세스들이 왔을 때, SJF 방식으로 처리하면 Gantt Chart가 다음과 같이 나오게 된다.

Round - Robin Scheduling

- 라운드 로빈은 FCFS 스케줄링과 비슷하지만 preemption이 들어갔다는 점에서 다르다.

- 일정 크기의 time quantum(time slice)을 정해 각 프로세스가 해당 시간 만큼 실행되고 끝나지 않았다면 다른 프로세스로 교체되는 방식으로 진행된다.

- n개의 프로세스가 있으면 각 프로세스가 CPU를 1/n 만큼 가져간다고 보면 된다.

위와 같은 프로세스들이 현재 ready queue에 있고 time quantum이 4라고 했을 때의 Gantt Chart는 다음과 같다.

- time quantum이 작으면 작을 수록 프로세스 간의 context switching이 많이 일어나게 된다. Round Robin에서의 context switching은 피할 수 없어서 pure overhead 이다.

Priority

- 각 프로세스 당 정수인 priority가 주어진다. CPU는 가장 높은 priority를 가진 프로세스부터 실행시킨다.

- SJF가 실행시간이 짧은 것을 priority로 하는 일종의 priority scheduling으로 볼 수 있다.

- pirority는 내부적으로(internally) 또는 외부적으로(externally) 정해질 수 있다.

· internally defined priority : 측정 가능한 값들을 이용하여 프로세스의 priority를 결정한다.

ex) 시간 제한, 메모리 요구량 등

· externally defined priority : OS 밖에서 정한 기준을 통해 priority를 결정한다.

ex) 프로세스의 중요성(사용자가 평가) 등

- priority 스케줄링도 preemptive한 방법과 nonpreemptive한 방법이 있다.

preemptive한 방법은 현재 실행하고 있는 프로세스보다 더 높은 priority를 가진 프로세스가 ready queue에 들어오면 현재 프로세스가 CPU는 양보하고 더 높은 priority를 가진 프로세스가 preempt하여 실행되는 방식이다.

- priority 스케줄링은 Starvation이라는 현상이 발생할 수 있다.

Starvation

실행하려는 프로세스보다 priority가 높은 프로세스가 계속해서 들어와서 프로세스가 계속 대기만 하는 현상

해결방안으로는 system 상에서 오래 기다릴수록 priority를 점점 높여주는 Aging이라는 기술이 있다.

위와 같은 프로세스들이 ready queue에 있다고 하면 Gantt Chart는 다음과 같이 나타나게 된다.

Multilevel Queue Scheduling

- 위 그림과 같이 priority에 따라 ready queue가 여러 개로 구성되고, 각각의 큐는 각각의 스케줄링 알고리즘을 갖게 되는 방식이다.

- 각각의 큐는 CPU burst 시간을 일정 비율만큼 나눠갖게 된다.(나눠갖지 않으면 높은 순위의 queue부터 처리되어 Starvation이 발생할 수 있음)

queue 간의 Round Robin 방식이라고 이해하면 될 것 같다.

- 큐 사이에 프로세스들이 이동할 수 없어 유연성이 떨어지는 특징이 있다.

Multilevel Feedback Queue Scheduling

- Multilevel Queue의 단점을 보완하고자 나온 알고리즘으로, 큐 사이에 프로세스들이 이동할 수 있도록 한 알고리즘이다.

일종의 aging 방식을 도입하여 Starvation을 예방하는 것으로 볼 수 있다.

[추가] Priority Inversion

Race Condition ( + Critical Section )

Race Condition

- race condition(경쟁 상태)은 공유 자원에 대해 여러 프로세스가 동시에 접근을 시도할 때, 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 말한다.

공유 자원에 여러 프로세스가 동시에 접근할 때 자료의 일관성을 해치는 결과가 나타날 수 있다.

- Race condition은 동기화(synchronization)를 통해 막을 수 있는데 이 동기화는 유저 모드의 동기화와 커널 모드의 동기화로 나뉜다.

유저 모드의 동기화로는 int형의 turn과 bool형 flag를 사용하여 동기화를 진행하는 Peterson 알고리즘 등이 있다.

커널 모드의 동기화에는 Mutex lock, Semaphore, Monitor 등이 있다.

Critical Section

- Critical section(임계 영역)은 운영체제에서 여러 프로세스가 데이터를 공유하면서 수행될 때 각 프로세스에서 공유 자원에 접근하는 프로그램 코드 부분을 말한다.

- 프로세스 간 공유 자원을 접근하는데 있어서 문제가 발생하지 않도록 공유 자원의 독점을 보장해줘야 하는 영역이다.

- 이 문제를 해결하기 위해서는 아래의 3가지 조건을 만족해야 한다.

1. Mutual Exclusion(상호 배제) : 한 프로세스가 자신의 critical section에 들어와있다면, 다른 프로세스들은 critical section에 들어올 수 없다.

2. Progress(진행) : 아무도 critical section에 들어와있지 않다면, 진입하고자 하는 프로세스를 진입하게 해줘야한다. Critical section에 아무도 진입하지 못하면 안되며, 다음에 어떤 프로세스가 진입해야 하는지는 유한한 시간에 결정되어야 한다.

3. Bounded Waiting(유한 대기) : 프로세스가 critical section에 진입하기 위해서 무한히 기다리는 현상이 발생하면 안된다.

Mutex와 Semaphore

Critical-Section 문제를 해결하기 위한 Software적 방법으로 대표적으로 Mutex와 Semaphore가 있다.

Mutex Locks

- Mutex는 공유된 자원이나 critical section 등에 두 개 이상의 process 혹은 thread가 접근하는 것을 막아준다.

- 만약 프로세스가 mutex를 사용한다면, critical section에 들어가기 전에 lock을 acquire 해야하고, critical section에서 나올 때 lock을 realease 해야한다.

- acquire()과 release()를 호출하면 반드시 atomical하게 실행되어야한다.(atomic하게 실행 : 반드시 실행된다는 의미)

- Mutex는 busy waiting(spinlock이라고도불림)이라는 현상을 유발할 수도 있다.

Busy Waiting

- lock을 기다리는 process가 lock을 얻기 전까지 계속해서 실행되고 있는 상황을 말한다.

- busy waiting이 발생하는 경우, 현재 실행될 수 없는 프로세스가 불필요하게 CPU 자원을 계속 사용 낭비한다.

mutex lock을 이용하여 critical-section 문제를 해결하는 예시

Semaphore

- 세마포어는 리소스의 상태를 나타내는 간단한 정수 카운터로 생각할 수 있다.

- 세마포어의 종류는 Counting Semaphore와 Binary Semaphore 두가지로 나뉜다.

· Binary Semaphore : 0과 1 값만 갖는 semaphore로 mutex lock과 비슷한 기능을 한다.

· Counting Semaphore : 제한 없는 정수 값을 가질 수 있으며, 공유 자원에 접근할 수 있는 thread나 process의 개수를 제한하는 역할을 한다.(ex : 네트워크에서 서버에 접속할 수 있는 클라이언트의 수를 제한하는 것)

- Semaphore에서는 mutex에서의 함수와 비슷하게 wait()과 signal() 함수를 사용하고 그 형태는 다음과 같다.

하지만 이 두 개로는 busy waiting을 해결할 수 없다.

- busy waiting을 해결하기 위해 sleep과 wakeup 이라는 두 개의 함수를 사용한다.

· sleep : process를 semaphore에 관련된 waiting queue에 넣어둔다.(process가 실행되지 않게 만든다.)

· wakeup : process를 waiting state에서 ready state로 바꾼다.

- 세마포어는 C언어에서 다음과 같은 형태로 만들 수 있다.

이 list에 semaphore가 lock을 해제하기를 기다리는 sleeping 하고 있는 프로세스들이 들어있다.

- sleep과 wakeup을 추가한 wait()과 signal()의 형태는 다음과 같다.

Monitor

Deadlock

Deadlock의 정의

- Deadlock(교착 상태)란 두 개 이상의 프로세스들이 시스템 자원에 대한 요구 때문에 서로 상대방의 작업이 끝나기 만을 기다리고 있어서 아무 것도 완료되지 못하는 상태를 말한다.

쉽게 말해, 두 개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때, 무한 대기에 빠지는 상황을 일컫는다.

Deadlock의 발생조건

상호 배제(Mutual Exclusion)

한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

점유 대기(Hold and Wait)

자원을 최소한 하나 보유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

비선점(No Preemption)

이미 할당된 자원을 강제로 빼앗을 수 없다.(비선점)

순환 대기(Circular Wait)

대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

데드락의 해결법

데드락 예방(Deadlock Prevention)

- 데드락 발생을 원천적으로 차단한다.

- 데드락이 발생하는 4가지 필수 조건(상호 배제, 점유와 대기, 비선점, 순환 대기) 중 적어도 하나를 제거함으로써 데드락을 방지한다.

ex) 비선점 조건을 제거하면 어떤 리소스도 필요할 때 다른 프로세스에 의해 선점될 수 있으며, 이는 데드락을 방지할 수 있다.

데드락 회피(Deadlock Avoidance)

- 데드락 회피는 시스템이 데드락 상태로 진입하는 것을 회피하는 전략이다.

- 시스템은 리소스 할당 결정 시 데드락의 가능성을 고려한다.

ex) 뱅커스 알고리즘(Banker's Algorithm) : 프로세스에 리소스를 할당하기 전에 안전 상태를 유지할 수 있는지 확인한다. 만약 할당으로 인해 데드락이 발생할 위험이 있다면, 리소스가 할당되지 않는다.

데드락 탐지 및 회복(Deadlock Detection and Recovery)

- 시스템이 데드락을 탐지하고, 이를 해결하기 위한 조치를 취하는 것을 포함한다.

- 데드락 탐지는 주기적으로 리소스 할당 그래프를 검사하여 순환 대기 조건을 찾는 것으로 이루어질 수 있다.

- 데드락이 탐지되면, 시스템은 프로세스를 중지하거나 리소스 할당을 롤백하여 데드락을 해결한다.

자원의 상호 배제 제거(Ignoring Mutual Exclusion)

- 일부 경우에, 리소스의 상호 배제 조건을 제거할 수 있다.

ex) 리소스가 복사가 가능하거나 공유가 가능한 경우, 여러 프로세스가 동시에 해당 리소스를 사용할 수 있다.

이러한 방식으로 상호 배제 조건을 제거함으로써 데드락 발생 가능성을 줄일 수 있다.