운영체제 정리

운영체제

• 컴퓨터 하드웨어를 관리하는 소프트웨어

• CPU, 메모리 및 입출력 장치 등의 자원들을 프로그램에 적절하게 할당해야 하는 책임

• 거의 모든 코드가 운영체제 위에서 실행되므로 운영체제 작동방식에 대한 지식은 적절하고 효율적이며 안전한 프로그래밍에 중요하기 때문

• 일반적으로 운영체제에는 각 장치 컨트롤러마다 장치 드라이버가 존재
  • 드라이버는 장치 컨트롤러의 작동을 잘 알고 있고 나머지 운영체제에 장치에 대한 일관된 인터페이스를 제공

인터럽트

• 장치 컨트롤러가 장치 드라이버에 작업을 완료했다는 사실을 알리는 방법

• 하드웨어는 어느 순간이든 시스템 버스를 통해 CPU에 신호를 보내 인터럽트를 발생시킬 수 있음

• CPU가 인터럽트 되면, 하던 일을 중단하고 즉시 고정된 위치로 실행을 옮기고 ISR(인터럽트 서비스 루틴)을 실행
  • 실행이 완료되면 인터럽트 되었던 연산을 재개

• CPU 하드웨어에는 인터럽트 요청 라인이라는 선이 있는 데, 하나의 명령어를 실행 완료할 때마다 CPU가 선을 감지
  • CPU가 이를 감지하면 인터럽트 번호를 읽고 이 번호를 인터럽트 벡터(배열)의 인덱스로 사용하여 인터럽트 핸들러 루틴으로 점프
  • 그런 다음 해당 인덱스와 관련된 주소에서 실행을 시작
  • 발생 → 포착 → 디스패치 → clear 순으로 동작

이중 모드(dual mode)

• 운영체제는 잘못된(혹은 악의적인) 프로그램으로 인해 다른 프로그램이나 운영체제로부터 보호하기 위해 두개의 독립적인 연산 모드를 나타낸다.

• 모드 비트라는 하나의 비트가 현재의 모드를 나타내기 위해 컴퓨터 하드웨어에 추가되었다.
  • 커널 모드(0): 운영체제가 지원하는 함수(시스템 콜)을 실행할 수 있는 명령어 실행 모드
  • 유저 모드(1): 사용자 프로세스를 실행하는 등 운영체제가 지원하는 함수를 실행할 수 없는 명령어 실행 모드

시스템 콜

• 운영체제에서 제공하는 서비스에 대한 인터페이스를 제공한다.

• 커널 영역의 코드(시스템 함수)를 실행하는 걸 말한다.

• 일반적인 함수 호출은 자신의 스택 영역을 사용하는 것이지만, 시스템 콜은 커널 영역의 함수 위치로 점프하는 방식이다. 이 방식은 인터럽트로 이뤄지며 (시스템 콜 인터럽트), 인터럽트 서비스 루틴 또한 커널 영역에 존재한다.

---

프로세스

• 실행 중인 프로그램을 말한다.

• 현재 상태를 프로그램 카운터 값과 프로세서 레지스터의 내용으로 나타낸다.

• 메모리 배치는 아래부터 코드, 데이터, 힙, 스택 영역으로 구분되고 배치된다.
  • 코드: 실행 코드
  • 데이터: 전역 변수
  • 힙: 프로그램 실행 중에 동적으로 할당되는 메모리
  • 스택: 함수를 호출할 때 임시 데이터 저장장소(예: 함수 매개변수, 복귀 주소, 지역 변수 등)

• 코드, 데이터 영역은 크기가 고정되기 때문에 실행 시간 동안 크기가 변하지 않는다. 하지만 스택, 힙 섹션은 프로그램 실행 중에 동적으로 줄어들거나 커질 수 있다.
  • 스택 및 힙 섹션이 서로의 방향으로 커지더라도 운영체제는 서로 겹치지 않도록 해야한다.

• 프로세스는 실행되면서 상태가 변할 수 있다.
  • new, running, waiting, ready, terminated

• 프로세스는 부모 자식의 계층 구조를 가진다.

• 좀비 프로세스: 종료되었지만 부모 프로세스가 아직 wait() 시스템 콜을 호출하지 않은 프로세스
  • 일반적으로 부모가 wait()하면 연쇄적으로 자식 프로세스가 종료된다. 즉 짧은 시간 동안 자식 프로세스들은 좀비 프로세스 상태가 된다.

• 고아 프로세스: 부모 프로세스가 wait() 을 호출하지 않고 종료된 프로세스

PCB

• 각 프로세스는 운영체제에서 PCB(프로세스 제어 블록)에 의해 표현된다.

• 커널 영역에 생성된다. (운영체제가 관리하기 위함이므로)

• Linux에서 PCB는 C 구조체 task_struct로 이뤄지고, 이중 링크드 리스트로 표현된다.

• PCB는 특정 프로세스와 연관된 여러 정보를 수록하며, 다음과 같은 것들을 포함한다.
  • PID (Process 고유 ID)
  • 레지스터 값 (PC)
  • 프로세스 상태
  • CPU 스케줄링 정보 (우선순위)
  • 메모리 관련 정보
    • 베이스 레지스터
    • 한계 레지스터
    • 페이지 테이블 정보
  • TCB (Thread Control Block) 리스트

---

스레드

• CPU 이용의 기본 단위

• 같은 프로세스에 속한 다른 스레드와 코드, 데이터, 힙 영역을 공유하기 때문에 메모리 점유가 낮아서 경량 프로세스 라고도 한다.
  • 스레드 ID, 프로그램 카운터 (PC), 레지스터 셋, 스택으로 구성된다.

• 한 프로세스 내의 스레드들은 서로 소통 가능

• 별도의 레지스터와 스택을 지닌다.

• 멀티 프로세스로 실행되는 작업을 멀티 스레드로 실행하게 되면 프로세스를 생성해서 자원 할당하는 과정도 줄어들고, 프로세스를 컨텍스트 스위칭하는 것 보다 스레드를 컨텍스트 스위칭 하는 것이 오버헤드를 줄일 수 있게 된다.

유저 스레드

• 유저 프로그램 안에서 생성되는 유저 레벨 스레드

• 커널 스레드에 비해 오버헤드가 작다.

