운영체제

프로그램

• 어떤 작업을 위해 실행할 수 있는 파일

프로세스

• 실행중인 프로그램
• 디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 것

PCB (Process Control Block)

• 특정 프로세스에 대한 중요한 정보를 저장하고 있는 운영체제의 자료구조
• 프로세스 생성과 동시에 생성된다
• 프로세스가 작업하다가 프로세스 전환이 발생하면 지금까지의 진행상황을 PCB에 저장하고, 다시 CPU를 할당 받게 되면 PCB에 저장된 정보를 불러온다
• 프로세스 식별자, 프로세스 상태, 프로그램 카운터, CPU 레지스터, CPU 스케줄링 정보, 메모리 정보, 입출력 상태 정보, 어카운팅 정보 들을 저장
• Linked List 방식으로 관리

스레드

• 프로세스의 실행 단위
• 한 프로세스 내에서 동작되는 여러 실행 흐름으로 프로세스 내의 주소 공간이나 자원을 공유

자바 스레드

• 자바에는 프로세스가 존재하지 않고 스레드만 존재
• 자바 스레드는 JVM에 의해 스케쥴되는 실행 단위 코드 블록
• 즉, 개발자는 자바 스레드로 작동할 스레드 코드를 작성하고, 스레드 코드가 생명을 가지고 실행을 시작하도록 JVM에 요청하는 일뿐이다

멀티 프로세스

• 하나의 컴퓨터에 여러 CPU를 장착하여 하나 이상의 프로세스들을 동시에 병렬 처리하는 것
• 장점은 메모리 침범 문제를 OS 차원에서 해결하기 때문에 안전
• 단점은 각각 독립된 메모리 영역을 갖고 있어서, 작업량이 많을수록 오버헤드가 발생한다는 것(문맥교환으로 인한 성능 저하)

멀티 스레드

• 하나의 응용 프로그램에서 여러 스레드를 구성해 각 스레드가 하나의 작업을 처리하는 것
• 장점은 서로 자원을 공유할 수 있어서 독립적인 프로세스에 비해 공유 메모리만큼의 시간, 자원 손실이 감소
• 단점은 하나의 스레드가 데이터 공간을 망가뜨리면, 모든 스레드가 작동 불가능 상태가 된다는 안정성의 문제
• 멀티스레드의 안전성에 대한 단점은 동기화를 통해 대비한다
• 동기화를 통해 작업 처리 순서를 컨트롤하고 공유 자원에 대한 접근을 컨트롤
• 하지만 이로 인해 병목현상이 발생하여 성능이 저하될 가능성이 높으므로 과도한 락으로 인한 병목현상을 여야한다 (하나의 스레드가 공유 데이터 값을 변경하는 시점에 다른 스레드가 그 값을 읽으려할 때 발생하는 문제를 해결하기 위한 동기화 과정)

문맥교환 (Context Switching)

• 프로세스의 상태 정보를 저장하고 복원하는 일련의 과정
• 즉, 동작 중인 프로세스가 대기하면서 해당 프로세스의 상태를 보관하고, 대기하고 있던 다음 순번의 프로세스가 동작하면서 이전에 보관했던 프로세스 상태를 복구하는 과정
• 프로세스는 각 독립된 메모리 영역을 할당받아 사용되므로, 캐시 메모리 초기화와 같은 무거운 작업이 진행되었을 때 오버헤드가 발생하는 문제가 존재

경쟁 상태(Race Condition)

• 공유 자원에 대해 여러 프로세스가 동시에 접근할 때, 결과값에 영향을 줄 수 있는 상태
• 즉, 두개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황

Deadlock

