WIL: WEEK 8

Process

프로세스란 실행 중에 있는 프로그램을 뜻한다. 하드디스크에서 프로그램 실행을 위해 메모리를 할당하고, 할당된 메모리 공간으로 바이너리 코드가 올라간다. 이 순간부터 프로세스라고 불린다.

운영체제는 프로세스가 필요로 하는 모든 상태정보의 변화를 추적하는데, 여기서 상태 정보는 context라고하며, 이 context에는 메인 메모리의 현재값, PC(program counter), 레지스터 파일을 포함한다.

Process State

• New: 프로세스를 생성 중인 상태
• Ready: 프로세스는 실행할 준비가 되어 있으나 운영체제가 다른 프로세스를 실행하고 있으므로 대기 상태이다.
• Running: 프로세스는 프로세서에서 실행 중이다.
• Blocked(waiting): 프로세스가 다른 사건을 기다리는 동안 프로세스 수행 중단
• Terminated: 실행이 끝나고 프로세스가 종료 중인 상태
  ex) 디스크에 대한 입출력 요청을 했을 때, 프로세스는 입출력이 완료될 때까지 대기하고 다른 프로세스가 실행됨

PCB(Process Control Block)

PCB는 운영체제가 프로세스 스케줄링을 위해 프로세스에 관한 모든 정보를 포함하고 있는 데이터베이스이다. PCB에는 그림과 같은 정보가 저장된다.

Context Switch(문맥 교환)

하나의 프로세스가 이미 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하기 위해, 즉 인터럽트(interrupt)가 발생했을 때, 기존에 사용 중이던 프로세스의 상태를 저장하고 새로운 프로세스를 로드하는 것을 context switch라고 한다.

입출력 요청이라던지 자식 프로세스(fork)를 만든다던지 등의 이유로 인터럽트가 일어나면 운영체제는 기존에 사용 중이던 프로세스의 문맥(CPU를 내어줄 때의 프로세스 상태)을 PCB에 저장한다. 그리고 새로운 프로세스의 상태를 PCB에서 불러온다.

참고로 process A -> OS -> process A는 context switching이 아니다. 다른 프로세스로 넘겨주는 과정이 있어야 context switching이다.

Thread

프로세스 하나만 써서 여러 프로그램을 실행하기에는 한계가 있고, 그렇다고 멀티 프로세스를 사용하기에는 메모리 낭비가 심해서 탄생된 것이 스레드다. 스레드란 하나의 프로세스 내에서 동시에 진행되는 작업 갈래, 흐름의 단위를 뜻한다. 하나의 프로세스에는 최소 하나의 스레드가 있으며, 여러 작업을 수행하기 위한 여러 개의 스레드가 있다면 멀티스레드라고 한다.

TCB(Thread Control Blocks)

TCB는 PCB 안에 들어있다. TCB도 운영체제가 생성하며 스레드가 실행을 마치고 소멸될 때 같이 없어진다.

스레드 간의 자원 공유는 TCB를 통해 관리되는데, 세마포어와 같은 동기화 기법을 사용할 때, TCB에서 세마포어 정보를 관리하고 스레드가 해당 자원에 대한 접근 권한을 흭득하거나 반납할 때 TCB 정보가 업데이트 된다. 세마포어에 관한 내용은 후술하겠다.

Difference Between Thread and Process

프로세스는 독립된 메모리 공간이 존재하기 때문에 다른 프로세스의 변수나 자료에 접근할 수 없지만, 스레드는 스레드끼리 자원을 공유한다. 좀 더 자세히 말하자면 스레드는 독립적인 스택 공간만 가지고 있으며 코드, 데이터, 힙 영역은 서로 공유한다.

멀티스레드와 멀티프로세스 방식을 사용할 때의 차이점은 프로세스는 하나의 프로세스가 다른 프로세스에게 영향을 미치지 않기 때문에 에러가 발생한다면 에러가 발생한 해당 프로세스만 문제가 되지만, 스레드는 하나만 문제가 생겨도 프로세스 전체가 종료되어버린다. 이를 동기화 문제라고 한다.

CPU 작업 처리 방식

병렬성(Parallelism)
병렬성은 동일한 시간에 독립적인 작업을 수행하는 것을 의미한다. 여러 작업을 다른 코어, 다른 프로세스 등에서 실행할 수 있다.