• 동일 프로세스 내 어떤 스레드가 waiting 되면 모든 스레드가 멈춘다.
  • waiting이라는 것은 프로세스 자체가 waiting 되었다는 뜻이기 때문

커널 스레드

• 커널도 프로그램이므로, 스레드가 사용된다.

• 이와 같이 커널 내의 스레드를 커널 레벨 스레드라고 한다.

• 동일 프로세스 내 다른 스레드가 waiting 되더라도 다른 스레드의 실행이 가능하다.

유저 스레드-커널 스레드의 매핑

• 궁극적으로 사용자 스레드와 커널 스레드는 어떤 연관 관계가 존재해야 한다.

• 다대일 / 일대일 / 다대다 모델이 있다.
  • Swift async/await 모델이 다대다 모델을 사용할 것으로 추정.

TCB

• 프로세스를 관리하기 위한 PCB가 있는 것처럼 스레드를 관리하기 위한 Thread Control Block가 존재한다.

• Thread ID< 스레드 상태, PCB 포인터, 스케줄링 정보 등을 포함한다.

• PCB는 커널 영역에 생성되지만, 유저 스레드 TCB는 프로세스 메모리 영역에, 커널 스레드 TCB는 커널 영역에 생성된다.

• PCB에서 TCB 리스트를 가리키고, TCB에서 PCB를 가리키게 된다.

---

다중 코어 프로그래밍

• 코어: 연산 작업을 수행하는 핵심 적인 부분

• 다중 코어는 단일 컴퓨팅 칩에 여러 컴퓨팅 코어를 배치하는 것을 말한다.

• 단일 코어 시스템에서는 처리 코어가 한번에 하나의 스레드만 실행할 수 있기 때문에 동시성이 시간이 지남에 따라 스레드 실행이 교차된다.

• 하지만 여러 코어가 있는 시스템에서 동시성은 시스템이 각 코어에 별도의 스레드가 할당될 수 있기 때문에 일부 스레드가 병렬로 실행될 수 있다.
  • Swift에서 비동기 작업을 async/await으로 처리하면 딱 코어 수 만큼만의 스레드를 생성하여 처리하기 때문에 스레드 폭발을 막아서 성능 처리에 도움을 줄 수 있다.

IPC (Inter Process Communication)

• 프로세스 끼리의 의사 소통을 말한다.

• 프로세스 끼리는 서로 독립적으로 수행되기 때문에 프로세스 끼리 데이터를 공유하기 위한 공유 기법

• 두가지 모델이 존재한다.
  • 공유 메모리: 프로세스 끼리 공유하는 메모리 영역을 구축하고 데이터를 공유한다. 메모리를 공유하므로 동기화 작업이 필요하다.
  • 메시지 전달: 프로세스 끼리 메시지를 전달해서 데이터를 교환한다. 공유 메모리 기법 보다는 느리다.
    • 소켓도 IPC 메시지 전달 기법에 속한다. 같은 컴퓨터가 아닌 다른 컴퓨터의 프로세스끼리도 소통할 수 있다.

---

CPU 스케줄링

• 코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만이 실행될 수 있다.

• 프로세스에서 I/O 작업을 하는 것을 I/O burst, CPU를 사용하는 작업을 CPU burst 라고 한다.

• I/O burst 비율이 높은 프로세스를 I/O bound 프로세스, CPU burst 비율이 높은 프로세스를 CPU bound 프로세스라고 한다.

• 일반적으로 I/O bound 프로세스가 CPU bound 프로세스 보다 우선순위가 높게 처리된다.
  • I/O bound 프로세스는 CPU를 잠깐만 사용하고 waiting 상태로 넘어가기 때문이다.

문맥 교환 (Context-Switch)

• 인터럽트가 발생하면 시스템은 인터럽트 처리가 끝난 후에 문맥을 복구할 수 있도록 현재 실행 중인 프로세스의 현재 문맥을 저장할 필요가 있다.

• CPU 코어를 다른 프로세스를 교환하기 위해 프로세스 상태를 PCB에 보관하고 새로운 프로세스의 보관된 상태를 복구하는 작업이다.

• 문맥 교환이 진행될 동안 시스템은 아무 작업도 수행하지 못하기에 문맥 교환 시간은 순수한 오버헤드이다.
  • 공룡책에서 모바일 시스템에서 멀티태스킹 설명 P.129
    • iOS 4이상 부터 제한된 형태의 멀티태스킹 지원 (백그라운드 앱이나 iPad에서 화면 분할하여 앱 동시 실행 같은 케이스)

CPU 스케줄러

• 운영체제에서 CPU 스케줄링 알고리즘이 적힌 코드를 CPU 스케줄러 라고 한다.

• 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여 이들 중 하나에게 CPU를 할당한다.

• 준비 큐에 있는 프로세스 중에서 하나를 선택해서 실행하게 되는 데, 일반적으로 큐에 있는 레코드들은 프로세스들의 PCB들이다.

선점형 / 비선점형 스케줄링

선점형 스케줄링 (preemptive scheduling)

• 어떤 프로세스가 CPU를 사용하고 있을 때, 다른 프로세스가 그 사용을 빼앗을 수 있는 스케줄링

• 한 프로세스의 CPU 독점을 막을 수 있다.

• context switch에 대한 오버헤드가 적다

• 데이터가 다수의 프로세스에 의해 공유될 때 race condition을 초래할 수 있다.

비선점형 스케줄링

• 어떤 프로세스가 CPU를 사용하고 있을 때, 다른 프로세스가 그 사용을 빼앗을 수 없는 스케줄링

• 한 프로세스가 CPU를 독점할 가능성이 있다.

• context switch에 대한 오버헤드가 적다

디스패처

• CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에게 넘겨주는 모듈(코드)이다.

• 현재 수행 중이던 프로세스의 context를 PCB에 저장하고, 새로운 프로세스의 context를 PCB로부터 복원 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.

CPU 스케줄링 알고리즘

• 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지 결정하는 알고리즘

FCFS (First Come First Served)

• 선입 선처리 스케줄링, 비선점형

• 준비 큐에 먼저 들어와서 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 스케줄링

• 구현이 간단하나, Convoy Effect(호위 효과)가 발생할 수 있다.
  • Convoy Effect: 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기까지 기다리게 되는 것

