PCB 와 컨텍스트 스위칭

PCB(Process Control Block) 은 운영체제에서 관리하는 프로세스에 대한 메타데이터를 저장한 데이터 블록이며, 커널 스택에 저장된다.

각 프로세스가 생성될 때 마다 고유의 PCB가 생성 되고, 프로세스가 종료되면 PCB 는 제거된다.

유저 메모리, 커널 메모리

가상메모리는 유저메모리와 커널 메모리로 나뉜다.

유저 메모리와 커널 메모리는 전부 스택 영역을 사용하기 때문에 유저 스택, 커널 스택이라고 부르기도 한다.

여기서 커널 모드일때만 사용할 수 있는 메모리를 커널 메모리(스택)이라고 한다.

반대로 유저 모드일때만 사용할 수 있는 메모리는 유저 메모리(스택) 이라고 한다.

PCB의 구조

Process State : 대기중, 실행 중 등의 프로세스 상태를 나타낸다.

Process Number : 각 프로세스의 고유 식별 번호

Program Counter : 이 프로세스에 대해 실행될 다음 명령의 주소에 대한 포인터

Registers : 레지스터 관련 정보

Memory Limits : 프로세스의 메모리 관련 정보

List of Open Files : 프로세스를 위해 열린 파일 목록들

컨텍스트 스위칭

앞서 설명한 PCB를 기반으로 프로세스의 상태를 저장하고 다시 복원시키는 과정

이는 프로세스가 종료되거나 인터럽트에 의해 발생된다.

컨텍스트 스위칭의 비용

• 유휴시간의 발생 : 컨텍스트 스위칭을 할 때 마다 유휴시간이 생겨서 CPU의 가용성이 떨어진다.
• 캐시 미스 : 프로세스가 가지고 있는 메모리 주소가 그대로 있으면 잘못된 주소 변환이 생기므로 캐시 클리어 과정이 무조건 일어나게되고, 이 때문에 캐시 미스가 발생 페이지 테이블에 가상 주소가 실제 주소와 매칭 되어 있음. 그 위에 TLB 캐싱 계층이 있는데, 계속 컨텍스트 스위칭을 하면 캐시 미스가 발생하게 된다. 따라서 캐시를 계속 바꿔야한다.

프로세스의 상태

프로세스의 상태변화

CREATE

프로세스가 생성된 상태

fork, exec 시스템 콜 등을 통해 프로세스가 생성된 상태이며 PCB 가 할당된다.

• fork : 부모 프로세스를 복제해서 자식 프로세스를 생성한다.
• exec: 현재 프로세스의 메모리 공간에 새로운 실행 파일을 로드하여 기존 프로그램을 대체한다.

보통은 fork 로 자식 프로세스를 생성한 후에, exec 로 해당 프로그램을 대체하는 방식을 주로 쓴다.

생성되고 나서는 대기(Ready) 상태로 간다.

Ready

처음 프로세스가 생성된 이후, 메모리 공간이 충분하면 메모리를 할당받고 아니면 준비큐에 들어가서 대기중인 상태

이는 CPU 스케쥴러로부터 CPU 소유권이 넘어오기를 기다리는 상태

Ready Suspend

Ready 큐가 꽉찬 상태라서, 메모리가 부족하기 때문에 Ready 상태가 아닌 Ready Suspend 가 된 상태

Running

실행 상태는 CPU 소유권과 메모리를 할당받고 명령어를 수행 중인 상태.

CPU Burst 가 일어났다고도 표현한다.

Blocked

어떤 이벤트가 발생한 이후, 잠시 중단되어 프로세스가 차단된 상태

예를 들어 프린트 인쇄 버튼을 눌렀을 때 프린트 인쇄 I/O 인터럽트에 의해, 현재 실행중이던 프로세스가 잠시 Blocked 상태로 들어갈 수 있다.

Blocked Suspend

Blocked 된 상태에서 프로세스가 실행되려고 했지만, 레디 큐로 들어가지 못하고 메모리 부족으로 또 다시 중단된 상태

