운영체제

CPU 스케줄링

SJF (Shortest Job First)

Burst Time이 짧은 프로세스를 먼저 실행한다
SJF 문제
- 어떤 프로세스가 얼마나 실행될지 예측하기 힘듦 => 종료시간 예측 어려움
- Burst Time이 긴 프로세스는 오랫동안 실행 안될 수 있음
- BUrst Time이 짧은 프로세스가 계속 추가되면 추가되는 만큼 지연됨

RR (Round Robin)

프로세스에서 일정시간만큼 CPU를 할당하고 할당 시간이 지나면 강제로 다른 프로세스에게 일정시간만큼 CPU를 할당하고 강제로 CPU를 뺏긴 프로세스는 큐의 가장 뒷부분으로 밀려남
알고리즘 성능
- 타임슬라이스(프로세스에게 할당하는 일정시간, 타임퀀텀이라고도 부름) 에 따라 다름
- 타임 슬라이스가 작은 경우
  컨텍스트 스위칭이 자주 일어나고 타임 슬라이스에서 처리되는 프로세스 처리량보다 컨텍스트 스위칭 처리량이 더 많아짐 => 오버헤드가 더 크다

FIFO와 Round Robin 비교

평균 대기 시간이 비슷하다면
- FIFO가 더 효율적
- Round Robin은 컨텍스트 스위칭이 있어 컨텍스트 스위칭 시간이 더 추가됨

MLFQ (Multi Level Feedback Queue)

RR의 업그레이드 된 알고리즘
CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임 슬라이스를 선택함
- 우선 순위를 가진 큐를 여러 개 준비한 후 우선순위가 클수록 타임 슬라이스가 작고 우선순위가 낮을수록 타임 슬라이스가 커짐
- 타임 슬라이스 크기를 오버해서 CPU를 뺏기면 우선순위가 더 낮은 큐로 이동 => 최종적으로 무한대에 가까운 타임슬라이스를 할당 받아 FIFO처럼 연속적으로 작업을 마칠 수 있음.

프로세스 동기화

프로세스 간 통신

한 컴퓨터 내에서 프로세스 간 통신
- 파일을 이용하는 방법: 통신하려는 프로세스들이 하나의 파일을 읽고 쓰는 것
- 파이프를 이용하는 방법: 운영체제가 생성한 파이프를 이용해 데이터를 읽고 씀
쓰레드를 이용한 방법
- 한 프로세스 내에서 쓰레드 간 통신
- 쓰레드의 데이터 영역에 있는 전역변수나 힙을 이용하면 통신가능
네트워크를 이용한 방법
- 운영체제 제공 소켓 통신
- RPC 통신

공유자원과 임계구역

공유자원
- 프로세스 간 통신할 때 공동으로 이용하는 변수나 파일
- 각 프로세스의 접근 순서에 따라 결과가 달라질 수 있음
- 컨텍스트 스위칭으로 시분할 처리를 하므로 어떤 프로세스가 먼저 실행되는지 예측하기 어려움 => 연선 결과 예측 어려움 => 동기화 문제 발생
임계구역
- 여러프로세스가 동시에 사용하면 안되는 영역
경쟁조건
- 공유자원을 서로 사용하기 위해 경쟁하는 것
상호배제메커니즘
- 임계구역 문제 해결 방법
- 요구사항
  - 임계영역엔 동시에 하나의 프로세스만 접근
  - 여러 요청에도 하나의 프로세스의 접근만 허용
  - 임계구역에 들어간 프로세스는 빠르게 나와야함

세마포어

상호배제 메커니즘 중 하나

모니터

세마포어의 단점을 해결한 상호배제 메커니즘

데드락

데드락이란?

교착상태 (데드락)
- 여러 프로세스가 서로 다른 프로세스가 끝나기를 기다리다가 아무 작업도 진행 못하는 상태
- 공유 자원으로 인해 발생
- 필요조건 (한 가지라도 충족되지 않으면 교착 상태가 발생하지 않음)
  - 상호배제 : 프로세스가 한 리소스를 점유했다면 다른 프로세스에게 공유되면 안됨
  - 비선점: 프로세스A가 리소스를 점유하고 있을 때 프로세스 B가 리소스를 뺏을 수 없어야함
  - 점유와 대기: 어떤 프로세스가 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야함
  - 원형대기 : 점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있음

데드락 해결