SJF (Shortest-Job-First)

• CPU 버스트 길이가 짧은 순으로 프로세스를 처리하는 방식

• 이론상 효율은 좋지만, CPU 버스트 길이를 알 수 없기 때문에 CPU 스케줄링 수준에서 구현할 수 없다.

RR (Round Robin)

• FCFS 스케줄링 방식에 타임 퀀텀(time quantum, 시간 할당량, 타임슬라이스라고도 함) 개념을 추가한 방식

• 선점형 방식

• FCFS로 프로세스를 처리하나, 최대 정해진 타임 퀀텀 시간 만큼만 CPU를 할당시킨다.

• 타임 퀀텀 이상으로 CPU가 사용되면 남은 작업을 준비 큐의 뒤로 보낸다.

• 타임 퀀텀값이 너무 크면 FCFS와 같은 성능으로 퇴보하고, 너무 작다면 너무 많은 Context-Switching을 야기하여 오버헤드가 커질 수 있다.

Priority

• 프로세스들에 우선순위를 부여하고, 우선순위 대로 CPU를 할당한다.

• 선점형, 비선점형 두가지 모두 구현될 수 있다.

• 단, 우선순위가 너무 작은 프로세스의 경우 우선순위가 높은 프로세스들이 계속 추가 되어 영영 실행되지 못하는 경우가 발생한다 → Starvation, 기아 현상
  • 이를 방지 하기 위해 aging 기법을 사용하여, 준비 큐에 들어온지 오래된 프로세스들을 시간이 지남에 따라 우선순위를 높여줄 수 있다.

MultiLevel Queue

• 우선순위, 라운드 로빈의 발전된 형태로 우선순위 별로 준비 큐를 여러 개 두는 방식이다.

• 큐별로 다른 스케줄링 알고리즘을 사용할 수 있고, 타임 퀀텀도 다르게 설정할 수 있다.

• 큐들 간의 스케줄링도 반드시 있어야 하고 일반적으로 선점형으로 구현된다.

MultiLevel Feedback Queue

• 멀티 레벨 큐의 발전된 형태이고, 멀티 레벨 큐들끼리 상호작용을 할 수 있다.
  • 멀티 레벨 큐 스케줄링에서는 일반적으로 프로세스가 영구적으로 하나의 큐에 할당되고, 다른 큐로 이동하지 않는다.

• 멀티 레벨 피드백 큐는 프로세스가 큐들 사이를 이동하는 것을 허용한다.

• CPU 버스트가 큰 프로세스들은 우선순위가 점차 낮은 큐로 내려가게 되고, CPU 버스트가 적은 프로세스들은 자연스레 우선순위가 높은 큐로 올라가서 실행을 마칠 수 있게 된다.
  • 이러한 형태로 자연스럽게 기아 상태를 예방할 수 있다.

스레드 스케줄링

• 대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다.

• CPU상에서 프로그램이 (혹은 프로세스가) 실행되기 위해서는 LWP(Light Weight Process)를 통한 간접적인 방식일지라도 사용자 수준 스레드는 결국 그것과 연관된 커널 수준 스레드에 매핑되어야 한다.

PCS (Process Contention Scope) 스케줄링

• 동일한 프로세스내의 스레드들이 CPU를 경쟁하는 것.

• 사용자 수준 - 커널 수준 스레드 매핑이 다대일, 다대다 인 경우 사용자 스레드를 가용한 LWP 상에서 스케줄링하게 된다 → PCS 에서 경쟁하게 된다.

• 전형적으로 PCS는 우선순위에 따라 행해진다.

SCS (System Contention Scope) 스케줄링

• CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하는 것.

---

프로세스 동기화

• 프로세스가 올바른 실행 순서로 실행되는 것 (순서 제어)

• Race Condition을 피하는 것 (공유자원 제어)

Race Condition(경쟁 상황)

• 동시에 여러 프로세스가 동일한 자료를 접근하여 조작하고, 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황

Critical Section (임계 구역)

• 여러 프로세스가 동시에 자원을 공유할 때, 동시에 수행되서는 안되는 코드 부분

• 해결안은 다음 3가지를 충족해야 한다.
  • 상호 배제: 프로세스가 자신의 임계구역에서 실행된다면 다른 프로세스들은 그들 자신의 임계 구역에서 실행될 수 없다.
  • 진행: 자신의 임계구역에서 실행되는 프로세스가 없고 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는 데 참여할 수 있다. 이 선택은 무한정 연기될 수 없다.
  • 한정된 대기: 프로세스가 자신의 임계 구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계 구역에 진입하도록 허용되는 횟수에는 한계가 있어야 한다.

Peterson의 해결안

• 임계구역을 해결하는 고전적인 방법을 제시. 현대는 load나 store같은 기본적인 기계어를 수행하는 방식 때문에 이러한 구조에서 올바르게 동작한다고 보장할 수는 없음

• 2개의 프로세스가 경쟁 상태에 있다고 가정하고, 해당 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결

• 진입 순번을 나타내는 정수 변수 turn와, 프로세스가 임계구역에 진입할 준비를 나타내는 불타입 배열 flag

• 임계 구역에 진입하기 전 turn을 상대의 값으로 지정하고 자신을 flag[i]로 설정
  • while loop를 돌면서 [flag 자신 인덱스 값이 참이고 turn이 자신인 경우 조건]을 계속 체크하여 해당 조건이 참인 경우 임계 구역에 진입을 허용
  • 임계 구역을 나가면서 flag[자신 인덱스]값을 false로 설정

Mutex Locks

• 동기화 문제를 해결하기 위한 대표적인 기법

• 프로세스가 임계 구역에 접근하려면 acquire() 함수를 통해 락을 획득해야만 하고, 임계 구역 실행이 종료되면 release() 함수를 통해 락을 반환해야 한다.
  • 뮤텍스는 available이라는 불 타입 변수를 통해 락의 가용 여부를 표시
  • Spin Lock(busy waiting): 프로세스가 임계 구역에 들어가 있는 동안 다른 프로세스들이 락을 획득하기 위해 acquire를 계속해서 반복문을 호출.
    • 계속된 반복문으로 다중 프로그래밍을 저해하지만, 문맥 교환에 상당한 시간이 소요될 때 문맥 교환이 필요하지 않다는 장점이 있다.
    • "조금만 기다리면 되는데 굳이 context switching을 해야하나?"라는 생각