Terminated / Exit

프로세스 실행이 완료되어 해당 프로세스에 대한 자원을 반납하고, PCB 가 삭제된 상태.

부모 프로세스가 자식 프로세스를 강제로 종료시킨 경우도 있다.

브라우저

멀티 프로세싱 + 멀티 스레딩

https://d2.naver.com/helloworld/5237120

멀티 프로세싱

브라우저의 멀티 프로세싱

멀티 스레딩

image.png

IPC

Inter Process Communication 이란 프로세스끼리 데이터를 주고 받고 공유 데이터를 관리하는 매커니즘이다.

IPC 의 종류로는 공유 메모리, 파일, 소켓, 파이프, 메시지 큐가 있다.

공유 메모리

프로세스와 프로세스가 메모리를 공유해서 데이터를 주고 받는 방식

메모리 자체를 공유하기 때문에 불필요한 데이터 복사의 오버헤드가 발생하지 않아 가장 빠르지만, 같은 메모리 영역을 여러 프로세스가 공유하기 때문에 동기화가 필요

IPC 중에서 가장 빠른 통신 방법.

파일

디스크에 저장된 데이터를 기반으로 통신한다.

요즘엔 잘 쓰이지 않는다.

파이프

파이프는 통신을 위한 메모리 공간(버퍼)를 생성해서 프로세스 간 통신을 하는 방식이다.

(Unnamed Pipe) 익명 파이프

익명 파이프는 프로세스 사이에 FIFO 기반의 통신 채널을 만들어 통신하는 방식

이름이 정해지지 않은, 즉 부를 수 없는 파이프라서 외부에서 사용할 수 없다.

단방향 통신이므로 양방향 통신을 하려면 2개의 익명 파이프가 필요

부모, 자식 프로세스 간에서는 파일 디스크립션을 상속 받아서 사용할 수 있으며 다른 네트워크상에서는 사용이 불가능

파이프의 데이터 용량은 제한되어 있으며 쓰기 프로세스가 읽기 프로세스보다 더 빠르게 데이터를 쓸 수는 없다

Named Pipe (명명 파이프)

익명 파이프의 확장된 개념이며 부모, 자식 뿐만 아니라 다른 네트워크 상에서도 통신할 수 있는 파이프

보통 서버, 클라이언트용 파이프를 구분해서 동작한다

파이프 시나리오

메세지 큐

메세지 큐는 자료구조 형태로 관리하는 버퍼를 만들어 통신하는 방식이다.

매세지 큐의 동작 방식

1. 프로세스가 메세지를 보내거나 받기 전에 메세지 큐를 초기화
2. Sender 의 메세지는 큐에 복사되어 Receiver 에 전달된다.

자원 경쟁

공유자원

공유자원이란 시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 모니터, 프린터, 메모리, 파일, 데이터 등의 자원이나 변수를 의미한다.

경쟁 상태

경쟁 상태(Race Condition)은 이 공유 자원을 둘 이상의 프로세스 또는 스레드가 동시에 읽거나 쓰는 상황을 말하며, 동시에 접근을 시도할 때 예상되는 결과값에 영향을 줄 수 있는 상태를 의미한다.

임계 영역

임계 영역(Critical Section) 은 둘 이상의 프로세스 또는 스레드가 공유 자원에 접근할 때, 순서 등의 이유로 결과가 달라지는 코드 영역을 의미한다.

즉 경쟁 상태에 있는 영역

이 영역은 한 번에 둘 이상의 프로세스나 스레드가 접근할 수 없도록 설계된다.

경쟁 상태 관리의 중요성

데이터 정합성

데이터 정합성(data consistency) 는 예상되는 데이터와 값이 같아야함을 의미한다.

데이터 무결성

데이터 무결성(data integrity) 는 데이터의 어떠한 규칙을 위반하지 않아야 함을 의미한다.

예를 들어, 잔고가 음수가 될 수는 없다.

