운영체제

eunsiver·2023년 3월 8일

운영체제

목록 보기

4/5

프로세스와 스레드

프로그램: 파일 단위로 저장 장치에 저장되어 있으며, 아직 실행되지 않은 상태의 코드 덩어리
프로세스: 실행 중인 프로그램.
- 운영체제로 부터 주소 공간, 파일, 메모리 등을 할당받은 프로그램
스레드: 프로세스의 실행 단위
- 같은 프로세스에 있는 스레드끼리 프로세스의 자원을 공유할 수 있다.

프로세스

프로세스는 운영체제로부터 메모리 공간을 할당 받아 실행 중인 프로그램

프로세스에 할당되는 메모리 영역

코드, 데이터, 힙, 스택

코드 영역
- 프로세스가 실행할 코드가 기계어의 형태로 저장
- 컴파일 타임에 결정 Read-Only
데이터 영역
- 전역 변수, static 변수 등이 저장된 공간
- 전역 변수, static 변수를 참조한 코드는 컴파일하고 나면 데이터 영역의 주소값을 가리킨다.
- 컴파일 타임에 결정, Read-Wirte: 실행 중 변경가능
- 프로그램 시작과 함께 할당
- 프로그램이 종료되면 소멸
힙 영역
- 프로그래머가 관리하는 메모리 영역
- 힙 영역에 메모리를 할당하는 것을 동적할 당
- 런타임에 결정
- 스택보다 할당할 수 있는 메모리 공간이 많으나 데이터 읽고 쓰기가 느림
- 참조형 데이터 값이 저장(클래스, 클로저)
- 낮은 주소에서 높은 주소로 할당
스택
- 함수 안에 선언된 지역변수, 매개변수, 리턴값, 복귀 주소 등이 저장
- 함수 호출 시 기록하고 종료 되면 제거한다.
- 컴파일타임에 결정
- 정해진 크기가 있으므로 stack overflow 에러 발생 가능
- 높은 주소에서 낮은 주소로 할당

힙만 런타임에 결정된다.

초기화 된 변수: Data 영역, 초기화하지 않은 변수: BSS

Stack과 Heap 공간 접근 속도

스택이 훨 빠름: 이미 할당되어 있는 공간 사용

스택할당: 이미 생성되어 있는 스택에 포인터 위치만 바꿔주는 단순 CPU 연산

힙은 사용자가 할당해서 사용

요청된 chuck의 크기, 현재 메모리의 fagmentation 상황 등 다양한 요소를 고려하기 때문에 더 많은 CPU 연산 필요

공간 분할 이유?

최대한 데이터를 공유하여 메모리 사용량을 줄이기 위해서

같은 프로그램을 띄울 때 code영역 공유 가능

Stack, Data 영역을 나눈 이유? 역할 분배

stack: 함수의 흐름 관리

data: 전역변수, 정적 변수를 관리

프로세스 제어 블록(PCB)

특정 프로세스에 대한 정보를 담고 있는 운영체제의 자료구조
프로세스는 운영체제의 스케줄링 알고리즘에 따라 CPU 할당
작업 진행하다 프로세스 전환이 발생하면 하던 일을 저장하고 CPU를 반환
나중에 스케줄링에 의해 재실행되었을 때, 이전에 어디까지 작업이 진행되었는지 정보를 알아야 한다.
그 정보가 담긴 공간이 PCB
프로세스 생성과 동시에 프로세스의 고유한 PCB도 함께 저장

프로세스 제어 블록(PCB)에 저장되는 정보

프로세스 식별자 (Process ID, PID)
프로세스 상태 (Process state) : new, ready, running, waiting, terminated
프로그램 카운터 (Program counter) : 프로세스가 다음에 실행할 명령어의 주소를 가리킴
CPU 레지스터 : Accumulator, Index Register, 범용 레지스터 등
CPU 스케줄링 정보 : 프로세스 우선순위, 최종 실행 시각, CPU 점유 시간 등
메모리 관리 정보 : Page table, Segment table 등
계정 정보 : CPU 사용 시간, 제한 시간, 계정 번호 등
입출력 상태 정보 : 프로세스에 할당된 입출력 장치, 개방된 파일 목록 등

스레드

