[인프런 워밍업 클럽 CS 2기] 2주차 발자국 - 운영체제

5. SJF (Shortest Job First)

Burst Time(연산 시간)이 짧은 프로세스를 먼저 실행하여 평균 대기 시간을 줄이는 알고리즘
Burst Time이 짧은 프로세스를 우선적으로 실행시, 상대적으로 Burst Time이 긴 작업은 실행될 기회를 얻지 못하고 계속 대기할 수 있게 되며 프로세스의 종료시간을 예측하기 어려울 수도 있다. 이러한 이유로 SJF 알고리즘은 실제로 사용하지 않음

6. RR (Round Robin)

한 프로세스에게 일정시간을 할당하고 할당된 시간이 종료되면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당한다. 강제로 CPU를 뺏긴 프로세스는 큐의 맨 뒷부분으로 밀려난다.
FIFO 알고리즘과 RR 알고리즘의 평균 대기시간이 비슷한 경우 오버헤드가 큰 RR 알고리즘이 비효율 적이다.
- RR 알고리즘은 컨텍스트 스위칭 발생이 있기 때문
RR 알고리즘의 성능은 타임 슬라이스의 값에 따라 달라짐

타임 슬라이스/타임 퀀텀

RR 알고리즘에서 프로세스들에게 부여되는 일정 시간
타임슬라이스가 크게 설정된 경우
- FIFO 알고리즘과 다를바가 없기 때문에 비효율적
타임슬라이스가 작게 설정된 경우 오버헤드가 너무 커진다.
- 오버헤드가 커지는 상황
  → 컨텍스트 스위칭이 자주 발생하여 타임 슬라이스에서 실행되는 프로세스의 처리량 보다 컨텍스트 스위칭을 처리하는 양이 훨씬 커짐

최적의 타임 슬라이스를 결정하는 방법

사용자가 느끼기에 타임슬라이스가 너무 크지 않아야 함
프로세스가 동시에 실행되는 것처럼 느껴저야 함
오버헤드가 너무 크지 않아야 함

7. MLFQ(Multi Level Feedback Queue)

오늘날 쓰이는 주류 알고리즘이며, RR의 업그레이드 된 알고리즘
CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임슬라이스를 선택한다.
CPU Bound Process 에게는 타임 슬라이스를 크게 주며 우선 순위가 낮은 큐에 배치한다.
I/O Bound Process 에게는 타임 슬라이스를 작게 주며 우선 순위가 높은 큐에 배치한다.
CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적은거니 I/O Bound Process 일 확률이 높다.
CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU 사용이 많은 것이니 CPU Bound Process일 확률이 높다.
큐의 우선순위 중 우선순위가 높으면 타임슬라이스가 적고 우선순위가 낮을수록 타임 슬라이스 크기가 커진다.
- 어떤 프로세스가 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏긴다면 해당 프로세스는 원래 있던 큐보다 우선순위가 더 낮은 큐로 이동하게 되고 타임 슬라이스가 조금 더 커진다.
  → 다음 실행시에도 타임 슬라이스가 부족하면 다음엔 우선순위가 더 낮은 큐로 이동하게 되어 더 큰 타임 슬라이스를 할당받게 된다.
- 우선순위가 낮아질 수록 타임슬라이스를 무한초로 할당 받게 되어 FIFO 처럼 연속적으로 작업을 마칠 수 있게 됩니다.

[ Section 4. 프로세스 동기화 ]

1. 프로세스 간 통신

프로세스간 통신의 종류

1) 파일과 파이프를 이용한 통신

파일을 이용한 통신
- 하나의 파일을 여러 프로세스가 같이 읽고 쓰는 방식
파이프를 이용한 통신
- 운영체제가 구축한 파이프를 이용하여 프로세스가 통신하는 방식

2) 하나의 프로세스 내부에서 쓰레드를 이용한 통신

하나의 프로세스 내부에 존재하는 여러 쓰레드는 스택을 제외한 코드, 데이터, 힙 영역을 공유하고 스택만 자신의 것을 가지고 있다.
데이터 영역의 전역 변수나, 힙 영역을 이용하여 쓰레드 간 통신이 가능하다.