동시성(Concurrency)
동시성은 동일한 시간에 여러 작업이 겹치는 것을 의미한다. 동시에 실행하는 것이 아니라 context switching을 해서 동시에 실행되는 것처럼 보이게 하는 것이다. 동시성의 핵심 목표는 유휴 시간 최소화인데, 여기서 유휴 시간이란 작동이 가능한데도 작업하지 않는 시간을 말한다.

병렬성은 여러 task가 어떤 자원을 공유하고 있는지 공유하기 때문에 메모리 손상, 누수 등의 문제가 발생할 수 있다.

동시성은 여러 작업을 계속 번갈아서 실행하기 때문에 다음과 같은 문제가 발생할 수 있다.

• Race Condition: 여러 프로세스가 하나의 자원에 접근해 서로의 실행 결과에 영향을 주는 현상

• Deadlock: 여러 프로세스가 서로 상대방의 작업이 끝나기를 무한히 기다리는 현상

• Starvation: 특정 프로세스가 우선순위가 낮아 원하는 자원을 계속 할당받지 못하는 현상

동기화(Synchronization)

임계구역(Critical Section)이란 둘 이상의 스레드가 동시에 접근해서는 안되는 공유자원에 접근하는 코드의 일부를 뜻한다. 임계구역 안에서 race condition이 발생한다.

이 문제를 방지하기 위해 여러 스레드에게 하나의 자원에 대한 처리 권한을 주거나 순서를 조정하는 기법이 동기화다.

• 실행 순서의 동기화: 스레드 실행 순서를 정의해서 순서를 반드시 따르도록 하는 것이다.

• 메모리 접근 동기화: 메모리 동시 접근을 막는 것. 실행 순서에 관계없이 하나의 스레드만 하나의 자원에 접근할 수 있게 하는 것이다.

동기화 기법

• 유저모드 동기화: 커널의 힘을 빌리지 않는 동기화 기법(커널 코드 실행x)이다. 커널 모드를 사용하지 않기 때문에 기능이 제한적이나 성능 면에서는 유리할 수 있다. 인터락 함수 기반과 임계구역 기반의 동기화가 이에 해당한다.

간단히 설명하자면 인터락 함수 기반 동기화 방식은 함수 내부적으로 한 순간에 하나의 스레드에 의해서만 실행되도록 동기화 되어있으며, 임계구역 기반의 동기화는 하나의 스레드가 실행되고 나서 그 다음 스레드에게 넘겨주는 식의 동기화이다.

• 커널모드 동기화: 커널에서 제공하는 동기화 기능을 사용하는 기법이다. 유저모드 동기화에 비하면 느리나 커널 모드로 전환하므로 좀 더 활용할 수 있는 방면이 많다.

세마포어, 락, 모니터 등이 동기화에 사용될 수 있다. 셋 다 유저모드와 커널모드의 동기화에서 사용될 수 있으나 락은 일반적으로 커널모드에서 사용한다.

세마포어(Semaphore)

공유 자원에 접근할 수 있는 스레드, 프로세스의 수를 제한한다. Deadlock의 해법으로 2개의 원자적(atomic)함수로 제어되는 정수와 변수를 통해 공유자원에 대한 접근을 제어하는 방식이다.

여기서 원자성이란 여러 개의 스레드가 존재할 때 특정 시점에서 어떤 메소드를 2개 이상의 스레드가 동시에 호출하지 못하는 경우를 말한다. 원자성을 보장한 함수가 원자적 함수이다.

세마포어는 상호 배제 알고리즘, 즉 공유 불가능한 자원의 동시 사용을 피하기 위해 임계구역에서 사용되는 알고리즘에 기반하여 작동한다. 일반적으로 세마포어의 값이 0이라면 자원에 접근할 수 없도록 블락하고 0보다 크면 접근함과 동시에 세마포어의 값을 1 감소시킨다. 종료하고 나갈 때는 세마포의 값을 1 증가시켜 다른 프로세스가 접근할 수 있도록 한다.

세마포어는 변수 S와 P 연산, V 연산으로 구성되어 있다. 세마포어 변수 S는 보통 정수형 변수를 사용하며, 종류는 이진형 세마포어와 계수형 세마포어가 있다.

• 이진형 세마포어(binary semaphore): 0 또는 1을 가진다. 1개의 공유 자원을 상호배제하며 이를 통해 계수 세마포어 구현이 가능하다.

• 계수형 세마포어(counting semaphore): 0과 양의 정수 값을 가진다. 여러 개의 공유 자원을 상호배제 할 수 있다.

변수 S는 P와 V라는 명령에 의해서만 접근이 가능하다.