프로세스를 구성하는 독립적인 실행단위
스레드는 같은 프로세스 내 다른 스레드와 메모리 영역 공유
스레드도 하나의 실행 흐름으로 실행과 관련된 데이터가 필요하다.
- 독립적
  : 각 스레드는 자신만의 고유한 스레드 ID, 프로그램 카운터(PC), 레지스터 집합, 스택 영역을 가진다.
- 공유
  : 속한 프로세스 내의 코드, 데이터, 힙 영역과 기타 운영체제 자원(열린 파일, 신호 등) 다른 스레드와 공유

독립적인 스택 / 코드,데이터,힙 공유
각 스레드는 스택을 통해 독립적인 실행 흐름을 가진다.

🌈🌈스레드는 프로세스 메모리 영역을 공유하기 때문에 어떤 스레드 하나에 오류가 발생하면 같은 프로세스 내의 다른 스레드 모두 강제 종료

🌈🌈프로세스는 한 프로세스가 강제 종료되어도 공유 자원을 손상시키는 경우가 아니라면 다른 다른 프로세스에게 영향을 주지 않는다.

멀티 프로세스와 멀티 스레드

동시성

Concurrent: 어떤 job 여러 개가 동시에 처리된다는 개념(멀티)
Parallel: 어떤 하나의 job을 쪼개서 여러 sub-job으로 나누고, 이를 물리적으로 분리된 구조에서 동시에 처리해서 완성하는 개념(자동차 조립을 여러 사람이 동시에 하는 것, CPU의 core 여러개 표현)

멀티 프로세서나 멀티 코어 구조가 발전하기 전에는 싱글 프로세서로 재빠르게 프로세스를 전환하여 concurrent하게 동작하지만 parallel하게 동작하는 것처럼 보이도록 함

컨텍스트 스위칭 (Context-Switching)

CPU 코어를 다른 프로세스로 전환한기 위해 현재 프로세스의 상태 저장 및 다른 프로세스의 상태 복원

Context

CPU가 프로세스를 실행하기 위한 정보, PCB에 저장되는 정보들이 해당
컨텍스트 스위칭이 발생하면, 커널이 이전 프로세스의 context를 그 프로세스의 PCB에 저장하고 새롭게 실행할 프로세스의 저장된 context를 불러오게 된다.
컨텍스트 스위칭 수행 중에는 CPU 자원이 어떤 프로세스에 할당 된 상태가 아니기 때문에 CPU가 아무 작업도 할 수 없다.(따라서 Context-Switching time은 pure overhead)

스레드와 프로세스 중 컨텍스트 스위칭이 빠른 것은 스레드

스레드는 stack을 제외한 프로세스 메모리 영역을 공유하기 때문에 자신의 PCB에는 스택 및 간단한 정보만 저장하기 때문에 더 빠르다.

프로세스는 공유하는 데이터가 없으므로 임시 저장소인 캐시 메모리가 지금껏 쌓아놓은 데이터들이 사라지고 새로 데이터를 쌓아야 한다.

컨텍스트 스위칭이 발생할 때

인터럽트(Interrupt)

입/출력을 요청할 때

CPU 사용시간이 만료되었을 때

자식 프로세스를 만들 때

인터럽트 처리를 기다릴 때

멀티 프로세스

여러 개의 프로세스를 동시에 수행하는 것

프로세스는 부모, 자식 관계라고 해도 자신만의 메모리 영역을 가지게 되며, 공유되는 메모리 영역 없이 독립적인 구조를 가진다.

크롬 브라우저 멀티 프로세스 구조

대부분의 브라우저는 탭 브라우징을 지원한다.
만일 브러우저가 멀티 프로세스 구조를 가지지 않는다면 어떤 탭의 웹 어플리케이션이 비정상 종료되었 때, 다른 모든 탭을 포함한 전체 프로세스가 종료 될 것이다.

구글의 크롬 브라우저는 멀티 프로세스 구조를 가지고 있다. 브라우저의 각 탭은 Renderer 프로세스이며, 이들은 각자 독립적으로 실행된다. 하나의 웹사이트가 비정상 종료되어도 다른 Renderer 프로세스는 영향을 받지 않는다.

크롬은 다음과 같은 3가지 유형의 프로세스를 지원한다.