Semaphore

• 뮤텍스 보다 일반화된 방안

• 뮤텍스는 공유자원에 접근할 수 있는 프로세스가 단 1개지만, 세마포어는 그 이상 개수를 지정하여 허용할 수 있다.

• 임계 구역에 진입하기 전 wait() 함수를 통해 세마포어 S 값을 감소, 임계 구역 실행이 종료되면 signal()을 통해 S 값을 증가시킨다.

• 이진 세마포어는 사실상 Mutex와 동일하게 동작한다.

Monitor

• 뮤텍스, 세마포어는 동기화를 편리하게 해결할 수 있지만, 프로그래머가 직접 사용해야 하기에 에러를 야기할 수 있다.
  • 적절한 타이밍에 release, signal같은 메서드를 사용하지 않으면 여전히 동기화 문제가 발생할 수 있다

• 고급언어에서 지원하는 동기화 해결법
  • 예를 들면 Java의 Synchronized 키워드

---

데드락

• 위와 같은 동기화 도구를 사용하는 것은, 임계 구역에 들어가려는 프로세스가 무기한 대기할 가능성이 존재한다.
  • 라이브니스(Liveness): 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성.
    • 예를 들면 Spin Lock과 같은 무한 루프

• 데드락은 2개 이상의 프로세스가 서로 Mutex락과 같은 공유자원을 할당받기를 기다리고 있어서 그 누구도 일을 하지 못하는 상태를 말한다.

• 교차로에서 꽉막힌 자동차들의 모습을 많이 예시로 든다.

• 유한 버퍼 문제, Reader-Writers 문제, 식사하는 철학자 문제들이 고전적인 동기화 문제이다.

Readers-Writers 문제

• DB처럼 읽기 작업만 하려는 프로세스(Reader)와 읽고 쓰기 둘다 하려는 프로세스(Writer)가 병렬적으로 실행되는 경우

• 하나의 writer가 쓰기 작업을 하면 다른 프로세스들이 배타적으로 DB에 접근하지 못하도록 조치해야 함

• 일반적으로 읽기를 위한 세마포어와 쓰기를 위한 lock 두 가지를 사용하여 해결할 수 있다.
  • 읽기 모드 세마포어는 여러 프로세스가 획득 가능
  • 쓰기 모드 락은 단 1개 프로세스만 획득 가능

식사하는 철학자 문제

• 아주 고질적인 동기화 문제.

• 원형 탁자에 철학자들이 앉아서 해당 철학자들 인원수 만큼의 포크를 두고, 양쪽의 포크를 집어 들었을 때만 식사가 가능한 조건
  • 왼쪽, 오른쪽 순으로 포크를 집고, 내려놓을 때는 오른쪽, 왼쪽 순으로 내려놓는다.
  • 그 누구도 식사를 못하는 상황이 발생할 수 있다. 예를 들어 모두가 전부 왼손에 포크를 집었을 때, 한명이라도 포크를 내려놓지 않으면 아무도 식사를 못한다.
  • 철학자들의 식사 = 프로세스 일처리, 포크 = 공유자원

• 간단한 해결안은 각 포크를 하나의 세마포로 표현하여 인접한 두 철학자가 동시에 식사하지 못하는 것을 방지하지만, 이는 데드락을 발생시킬 가능성이 있다.
  • 따라서 4명의 철학자만 테이블에 앉도록 조치하거나
  • 한 철학자가 두 포크 모두 집을 수 있을 경우에만 포크를 집도록 허용하거나
  • 비대칭적으로 홀수 번호 철학자는 왼쪽 → 오른쪽으로 포크를 집도록 하고, 짝수 번호 철학자는 오른쪽 → 왼쪽으로 집도록 하여 해결할 수 있다.

라이브락

• 또다른 형태의 라이브니스 장애. 데드락과 유사하다.

• 데드락은 어떤 스레드 집합 내의 모든 스레드가 같은 집합에 속한 다른 스레드에 의해서만 발생할 수 있는 이벤트를 기다리면서 봉쇄되면 발생하지만, 라이브락은 봉쇄되지는 않았지만, 스레드들이 실패한 행동을 계속해서 재시도할 때 발생한다.

• 예를 들어 복도를 두 사람이 지나갈 때, 서로 계속해서 마주쳐서 서로 다른 방향으로 지나가려고 하지만 계속해서 마주치는 경우

데드락의 필요조건

• 데드락은 다음 4가지가 동시에 성립될 때 발생한다. 상점비원으로 외우자.

1. 상호 배제(Mutual Exclusion): 포크 하나는 1명의 철학자만이 동시에 사용 가능하다.

2. 점유와 대기(Hold and Wait): 포크를 다른 철학자가 사용하고 있으면 기다려야 한다. 그리고 본인이 포크를 쥐었으면, 다른 포크를 쥐기까지 놓지 않는다(점유한다).

3. 비선점(NonPreemption): 다른 철학자가 쥔 포크를 빼앗을 수 없다.

4. 원형 대기(Circular Wait): 탁자가 원형이었기 때문에, 원하는 방향이 사이클로 기다리기 때문에 데드락이 발생했다.

데드락의 해결방법

• 해결 방법은 예방 / 회피 / 검출 및 회복 / 무시 가 있다.

1) 예방

• 상/점/비/원 중 하나라도 만족하지 못하면 데드락이 발생하지 않는다는 원칙.

• 상호 배제, 점유와 대기, 비선점의 경우 실질적으로 해소할 수 없다. mutex 락이나 세마포어 같은 리소스는 해당 조건을 반드시 사용해야 하기 때문이다.

• 단, 원형 대기 조건은 이를 무효화하여 데드락을 해결할 수 있는 기회가 있다.
  • 모든 자원에 전체적인 순서를 부여해서 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구할 수 있다.

• 점유와 대기 조건을 해결할 수 있다 가정하고, 스레드가 실행 전 모든 자원을 한꺼번에 요청하고 한꺼번에 할당받도록 하거나, 스레드가 자원을 전혀 안가지고 있을 경우만 자원을 요청하도록 변경할 수 있도록 수정했다고 하면 CPU 이용률이 낮아지거나, 기아 상태가 발생할 수 있다.