3) 네트워크를 이용한 통신

운영체제가 제공하는 소켓 통신
다른 컴퓨터에 존재하는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신

2. 공유자원과 임계구역

공유자원이란?

프로세스 통신시 공통으로 이용하는 변수나 파일

프로세스의 접근 순서에 따라 결과가 달라질 수 있다.

동기화 문제

프로세스 통신시 공유자원의 연산 결과를 예측 할 수 없고 어떤 프로세스가 먼저 실행될지 예측 할 수 없는 문제

임계구역(Critical Section이란?

여러 프로세스가 동시에 사용하면 안되는 영역을 정의한 구역

경쟁조건(Race Condition)

공유자원을 서로 사용하기 위해 경쟁하는 것

상호 배제(Mutual Exclusion)

임계구역 문제를 해결하기 위해 필요한 매커니즘

상호 배제의 요구 사항

임계 영역엔 동시에 하나의 프로세스만 접근한다.
여러 요청에도 하나의 프로세스의 접근만 허용한다.
임계구역에 들어간 프로세스는 빠르게 나와야 한다.

3. 세마포어

상호배제의 매커니즘 중 하나이다.

세마포어는 실제로 정수형 변수이다.
세마포어를 사용하면 공유자원에 여러 프로세스가 동시에 접근하지 못하기 때문에 동기화 문제가 발생하지 않는다.
- wait() 함수와 signal() 함수 사용
세마포어는 공유 자원의 개수만큼 가질 수 있다.

세마포어 사용의 단점

wait() 함수와 signal() 함수 사용 순서가 꼬일 경우 세마포어를 잘못 사용할 가능성이 있다.

4. 모니터

세마포어의 단점을 해결한 상호배제 매커니즘
운영체제가 처리하는 것이 아니라 프로그래밍 언어 차원에서 지원하는 방법
ex.) 자바에서 synchronized키워드가 붙은 함수들은 여러 프로세스에서 동시에 실행할 수 없다.
모니터가 완벽하게 구현된 경우 프로그래머는 세마포어 처럼 wait() 함수와 signal() 함수를 임계 영역에 감싸지 않아도 돼어 편리하고 안전하게 코드를 작성할 수 있다.

[ Section 5. 데드락 ]

1. 데드락이란? (feat. 식사하는 철학자)

교착상태(데드락)

여러 프로세스가 서로 작업이 끝나기를 기다리다 아무도 작업을 진행하지 못하는 상태

교착상태가 발생하는 이유는 공유자원 때문이며, 어떤 자원을 여러개의 프로세스가 공유하지 않는 경우 교착상태는 발생하지 않는다.

교착상태의 필요조건

1. 상호배제

어떤 프로세스가 한 리소스를 점유 했다면, 해당 리소스는 다른 프로세스에게 공유가 되면 안된다.

2) 비선점

프로세스 A가 리소스를 점유하고 있을 때, 다른 프로세스는 해당 리소스를 빼앗을 수 없다.

3) 점유와 대기

어떤 프로세스에서 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 한다.

4) 원형 대기

점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있어야 한다.

2. 데드락 해결 (feat. 은행원 알고리즘)

교착상태 해결방법

교착상태 회피(Deadlock avoidance)

프로세스에게 교착상태가 발생하지 않는 수준의 자원을 할당
전체 자원의 수와 할당된 자원의 수를 기준으로 안정 상태(Safe state)와 불안정 상태(Unsafe state)로 나눈다.
운영체제는 안정 상태를 유지하려 노력하며, 불안정 상태에 빠지면 교착상태에 빠질 확률이 높아진다.

은행원 알고리즘(Banker’s algorithm)

은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황(안전상태)인지 확인하고 빌려준다.

운영체제에서 은행원 알고리즘 구현

운영체제는 자기가 가지고 있는 시스템의 총 자원을 파악한다.
프로세스는 자기가 필요한 자원의 최대 숫자(최대 요구 자원)를 운영체제에게 알려준다.

안정 상태

불안정 상태

순환구조가 발생한 그래프 → 교착상태 발생

교착상태 검출 방법

(1) 가벼운 교착 상태 검출