브라우저 프로세스: 사용자 인터페이스와 디스크 및 네트워크 I/O를 관리한다. 크롬이 시작되면 새 브라우저 프로세스가 생성
Renderer 프로세스: 웹 페이지 렌더링을 위한 로직(HTML, JavaScript, 이미지 등 처리)을 포함한다.
플러그인 프로세스: 각 플로그인 유형에 대해 플로그인 프로세스가 생성된다. 플러그인 프로세스에는 플러그인에 대한 코드와 연관된 Renderer, 브라우저 프로세스와 통신할 수 있는 추가 코드가 포함되어 있다.

멀티 프로세스의 통신 방법(IPC)

독립적인 메모리 영역을 가지는 프로세스끼리 통신하는 방법
데이터를 교환하기 위해서 IPC(Inter-Process Communication) 매케니즘이 필요하다.

공유 메모리: 프로세스가 공유하는 메모리 영역이 설정되며, 각 프로세스는 공유 영역에서 데이터를 읽고 쓰는 방식으로 정보를 교환할 수 있다.
- 중개자 없이 곧바로 메모리에 접근할 수 있기 때문에 모든 IPC 중에서 가장 빠르게 이동
- PC 재부팅하거나 직접 삭제하지 않는 한, 모든 프로세스가 종료 되었다고 하더라도 공간을 계속 유지
- 프로세스 간 read, write를 모두 필요로 할 때 사용
- 프로세스가 공유 메모리 할당을 커널에 요청하면, 커널은 해당 프로세스에 메모리 공간을 할당한다. 이후 어떤 프로세스 건 해당 메모리 영역에 접근 가능
  - 공유 메모리가 각 프로세스에게 첨부하는 방식으로 작동

파이프
소켓
메세지 큐
- 다수의 프로세스간 메시지 전달 가능
- 사용할 데이터에 번호를 붙이면서 여러 프로세스가 동시에 데이터를 쉽게 다룰 수 있다.
- 메시지 접근을 위해서는 key가 필요하다
메모리 맵
- 공유 메모리처럼 메모리 공유
- 열린 파일을 메모리에 맵핑 시켜 공유(공유 매개체: 파일+메모리)
- 주로 파일로 대용량 데이터를 공유해야 할 때

멀티 프로세스 장점

독립된 구조를 가지기 때문에 안전성이 높다.
하나의 프로세스가 비정상적으로 종료되어도 자식 프로세스 이외의 다른 프로세스들은 아무런 영향을 받지 않는다.

멀티 프로세스의 단점

독립된 메모리 영역을 가지고 있기 때문에 context switching을 위한 오버헤드(캐시 초기화 등)가 발생한다.
Context Switching이 빈번하게 일어나면 성능 저하를 유발할 수 있다.

멀티 스레드

한 프로세스에서 여러 개의 스레드를 동시에 수행하는 것

🌈멀티 스레드를 적용한 어플리케이션의 예시 (Multi-threaded applications example)

웹 서버 프로세스는 클라이언트 요청이 들어오면 그 요청을 처리하기 위한 별도의 스레드를 생성한다.
이는 새 프로세스를 생성하는 것보다 비용적인 측면에서 훨씬 효율적이다.
운영체제의 커널은 멀티 스레드이다.
Linux 시스템 부팅 시 여러 커널 스레드가 생성되고, 각 스레드는 장치 관리, 메모리 관리 또는 인터럽트 처리와 같은 특정 작업을 수행한다. (ps -ef 명령을 사용하여 실행 중인 Linux 시스템에서 커널 스레드를 표시 할 수 있다.)
이미지의 모음에서 사진 썸네일을 생성하는 어플리케이션은 별도의 스레드를 사용하여 각각의 개별 이미지에서 썸네일을 생성할 수 있다.
웹 브라우저는 하나의 스레드에서는 이미지나 텍스트를 보여주고, 또다른 스레드에서는 네트워크를 통해 데이터를 검색할 수 있다.

멀티 스레드의 장점

응답성이 좋아진다.
- 단일 스레드를 사용하면 그 작업이 완료될 때까지 응답을 기다려야 한다.
자원을 공유할 수 있다.
- 프로세스는 공유 메모리 및 메시지 전달과 같은 기술을 통해서만 자원을 공유할 수 있다.
- 스레드는 기본적으로 자신이 속한 프로세스의 자원을 공유하기 때문에 동일한 주소 공간 내에서 여러 스레드를 가질 수 있다.
비용이 적다.
- 스레드는 자신이 속한 프로세스의 자원을 공유하므로 스레드 생성과 context swtiching 비용이 더 적다.