2) 회피

• 데드락이 발생하지 않도록 조심해서 자원을 할당하는 방식이다.
  • 안전 상태(시스템이 어떤 순서로든 데드락을 발생시키지 않고 차례로 모두 할당할 수 있는 상태)를 유지하도록 자원을 할당하는 방식이다.

• 대표적으로 은행원 알고리즘이 존재한다.
  • 은행원이 금고에 있는 돈을 고려하여, 돈을 빌려줄 때 그 사람이 돈을 갚을 수 있는 능력을 고려하여 돈을 빌려주는 원리
  • CPU가 프로세스에게 공유 자원을 할당하기 전, 남아 있는 공유 자원의 양을 점검하고, 그 프로세스가 필요로 하는 총 자원의 양을 고려한다.
    • 예를 들어 프로세스 A 가 자원을 조금만 할당시켜줘도 바로 자원을 반납할 수 있으면 A의 할당 우선순위를 높여준다.
  • 또는 프로세스들의 할당 순서가 데드락을 야기하지 않는다는 계산 결과가 나오면 그대로 순서대로 할당한다.
    • 해당 프로세스 순서열을 안전 순서열이라고 한다.

3) 검출 및 회복

• 데드락이 발생할 수 있다고 인정하고, 발생하면 데드락을 해결해주는 방식이다.

• 주기적으로 데드락 발생 여부를 검사하고, 검출되었다면 다음과 같이 회복한다.
  1. 선점(빼앗기)를 통해 회복
     • 희생자 선택, 후퇴, 기아 상태 발생을 고려해서 선점해야 한다.
  2. 프로세스 강제 종료를 통해 회복한다.
     • 모두 중지시키기: 비용이 굉장히 큰 방법이다.
     • 회복이 될 때까지 하나씩 중지: 계속해서 데드락 상태인지 검사해야 하므로 오버헤드가 큰 방법이다.

4) 무시

• 그냥 데드락을 무시하는 방법이다.

• 문제의 빈도나 심각성에 따라 떄때로 선택한다.

---

메모리 관리

• CPU는 PC(Program Counter)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져오는데 그 명령어는 필요한 경우 추가적인 데이터를 더 가져올 수 있으며 반대로 데이터를 메모리로 내보낼 수도 있다.

논리 주소

• CPU가 생성하는 주소

• 사용자 프로그램은 결코 실재적인 물리 주소에 접근하지 않는다.

물리 주소

• 하드웨어 메모리가 직접 취급하는 주소

• 프로그램 실행 중에서는 논리 주소를 물리 주소로 매핑시켜야 하는 데, 이러한 매핑 작업을 주소 바인딩 이라고 하고, MMU(Memory Management Unit)라는 하드웨어 장치가 맡아 실행해주게 된다.

• 전통적으로 메모리 공간에서 명령어와 데이터의 바인딩은 그 바인딩이 이루어지는 시점에 따라 컴파일 타임 바인딩, 로드 타임 바인딩, 실행 시간 바인딩 세가지로 나뉜다.

단편화 (fragmentation)

내부 단편화 (internal fragmentation)

• 메모리 공간을 일정한 크기의 파티션으로 나눴을 때, 들어가는 프로세스가 파티션 크기보다 작아서, 파티션의 공간이 남아 낭비되는 문제.

• 또한, 이미 해당 자리에 프로세스가 할당된 것으로 간주되기 때문에 새로운 작은 프로세스가 들어갈 수 있는 공간이라도 적재할 수 없다.

외부 단편화 (external fragmentation)

• 전체적인 가용공간의 크기를 합치면 새로운 프로세스를 충분히 할당할 수는 있지만, 그 가용공간들이 연속적이지 않아서 프로세스를 할당할 수 없는 문제.

내부 단편화는 가용공간이 프로세스보다 커서 발생하는 문제.

외부 단편화는 가용공간이 프로세스보다 크지만, 연속적이지 않아서 발생하는 문제.

메모리 할당 방식

연속 메모리 할당

• 하나의 프로세스에 필요한 메모리들이 반드시 연속해서 메모리 공간에 위치하는 방식이다.

• 크게 고정 분할 방식과 가변 분할 방식 두 가지 방식이 존재한다.

고정 분할 방식

• 물리 메모리를 고정된 크기의 파티션으로 나누고, 그에 맞춰 프로세스를 적재시키는 방식이다.

• 하나의 파티션에는 하나의 프로세스만 적재한다.

• 원리가 단순하고, 시스템 생성 시 미리 메인메모리가 분할되므로 운영체제의 오버헤드가 줄어든다.

• 하지만 내부 단편화가 발생하고, 외부 단편화가 발생한다. 그리고 낮은 융퉁성으로 인해 동시에 메모리에 올릴 수 있는 프로그램 수가 고정되며, 수행 가능한 프로그램의 크기도 고정된다.

가변 분할 방식

• 메모리에 적재되는 프로그램의 크기에 따라 파티션의 크기와 개수가 동적으로 변하는 방식이다.

• 고정 분할 방식과는 달리 파티션 크기를 조절할 수 있기 때문에 내부 단편화가 발생하지 않고 융퉁성이 있다.

• 외부 단편화 문제가 발생한다.
  • 압축(가변 분할 방식에서 외부 단편화를 해결하기 위해 빈 가용공간들을 압축해 한 곳으로 모으는 방법) 방식으로 해결할 수 있다.
  • 단, 메모리가 대이동 하므로 오버헤드가 매우 크다.

• 동적 메모리 할당 문제(메모리의 가용 공간 중 어디에 프로세스를 적재할 것인지 결정하는 문제)가 발생한다.
  • 배치 알고리즘으로 해결할 수 있다.
    1. 최초 적합(first fit)
       • 메모리를 적재할 수 있는 가용 공간을 탐색하다가, 처음 조건에 맞는 가용 공간에 적재시키는 방법. 시간적으로는 가장 효율적이다.
    2. 최적 적합(best fit)
       • 가용공간을 모두 탐색한 후, 적재할 수 있는 가장 작은 가용공간에 적재하는 방법. 매우 작은 가용 공간이 생길 수는 있으나, 대체적으로 공간적인 면에서 가장 효율적이다.
    3. 최악 적합(worst fit)
       • 가용공간을 모두 탐색한 후, 적재할 수 있는 가장 큰 가용 공간에 적재하는 방법. 나중에 적재하고 남은 가용 공간에 다른 프로세스를 적재할 수 있겠다는 컨셉을 가진다.
  • 일반적으로 (first fit, best fit) > (worst fit) 으로 효율적인 것으로 입증되었다.