타이머를 이용하여 프로세스가 동작하지 않는 경우 교착상태에 빠진것으로 간주하고 교착상태를 해결한다.
마지막으로 저장했던 체크포인트로 롤백하여 교착상태를 해결한다.

(2) 무거운 교착 상태 검출

자원 할당 그래프를 이용하여 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생하면 해결한다.
교착상태를 검출한 경우 교착상태를 일으킨 프로세스를 강제로 종료하고, 다시 실행 시킬때 체크포인트로 롤백을 시킨다.
이 방식은 운영체제가 지속적으로 ‘자원 할당 그래프’를 유지, 검사 해야 하기 때문에 오버헤드가 발생한다.
가벼운 교착 상태 검출방식 보다 억울하게 종료되는 프로세스는 발생하지 않는다.

[ Section 6. 쉬어가기 ]

1. 컴파일과 프로세스

작성한 프로그램 코드가 프로세스가 되고 메모리에 할당되는 전반적인 과정

프로그래밍 언어

컴파일 언어
- 개발자가 작성한 코드를 컴파일 과정을 거쳐 실행 가능한 기계어로 변환
- 컴파일 과정에서 문법 오류를 잡아낼 수 있다.
- C, C++, C# 등
인터프리터 언어
- 개발자가 작성한 코드를 한줄씩 해석하며 실행하는 언어
- 컴파일 과정이 없어 실행시 오류가 발생 할 수 있고, 속도도 컴파일 언어와 비교하면 느리다.
- JS, Python, Ruby 등

프로세스의 구조

Code 영역
- 실행해야 될 코드가 들어가는 영역
Data 영역
- 전역 변수나 배열이 들어가는 영역
Stack 영역, Heap 영역 : 프로세스가 실행될 때 할당되는 메모리
- Stack 영역
  - 지역변수와 함수 관련 값들이 들어가는 영역
- Heap 영역
  - 실행 중 메모리 공간을 할당할 수 있는 유동적인 공간

컴파일 언어로 작성된 파일이 프로세스가 되는 과정

코드 작성
컴파일러로 작성한 코드를 컴파일
컴파일 과정을 거쳐 실행 파일이 생성된다.
사용자가 프로그램을 실행시키면 운영체제가 프로세스를 만든다.
운영체제는 실행파일에 있는 코드 영역과 데이터 영역을 가져와 프로세스의 코드 영역과 데이터 영역에 넣어주고 빈 상태의 스택과 힙을 할당한다.
PCB를 만들어 관리가 가능하도록 하고, 프로그램 카운터(실행할 명령어의 주소)를 생성한 프로세스의 코드 영역의 첫번째 주소로 설정한다.
운영체제 CPU 스케줄링에 따라 프로세스가 실행되다 작업을 마친다.

[ Section 7. 메모리 ]
1. 메모리 종류
컴퓨터의 여러 종류 메모리
레지스터
- CPU에 존재하며 가장 빠른 기억 장소
- 컴퓨터의 전원이 꺼지면 데이터가 사라진다. = 휘발성 메모리
- 32bit CPU, 64bit CPU → 32bit, 64bit는 레지스터의 크기를 말한다.
- CPU는 연산시 메인메모리(RAM) 에 있는 값을 레지스터로 가져와 연산하고 다시 메인메모리(RAM)에 저장한다.
- 메인메모리의 값을 레지스터로 옮기려면 오래 걸리기 때문에 필요할 것 같은 데이터를 미리 캐시에 저장한다.
메인메모리
- 운영체제와 프로세스가 올라가는 공간
- 전원이 공급되지 않으면 데이터가 지워진다. = 휘발성 메모리
- 하드디스크나 SSD보다 속도는 빠르지만 가격이 비쌈 → 데이터 저장 X, 실행중인 프로그램만 올린다.
보조저장장치(SSD, 하드디스크)
가격이 저렴하고 전원이 공급되지 않아도 데이터가 지워지지 않는 비 휘발성 메모리
2. 메모리와 주소
운영체제는 메모리(메인 메모리, RAM) 관리를 위해 1바이트(8bit) 크기로 구역을 나누고 숫자를 매긴다. 이 숫자를 ‘주소’ 라고 부른다.
32bit CPU 와 64bit CPU
64bit CPU가 32bit CPU 보다 한번에 처리할 수 있는 양이 많기 때문에 속도가 더 빠르다.
- 32bit CPU
  - 레지스터 크기: 32bit
  - ALU(산술논리연산장치) : 32bit
  - (데이터가 이동하는) 버스 : 32bit
  - CPU가 다룰 수 있는 메모리 : 2³² = 4GB