멀티 스레드의 단점

스레드는 프로세스 내 자원을 공유하기 때문에 스레드 하나에서 오류가 발생하면 같은 프로세스 내의 모든 스레드가 종료될 수 있다.
공유 자원에 대한 동기화 문제를 고려해야 한다.

프로세스 스케줄링

프로세스 스케줄러는 멀티 프로그래밍과 time sharing의 목적을 달성하기 위해 실행 가능한 여러 프로세스 중에서 하나의 프로세스를 선택해 실행한다.

각 CPU 코어는 한번에 한 프로세스를 실행할 수 있다.
단일 CPU 코어 시스템에 반해 멀티 코어 시스템은 한 번에 여러 프로세스를 실행할 수 있다.

멀티 포르그래밍: CPU 사용률을 최대화하기 위해 항상 프로세스를 실행하도록 한다. 어떤 프로세스가 CPU를 사용하다가 I/O 작업 등 CPU를 필요로 하지 않는 순간이 오면 다른 프로세스가 CPU를 사용할 수 있도록 한다.
시분할 (time sharing) : 각 프로그램이 실행되는 동안 사용자들이 상호작용할 수 있도록 프로세스 간 CPU 코어를 자주 전환하는 것이다. CPU가 하나의 프로그램을 수행하는 시간을 매우 짧은 시간(ms)으로 제한하여 프로그램을 번갈아 수행하도록 하면 CPU가 하나인 환경에서도 여러 사용자가 동시에 사용하는 듯한 효과를 가져올 수 있다.

프로세스 상태

New : 프로세스가 생성됨
Running : 프로세스의 Instruction이 실행됨
Waiting : (I/O 작업 완료나 신호 수신과 같은) 이벤트가 발생하기를 기다림
Ready : 프로세서에 할당되기를 기다림
Terminated : 프로세스가 실행을 끝냄

스케줄링 큐

Ready Queue

프로세스가 시스템에 들어오면 ready queue에 들어가서 CPU 코어에서 실행되기를 기다린다.
Linked List 형태로 저장되며, ready queue의 header는 list의 첫번째 PCB를 가리키고, 각 PCB의 포인터는 ready queue에 있는 다음 PCB를 가리킨다.

Wait Queue

I/O 요청과 같은 특정 이벤트가 처리 완료되기까지를 기다리는 프로세스가 wait queue에 배치된다.
프로세스는 waiting 상태에서 ready 상태로 바뀌면 ready queue에 들어가게 된다.

프로세스는 종료될 때까지 위의 Queueing-diagram과 같은 주기를 반복하고, 종료되면 모든 큐에서 제거되고 PCB 및 자원 할당이 해제된다.

CPU 스케줄링

CPU 스케줄링은 Ready Queue에 있는 프로세스들을 대상

CPU 스케줄링 발생 상황

프로세스가 running → waiting 상태로 전환 (ex. I/O 요청 또는 하위 프로세스 종료를 위한 wait() 호출)
프로세스가 running → ready 상태로 전환 (ex. interrupt 발생)
프로세스가 waiting → ready 상태로 전환 (ex. I/O 완료)
프로세스 종료

스케줄링 시 상황 1, 4에서는 선택권 없이 새 프로세스를 선택해야 한다. 하지만 상황 2, 3에서는 다음과 같은 선택권이 있다.

선점/비선점 스케줄링

비선점 스케줄링 : CPU가 할당된 어떤 프로세스는 종료 / waiting 상태로 전환하여 CPU를 해제할 때까지 CPU를 유지하고, 다른 프로세스는 그 때까지 CPU를 사용할 수 없다.
선점 스케줄링 : 어떤 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 선점할 수 있다. Windows, macOS, Linux 및 UNIX를 포함한 거의 모든 최신 운영체제는 선점 스케줄링 알고리즘을 사용한다.

스케줄링 알고리즘

FCFS (First-Come, First-Served) Scheduling