• 이러한 외부 단편화와 압축 문제를 해결하기 위해 페이징 방식이 제안되었다.

불연속 메모리 할당

• 하나의 프로세스에 필요한 메모리들이 연속하지 않아도 되는 방식이다.

• 페이징, 세그멘테이션, 페이지드 세그멘테이션 방식이 속한다.

페이징

• 현대 메모리 관리 기법 중 가장 중요한 개념 중 하나로, 가상 메모리 관리 기법 중 하나다.

• 물리 메모리는 프레임이라는 같은 크기 블록으로 나누고, 논리 메모리는 페이지라 불리는 같은 크기의 블록으로 나눈다.

• CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 오프셋(d: offset) 두 개의 부분으로 나뉜다.
  • 페이지 번호는 페이지 테이블을 액세스 할 때 사용한다. 페이지 테이블은 페이지 번호를 프레임 주소로 매핑한다.
  • 페이지 오프셋은 참조되는 프레임 내의 위치를 나타낸다.
  • 두 값을 합쳐 물리 메모리 주소를 참조할 수 있게 되고, MMU가 이를 수행한다.

• 모든 빈 프레임이 프로세스에 할당될 수 있으므로 외부 단편화가 발생하지 않는다.

• 하지만 내부 단편화는 여전히 발생한다. 프로세스의 크기가 항상 페이지 크기의 배수가 될 수 없기 때문.

• 페이지 크기가 작아지면 그에 반비례해서 페이지 테이블의 크기는 커지기에 테이블이 차지하는 공간이 늘어난다.

페이지 테이블

• 논리 주소 단위인 페이지를 물리 주소 단위인 프레임으로 매핑시켜주는 테이블

• [페이지 번호, 오프셋]으로 구성된다.

• 페이지 테이블 엔트리
  • 유효 비트: 해당 페이지에 접근 가능한지 여부. 페이지가 물리 메모리에 존재하면 1, 스왑영역에 존재하면 0
    • 페이지 폴트: 유효비트가 0 인 페이지에 접근하려는 시도
  • 보호 비트: 0이면 읽기만 가능한 페이지, 1이면 읽기와 쓰기가 가능한 페이지
  • 참조 비트: CPU가 해당 페이지에 접근한 적이 있는지 여부. 0이면 한번도 읽거나 쓰기를 한 적이 없는 페이지, 1이면 적재 이후 CPU가 읽거나 쓴 페이지

• 페이징에서는 COW(Copy On Write)가 일어난다.

세그멘테이션 (Segmentation)

• 프로세스의 주소 공간을 의미 단위의 세그먼트로 나눠 물리 메모리에 올리는 기법

• 페이징 분할 단위인 페이지는 크기가 고정적이지만, 세그먼트의 크기는 가변적이다.

• 내부 단편화가 발생하지 않고, 의미있는 단위로 프로그램을 나누기 좋지만 외부 단편화 문제가 발생한다.

• <세그먼트 번호, 오프셋>으로 논리 주소가 이루어지고, 세그먼트 테이블을 이용해 물리 주소를 찾는다.

세그먼트 테이블

• 각 항목이 base, limit을 가지고 있고, 세그먼트 오프셋이 limit을 넘으면 배제된다.

• context switching시 세그먼트 테이블도 업데이트 된다.

페이지드 세그멘테이션 (paged segmentation)

• 페이징과 세그멘테이션의 혼용기법

• 세그멘테이션과 마찬가지로 프로그램을 의미있는 단위인 세그먼트로 나눈다. 그리고 각각의 세그먼트를 일정한 크기의 페이징 집합으로 바꾼다.

• 페이징 단위로 나뉘기에 외부 단편화 문제가 해결되고, 세그먼트 단위로 나뉘기에 공융와 보호가 잘 이뤄져 페이징의 약점이 보완된다.

• <세그먼트, 오프셋>으로 논리 주소가 나뉘고, 오프셋이 상위비트/하위비트로 나뉜다.
  • 상위 비트는 세그먼트내의 페이지 번호, 하위 비트는 페이지 내 오프셋을 의미한다.

• 외부의 세그먼트 테이블, 내부의 페이지 테이블 2개 테이블이 사용된다.

• 세그먼트로 찾아가면 <세그먼트 길이, 페이지 테이블 시작 주소>가 있다. 그러면 다시 페이지 테이블을 상위비트 참조, 참조한 값과 하위비트로 물리 주소를 찾아낸다.

PTBR (Page Table Base Register)

• CPU내 페이지 테이블 베이스 레지스터

• 페이지 테이블이 메모리에 있기 때문에 해당 페이지 테이블의 메모리 위치를 가리킨다.

PTLR (Page Table Length Register)

• 페이지 테이블의 크기를 나타내는 레지스터

TLB (Translation Lookaside Buffer)

• 페이지 테이블의 캐시 메모리.

• PTBR을 사용하면 결과적으로 두 번의 메모리 접근(페이지 테이블 접근 + 실제 메모리 주소 접근)이 소모되기에 이를 해결하기 위한 하드웨어 캐시

• TLB 히트: 찾으려는 페이지 번호가 TLB에 있는 경우

• TLB 미스: 찾으려는 페이지 번호가 TLB에 없는 경우
  • context switching시 PCB 뿐 아니라 TLB도 교체가 일어난다.

• ASID 지원이 없으면 context switching시 PCB 뿐 아니라 TLB 플러시가 일어난다.

공유 페이지

• 여러 프로세스에 의해 공유되는 코드를 담는 페이지

• 공유 코드: 메모리 공간을 효율적으로 사용하기 위해 여러 프로세스에 의해 공통적으로 사용될 수 있도록 작성된 코드. 예를 들면 libc 같은 C언어 라이브러리가 있다.

• 공유 페이지는 물리 메모리에 하나만 적재되어 메모리를 효율적으로 사용할 수 있게 된다.