교차상태 회피
- 프로세스들에게 자원을 할당할 때 어느 정도 할당해야 교착 상태가 발생하는지 파악해서 교착 상태가 발생하지 않는 수준으로 할당함
- 전체 자원의 수와 할당된 자원의 수로 안정상태와 불안정 상태로 나눔
  - 운영체제는 최대한 안정상태를 유지하려고 자원할당함
  - 불안정상태
    - 사용 가능한 자원이 적어 프로세스 요청 예상 자원을 충족시키지 못하는 상태
    - 교착 상태에 빠질 확률 높음
    - 은행원 알고리즘(각 프로세스가 현재 요청이 예상되는 자원을 구함) 은 비용이 비싸고 비효율적임
타이머 이용
- 가벼운 교착 상태 검출에 이용
- 일정 시점마다 체크 포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크 포인트로 롤백
- 억울하게 종료되는 프로세스 발생할 수 있음
자원 할당 그래프
- 무거운 교착 상태 검출에 이용
- 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태 발생 시 해결
- 지속적으로 자원할당 그래프 유지 및 검사 -> 오버헤드 발생
- 교착상태 일으킨 프로세스 강제종료 후 다시 실행 시 체크포인트로 롤백
- 타이머 이용 시 발생했던 억울하게 종료되는 프로세스 발생 안 함

메모리

메모리 종류

레지스터
- 가장 빠른 기억 장소로 CPU에 위치
- 컴퓨터가 꺼지면 데이터가 사라짐 => 휘발성 메모리
- CPU가 계산할 때 메인 메모리 값을 가져와서 계산하고 결과는 다시 메인 메모리에 저장시킴
캐시
- 레지스터와 속도 차이가 많이 나는 메인 메모리가 필요할 데이터를 예측해 가져온 데이터를 저장하는 곳
- 레지스터와 메인 메모리 사이에 위치
- 휘발성 메모리
- 성능의 이유로 여러 개 있음.
메인메모리
- 속도는 빠르지만 비싸기 때문에 실행중인 프로그램만 올림
- 휘발성 메모리
보조저장장치
- 비휘발성 메모리

메모리와 주소

주소
- 메모리를 관리하기 위해 1바이트 크기로 구역을 나누고 숫자를 매김
- 32bit보다 64bit가 한 번에 처리할 수 있는 양이 많아 속도가 빠름
물리주소공간
- 메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소공간
논리주소공간
- 사용자 입장에서 바라본 주소공간
- 사용자는 물리주소를 몰라도 논리주소로 접근할 수 있음
상대주소(논리주소)
- 컴파일러는 0x0번지라고 가정해서 프로그램을 만듦
절대주소(물리주소)
- 메모리 관리자가 바라본 실제 프로그램이 올라간 번지
경계레지스터
- 하드웨어적으로 운영체제 공간과 사용자 공간을 나눔
- 메모리 관리라는 사용자 프로세스가 경계 레지스터를 벗어났는지 검사하고 종료시킴
재배치 레지스터
- 프로그램의 시작 주소가 저장되어있음

메모리 할당방식

메모리 오버레이
- 큰 프로그램을 잘라서 당장 실행시켜야할 부분만 메모리에 올리고 나머지는 용량이 큰 하드디스크의 스왑영역에 저장하는 기법
스왑
- 스왑영역에 있는 데이터 일부를 메모리로 가져오고 메모리에 있는 데이터를 스왑영역으로 옮김
가변분할방식
- 프로세스의 크기에 따라 메모리를 나누는 방식
- 프로세스 크기에 맞게 할당되기 때문에 낭비 공간인 내부 단편화가 없음
- 단점
  - 외부단편화: 연속되지 않은 공간은 새로운 프로세스에게 메모리를 할당할 수 없음
  - 외부단편화가 발생한 공간을 합쳐주는 조각모음을 하면 됨
  - 조각모음을 할 경우 프로세스를 일시중지 해야하고 메모리를 옮겨야해서 오버헤드 발생
고정분할방식
- 비연속 메모리할당
- 프로세스 크기와 상관없이 메모리를 정해진 크기로 나누는 방식
- 구현이 간단하고 오버헤드가 없음
- 단점
  - 내부단편화: 분할되는 크기를 조절해서 내부 단편화를 최소화
버디시스템
- 2의 승수로 메모리를 분할해 할당함
- 가변분할방식과 고정분할방식을 합쳐 단점을 최소화함
- 프로세스 크기에 따라 할당되는 메모리 크기가 달라짐
- 외부 단편화를 방지하기 위해 메모리 공간을 확보하는 것이 간단함
- 내부 단편화가 발생해도 많은 공간의 낭비가 발생하지 않음