비선점 스케줄링
먼저 CPU를 요청하는 프로세스에 먼저 CPU가 할당된다.
FIFO queue 를 사용해 쉽게 구현할 수 있다.
문제점) convoy effect
- 먼저 들어온 어떤 프로세스의 CPU 처리 시간이 길 경우 다른 모든 프로세스들이 기다림으로서 더 짧은 프로세스가 먼저 진행될 수 있는 경우보다 CPU 및 장치 사용률이 낮아지는 현상

SJF (Shortest-Job-First) Scheduling

비선점 스케줄링 방식
- CPU burst time이 가장 작은 프로세스에게 먼저 CPU를 할당한다. 만일 CPU burst time이 같다면, FCFS 방식을 적용한다.
선점 스케줄링 방식 (SRTF (Shortest-Remaining-Time-First) Scheduling)
- 새로 들어온 프로세스의 CPU burst time이 현재 실행 중인 프로세스의 남은 burst time 보다 작다면 현재 실행 중인 프로세스를 새로 들어온 프로세스가 선점한다.
Priority Scheduling의 한 예이다. (우선순위 = CPU burst time)
주어진 프로세스 집합에 대해 최소 평균 대기 시간을 제공한다는 점에서 최적의 알고리즘이다.
하지만 CPU burst time을 알 수 있는 방법이 없기 때문에 CPU 스케줄링 수준에서 구현할 수 없다.
- 이에 대한 한 가지 접근 방식은 SJF 스케줄링을 근사화하는 것이며, 이전 CPU burst time 지수 평균으로 예측할 수 있다.
문제점) starvation
- CPU 처리 시간이 긴 프로세스는 계속 Ready Queue의 뒤로 밀려나기 때문에 무한정 기다리는 상황이 발생할 수 있다.

RR (Round-Robin) Scheduling

선점 스케줄링
각 프로세스는 time quantum (or time slice) 이라는 작은 시간 단위(10-100ms)를 갖게 된다.
프로세스는 1 time quantum 동안 스케줄러에 의해 CPU를 할당 받고, 시간이 끝나면 interrupt를 받아 Ready Queue의 tail에 배치된다.
Ready Queue는 Circular FIFO queue 형태
RR의 평균 대기 시간은 긴 편이다. 하지만 공정하다.
n개의 프로세스가 있고 time quantum이 q일 때, 어떤 프로세스도 (n-1) x q 시간 단위 이상 기다리지 않는다.

Time quantum 설정 시 주의할 점

Time quantum이 너무 크다면 : FCFS와 같아진다.

Time quantum이 너무 작다면 : Context Switching이 너무 빈번하게 일어나 overhead가 발생한다.

위와 같이 RR 알고리즘의 성능은 time quantum의 크기에 좌우될 수 있으므로 적절히 선정해야 하며 이는 context-switch time보다 큰 것이 좋지만 또 너무 커서는 안 된다. (경험적으로 CPU burst의 80프로는 time quantum보다 짧은게 좋다고 함)

Priority Scheduling

정수로 표현된 우선순위가 더 높은 프로세스에게 CPU를 할당하는 스케줄링이다. 우선순위는 내부적/외부적으로 정의할 수 있다.
- 내부적 : 시간 제한, 메모리 요구 사항, 열린 파일 수, 평균 I/O burst 대 평균 CPU burst 비율 등 측정 가능한 수량 사용해 계산
- 외부적 : 프로세스의 중요성, 컴퓨터 사용에 대해 지불되는 자금의 유형 및 금액, 작업을 후원하는 부서, 기타 정치적 요인 등

선점 / 비선점 스케줄링 모두 가능하다.

선점 방식 : 새로 도착한 프로세스의 우선 순위가 현재 실행 중인 프로세스의 우선 순위보다 높으면 CPU 선점

비선점 방식 : 같은 경우 단순히 새 프로세스를 Ready Queue의 맨 앞에 둔다.

문제점) indefinite blocking, starvation
- 실행할 준비가 되었으나 CPU를 기다리는 프로세스는 block된 것으로 간주될 수 있다.
- 우선 순위가 낮은 일부 프로세스는 무기한 대기 상태가 될 수 있다.
해결 방안) Aging, Round-Robin과 결합
- Aging : 오랫동안 대기하는 프로세스의 우선순위를 점진적으로 높이는 방식으로 문제점을 해결할 수 있다. 예를 들어 대기 중인 프로세스의 우선순위를 매초 늘리는 것이다.
- RR+PS : 우선순위가 가장 높은 프로세스를 실행하는데, 동일한 우선순위의 프로세스에 대해서는 Round-Robin 스케줄링을 적용한다.

