CS 스터디 1주차

HR·2023년 1월 18일
OS운영체제
0

CS

목록 보기
1/1

데드락

데드락의 정의

한국말로는 교착 상태라 한다.
위키 백과에 의하면, 아래와 같다.

교착 상태(膠着狀態, 영어: deadlock)란 
두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 
결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

결국에는 프로세스들이 서로 상대방이 가지고 있는 자원을 가지고 있어, 무한 대기에 빠진 상황을 말한다.

데드락의 발생 조건

데드락은 아래 4가지 조건을 만족하는 경우에 발생한다.

1) 상호배제(Mutual Exclusion)
하나의 프로세스만이 자원을 사용한다. Mutex라고도 불리며, 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 개념이다. 임계 구역(critical section)으로 불리는 영역을 통해 구현된다.

2) 점유대기(Hold And Wait)
프로세스는 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
다른 말로, 다른 프로세스를 기다릴 때 자원을 놓지 않는다.

3) 비선점(No Preemption)
프로세스가 어떤 자원의 사용을 끝낼 때 까지 OS등이 그 자원을 뺏을 수 없다.
프로세스가 자원을 스스로 반납하기 전까지는 해당 자원의 사용을 허용한다.

4) 순환대기(Circular Wait)
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
다른 말로, 서로의 자원을 기다리는 프로세스들 간에 사이클이 형성되어야 한다.

데드락 예방

위에서 언급한, 데드락의 4가지 조건 중 하나라도 발생하지 않도록 하면 데드락을 예방할 수 있다.

1) 자원의 공유
한 번에 여러 프로세스가 자원을 공유할 수 있도록 한다.
이는 Critical Section 문제를 일으킬 수 있으므로, 좋은 방법은 아니라고 할 수 있다.

2) 점유 대기 조건
프로세스가 어떠한 자원을 요청하기 위해서는, 현재 점유하고 있는 자원이 없어야 한다.

3) 우선 순위에 따른 정책
우선순위가 높은 프로세스가 해당 자원을 선점할 수 있도록 한다.
이 때에 스케줄링 알고리즘이 사용되는데,
우선순위가 높은 순서대로 처리하는 우선순위 알고리즘,
먼저 요청하는 순서대로 할당하는 FCFS(First-Come-First-Serve) 등이 있다.

4) 순환 방지
자원을 프로세스마다 할당 순서를 정해, 정해진 순서대로만 자원을 할당한다.

데드락 회피

안정 상태 (Safe state)
모든 프로세스들에게 데드락을 발생시키지 않으면서 자원을 모두 할당해 줄 수 있는 상태

안전 순서 (Safe sequence)
프로세스들에게 데드락을 발생시키지 않고 자원을 할당할 수 있는 순서

cf) banker's algorithm

세마포어, 뮤텍스, 모니터

위에서 언급한 자원의 동시 사용을 막기 위한 전략들, 즉 상호배제를 위한 동기화 기법이다.

뮤텍스와 모니터는 임계구역과 관련된 개념이다. 상호배제를 통해 임계구역에 접근하는 조건을 설정하는 방법이고, 세마포어는 전략에 따라 하나의 스레드 또는 여러개의 스레드가 임계 구역에 접근하게 할 수 있다.

뮤텍스

'임계 구역(Critical Section)'에 여러 스레드가 접근하는 것을 막는 것

Locking과 Unlocking을 사용한다. 한 스레드가 자원을 사용하기 위해서는, 먼저 사용한 스레드가 자원을 반납해야 소유권을 얻을 수 있다.

-> 들어갈 때 Lock을 하고, 나올 때 Unlock을 수행함.

세마포어

뮤텍스에서 Lock과 Unlock시에 사용하는 '키'의 개념이 세마포어이다.
wait와 signal을 통해 구현된다. 임계 영역으로 들어가기 전에 wait를 해제하면서 임계 영역으로 진입하고, 임계 영역을 빠져나오며 signal이 호출된다.