또한 데이터가 전송, 저장되고 처리되는 모든 과정에서 변경되거나 손상되지 않고 완전성, 정확성, 일관성을 유지함을 보장하는 특성을 말한다.

경쟁 상태의 해결 조건

아래의 세 조건을 만족해야 경쟁 상태를 해결할 수 있다.

상호 배제

상호 배제(mutual exclusion) 은 한 프로세스가 임계 영역에 들어갔을 때, 다른 프로세스는 들어갈 수 없음을 의미한다.

한정 대기

한정 대기(bounded waiting) 은 특정 프로세스가 임계영역 진입을 요청한 후, 해당 요청이 승인되기 전까지 다른 프로세스가 임계영역에 진입하는 횟수를 제한하는 것을 말하며, 이를 통해 특정 프로세스가 영원히 임계 영역에 들어가지 못하게 되는 것을 방지한다.

(자원이 독점되지 않도록)

진행의 융통성

진행의 융통성(progress) 는 만약 어떠한 프로세스도 임계 영역을 사용하지 않는다면, 임계영역 외부의 어떠한 프로세스도 들어갈 수 있으며 이 때 프로세스끼리 서로 방해하지 않는 것을 의미한다.

경쟁 상태의 해결 방법

뮤텍스

뮤텍스(mutex) 는 공유 자원을 lock() 을 통해 잠금 설정하고 사용한 후에, unlock() 을 통해 잠금해제한다.

이러한 객체 Lock 을 기반으로 경쟁 상태를 해결하는데, 잠금 상태가 되면 다른 프로세스나 스레드는 해당 코드 영역에 접근할 수 없고, 해제되면 가능하다.

한 번에 하나의 프로세스만 임계 영역에 있을 수 있다.

세마포어

세마포어(semaphore) 는 일반화된 뮤텍스를 의미한다.

정수 S, Wait(), Signal() 을 통해서 공유 자원에 대한 접근을 처리한다. 이를 통해 여러 프로세스가 동시에 임계 영역에 접근할 수 있다.

• S : 현재 쓸 수 있는 공유 자원의 수
• Wait() : S 를 1씩 감소 시킨다. 만약 S가 음수라면 공유 자원에 대한 접근은 못하고 블락된 채, 대기열로 들어간다.
• Signal() : S 를 1씩 증가 시킨다. 프로세스가 공유 자원 사용을 마친 상태이고, S 가 0 이하라면 대기열에 있던 프로세스가 동작하게 된다.

바이너리 세마포어

바이너리 세마포어는 0과 1 두 가지 값만 가질 수 있는 세마포어이다.

구현의 유사성으로 인해 뮤텍스는 바이너리 세마포어와 유사하다고 할 수 있으나, 뮤텍스는 잠금을 기반으로 상호 배제가 일어나는 잠금 매커니즘이고, 세마포어는 신호를 기반으로 상호 배제가 일어나는 신호 매커니즘이다.

카운팅 세마포어

카운팅 세마포어는 S의 숫자가 1보다 큰, 세마포어를 의미한다.

모니터

모니터

모니터는 둘 이상의 스레드나 프로세스가 공유 자원에 안전하게 접근할 수 있도록 공유 자원을 숨기고 해당 접근에 대해 인터페이스만 제공하는 객체이다.

이를 통해 공유 자원에 대한 작업들을 순차적으로 처리한다.

교착 상태

교착상태(deadlock) 은 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 말한다.

각각의 프로세스는 서로가 원하는 자원을 유지한 채, 다른 프로세스의 자원을 얻기를 기다린다.

교착상태가 발생하기 위한 4가지 필요조건은 다음과 같다.

• 상호 배제: 주어진 시간 내에 하나의 프로세스만 자원을 독점할 수 있다. 즉 다른 프로세스들은 접근이 불가능
• 점유 대기: 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하며 대기하는 상태
• 비선점: 다른 프로세스의 자원을 강제적으로 가져올 수 없다.
• 환형 대기: 프로세스 A는 프로세스 B의 자원을 요구하고, 프로세스 B는 프로세스 A의 자원을 요구하는 등 서로가 서로의 자원을 요구하는 상황