MLFQ(Multi-Level Feedback Queue)

프로세스가 큐들 사이를 이동하는 것을 허용
Aging으로 Starvation을 예방
이 알고리즘은 특정 시스템에 부합하도록 구성이 가능하므로 현대 사용되는 알고리즘 중 가장 일반적인 CPU 스케줄링 알고리즘
가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수 값들을 선정하는 특정 방법이 필요하기 때문에 가장 복잡한 알고리즘

동기와 비동기의 차이

Synchronous == Blocking ? Asynchronous == Non-blocking?

결론 부터 말하자면 다르다!

Sync & Async

동기와 비동기는 호출 되는 함수의 완료를 호출한 쪽에서 신경 쓰느냐 호출 받은 쪽에서 신경을 쓰냐의 차이

Blocking & Non-blocking

Blocking 호출받은 쪽이 호출한 쪽에 제어권을 넘겨주지 않는 것이고 Non-blocking은 다시 제어권을 넘겨주는 것

Sync & Blocking

가장 기본적으로 생각하는 Sync 이다. 함수를 호출하면 호출 받은 쪽에서 제어권을 가지고 있기 때문에 결과값이 반환 될때 까지 다음 동작을 시행 하지 않는다.

Sync & Non-Blocking

Non-Blocking 이라 함수가 완료 되지 않아도 제어권은 넘겨 주어 함수를 호출한 쪽에서 다음 동작을 시행 할 수는 있지만 함수가 완료되는 것을 신경을 써야하기 때문에 주기적으로 함수가 완료 되었는지 확인 해야한다.

Async & Blocking

잘 상상이 안 가는 그림이다. 작업완료 여부를 호출된 쪽에서 신경 쓰고 제어권도 호출된 쪽에서 가지고 있다. 사실상 Sync & Blocking과 거의 같아 잘 사용되지 않는다.

Async & Non-blocking

가장 기본적으로 생각하는 Async이다. 함수를 호출하면 제어권을 다시 호출 한쪽으로 넘겨주어 다음 동작을 이어 나가면서 호출 받은 쪽에서 알아서 콜백 함수의 결과를 리턴하여준다.

네 가지 조합의 모든 경우의 수가 가능하다고 하는데 잘 이해가 안된다. 다음에 다시 보기로!!!

참고
https://github.com/Seogeurim/CS-study/tree/main/contents/operating-system#priority-scheduling

프로세스 동기화

Critical Section(임계구역) 이란?

동일한 자원을 동시에 접근하는 작업을 실행하는 코드영역
멀티 쓰레딩의 문제점이 발생

Ctritical Section Problem

공통된 (data) 영역에 하나의 프로세스(task or thread) 만 들어 갈 수 있도록 설계하는 것

Mutual Exclusion(상호배타)
- 어떠한 Task(Thread)가 Critical Section 을 사용중이면 다른 Task는 사용이 불가함.
Progress
- 현재 Critical Section 을 사용중인 Task가 없고 Critical Section에 들어가길 원하는 Task 가 있다면 바로 들여보냄
Bounded Waiting
- 한정된 대기시간을 가져야 한다 => 무한 대기 X

Hardware Solution

Memory Barriers
Compare & Swap
Atomic Variables.

Software Solution(Mutex Lock, Semaphores)

1. Mutex Lock (hardware-based)

Acquire() : Lock 획득
Release() : Lock 방출
Task가 Crtical Section에 들어갈 때 acquire() 하고 나올 때 release() 하여 한 Task만 Critical Section 에 들어 갈 수 있게 한다.

while(true){
  acquire();
  /* Critical Section*/
  release();
  /* Remainder Section*/
}

acquire(){ // 사용가능 해지면 크리티컬 섹션에 들어간후 문을 잠금!
  while(!available) // Busy Waiting
    available = false;
}
release(){ // 사용가능 하게 해줌
  available = true;
}

문제점 : Busy waiting(spin lock) 으로 인해 효율이 떨어진다.

2. Semaphores