• 따라서 다른 프로세스라 하더라도 공유 페이지의 번호는 같게 표시된다.

• 이와 반대되는 개념은 private page

계층적 페이징

• 페이지 테이블에 계층을 두는 방법

• 프로그램의 크기가 매우 크면 페이지 테이블의 크기도 커지기 때문에 메모리에 차지하는 공간이 많아지게 된다.

• 이를 해결하기 위해 외부 페이지 테이블과 내부 페이지 테이블을 나눠 저장하면 메모리를 아낄 수 있다.

해시 페이지 테이블

• 주소 공간이 32비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 사용한다.

• 해시 페이지 테이블의 각 항목은 연결 리스트를 가지며, 충돌을 일으켜서 모두 해당 항목으로 해시되는 원소들이 연결되게 된다.

• 가상 주소 공간으로부터 페이지 번호가 오면 해싱을 하고, 그것으로 해시 페이지 테이블에서 연결리스트를 따라가며 첫번째 원소와 가상 페이지 번호를 비교해본다. 일치할 때까지 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.

역 페이지 테이블

• 보통 프로세스는 각자 하나씩 페이지 테이블을 가지고 또 페이지 테이블은 프로세스가 사용하는 페이지마다 하나의 항목을 가진다.
  • 그러나 이 방법의 문제는 각 페이지 테이블 항목의 개수가 수백만 개가 될 수 있다는 점이다. 이를 해결하는 방법이 역 페이지 테이블이다.
  • 모든 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체에 대해 공용의 역페이지 테이블을 단 하나를 두는 방법이다.

• 물리 주소인 프레임에 각 프로세스들의 논리 주소 페이지를 매핑시키는 방법이다.

• 역페이지 테이블의 항목은 프로세스 id(pid)와 그 프로세스 내 논리적 페이지 번호(p)를 가진다.

• 논리주소는 <pid, p, d>로 들어온다.

• 역 페이지 테이블은 공유 메모리를 사용할 수 없다.
  • 왜냐하면 일반적인 페이징은 프로세스마다 공유 페이지가 있기 때문에 페이지 → 동일한 프레임으로 매핑할 수 있지만, 역 페이지 테이블은 물리 페이지마다 하나의 가상 페이지 항목만 있기 때문이다.

• 역 페이지 테이블은 주소 변환 요청이 들어올 때 pid, p를 모두 만족하는 곳을 완전탐색해야 하기 때문에 시간적으로 매우 비효율적이다.

스와핑

• 프로세스 또는 프로세스의 일부분은 실행 중 임시로 백업 저장장치(backing store)에 내보내어 졌다가 실행을 계속하기 위해 다시 메모리로 되돌아 올 수 있다.

• Swap Out: 메모리에서 스왑영역으로 내보내는 것

• Swap In: 스왑영역에서 메모리로 들여보내는 것

• 페이지 단위로 스와핑 하는 것이 현대 컴퓨터의 대부분이지만, 모바일 시스템의 경우 어떠한 형태의 스와핑도 지원하지 않는 것이 일반적이다. 왜냐하면 플래시 메모리의 쓰기 횟수가 정해져 있기 때문.
  • 스와핑을 사용하는 대신 가용 메모리가 정해진 임계값보다 떨어지면 iOS의 경우 할당된 메모리를 자발적으로 반환하도록 요청한다.
    • 코드 영역과 같은 읽기 전용 데이터는 필요에 따라 메인 메모리에 제거되고 나중에 플래시 메모리로부터 적재될 수 있지만, 스택 영역과 같이 변경되는 데이터는 제거될 수 없다. 충분히 메모리를 반환시키지 못하는 앱은 iOS 운영체제가 종료시킬 수 있다.

---

가상 메모리

• 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법

• 가상 메모리 기법을 활용하면 사용자 프로그램이 물리 메모리보다 커져도 된다.

요구 페이징 (demand paging)

• 프로세스를 메모리에 적재할 때 모든 페이지를 적재하지 않고 필요한 페이지만 메모리에 적재하는 기법을 말한다.

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.

2. 해당 페이지가 현재 메모리에 있으면 (유효 비트 1) CPU는 페이지가 적재된 프레임에 접근

3. 해당 페이지가 현재 메모리에 없으면 (유효 비트 0 = 스왑 영역에 존재) 페이지 폴트가 발생된다.

4. 페이지 폴트 처리 루틴이 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.

5. 다시 중단되었던 명령어를을 수행한다.

• 순수 요구 페이징: 어떤 페이지가 필요해지기 전에는 결코 그 페이지를 메모리로 적재시키지 않는 것을 말한다.

• 요구 페이징 기법이 잘 작동하려면 페이지 교체, 프레임 할당 두 가지가 매우 중요하다.

• 익명 메모리: 스택 및 힙과 같은 영역에서 사용. 특정 파일과 상관없이 메모리 그 자체로 존재하는 영역.

가용 프레임 리스트

• 가용 프레임의 풀을 말한다.

• zero-fill-on-demand 기법: 프레임이 할당되기 전, 내용을 모두 0으로 채워서 이전 내용을 지우는 것

페이지 교체

• 메모리 공간은 한정적이기 때문에, 당장 필요한 페이지를 메모리에 적재하기 위해서는 메모리에서 당장은 불필요한 페이지를 스왑 영역으로 내보내야 하는데 이를 페이지 교체라 한다.

• 빈 프레임이 없는 경우, 디스크를 두 번(한 번은 프레임을 비울 때, 다른 한 번은 읽어들일 때) 접근해야 하는 데, 이러면 오버헤드가 커진다.
  • 오버헤드를 줄이기 위해 변경 비트(modify bit)를 사용해서 감소시킬 수 있다.
  • 변경 비트는 CPU가 페이지 내 어떠한 바이트라도 쓰면 페이지가 변경되었다고 표시한다. 변경 비트를 확인해서 변경되었다고 표시된 페이지라면 디스크로 기록시키고, 그렇지 않으면 저장할 필요가 없기에 디스크로 접근할 필요가 없다.

• 전역 교체: 페이지 교체 대상이 같은 프로세스가 아니어도 되고, 메모리 전체의 페이지에서 찾는 것
  • 해당 프로세스의 페이징 뿐만 아니라, 다른 프로세스의 페이징 동작에도 영향을 받는다.
  • 일반적으로 지역 교체방식 보다 성능이 좋다고 알려져 있다.