• 프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
• 서로 원하는 자원이 상대방에 할당되어 있어서 각각 무한정 대기 상태에 빠진 상황
• 데드락이 발생하는 조건
  • 상호 배제(Mutual exclusion) : 자원은 한번에 한 프로세스만 사용가능
  • 점유 대기(Hold and wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하고 있는 프로세스가 존재
  • 비선점(No preemption) : 다른 프로세스에 할당된 자원을 사용이 끝날때까지 강제로 뺏을 수 없음
  • 순환 대기(Circular wait) : 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
• 데드락을 처리하는 방법
  • 예방 : 교착 상태 발생 조건 중 하나를 제거해서 해결
  • 회피 : 교착 상태 발생 시에 피해가는 방법, 은행원 알고리즘
  • 탐지&회복 : 교착 상태가 되도록 허용한 다음 회복시키는 방법, 자원 할당 그래프를 통해 교착상태를 탐지하고 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜서 회복

동기와 비동기

• 메소드를 실행시킴과 동시에 반환 값이 기대되는 경우를 동기, 그렇지 않은 경우를 비동기
• 동시에 라는 말은 실행되었을 때 값이 반환되기 전까지는 blocking되어 있다는 것을 의미
• 비동기는 blocking 되지 않고 이벤트 큐에 넣거나 백그라운드 스레드에게 해당 task를 위임하고 바로 다음 코드를 실행하기 때문에 기대되는 값이 바로 반환되지 않는다.
• 동기
  • 전체적인 수행 속도는 빠름
  • 한 작업에 대한 시간이 길어질 경우, 전체 응답이 지연
• 비동기
  • 다수의 작업을 처리할 수 있음
  • 작업이 끝날 때 따로 이벤트를 감지하고 결과를 받아 그에 따른 추가 작업을 해줘야 하기 때문에, 비교적 느릴 수 있음
  • 입출력 작업이 잦고, 빠른 응답속도를 요구하는 프로그램에 적합

스케줄러

• 프로세스를 스케줄링하기 위한 Queue는 세 가지 종류가 존재
• 현재 시스템 내에 있는 모든 프로세스 집합인 Job Queue, 현재 메모리 내에 있으면서 CPUT를 잡아서 실행되기를 기다리는 프로세스의 집합인 Ready Queue, Device I/O 작업을 대기하고 있는 프로세스 집합 Device Queue
• 장기 스케줄러
  • 프로세스 중 어떤 프로세스에 메모리를 할당하여 Ready Queue로 보낼지 결정하는 역할
  • 메모리와 디스크 사이의 스케줄링을 담당
• 단기 스케줄러
  • Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
  • CPU와 메모리 사이의 스케줄링을 담당
• 중기 스케줄러
  • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫒아내는 역할(Swapping)
  • 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절

---

CPU 스케줄러

• Ready Queue에 있는 프로세스들의 대상으로 한다
• FCFS(First Come First Served)
  • 먼저 온 순서대로 처리
  • 비선점형 스케줄링
  • 소요시간이 긴 프로세스가 먼저 도달하면 뒤에 도착한 짧은 프로세스의 대기 시간이 길어져 효율성이 낮아진다
  • Queue
• SJF(Shortest Job First)
  • 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
  • 비선점형 스케줄링
  • FCFS보다 편균 대기 시간이 감소하지만 기아현상 발생
  • priority Queue
• HRN (Highest Response-ratio Next)
  • (대기시간+실행시간)/(실행시간) 의 우선순위를 계산하여 점유 불편등을 보완한 방법이다.
  • SJF를 보완
  • priority Queue
• SRTF(Shortest Remaining Time First)
  • 현재 수행중인 프로세스의 남은 실행시간보다 더 짧은 CPU 실행시간을 가지는 새로운 프로세스가 도착하면 선점당하는 스케줄링
  • 기아문제와 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time을 측정하기 어려움
  • priority Queue
• Priority Scheduling
  • 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링
  • 기아 문제가 발생
  • 이는 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주는 Aging으로 해결 가능하다.
  • priority Queue
• Round-Robin
  • 각 프로세스는 동일한 크기의 할당 시간을 갖게 된다.
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
  • RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 경우에 효율적이다.
  • 공정한 스케줄링, 응답시간이 빨라진다.
  • Time quantum이 너무 커지면 FCFS와 같아지고 너무 작아지면 잦은 context switch로 오버헤드가 발생한다. 적당히 설정
  • Queue
• 다단계 큐
  • 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 큐마다 다른 Time quantum, 우선순위가 높은 큐는 작게 낮은 큐는 크게 할당

---

Critical Section(임계영역)

• 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분
• 공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야한다
• Critical Section 을 해결하기 위한 세가지 조건
  • Mutual Exclusion(상호 배제) : 하나의 프로세스가 임계영역에서 실행중이라면, 다른 프로세스들은 임계 영역에서 실행될 수 없다는 조건
  • Progress(진행) : 임계 영역에서 실행중인 프로세스가 없을 때, 들어가려는 프로세스가 여러 개라면 어느 것이 들어갈지 결정해주어야 한다는 조건
  • Bounded Waiting(한정된 대기) : 다른 프로세스의 기아를 방지하기 위해 한번 임계 구역에 들어간 프로세스는 다음 번 임계영역에 들어갈 때 제한이 있어야 한다는 조건
• 해결하기 위한 방법으로 학, 세마포어, 모니터 등

Lock

• 하드웨어 기반 해결책
• 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section 에 진입하는 프로세스는 Lock을 획득하고 빠져나올 때 Lock을 방출함으로써 동시에 접근이 되지 않도록 한다.

Semaphore

• Critical Section 문제를 해결하기 위한 동기화 도구이다.
• 세마포는 카운팅 세마포와 이진 세마포로 나뉜다.
• 카운팅 세마포 : 가용한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수로 초기화 된다. 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가한다.
• 이진 세마포 : 뮤텍스라고도 부르며, 0과 1 값만 가능하며 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.
• 단점
  • Busy Waiting(바쁜 대기)이다.
  • Spin lock이라고 불리는 세마포 초기 버전에서 Critical section에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야 하며 CPU 시간을 낭비했었다.
  • 이는 짧게 수행하는 작업에 사용되지만 일반적으로 비효율적이다.
  • 일반적으로는 세마포에서 크리티컬 섹션에 진입을 시도했지만 실패한 프로세스에 대해 Block 시킨 뒤, 크리티컬 섹션에 자리가 날 때 다시 깨우는 방식을 사용한다.
  • 이 경우 바쁜 대기로 인한 시간낭비 문제가 해결된다.

Mutex

• 자원에 대한 접근을 동기화하기 위해 사용되는 상호 배제 기술이다.
• Lock과 unlock을 사용한다.
• 상태를 0,1로 표현하여 이진 세마포라고도 불린다.
• 시스템 전반의 성능에 영향을 주고 싶지 않고 길게 처리해야 하는 작업의 경우 주로 사용한다.

세마포어와 뮤텍스 차이점

• 뮤텍스는 동기화 대상이 오직 하나뿐일 때, 세마포어는 동기화 대상이 하나 이상일 때 사용한다.
• 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다.
• 세마포어는 소유할 수 업는 반면, 뮤텍스는 소유가 가능하며 소유주가 이에 대한 책임을 가진다.
• 뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 이 뮤텍스를 해제할 수 있다. 하지만 세마포어의 경우 이러한 세마포어를 소유하지 않는 스레드가 세마포어를 해제할 수 있다.
• 세마포어는 시스템 범위에 걸쳐있고 파일시스템상의 파일 형태로 존재하는 반면 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 clean up된다.
  https://gyoogle.dev/blog/computer-science/operating-system/Semaphore%20&%20Mutex.html

메모리 관리 전략

• 다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요해서 페이징과 세그먼테이션을 사용한다.
• 연속 메모리 관리
  • 프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되어야 하는 기법
  • 고정 분할 기법 : 주기억장치가 고정된 파티션으로 분할하는 것인데 이것은 내부 단편화가 발생한다.
  • 동적 분할 기법 : 파티션들이 동적 생성되며 자신의 크기와 같은 파티션에 적재되고 외부 단편화가 발생한다.
• 불연속 메모리 관리
  • 프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법
  • 고정크기인 페이징과 가변크기인 세그먼테이션이 있다.

단편화

• 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼의 작은 자유공간들이 늘어나게 되는데, 이것이 단편화이다.
• 외부 단편화 : 메모리 공간 중 사용하지 못하게 되는 일부분, 물리 메모리에서 사이사이 남은 공간들을 모두 합치면 충분한 공간이 되는 부분들이 분산되어 있을 때 발생한다.
• 내부 단편화 : 프로세스가 사용하는 메모리 공간에 포함된 남는 부분이다.

페이징

• 단순 페이징
  • 외부 단편화와 압축 작업을 해소하기 위해 생긴 방법론
  • 물리 메모리는 Frame이라는 고정 크기로 분리되어 있고, 논리 메모리는 페이지라 불리는 고정 크기의 블록으로 분리된다.
  • 내부 단편화 발생.
• 가상 메모리 페이징
  • 단순 페이징과 비교해서 프로세스의 페이지 전부를 로드시킬 필요가 없다.
  • 필요한 페이지가 있으면 후에 자동적으로 불러들어진다.
  • 외부 단편화도 해결하고 다중 프로그래밍 정도가 높으며 가상 주소 공간이 크다.
  • 그러나 복잡한 메모리 관리의 오버헤드가 발생한다.

세그먼테이션

• 서로 다른 크기의 논리적 단위인 세그먼트로 분할한다.
• 내부단편화 해소, 외부단편화의 문제가 발생.
• 가상 메모리 세그멘테이션은 필요하지 않은 세그먼트들을 로드하지 않는다.
• 필요한 세그먼트 자동적으로 불러들임.
• 내부 단편화 없고 높은 수준의 다중 프로그래밍, 큰 가상 주소 공간, 보호와 공유를 지원한다.
• 복잡한 메모리 관리의 오버헤드 발생

가상 메모리

• 다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야 한다.
• 가상메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법
• 프로그램이 물리 메모리보다 커도 된다는 주요 장점
• 물리 메모리 크기에 제약 받지 않게 되고 더 많은 프로그램을 동시에 실행할 수 있게 된다.
• 이에 따라 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다.
• Swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.
• 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다.
• 각 프로세스들은 공유 라이브러리를 자신의 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있다.
• 프로세스들이 메모리를 공유하는 것을 가능하게 하고, 프로세스들은 공유 메모리를 통해 통신할 수 있다.
• 이 또한, 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있다.
• Fork( )를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

Demending Paging(요구 페이징)

• 프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리로 적대하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징
• 가상 메모리 시스템에서 많이 사용된다.
• 그리고 가상 메모리는 대개 페이지로 관리된다.
• 요구 페이징을 사용하는 가상 메모리에서는 실행과정에서 필요해질 때 페이지들이 적재된다.
• 한 번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.

---

페이지 교체 알고리즘

• 프로그램 실행시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 page fault(페이지 부재) 가 발생되면, 원하는 페이지를 보조저장장치에서 가져오게 된다. 하지만, 만약 물리 메모리가 모두 사용중인 상황이라면, 페이지 교체가 이뤄져야 한다.
• FIFO(First In First Out)
  • 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다.
  • 이해하기 쉽고 프로그램하기도 쉽다.
  • 단점은 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.
  • Belady의 모순 : 페이지를 저장할 수 있는 페이지 프레임의 개수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순이 존재
  • Queue
• OPT(Optimal Page Replacement)
  • 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다.
  • 알고리즘 중 가장 낮은 페이지 부재율을 보장하지만 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문에 구현의 어려움이 있다.
• LRU(Least Recently Used)
  • 가장 오랫동안 사용되지 않은 페이지를 내보내는 알고리즘
  • OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 알고리즘중에서는 가장 좋은 방법 중 하나이지만 거의 사용되지 않음
  • Hash Map, Priority_Queue
  • https://hee96-story.tistory.com/47
• LFU(Least Frequently Used)
  • 참조 횟수가 가장 적은 페이지를 교체하는 방법이다.
  • 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어졌다.
  • 어떤 프로세스가 특정 페이지를 집중적으로 사용하다가 다른 기능을 사용하게되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있다.
• MFU(Most Frequently Used)
  • 참조 회수가 가장 적은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.

---

캐시의 지역성

• 캐시 메모리는 속도가 빠른 장치과 느린 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리이다.
• 이런 역할을 수행하기 위해서는 CPU가 어떤 데이터를 원할 것인가를 어느 정도 예측할 수 있어야한다.
• 캐시의 성능은 작은 용량의 캐시 메모리에 CPU가 이후에 참조할, 쓸모 있는 정보가 어느 정도 들어있느냐에 따라 좌우되기 때문이다.
• 이때 적중율을 극대화시키기 위해서 데이터 지역성의 원리를 사용한다.
• 지역성의 전제조건으로 프로그램은 모든 코드나 데이터를 균등하게 Access 하지 않는다는 특성을 기본으로 한다.
• 즉, 지역성이란 기억 장치 내의 정보를 균일하게 엑세스 하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성인 것이다.
• 지역성은 대표적으로 시간 지역성과 공간 지역성으로 나뉜다.
  • 시간 지역성은 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성
  • 공간 지역성은 대부분의 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성이다.