Wait 과 Signal을 이용하여 control 한다.
Semaphore는 Critical Section에 들어갈 수 있는 task의 수이다. 자원의 갯수가 여러개라고 생각하는 것이 편하다. 따라서 Critical Section에 상호 배타적으로 들어 갈 수 있는 것이다.
Semaphore = 1 이면 Mutex Lock 과 같은 방식으로 움직인다.
화장실(Critical Section)안에 칸(자원) n개 , 전광판에 n 표시

Semaphore s // Integer Value & Positive #

Busy Waiting 을 사용하는 Semaphore
wait(s){
  while(s <= 0){} // busy waiting
  s--
}
signal(s){
  s++
}
s 값이 양수여야지만 Critical Section에 들어가 작업을 수행 할 수 있음.

Busy waiting을 사용하는 구현은 Critical Section 은 있지만 사용하고자 하는 Task의 수가 적을 때 사용함.

Busy Waiting 을 사용하지 않는 Semaphore
// waiting queue를 사용
wait(s){
  s--;
  if(s < 0){ // s < 0 이면 s의 절댓값 만큼 waiting queue에서 Task 대기중
    // waiting queue에 task t 를 집어넣음
    block();
  }
}
signal(s){
  s++;
  if(s <= 0){ // waiting queue에서 대기중인 task 존재
    // waiting queue에서 task t 를 제거
    wakeup(t);
  }
}

Mutex Lock 과 Semaphore 의 차이!

Semaphore 는 Mutex Lock이 될 수 있지만 역은 성립하지 않는다.
Mutex Lock은 Lock을 갖고 있는 thread가 해제 가능한 반면, Semaphore는 외부에서도 해제 가능
Semaphore 는 프로세스 범위에서 소유 불가능 , Mutex는 소유 가능
Semaphore는 시스템 범위에 걸쳐져 있고 파일형태로 존재하는 반면, Mutex Lock은 프로세스 범위 내에 잇어서 종료시 자동으로 clean up 되어짐

Monitor

가장 발전된 기술
자바에서 모든 객체는 monitor을 가지고 있다.
JVM은 상호 배제를 위해 Monitor 방식을 사용한다.
Monitor는 공유자원, 프로시저로 크게 두가지로 구성된다.
Monitor는 한번에 하나의 스레드만 접근 가능하고 공유자원 접근은 프로시저가 대신 접근한다.
JAVA에서 synchronized 키워드가 사용된 객체는 공유 객체가 된다.
공유자원은 동기화된 메소드가 접근하는 공유 객체의 필드가 된다.
동기화된 메소드들은 프로시저가 된다.
스레드가 모니터에 접근하면, 스레드는 공유자원에 직접 접근할 수 없으며 무조건 프로시저를 통해 접근해야 한다.

스레드 하나가 withDraw()에 접근하면, withDraw()는 스레드 대신 account에 접근. Monitor에는 한 스레드만 접근 가능하므로, 스레드가 deposit() 프로시저를 사용하지 않아도 다른 스레드는 deposit() 프로시저에 접근할 수 없다

교착상태(Deadlock)

교착상태 발생의 필요 충분 조건

교착상태가 발생하기 위해서는 다음의 네 가지 조건이 충족되어야 하는데, 하나라도 충족되지 않으면 교착상태가 발생하지 않는다.

상호배제(Mutual Exclusion) : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.