- 64bit CPU
  - 레지스터 크기: 64bit
  - ALU(산술논리연산장치) : 64bit
  - (데이터가 이동하는) 버스 : 64bit
  - CPU가 다룰 수 있는 메모리 : 2⁶⁴

물리주소와 논리 주소

물리 주소 공간

컴퓨터를 연결하면 0x0번지부터 시작하는 주소 공간

논리 주소 공간

사용자 관점에서 바라본 메모리 공간

사용자는 논리주소로 물리주소에 접근 가능

경계 레지스터

하드웨어 적으로 운영체제 공간과 사용자 공간을 나눈다.
CPU 내부에 존재하며 메모리 관리자가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고 벗어난 경우 그 프로세스를 종료시킨다.

절대 주소와 상대 주소

절대 주소

실제 프로그램이 올라간 메모리 주소이며 메모리 관점에서의 절대 주소

‘물리 주소 공간’ 이라 부른다.

상대 주소

사용자가 바라본 주소이며 실제 메모리 주소가 아니다.

‘논리 주소 공간’이라 부른다.

재배치 레지스터

메모리 관리자는 CPU가 요청한 메모리 주소 값과 재배치 레지스터에 저장된 값을 더한 메모리 주소에 접근해서 데이터를 가져온다.
재배치 레지스터에는 프로그램의 시작 주소가 저장되어 있다.
재배치 레지스터 덕분에 모든 사용자 프로세스는 0x0번지 부터 시작한다는 가정을 사용할 수 있고, 시작 영역이 변경되어도 재배치 레지스터만 변경해주면 되는 장점이 있다.

3. 메모리 할당방식

메모리 오버레이(memory overlay)

메모리 보다 큰 프로그램 실행 시 당장 실행할 부분만 메모리에 올리고, 나머지는 하드디스크 내부의 스왑 영역에 저장하는 기법
스왑과정이 있기 때문에 조금 느리다.

가변 분할 방식 (세그멘테이션)

프로세스의 크기에 따라 메모리를 나누는 방식

한 프로세스가 메모리의 연속된 공간에 할당되기 때문에 “연속 메모리 할당”이라고 한다.

가변 분할 방식의 장/단점

장점

메모리의 연속된 공간에 할당되기 때문에 *내부 단편화가 없다
- *내부 단편화 : 크기가 더 크게 할당되어 낭비되는 공간

단점

외부 단편화 발생

고정 분할 방식 (페이징)

프로세스 크기와 상관없이 메모리를 정해진 크기로 나누는 방식

한 프로세스가 메모리에 분산되어 할당되기 때문에 “비연속 메모리 할당” 이라고 한다.

고정 분할 방식의 장/단점

장점

구현이 간단, 오버헤드가 적다.

단점

작은 프로세스도 큰 공간에 할당되어 공간이 낭비되는 내부 단편화가 발생

외부 단편화 문제

메모리를 할당 할 수 있는 공간이 충분함에도 연속된 공간에 프로세스를 할당할 수 없으면 할당하지 못하는 것

내부 단편화 문제

프로세스의 크기가 분할된 공간의 크기보다 작기 때문에 내부에 빈 공간이 생겨 낭비된다.

분할되는 크기를 조절해서 내부 단편화를 최소화 한다.

버디 시스템

가변 분할 방식과 고정 분할 방식을 혼합해 단점을 최소화 함

2의승수로 메모리 분할하여 메모리를 할당하는 방식

버디 시스템의 장점

외부 단편화 방지를 위한 메모리 공간 확보가 간단
내부 단편화가 발생하긴 하지만 많은 공간의 메모리 낭비가 발생하지는 않음