Sunny's Tech Blog

사전지식

1) 메모리란?

  -  프로그램과 프로그램 수행에 필요한 데이터 및 코드를 저장하는 장치
  - 메모리는 크게 내부 기억장치인 주기억장치와 외부 기억장치인 보조 기억장치로 분류됨
    ▷ DRAM(RAM, DDR4) 등의 메모리, CPU 안에 있는 레지스터(register)와 캐쉬(cache memory) 등이 주기억장치
    ▷ SSD, HDD 등이 보조 기억장치

2) 가상 메모리란?

  - 메모리가 실제 메모리보다 많아 보이게 하는 기술
  - 어떤 프로세스가 실행될때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행 가능함
  - 프로그램 실행에 필요한 일부분만 메모리에 올라가며, 나머지는 디스크에 남음 (즉, 디스크가 RAM의 보조 기억장치처럼 작동 → 가상메모리의 핵심은 보조 기억장치)  
  - 가상 메모리 구현을 위해서는 컴퓨터가 특수 메모리 관리 하드웨어를 갖춰야함 = MMU(Memory Management Unit)
  - MMU는 가상주소를 물리주소로 변환 & 메모리를 보호하는 기능을 수행

3) (가상) 메모리 관리 기법

  - 할당정책, 호출정책, 배치정책, 교체정책 이 존재
  ≫ 페이징 기법과 세그먼트 기법은 할당정책에 해당!

4) 메모리 단편화란?

  - 메모리의 빈 공간이 여러 조각으로 나뉘는 현상
  - 컴퓨터에서 어떤 프로그램을 실행할 때, 메모리의 공간을 연속적인 형태로 할당하여 사용하게 됨
  - 이렇게 프로그램이 메모리에 할당되고, 해제되고, 다시 새로운 프로그램이 할당되고를 반복하다보면 메모리 공간이 조각조각 나뉘게 되어 실제로는 사용가능한 메모리가 충분히 존재하지만, 할당이 불가능한 상태가 발생함 > 이를 메모리 단편화 문제라고 함

  - 내부단편화, 외부단편화 존재
    ▷ 내부단편화 : 메모리를 할당할때, 프로세스가 필요한 보다 더 큰 메모리가 할당되어 프로세스에서 사용하는 메모리 공간이 낭비되는 상황
    ▷ 외부단편화 : 메모리가 할당되고 해제되는 작업이 반복적으로 발생할때, 중간중간 사용하지 않는 작은 메모리가 생김 / 총 메모리공간은 충분하지만, 실제로는 할당할 수 없는 상황을 외부 단편화라고 함

참조 : https://m.blog.naver.com/rbdi3222/220623825770

→ 이러한 메모리 단편화 문제 해결 방법으로 페이징과 세그멘테이션이 있음
  

페이징 기법

- 고정 분할 기법

- 프로세스를 일정한 크기의 페이지로 분할해서 메모리에 적재하는 방식

• 페이지(Page) : 고정 사이즈의 가상 메모리 내 프로세스 조각
• 프레임(Frame) : 페이지 크기와 같은 주 기억 장치의 메모리 조각

- 모든 프로세스는 하나의 페이지 테이블을 가지고 있음

- 페이지 테이블에는 각 페이지 번호와 해당 페이지가 할당된 프레임의 시작 물리 주소를 저장

- CPU는 논리 주소로 프로그램이 설정한대로 연속적인 주소값으로 명령을 내리고, 이는 메모리로 가기전에 각 페이지의 실제 메모리 주소가 저장되어 있는 테이블에서 물리 주소로 변경

- 고정 크기로 분할된 가상 메모리의 각 개별 페이지는 순서에 상관없이 물리 메모리에 있는 프레임에 매핑되어 저장

페이징의 장단점

장점

외부 단편화 해결

단점

내부 단편화 문제가 발생 가능

세그멘테이션 기법

- 가변 분할 기법

- 프로세스의 주소 공간을 동적으로 설정되는 가변 크기의 블록들로 분할

• 세그먼트(Segment) : 가상 메모리를 서로 크기가 다른 논리적 단위로 분할한 것

- 세그멘테이션은 프로세스를 물리적 단위인 페이지가 아닌 논리적 단위인 세그먼트로 분할해서 메모리에 적재하는 방식

- 세그먼트 테이블은 세그먼트 번호와 시작 주소(base), 세그먼트 크기(limit)를 저장

- 가상 주소의 세그먼트 번호를 이용하여 해당 세그먼트가 적재된 물리 메모리 블록의 시작 주소를 얻음

- CPU에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해서 해당 프로세스를 강제로 종료

세그멘테이션의 장단점

장점

내부 단편화 해결

단점

외부 단편화 문제가 발생 가능

→ 이러한 두가지 방법을 혼합한 Paging / Segmentation 기법 활용 가능

파일관리는 Segment 단위로 하고, 메모리에 올라오는 프로그램의 조각은 Page 단위로 관리

페이징 또는 세그멘테이션을 사용하는 이유

메모리 단편화 문제를 해결하기 위해