점유와 대기(Hold and Wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

비선점(Non-preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.

원형 대기

[예방 기법 (Prevention)]

교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로, 교착상태 발생의 네 가지 조건중에서 어느 하나를 제거하는 방법이다. 자원 낭비가 가장 심한 기법이다.

상호 배제 부정 : 한 번에 여러개의 프로세스가 공유 자원을 사용할 수 있게 한다.

점유 및 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원을 요구한다.

비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.

원형 대기 부정 : 자원을 선형 순서로 분류하여 고유번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구한다.

[회피 기법 (Avoidance)]

교착상태가 발생할 가능성을 배제하지 않고, 교착상태가 발생하면 적절히 피해나가는 방법으로, 은행원 알고리즘(Banker's Algorithm) 이 사용된다.

은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법

각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며, 모든 프로세스가 완료될 수 있는 상태를 안전 상태(safe state)라고 하며, 교착상태가 발생할 수 있는 상태를 불안전 상태(unsafe state)라고 함

은행원 알고리즘을 적용하기 위해서는 자원의 양과 프로세스 수가 일정해야 함

은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장함

[발견 기법 (Detection)]

시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 기법이다. 발견 후엔 교착상태 회복(Recovery) 직업을 수행하므로 발견기법과 회복기법을 함께 쓴다. (Detection & Recovery)

[회복 기법 (Recovery)]

교착상태를 일으킨 프로세스를 종료하거나, 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미한다. 크게 프로세스 종료와 자원 선택으로 나뉜다.

프로세스 종료
프로세스 하나를 임의로 종료하여 교착상태를 해결하는 방법이다. 두 가지의 방법을 사용할 수 있다.

첫번째, 교착상태 프로세스를 모두 중지한다. 상당히 큰 비용이 들어가지만, 단순하다.
두번째, 교착상태가 제거될 때까지 한 프로세스씩 중지한다. 각 프로세스가 중지될 때마다 교착상태를 확인해야하기 때문에, 상당한 오버헤드를 유발한다.

자원 선점
교착상태가 깨질 때까지 프로세스로부터 자원을 계속적으로 선점해 다른 프로세스에게 주어야 한다. 따라서 다음 사항들을 꼭 고려해야 한다.

희생자 선택 : 어떤 자원과 프로세스가 선점될 것인가를 고민한다. 비용을 최소화 하기 위해 교착상태 프로세스가 점유하고 있는 자원의 수, 교착상태 프로세스가 지금까지 실행하는데 소요한 시간과 같은 변수를 고려하여 희생자를 선택한다.
롤백 : 만약 특정 프로세스 자원을 강제로 방출하고 선점했다면, 그 프로세스를 어떻게 처리할 것인지 고민해야 한다. 가장 안전한 방법은 프로세스를 중지하고 재시작하는 롤백이다.
기아 상태 : 계속해서 특정 프로세스의 자원을 강제로 방출시켜 선점을 시켜주면, 그 프로세스는 계속해서 희생자가 될 확률이 높아지고, 영원히 실행이 완료되지 못하는 기아상태에 빠질 수 있다. 따라서 프로세스에 롤백 횟수 제한을 두는 등, 프로세스가 한정된 시간에만 희생자로 선정된다는 것을 반드시 보장해야한다.

eunsiver

Let's study!

이전 포스트

프로세스 동기화, CAS 알고리즘, Volatile

다음 포스트

운영체제

운영체제

프로세스와 스레드

프로세스

프로세스에 할당되는 메모리 영역

Stack과 Heap 공간 접근 속도

공간 분할 이유?

프로세스 제어 블록(PCB)

프로세스 제어 블록(PCB)에 저장되는 정보

스레드

멀티 프로세스와 멀티 스레드

동시성

컨텍스트 스위칭 (Context-Switching)

Context

스레드와 프로세스 중 컨텍스트 스위칭이 빠른 것은 스레드

멀티 프로세스

크롬 브라우저 멀티 프로세스 구조

멀티 프로세스의 통신 방법(IPC)

멀티 프로세스 장점

멀티 프로세스의 단점

멀티 스레드

🌈멀티 스레드를 적용한 어플리케이션의 예시 (Multi-threaded applications example)

멀티 스레드의 장점

멀티 스레드의 단점

프로세스 스케줄링

프로세스 상태

스케줄링 큐

CPU 스케줄링

CPU 스케줄링 발생 상황

선점/비선점 스케줄링

스케줄링 알고리즘

FCFS (First-Come, First-Served) Scheduling

SJF (Shortest-Job-First) Scheduling

RR (Round-Robin) Scheduling

Priority Scheduling

MLFQ(Multi-Level Feedback Queue)

동기와 비동기의 차이

Sync & Async

Blocking & Non-blocking

프로세스 동기화

Critical Section(임계구역) 이란?

Ctritical Section Problem

Hardware Solution

Software Solution(Mutex Lock, Semaphores)

1. Mutex Lock (hardware-based)

2. Semaphores

Mutex Lock 과 Semaphore 의 차이!

Monitor

교착상태(Deadlock)

교착상태 발생의 필요 충분 조건

[예방 기법 (Prevention)]

[회피 기법 (Avoidance)]

[발견 기법 (Detection)]

[회복 기법 (Recovery)]

프로세스 동기화, CAS 알고리즘, Volatile

IO multiplexing

0개의 댓글

스레드와 프로세스 중 컨텍스트 스위칭이 빠른 것은 `스레드`