뮤텍스는 오로지 하나의 동기화에만 사용되고, 세마포어는 여러개가 가능하다.

모니터

세마포어는 비교적 저수준의 언어(ex. 어셈블리, C) 에 적합하다. 그에 반해, Java와 같은 고수준의 언어에서는 모니터가 활용된다.

자바에서는 모든 객체가 모니터가 될 수 있으며, 공유자원에는 최대 1개의 스레드만 진입이 가능하다.

모니터는 두 개의 queue로 이루어져 있는데, 각각 배타동기와 조건 동기의 역할을 한다.

배타 동기
뮤텍스와 비슷한 원리이다. 하나의 함수가 자원을 사용하고 있으면 다른 스레드는 대기해야 한다.
synchronization키워드를 사용하여 지정한다.

class Monitor {
	int value;
    
    synchronization void func() { //이 함수 외의 다른 스레드는 접근 불가능
    	...
    }
    
    synchronization void gunc() { //func 함수 이후에 실행
    	...
    }
    
    void hunc() { //공통 자원을 사용하지 않으므로 별개로 실행 가능
    	...
    }
}

조건 동기
진입 스레드 블록 -> 새로운 스레드 진입 가능해짐 -> 블록된 스레드 깨움 -> 현재 스레드가 나가면 진입 가능
wait, notify, notifyAll 메소드 사용

class Monitor {
	int using = false
    
    void acquire() {
      while(using) {
          wait();
      }
      using = true
    }
    
    void release() {
    	using = false
        notify();
    }
}

프로세스 vs 스레드

프로세스

위키백과

컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램

task와 같은 의미이다.

메모리에 올라와 실행되고 있는 프로그램의 인스턴스(독립적인 개체)

OS에게 시스템 자원을 할당받는 작업의 단위

PCB (Process Control Block)

  • PID
  • 프로세스 상태
    • new: 생성, Ready queue에 올라가 ready 상태가 됨
    • ready: 프로세스가 cpu로부터 메모리 공간을 할당받길 기다리는 상태
    • running: 실행중. interrupt가 발생하면 ready 상태로 변함. 실행이 끝나면 종료되고 terminate 상태로 변함. I/O나 이벤트가 발생하면 waiting으로 변함.
    • waiting(blocked): event 기다리는중. waiting이 끝나면 ready 상태로 변함
    • terminated : 실행 완료
  • 프로그램 카운터
  • 스케줄러: 스케줄링에는 Queue들을 사용.
    • Job queue : 모든 프로세스 집합
    • Ready queue : 실행 대기중인 프로세스 집합
    • Device queue : I/O device 처리 기다리는 프로세스 집합
    • Long-term 스케줄러(장기 스케줄러, job scheduler) : 시작 프로세스중 어떤 애들을 ready queue로 보낼지 결정
    • Short-term 스케줄러(단기 스케줄러, CPU scheduler) : ready queue에 있는 프로세서 중 어떤 것을 다음에 running 할 것인가?
    • Medium-term 스케줄러(중기 스케줄러, Swapper): 최대한 많은 프로세스들에게 메모리를 할당해 시스템 성능 저하 조절
  • 권한
  • 계층 정보 (부모, 자식 프로세스)
    • fork() : pid 이외의 모든 내용을 그대로 복제해 생성, 서로 다른 주소 공간
    • exec() : 하나의 프로세스를 완전히 새로운 프로세스로 덮어 씀
    • wait() : 자식 종료를 기다리며 부모 프로세스가 blocking
    • exit() : 프로세스 종료
  • 프로세스 문맥(context)

process context

CPU 수행 상태를 나타냄
프로세스가 어떤 상태에서 수행되고 있는지 정확히 나타내기 위해 필요

  • Program Counter
  • Register
  • Memory
    • 코드 : 컴파일된 코드
    • 데이터 : 변수, 초기화된 데이터
    • 스택 : 함수 호출 등 임ㅅ 데이터
    • 힙 : 동적 할당 ex. malloc()