최초 적합, 최적 적합, 압축 등의 방식을 통해서도 단편화를 해결할 수 있지만, 메모리 계산의 비용이 적은 페이징 또는 세그멘테이션을 주로 사용

사전지식

IPC 란 Inter Process Communication의 약자로, 직역하면 프로세스간의 통신을 의미한다.
프로세스간의 통신이 가능하도록 커널에서는 IPC 통신 설비를 제공해주는데, IPC 설비 종류에도 여러가지가 있고 (PIPE, Message Queue, Socket ...) 이는 필요에 따라 선택해서 사용한다.

이러한 IPC 통신에서 프로세스 간의 데이터를 동기화하고 보호하기 위해 운영체제에서 제공하는 동기화용 커널객체가 있다.

즉, 데이터를 한번에 하나의 프로세스만 접근할 수 있도록 제한을 두는 일종의 프로세스 동기화 메커니즘이 존재한다.

이걸 다른 말로 한번더 설명한다면…
운영체제 상에는 '임계구역' 이라는 것이 존재한다.

임계구역이란, 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유자원의 코드 영역이다.
이렇게 임계 구역에 여러 프로세스 및 스레드가 함부로 접근할 수 없도록 관리를 잘 해줘야 하는데, 이를 위해 사용하는 방식에 대표적으로 세마포어(Semaphore)와 뮤텍스(Mutex)가 있다

세마포어 (Semaphore)

멀티 프로그래밍 환경에서 공유된 자원에 대한 접근을 제한하는 방법

뮤텍스 (Mutex)

공유 불가능한 자원의 동시 사용을 피하기 위해 사용하는 방법

→ 접근 제어를 위해 lock과 unlock 사용

- lock: 현재 임계 구역에 들어갈 권한을 얻어옴
- unlock: 현재 임계 구역을 모두 사용했음을 알림

참조) 세마포어와 뮤텍스에 대한 개념을 알기 쉽게 화장실에 비유하여 설명해준 블로그

https://worthpreading.tistory.com/90

→ 세마포어와 뮤텍스 둘다 공유자원에 여러 프로세스가 동시에 접근하는 것을 막는다.

세마포어 (Semaphore) vs 뮤텍스 (Mutex)

1) 세마포어

  - 현재 공유 자원의 상태를 나타내는 카운터 변수를 사용
  - 카운터 변수는 운영체제 혹은 커널에 값으로 저장

  - 각 프로세스는 해당 카운터 변수를 확인하고 변경 가능
  - 카운터 변수의 값은 1보다 더 큰 숫자도 가질 수 있음
  - 해당 변수값이 공유 자원에 접근할 수 있는 프로세스 개수의 임계치
  - 이를 조정해 접근 가능한 프로세스 개수 통제

2) 뮤텍스
  - 이진 세마포어라고도 불림 (상태가 0,1)
  - 1개의 프로세스 혹은 스레드만이 공유 자원에 접근 가능함
  - lock과 unlock
    ▷ 뮤텍스는 자원을 점유하고 있는 프로세스가 lock을 할 수 있는 권한을 가져서, 자원을 점유하기 시작할때 lock을 걸어버림
    ▷ lock을 가지고 있는 변수만이 unlock을 할 수있고, 다른 프로세스들은 unlock 상태가 될때까지 기다렸다가 나중에 해당 공유 자원에 접근 가능
    ▷ 반면 세마포어는 현재 공유 자원을 사용중인 대상뿐만 아니라 다른 프로세스 및 스레드도 unlock이 가능함

정리하자면...

세마포어는 카운터 변수값만큼 공유 자원에 해당 프로세스(또는 스레드)가 접근 가능

뮤텍스는 오직 하나의 프로세스(또는 스레드)가 접근 가능

세마포어는 현재 수행중인 프로세스가 아닌 다른 프로세스가 unlock이 가능

뮤텍스는 lock을 획득한 프로세스가 반드시 unlock을 해야 다른 프로세스가 접근 가능

CPU 스케줄링 (=프로세스 스케줄링)

프로세스 스케줄링이란, CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업

스케줄링의 목표

- 처리율, CPU 이용률↑

- 오버헤드, 응답시간, 반환시간, 대기시간 ↓

*오버헤드란?

어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 의미

ex. A라는 작업을 실행하는 데에 10초가 소요되는데, 안전성을 고려하여 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초

1. 프로세스 상태

- 생성(Create) : 사용자에 의해 프로세스가 생성된 상태

- 준비(Ready) : CPU를 할당받을 수 있는 상태

   → 준비 리스트가 존재하며, 높은 우선순위를 가진 프로세스 순서대로 CPU를 할당받음

- 실행(Running) : 프로세스가 CPU를 할당받아 동작 중인 상태

- 대기(Waiting) : 프로세스 실행 중 입출력 처리 등으로 인해 CPU를 양도하고 처리가 완료될 때까지 대기 리스트에서 기다리는 상태

- 완료(Complete) : 프로세스가 CPU를 할당받아 주어진 시간 내에 완전히 수행을 종료한 상태

2. 프로세스 상태 전이

- 프로세스의 상태가 준비, 실행 및 대기 상태 등으로 변하는 활동을 의미