P(or down)는 임계 구역을 사용하려는 프로세스들의 진입 여부를 결정하기 때문에 Wait 동작이라고도 한다. P는 임계 구역에 들어가기 전에 실행하며, 값이 양수가 되기를 기다렸다가, 양수가 되면 감소시킨다.

V는 대기중인 프로세스를 깨우는 신호(wake-up)로 signal 동작이라고도 한다. V는 임계 구역에서 나올 때 수행한다.

Scheduling Queue

스케줄링이란 처리할 일들의 진행순서를 정하는 일이다. 그래서 프로세스 스케줄링이라고 한다면 CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 일이다.

스케줄링 큐는 실행될 프로세스가 여러 개 있다면 하나만 실행되고 나머지는 CPU가 자유로워질 때까지 대기하는 것으로 선입선출 방식을 따른다.

• Job Queue: 메모리 할당을 대기 중인 프로세스들로 구성
• Ready Queue: CPU 할당을 대기 중인 프로세스들로 구성
• Device Queue: 입출력 장치 할당을 대기 중인 프로세스들로 구성

Round Robin Scheduling

선점형 스케줄링 중 하나로, 프로세스들 사이에 우선순위를 두지 않고 순서대로 시간단위로 CPU를 할당하는 방식이다. 라운드 로빈 스케줄링은 한 프로세스가 할당받은 시간(time slice, time quantum)동안 작업을 하다가 작업을 완료하지 못하면 타임아웃되어 ready queue의 맨 뒤로 가서 순서를 기다린다. 프로세스들이 작업을 완료할 때까지 계속 순환하면서 진행한다. 이번 핀토스 프로젝트 1 alarm clock을 구현할 때 이 스케줄링을 사용한다.

응답 시간이 짧기 때문에 응답 시간이 짧은 작업이 많을 수록 유리하다. 그런데 time slice를 너무 짧게 지정하면 잦은 context switching으로 인한 오버헤드가 과도하게 발생하니 주의해야 한다. 이에 따라 유닉스에서는 타임 슬라이스를 대략 100ms로 정한다.

Priority Scheduling(우선순위 스케줄링)

우선순위 번호를 각각의 프로세서에 할당하고, 높은 우선 순위를 가질수록(숫자가 낮을수록) 프로세서에 우선적으로 CPU를 할당한다.

Priority scheduling은 선점형(preemptive)과 비선점형(non-preemptive)으로 나뉜다.

• 선점형: 우선순위가 더 높은 프로세스가 들어올 시 CPU를 뺏어서 준다.
• 비선점형: 우선순위가 더 높은 프로세스가 들어와도 해당 프로세스 완료 전까지는 CPU를 넘겨주지 않는다.

우선순위 스케줄링은 우선순위가 낮은 프로세스가 cpu를 점유하지 못하는 starvation 현상이 일어날 수 있으며, ready queue에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꾸어야 하기 때문에 오버헤드가 발생하여 시스템 효율성을 저하시킨다는 단점이 있으나 프로세스의 중요도를 기준으로 작업해야할 때 적합한 스케줄링이다.

사진 출처 및 참고 자료
OSTEP BOOK
https://jeong-pro.tistory.com/93
https://woonys.tistory.com/entry/%EC%A0%95%EA%B8%80%EC%82%AC%EA%B4%80%ED%95%99%EA%B5%90-54%EC%9D%BC%EC%B0%A8-TIL-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-2-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4
https://velog.io/@chappi/OS%EB%8A%94-%ED%95%A0%EA%BB%80%EB%8D%B0-%ED%95%B5%EC%8B%AC%EB%A7%8C-%ED%95%A9%EB%8B%88%EB%8B%A4.-6%ED%8E%B8-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%813-%EC%84%A0%EC%A0%90%ED%98%95-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Round-Robin-SRT-%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%EB%B0%A9%EC%8B%9D-Multilevel-Queue
https://velog.io/@infoqoch/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81%EC%9D%B4%EB%9E%80
https://inpa.tistory.com/entry/%F0%9F%91%A9%E2%80%8D%F0%9F%92%BB-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%E2%9A%94%EF%B8%8F-%EC%93%B0%EB%A0%88%EB%93%9C-%EC%B0%A8%EC%9D%B4
https://yeonyeon.tistory.com/270
https://velog.io/@octo__/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4Semaphore
https://woonys.tistory.com/entry/PintOS-Project-2-Priority-Scheduling