해결 방법 1. Banker’s Algorithm

교착 상태 가능성이 없을 때만 자원 할당되며, 프로세스당 요청할 자원들의 최대치를 통해 자원 할당가능 여부를 파악하는 ‘은행원 알고리즘(banker’s algorithm)’

은행원 알고리즘은 교착 상태를 회피하는 알고리즘으로, 총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정, 불안정 상태로 나누고 안정 상태로 가도록 자원을 할당하는 알고리즘

안정 상태 : 교착 상태를 일으키지 않은 상태이며, 프로세스의 최대 자원 요구량을 운영체제가 충족시킬 수 있는 상태

불안정 상태 : 안전 상태로 가는 순서열이 존재하지 않는 상태

은행원 알고리즘 예시1

은행원 알고리즘 예시1

해결방법 2, 3

• 교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 한 개씩 지우기
• 해결 방법은 아니지만, 교착 상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 오히려 더 클 수도 있다. 따라서 교착 상태가 발생하면 사용자의 작업을 종료시켜버린다.

CPU 스케줄링 알고리즘

스케줄링 알고리즘에는 선점형(preemptive) 알고리즘과, 비선점(non-preemtive)형 알고리즘이 있다.

중간에 인터럽트를 발생시켜서 강제적으로 컨텍스트 스위칭을 일으키는 것이 선점형알고리즘,

하나의 프로세스가 종료될 때 까지 대기하고 컨텍스트 스위칭을 일으키는 것이 비선점형 알고리즘이다.

비선점형 알고리즘

FCFS(First Come, First Saved)

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘

길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect) 가 발생할 수 있다.

FCFS 알고리즘 예시

p1 → p2 → p3 → p4

p1 이 버스트 타임이 길기 때문에 나머지가 오래 기다려야 한다.

SJF (Shortest Job First)

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

긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation) 이 일어날 수 있지만, 평균 대기 시간이 가장 짧다

하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행 정보를 토대로 추측해야한다.

image.png

실행시간이 매우 긴 프로세스가 있으면 레디큐에서 계속 대기할 확률이 매우 높다.

우선 순위 알고리즘

오래된 작업일수록 우선순위를 높이는 방법(aging) 을 통해 SJF 의 단점을 보완한 알고리즘

우선순위는 작업의 시간, 프로세스의 메모리 요구사항, 열린 파일 수, 평균 CPU 사용량 등을 고려해서 설정

선점형 알고리즘

현대 운영체제가 쓰고 있는 방식으로, 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시키고 강제로 다른 프로세스에 CPU 소유권을 할당할 수 있는 방식

라운드 로빈 (RR, Round Robin)

현재 컴퓨터가 쓰는 스케쥴링 방법이자 단순한 선점형 알고리즘

각 프로세스에게 동일한 할당 시간을 주고, 그 시간 안에 끝나지 않으면 다시 준비 큐의 마지막으로 들어가는 알고리즘.

그런데 동일한 할당 시간을 q 라고 할 때, q 를 너무 크게 주면 사실 상 들어온 순서대로 프로세스를 진행하는 FCFS 가 되어버린다. 따라서 q 를 적절히 조절할 수 있어야 한다.

너무 작게 하면 컨텍스트 스위칭이 너무 많이 일어나면서 오버헤드가 과하게 생길 수 있다.

일반적으로 전체 작업 시간은 길어지지만, 평균 응답 시간은 짧아진다는 특징이 있다.

SRF(Shortest Remaining Time First)

SRF 는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 즉시 중지하고 더 짧은 프로세스를 수행한다.

SJF 는 비선점형이기 때문에 해당 프로세스가 끝나야 그 다음 제일 짧은 프로세스를 수행하는 것과의 차이가 있다.

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐 마다 라운드 로빈이나 FCFS 등 다른 스케쥴링 알고리즘을 적용한 것을 말한다.

큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.

우선순위가 높은 큐부터 처리되기 때문에 낮은 큐의 프로세스가 처리 되지 않는 기아 현상(starvation) 이 발생할 수도 있다.

image.png

캐시

데이터를 미리 복사해 놓는 임시 저장소이자, 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리를 말한다. 이를 통해 데이터 접근 시간의 단축, 데이터를 다시 계산하는 등의 시간을 절약할 수 있다.

캐시의 예로 CPU 레지스터를 들 수 있다.

캐시 설정 원리

캐시를 설정할 때는 자주 사용하는 데이터 를 기반으로 설정해야 한다.

이 때 지역성을 기반으로 설정하게 되는데 지역성은 시간 지역성 과 공간 지역성 으로 나뉜다.

시간 지역성

시간 지역성은 최근 사용한 데이터에 다시 접근하려는 특성

공간 지역성

공간 지역성은 최근 접근한 데이터를 이루고 이쓴ㄴ 공간이나 그 가까운 공간에 접근하는 특성

캐시 매핑

캐시의 크기는 메모리보다 항상 작기 때문에 효율적으로 매핑하는 것이 중요하며 매핑 방식에는 직접 매핑, 연관 매핑, 집합 - 연관 매핑이 있다.

직접 매핑(direct mapping)

직접 블록별로 매핑을 한다.

캐시가 다섯 블록이라면, 메모리를 5개의 영역으로 나누어서 각각의 영역당 하나의 캐시에 매핑 할 수 있도록 만든다.

image.png

특정 라인과 특정 블록이 매핑되어 있는 것

메모리 블록의 사이즈는 메모리의 크기 / 캐시의 블록 개수

운영체제는 보통 메모리를 똑같은 크기의 페이지(보통 4kb)

4kb 인 이유? : https://velog.io/@dosadola/pintos-%EC%A4%91%EA%B0%84-%EB%B0%9C%ED%91%9C-%EC%99%9C-memory-block-%EC%9D%80-4kb%EC%9D%B8%EA%B0%80

• 블록 당 영역이 정해져있기 때문에, 같은 블록에서 여러 개를 캐싱할 수 없다.

  따라서 같은 블록의 참조가 빈번하다면 계속 캐시를 스와핑해주어야 한다.

• 대신 특정 정보의 캐시를 찾을 때 특정 블록만 찾으면 된다는 장점이 있다.

연관 매핑(associative mapping)

순서를 일치시키지 않고 관련 있는 캐시와 메모리를 매핑하며 메모리의 컨텐츠가 캐시의 어느 위치에도 올라갈 수 있는 방법(자유롭게 캐싱)

• 특정 정보의 캐시를 찾을 때, 모든 캐시를 탐색해야한다.
• 그러나 스와핑이 빈번하게 일어나지는 않는다.

집합 연관 매핑(set associate mapping)

집합을 나누고(집합 매핑과 유사) 해당 집합에는 block descriptor 만 같으면 들어올 수 있게 하는데, 이 때 어떤 블럭에도 들어갈 수 있게 한다.(연관 매핑과 유사)

즉 캐시의 집합을 나누었는데, 집합에 1개의 블록만 있다면 직접 매핑이고, 캐시 집합이 1개라면 연관 매핑인 것이다.

이를 통해 모든 블럭을 찾을 필요 없이, 특정 블럭을 찾게 해 탐색 비용을 낮춘 직접매핑의 장점과 스와핑을 완화시키는 연관매핑의 장점을 모두 지니게 된다.

메모리 할당

프로그램에 필요한 메모리를 할당할 때 시작 메모리 위치, 메모리 할당 크기를 기반으로 할당하는데 이는 연속할당과 불연속 할당으로 나뉜다.

연속 할당

메모리에 연속적으로 공간을 할당하는 것. 사용 가능한 모든 메모리 공간이 같은 위치에 있다.

즉 메모리 파티션이 전체 메모리 공간에 분산되어 있지 않다.