def func(a, b):
	print(a+b)
    
c = 0
c = func(1, 2)
print(c)

스레드

프로세스 하나만 사용하기에는 메모리의 낭비가 발생한다.
프로세스 내부, 실행 흐름의 단위
서로 메모리를 공유한다.
하나의 프로세스는 최소 하나의 스레드를 가진다.

스레드가 독립적으로 가진 부분

  • Program Counter
  • Register

다른 스레드와 공유하는 부분

  • 코드
  • 데이터
  • OS 자원

멀티 스레드의 장점과 단점

멀티 프로세스

하나의 프로그램을 여러 개의 프로세스로 구성, 각 프로세스가 하나의 작업을 처리

장점
하나가 뻗어도 그 친구만 죽고 다른 영역으로 확산되지 않음

단점
Context switch 비용이 매우 큼

멀티 스레드

하나의 스레드가 하나의 작업을 처리
웹 서버가 대표적인 멀티 스레드 응용프로그램

장점
Context switch, 메모리 자원 절약 가능
응답 시간 빠름

단점
스레드 하나가 뻗으면 모든 프로세스가 죽을 수 있다.
자원을 공유하기 때문에 교착 상태 (Deadlock)이 발생할 수 있다. - 동기화 문제.

멀티 스레드 사용시 주의할 점

1) 상호 배제

  • critical section

2) 메모리 일관성

race condition

유저 레벨 스레드와 커널 수준 스레드

둘 다 멀티 스레드 기반한 이야기이다.

커널 수준 스레드

CPU에서 I/O 요청으로 프로세스가 block되고, 다른 프로세스로 변경되는 것을 context switching이라고 한다.

원래는 컨텍스트 스위칭이 자주 일어나면 성능이 안좋아지는데, 커널 수준에서는 특정 스레드가 block 되어도 다른 스레드들이 독립적으로 일을 할 수 있다.

유저 레벨 스레드

실제 물리적으로 커널 밖에 있는 것은 아니다. 실제로는 커널 내부에 있지만 통제권만 커널에게 없는 것이다.

I/O interrupt가 발생하면 유저 레벨 스레드로 변화해, 응답을 기다린다. 유저 레벨로 진입한 스레드의 응답이 오면, 커널 모드로 다시 변환된다.

CPU 스케줄러(FCFS, SJF, SRT, Priority scheduling, RR)

여러 개의 프로세스들이 대기하는 시간을 최소화하고, 자원을 효율적으로 사용하기 위해 존재한다.
기본적인 역할은 다음에 실행할 프로세스를 선택하는 일이다.

선점 & 비선점 스케줄링

스케줄링은 다음과 같은 경우에 일어난다.

  • Running -> waiting (I/O 요청, wait()을 통한 자식프로세스의 종료)
  • Running -> terminate (부모 프로세스 종료)
  • Running -> Ready (인터럽트)
  • Waiting -> Ready (I/O 완료)

비선점
CPU를 자율적으로 반납하는 방식

  • Running -> waiting
  • Running -> terminate

선점
우선순위에 따라 CPU를 선점
OS가 프로세스에게 CPU를 할당 및 회수, 스케줄링 알고리즘에 따름

  • Running -> Ready
  • Waiting -> Ready

CPU 스케줄링의 목적

  • starvation 방지
  • fairness : 공평하게 할당
  • balance : 모두가 바쁘게

FCFS (First-Come-First-Serve) - 비선점

먼저 요청하는 프로세스에게 CPU를 할당

  • 알고리즘 효율이 매우 낮음

SJF (Shortest Job First) - 비선점

사용 시간(burst time)이 가장 짧은 프로세스부터 CPU 할당

  • 사용 시간이 긴 프로세스는 오래 기다려야 하므로 starvation이 발생할 가능성 있음