• 지역 교체: 페이지 교체 대상이 같은 프로세스 내에서 찾는 것
  • 다른 프로세스의 페이징 동작에는 영향을 받지 않지만, 오래된 페이지가 아님에도 교체될 수 있기 때문에 성능이 떨어진다.

• 리퍼: 가용 메모리 양을 최소 임계값 이상으로 유지하는 루틴

• 페이지 교체 알고리즘: 어떤 페이지를 메모리에서 내보낼지 결정하는 알고리즘
  • 페이지 폴트 횟수를 줄일 수록 좋은 알고리즘
  • FIFO, SCR, Optimal, LRU, LFU, Clock이 있다.

FIFO

• 가장 간단하게 메모리에 먼저 들어온 페이지부터 스왑아웃 시키는 알고리즘

• 앞으로 사용될 페이지가 나갈 수 있기 때문에 비효율적이다.

• Belady의 모순: 프로세스에 프레임을 더 주었는데 오히려 페이지 폴트율이 증가하는 현상.
  • 보통 프로세스에 더 많은 프레임을 할당하면 성능이 좋아질 것으로 예상되지만 그러한 가정이 항상 옳은 것은 아님.

SCR (Second Chance Replacement)

• FIFO를 개선시킨 알고리즘으로, 메모리에 먼저 들어온 페이지부터 스왑아웃 시키되, 한 번의 기회를 준다.

• 해당 페이지가 언제 또 참조될 지 모르기 때문이다.

• 나가야 할 페이지의 참조비트가 1인 경우, 우선 스왑아웃을 시키지 않고 참조 비트 값을 0으로 만들고, 그 이후에 참조 비트 값이 0이 된 상태이면, 그제서야 스왑아웃 시킨다.
  • 개선된 SCR (Enhanced SCR)
    • 참조 비트와 변경 비트를 함께 사용한 알고리즘.
    • 두 비트가 모두 0인 프레임이 가장 교체하기 좋은 프레임이다.

Optimal (최적 페이지 교체)

• 이론 상 가장 좋은 알고리즘으로, 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다.

• 하지만 앞으로 해당 페이지가 얼마나 참조될지 미리 아는 것은 불가능에 가까워 이론적인 비교대상으로 사용된다.

LRU (Least Recently Used)

• 사용한지 가장 오래된 페이지를 내보낸다.

• 미래 시간 대신 과거 시간을 최적 교체 대상으로 보는 것.

• 알고리즘을 counter, stack 등으로 구현할 수 있다.
  • 두 가지로 구현하는 방법 모두 TLB 레지스터 이상의 하드웨어 지원이 있어야 한다. 그렇지 않고 두 가지를 갱신하는 작업을 인터럽트를 사용해 처리하게 되면 최소 10배 이상 메모리 참조 속도가 느려진다.

LFU (Least Frequently Used)

• 가장 적게 사용한 페이지를 교체하는 방법

• 페이지 중에서 참조 횟수가 가장 적은 페이지를 내보낸다.

MFU (Most Frequently Used)

• LFU와 반대로 가장 작은 참조 횟수의 페이지가 가장 최근에 참조된 것이므로, 가장 많은 참조 횟수의 페이지를 교체하자는 방법

Clock

• SCR을 원형 큐로 구현한 알고리즘

• 기준 점인 클락 핸드가 시계방향으로 돌아가며, 유효 비트가 1이면 0으로 교체한 뒤 기회를 주고 다음 페이지로 넘어간다.

• 현재 페이지의 유효 비트가 0이면, 그 페이지를 스왑아웃 시킨다.

프레임의 할당

• 각 프로세스들이 효율적으로 수행되는 데 필요한 프레임 수가 서로 다르기에, 어떤 프로세스에 얼만큼의 프레임을 할당하는 지 결정하는 것이 중요하다.

정적 할당 방식

• 프로세스를 실행하기 전 미리 프레임 수를 할당하는 방식

• 균등 할당
  • 모든 프로세스에 균일하게 프레임 수를 할당하는 비효율적 방식

• 비례 할당
  • 프로세스 크기에 비례해서 프레임 수를 할당하는 방식, 하지만 프로세스 크기와 필요한 프레임 수가 반드시 비례하지는 않기 때문에 그리 효율적이진 않다.

동적 할당 방식

• 프로세스 실행 중 유동적으로 프레임 수를 변경하며 할당하는 방식

스레싱 (Thrashing)

• 과도한 페이지 교체로 인해, 프로세스 자체 일을 수행하는 것보다 페이지 교체를 하는 데 CPU를 더 많이 사용하여 다중 프로그래밍 지수가 높아짐에도, CPU 사용률이 떨어지는 것.

• 근본적인 이유는 프로세스에 할당된 프레임 수가 적기 때문이다.

• 일반적인 멀티 프로세스에서 동시에 실행하는 프로세스가 많을 수록 CPU를 바쁘게 일하게 만드는 것이기에 CPU 사용률이 높아지지만, 어느 임계점이 넘어가면 프로세스마다 할당해줄 수 있는 프레임 수에 한계가 오고, 페이지 교체가 너무 많이 일어나기 때문에 CPU 사용률이 낮아진다.
  • 따라서 해당 임계점에서는 CPU 사용률을 높이고, 스레싱을 중지하기 위해 다중 프로그래밍 정도를 낮춰야 한다.

• 스레싱을 방지하기 위해 워킹셋 알고리즘과 페이지 폴트 빈도 알고리즘이 있다.

워킹셋

• 지역성을 토대로 함

• working set = 단위시간 동안 사용한 페이지 집합

• 단위 시간에 워킹셋 수만큼 유동적으로 프레임 수를 할당한다.

페이지 폴트 빈도

• 페이지 폴트가 매우 많이 발생 → 프레임 수가 부족하므로 프레임 수를 늘리기

• 페이지 폴트가 적게 발생 → 프레임 수가 넘친다는 뜻이므로 프레임 수를 줄이기

참고: https://velog.io/@heyksw/CS-운영체제-pf3026ep, 공룡책 운영체제 10판

Uploaded by N2T