이는 고정분할방식과 가변분할방식이 있다.

고정 분할 방식

고정분할방식은 메모리를 미리 같은 크기로 분할해서 할당하는 방법.

고정 크기를 프로그램에 할당하므로, 프로그램의 크기보다 더 큰 메모리를 할당하게 된다.

따라서 내부 단편화(internal framentation)가 발생할 수 있다.

image.png

가변 분할 방식

가변분할방식은 프로그램에 필요한 만큼 동적으로 할당하는 방법.

내부 단편화가 아닌 외부 단편화가 발생할 수 있다.

image.png

가변 분할 방식에는 최초 적합, 최적 적합, 최악 적합이 있다.

홀(hole) : 할당할 수 있는, 비어 있는 메모리 공간

• 최초 적합(frist fit) : 위쪽이나 아래쪽부터 시작해서 홀을 찾으면 바로 할당
• 최적 적합(best fit) : 필요한 메모리 크기 이상인 공간 중에서 가장 작은 홀에 할당
• 최악 적합(worst fit) : 프로세스의 크기와 가장 많이 차이가 나는 홀에 할당

불연속 할당

메모리를 연속적으로 할당하지 않는 방법으로, 현대 운영체제가 쓰는 방법.

프로그램에 필요한 메모리를 쪼개어 서로 다른 위치에 있는 메모리 공간에 할당

페이징, 세그멘테이션, 페이지드 세그멘테이션 기법이 있다.

페이징

페이징은 동일한 크기의 페이지 단위(보통 4kb)로 나누어 메모리의 서로 다른 위치에 프로세스를 할당

홀의 크기가 균일하지 않은 문제는 없어지지만 주소 변환을 페이지별로 해야 하기 때문에 주소 변환이 복잡해지는 단점이 있다.

외부 단편화가 생겨도 분할해서 할당할 수 있기 때문에, 외부 단편화를 해결할 수 있다.

그렇지만 결국 동일한 크기의 페이지 단위로 나눈다는 것은 언제나 내부 단편화를 유발할 수 있다.

세그멘테이션

페이지 단위가 아닌, 의미 단위인 세그먼트로 나누는 방식(즉, 동일한 크기가 아닐 수 있다.)

프로세스는 코드, 데이터, 스택, 힙으로 나누어져서 메모리가 할당되는데 코드와 데이터, 또는 코드와 스택 등으로 나눌 수도 있으며 함수 단위로도 나눌 수 있다.

공유와 보안 측면에서 좋지만 홀 크기가 균일하지 않게 된다.

내부 단편화는 해결될 수 있지만, 다시 외부 단편화가 일어날 수 있다.

페이지드 세그멘테이션

세그멘테이션으로 나누되, 해당 세그멘테이션을 동일한 크기의 페이지로 나누는 방법

세그먼트에 의해 1kb, 5kb 로 나뉘었다면 이를 2kb 기준으로 나누어 2kb, (2kb, 2kb, 2kb) 로 나누는 방식

busy wait

busy wait 는 프로세스, 스레드가 어떠한 일을 실행하기 전에 만족하는 조건을 지속적으로 확인하는 동기화 기술이다.

프로세스1이 점유하고 있는 자원을, 프로세스 2가 사용하고 싶을 때 blocking 되고 대기하는 과정이다.

운영체제와 펌웨어의 차이

• 펌웨어는 ROM 이라고 불리는 비휘발성 메모리 하나를 쓰는 반면, 운영체제는 휘발성 비휘발성 메모리를 계층화해서 사용한다.
• 펌웨어는 자유롭게 프로그램을 설치할 수 없으며, 미리 설치해놓은 프로그램을 기반으로 업데이트가 일어난다. ROM 에 해당 소프트웨어를 지우고 덮어쓰면서 업데이트가 발생. → 멱등성처럼 변화를 최소화 하는 느낌인거 같다 반면, 운영체제는 정기적으로 업데이트 되며 프로그램을 자유롭게 설치할 수 있다.