SRT (Shortest Remaining Time) - 선점

남은 시간이 최소인 프로세스부터 CPU 할당
진행중인 프로세스가 있어도 sleep 시키고 남은 시간이 짧은 프로세스에게 먼저 할당

RR (Round Robin) - 선점

정해진 시간 (time slice)만큼만 프로세스를 실행
정해진 시간 만큼 실행하고 나면 스케줄링 큐의 맨 끝으로 이동

  • 정해진 시간, time slice의 값이 너무 크다면 FCFS와 비슷해진다.
  • time slice의 값이 너무 작다면 context switch의 비용이 매우 커진다.

Priority Scheduling - 선점 & 비선점

우선순위에 따라 CPU 할당
우선순위는 경우에 따라 달라질 수 있다.
만약 모두 우선순위가 같으면, FCFS와 동일

동기와 비동기

동기와 비동기는 함수의 리턴 값을 기다리는지 여부의 차이가 있다.

동기 (Synchronous)

특정 코드의 연산을 기다린 이후, 이후의 코드를 실행한다.

function A() {
  var result = syncB();
  
  /* do something */ => syncB 함수가 리턴된 뒤 실행된다.
}

비동기 (Asynchronous)

특정 코드의 연산을 기다리지 않고, 이후의 코드를 먼저 실행한다.

function A() {
  var data;
  /* get data with ajax */
  
  return data;
}

console.log(A()); //undefined

Blocking & non-blocking?

동기, 비동기 개념과 연관은 없다. 조합해서 사용되는 것일 뿐.

동기&비동기는 프로세스의 실행 순서와 관련된 개념이고,
블로킹과 논블로킹은 프로세스의 유휴 상태와 관련된 개념이다.

Blocking
A함수가 B 함수를 호출하면, 제어권이 B에게 넘어간다.

제어권을 잃은 A는 함수 실행을 중단하고,
제어권을 얻은 B는 함수를 실행한다.

B의 실행이 끝나면 A에게 제어권을 돌려준다.

cf) 제어권?
함수를 실행할 권리. 제어권을 가진 함수는 코드를 실행한 후 리턴한다.

Non-blocking
A함수가 B함수를 호출해도, 제어권은 넘겨주지 않는다.

A함수는 제어권을 가지고 있으므로, B함수를 호출한 뒤에도 계속 실행한다.

동기&비동기 + 블로킹&논블로킹

1) 동기 + 블로킹
1. A는 B의 리턴값을 기다린다. 동기
2. 제어권을 B에게 넘겨주고, B가 실행을 완료한 뒤 리턴과 제어권을 돌려줄 때 까지 기다린다. 블로킹

2) 동기 + 논블로킹
1. A는 B의 리턴을 기다린다. 동기
2. 그런데 제어권을 주지 않고, 자신의 코드를 계속 실행한다. 논블로킹
3. 하지만 B의 리턴 값이 필요하므로, 자신의 코드를 실행하면서 B의 실행이 완료되었는지 확인만 한다.

3) 비동기 + 논블로킹
1. A함수가 B함수를 호출한다.
2. 이 때, 제어권은 B함수에 주지 않고 자신은 계속 실행한다. 논블로킹
3. B함수를 호출할 때 콜백함수를 전달한다. B함수는 작업이 끝나면 A함수가 준 콜백함수를 실행한다. 비동기

4) 비동기 + 블로킹
1. A는 B의 리턴에 관심이 없지만, 콜백 함수를 보낸다. 비동기
2. 관심은 없지만 제어권은 B에게 넘겨준다. 블로킹
3. 따라서 관심없는 B가 끝날 때까지 기다려야 한다.

이 경우는 동기+블로킹과 비슷하기 때문에 거의 사용되지 않는다.

profile
HR
이전 포스트

운영체제에 대해 알아보자

0개의 댓글