- 활동 상태란, 프로세스가 기억장치를 할당받은 상태

- 지연 상태란, 프로세스가 기억장치를 할당받지 못한 상태

* 디스패치 (Dispatch) : 준비 상태 리스트에 있는 프로세스들 중 실행될 프로세스를 선정하여 CPU를 할당

* 타이머 런 아웃 (Timer run out = Timeout) : CPU를 할당받은 프로세스는 지정된 시간이 초과되면 스케줄러에 의해 PCB에 저장, CPU 반납 후 다시 준비 상태로 전이

* 블록 (Block) : 실행 상태에 있는 프로세스가 지정된 시간을 초과하기 전에 입출력이나 기타 사건 등이 발생하면 CPU를 스스로 반납하고, 입출력이 완료될 때까지 대기 상태로 전이

* 웨이크 업 (Wake-up) : 어느 순간 입출력이 종료되면, 대기 상태에서 준비 상태로 전이

* Swap-in : 프로세스에게 다시 기억장치가 할당될 경우

* Swap-out : 프로세스가 기억장치를 잃은 경우

3. 프로세스 스케줄링 주요 용어

- 시간 할당량 : 한 프로세스가 프로세서를 독점하는 것을 방지하기 위해 서비스되는 시간 할당량

- 서비스 시간 : 프로세스가 결과를 산출하기까지 소요되는 시간

- 응답시간(반환시간) : 프로세스들이 입력되어 수행하고 결과를 산출하기까지 소요되는 시간

- 대기 시간 : 프로세스가 자원의 할당을 대기하는 시간

 응답시간 = 대기시간 + 수행시간(=서비스 시간)

4. 프로세스 스케줄링 유형

4-1) 선점형 스케줄링

- 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식

- 장점

비교적 빠른 응답

대화식 시분할 시스템에 적합

*시분할 시스템이란? 여러 사용자가 각자의 단말장치를 통하여 동시에 운영체제와 대화하면서 각자의 프로그램을 실행하는 듯한 느낌을 받는 방식

- 단점

높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래

- 종류

1) 라운드 로빈 (Round Robin)

- 모든 프로세스는 같은 크기의 CPU 시간을 할당받음(시간 할당량)

- 프로세스가 할당된 시간 내에 처리 완료를 못하면 준비 리스트의 가장 뒤로 보내지고, CPU는 대기 중인 다음 프로세스로 넘어감

2) SRT (Shortest Remaining Time First)

- 가장 짧은 시간이 소요되는 프로세스를 가장 먼저 수행

- 남은 처리시간이 더 짧다고 판단되는 프로세스가 준비 리스트에 생기면, 언제라도 프로세스가 선점됨

3) 다단계 큐 (MLQ: Multi Level Queue)

- 어떤 프로세스냐에 따라서 여러 종류의 그룹으로 분류하고, 여러개의 큐에 다양한 알고리즘을 적용하는 스케줄링 방식

   → 운영체제는 프로세스를 분류할때 보통 사용자와 상호작용하는 앞단의 프로세스(ex.구글검색)를 중요하게 여기고, 백그라운드에서 돌아가는 프로세스들 (ex.압축풀기, 영화다운로드)은 상대적으로 덜 중요하다고 판단

- 각각의 큐는 자신의 스케줄링 알고리즘(RR, FCFS 등)을 수행

4) 다단계 피드백 큐 (MFQ: Multi Level Feedback Queue)

- 다단계 큐와 비슷하지만, 프로세스들이 큐를 이동할 수 있음

- 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동하고 마지막 단계는 라운드 로빈 방식을 적용

4-2) 비선점형 스케줄링

- 하나의 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식

- 장점

응답시간 예상 용이

모든 프로세스에 대한 요구를 공정하게 처리

- 단점

짧은 작업을 수행하는 프로세스가 긴 작업 종료시까지 대기해야 함

- 종류

1) 우선순위 (Priority)

- 프로세스별로 우선순위가 주어지고, 해당 우선순위에 따라 CPU를 할당함

- 동일 순위는 FCFS(FIFO)로 처리

2) 기한부 (Deadline)

- 작업들이 명시된 시간이나 기한 내에 완료되도록 계획

3) FCFS (First Come First Service) = FIFO (FIRST IN FIRST OUT)

- 프로세스가 대기 큐에 도착한 순서에 따라 CPU를 할당받음 (도착 순서대로 처리)

4) HRN (High Resposne Ratio Next)

- 대기 중인 프로세스 중 현재 응답률(Response Ratio)이 가장 높은 것을 선택 (우선순위를 계산하여 선택)

- HRN의 우선순위 : (대기시간 + 서비스시간) / 서비스시간

5) SJF (Shortest Job First)

- 프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료시까지 자원을 점유

* SRT vs SJF

SRT는 다른 프로세스가 실행 중에, 서비스 시간이 짧은 프로세스가 생기면 언제든지 자원을 점유할 수 있음

반면 SJF는 한번 서비스 시간이 가장 짧은 프로세스가 자원을 점유하게 되면, 해당 작업이 끝날 때까지 계속 자원을 점유