개발자 Lim

내부 단편화

• 할당된 메모리 블록이 실제로 사용되는 데이터보다 크기 때문에 낭비 공간이 생기는 문제
• 페이지 프레임의 크기를 줄이면 내부 단편화는 덜 될지 몰라도 페이지의 갯수가 늘어나기 때문에 페이지 테이블의 크기는 커진다.
  • 메모리와 CPU 부담 증가

페이지 테이블

• 가상 메모리 공간(페이지)와 물리 메모리 공간(페이지)의 대응 정보를 저장하는 데이터 구조
  • 프레임 번호(Frame Number): 해당 가상 페이지가 매핑된 물리적 페이지 프레임의 번호
  • 프레젠트 또는 벨리드 비트(Present or Valid Bit): 해당 가상 페이지가 현재 메모리에 로드되어 있는지(즉, "프레젠트") 또는 유효한지(즉, "벨리드")를 표시하는 비트 값
  • 프로텍션 비트(Protection Bits): 해당 페이지에 대한 접근 권한을 표시하는 비트 값
  • 수정 비트(Modified Bit): 해당 페이지가 프로세스에 의해 수정되었는지를 나타내는 비트 값
  • 참조 비트(Referenced Bit): 해당 페이지가 최근에 접근되었는지를 나타내는 비트 값
• 데이터 저장 작업 수행시 활용되는 레지스터들
  • PTBR(Page-table base register): 현재 실행 중인 프로세스의 페이지 테이블의 시작 위치를 가리키는 포인터를 저장하는 레지스터
    • 활용: 가상 주소를 물리 주소로 변환하는 작업을 수행
  • PTLR(Page-table length register): 메모리 관리를 위해 현재 실행 중인 프로세스의 페이지 테이블의 길이를 저장하는 레지스터
    • 활용: 주소 변환 시 참조하려는 가상 주소가 유효한 범위 내에 있는지 확인하는 작업을 수행
• 모든 데이터/명령 접근은 2번의 메모리 접근이 필요
  • (가상 주소가 매핑된 물리적 주소 찾기)페이지 테이블 접근 1번
  • (찾아낸 물리적 메모리 주소에서 실제 데이터 또는 명령 가지고 오기)데이터/명령 접근 1번
  • 특별한 빠른 검색 하드웨어 캐시(연관 메모리, TLBs)로 해당 문제 해결 가능

TLB(Translation Lookaside Buffer)

• 매우 빠른 접근 시간을 갖는 캐시로, 최근에 사용된 페이지 주소 변환을 저장 이후 CPU가 가상 주소를 참조할때 먼저 TLB를 확인하여 해당 정보를 가지고 있다면 가상 주소를 통해 물리적 주소를 알아낼 필요없이 단번에 물리적 주소에 접근 할 수 있게 된다.
• 페이지 테이블의 일부를 캐시하여 CPU의 메모리 접근 속도를 향상시키는 도구

페이지 테이블 종류

• 단일 레벨 페이지 테이블 (Single-Level Page Table): 가장 기본적인 형태의 페이지 테이블로, 각 가상 페이지에 대해 한 개의 페이지 테이블 항목이 존재
• 다단계 페이지 테이블 (Multi-Level Page Table): 페이지 테이블이 여러 단계로 나뉘어 있어서, 대용량 메모리를 관리하는 데 더 효율적 각 단계에서 부분적인 가상 주소가 인덱스로 사용되어 다음 단계의 테이블에 대한 참조를 제공한다. 즉 여러 단계를 거쳐서 물리 메모리 주소에 접근하는 페이지 테이
• 역페이지 테이블 (Inverted Page Table): 각 물리 메모리 페이지에 대한 엔트리를 하나만 가짐으로써 전통적인 페이지 테이블보다 테이블의 크기가 작은 테이블을 구성
• 세그먼테이션 테이블 (Segmentation Table): 가상 메모리를 여러 세그먼트로 나누는 메모리 관리 기법 각 세그먼트는 다양한 크기를 가질 수 있으며, 일반적으로 코드, 데이터, 스택 등의 다른 유형의 정보를 구분하는 데 사용
• 해시된 페이지 테이블 (Hashed Page Table): 이 구현 방법은 역페이지 테이블과 비슷하며, 주로 대용량 주소 공간을 관리하기 위해 사용 해시된 페이지 테이블은 가상 페이지 번호를 해싱하여 페이지 테이블 항목을 찾는다.

배경지식

• 프로그램이 실행되기 위해서는 메모리로 반입되어 프로세스 내에 배치되어야 한다.
• 메인 메모리와 레지스터는 cpu가 직접 접근할 수 있는 유일한 저장장치이다.
• 메모리 하드웨어는 주소, 읽기 요청, 쓰기 요청이 가능해야 한다.
• 메인 메모리와 CPU레지스터 사이에 캐시가 존재한다.

메모리 주소 바인딩 시점 3가지

• 컴파일 시간 바인딩: 컴파일시 메모리 주소를 정하고 생성 되는 이진코드
  • 이는 절대 코드라고 한다
  • 만약 해당 위치가 변경되어야 한다면 다시 컴파일 되어야 한다.
• 적재 시간 바인딩: 프로세스가 메모리 내 어디로 올라오게 될지 컴파일 시점에서 알 수 없을 때 컴파일러가 만드는 이진 코드
  • 재배치 가능 주소
  • 메인 메모리로 실제 적재되는 순간에 바인딩이 이루어짐
• 실행 시간 바인딩: 실행 중에 메모리 위치 변경(메모리 참조가 일어 날때)
  • 특별한 하드웨어가 필요하다.

사용자 프로그램 처리의 여러 단계 

논리 대 물리 주소 공간

• 논리 주소: CPU에 의해 생성되는 가상 주소 (논리 주소는 연속적으로 할당)
• 물리 주소: 메모리 장치에서 인식되는 주소 (물리 주소는 연속적으로 할당 되지 않음 그때 그때 빈 공간 할당)
• 프로그램 실행 중에는 가상 주소를 물리 주소로 바꾸어주어야 한다.
  • 하드웨어 장비 메모리 관리기(MMU) 를 통해 작업
    • 재배치 레지스터를 사용하여 CPU와 메모리 사이에서 주소를 변환
    • 논리적인 주소를 매우 빠른 속도로 물리적인 주소로 바꿔주는 장치               
• 컴파일 시간과 적재 시간 바인딩 기법에서는 동일하지만 실행 시간 바인딩 에서는 서로 다르다.
• 사용자 프로그램은 논리 주소만을 다루고 절대로 실제 물리 주소를 다룰 수 없다.

동적 링킹, 정적 링킹

• 정적 링킹: 로더가 시스템 라이브러리와 프로그램 코드를 결합하여 이진 프로그램 이미지 생성 정적 라이브러리를 이용할 때 사용
• 동적 링킹: 실행 시간까지 링킹이 연기됨 공유되는 라이브러리를 이용할때 사용
  • 루틴이 필요한 경우에만 적재되기 때문에 선호되는 방식

기본 스와핑

• 프로세스가 메모리에서 보조 저장장치로 스왑(아웃, 인) 되는 것
  • 스왑 아웃(롤 아웃): 메모리 → 보조 저장장치
  • 스왑 인(롤 인): 보조 저장장치 → 메모리
• 총 전송 시간은 스왑 되는 메모리의 양의 비례한다.
• 스왑 아웃된 프로세스는 다시 스왑 인 될 때 같은 물리 주소에 적재되지 않을 수도 있다.
• 현대 운영체제는 기본 스와핑을 사용하지 않는다.
  • 초기 운영체제는 메모리가 부족하는 문제가 잦고 이를 해결할 고급 기법이 존재하지 않았기에 메인 메모리를 보조 저장 장치로 옮길 필요가 있었다.

스와핑의 메모리 효율

• 메모리 사용 효율이 좋지 않아 이를 해결 하기 위해 페이징 기법이 생겼다.

스와핑을 포함한 문맥 교환 시간

• 프로세스의 크기에 비례하여 문맥 교환 시간이 길어진다.
• 함부로 Swap out을 한다면 데이터 일관성을 해칠 수 있기 때문에
  • 이중 버퍼링 기법(작업을 따로 버퍼에 저장하고 끝나면 반영하는 방식)을 사용하게 되어 (오버 헤드)문맥 교환 시간이 늘어나게 된다.
• 다음에 실행시킬 프로세스가 메모리에 없다면 프로세스 하나를 스왑 아웃 시키고 목표 프로세스를 스왑인 해야 한다.
• 추가 제약
  • 기존 프로세스의 I/O 작업이 끝나지 않았다면 스와핑이 불가능 하다.

모바일 시스템에서의 스와핑

• 보통은 지원되지 않음
  • 플래시 메모리 기반으로 적은 공간을 가지고 쓰기 사이클의 횟수가 제한적
• 메모리 확보를 위해 다른 방법 사용
  • IOS에서는 앱이 자발적으로 메모리를 반환할 것을 요구한다.
    • 메모리 확보에 실패하면 앱을 종료시킴
  • Android에서는 IOS와 마찬가지로 가용 메모리가 적을 경우 앱을 종료시키지만 추가로 빠르게 재시작 시킬 수 있도록 앱 상태를 플래시에 기록한다.

연속 메모리 할당

• 메인 메모리는 운영체제와 사용자 프로세스 모두 지원해야 한다.
• 메인 메모리를 2개로 분할
  • 상주하는 운영체제, 보통 인터럽트 벡터와 함께 메모리 앞쪽에 위치
  • 사용자 프로세스는 그 이후 영역에 배치한다

다중 분할 할당

• 분할의 개수가 다중 프로그래밍의 정도를 제한
• 가변분할: 효율을 위하여 크기를 조절
• Hole: 가용 메모리 블록에서 빈 부분
  • 프로세스가 도착할 때 프로세스를 포함할 만큼 큰 Hole에서 메모리를 할당 받는다.

동적 메모리 할당 문제

• 최초 적합(First-fit): 충분히 큰 최초의 hole을 할당
• 최적 적합(Best-fit): 충분히 큰 가장 작은 hole을 할당
  • 시간은 오래 걸리지만 메모리를 효율적으로 관리 가능
• 최악 접합(Worst-fit): 가장 큰 hole을 할당
• 최초 적합과 최적 접힙이 최악 적합 보다 속도와 공간 이용률 측면에서 더 좋다.

단편화

• 외부 단편화: 프로세스들이 메모리에 적재되고 제거되면서 생성된 작은 자유 공간（ｈｏｌｅ）들
  • 밀집(compaction)작업으로 줄이는 것이 가능: 주 기억 장치에서 사용 되지 않은 공간을 한 곳으로 모으는 것
• 내부 단편화: 홀에서 다른 프로세스에게 공간을 할당 하고 남은 공간
• 최초 적합에 대해 N 블록이 할당된다면 0.5N개의 블럭이 단편화로 사용할 수 없게 된다. (50% 규칙)

세그먼테이션

• 가변적인 메모리 공간(세그먼트)를 관리하는 기법
• 세그먼트 구조
  • <segment-number, offset> 2tuple 구조
• 세그먼트 테이블 (메인메모리에 존재하는 세그먼트 정보가 새겨진 테이블)
  • 물리적 주소와 논리적 주소가 둘다 연속적이지 않기 때문에 대응시켜주는 표가 필요하기 때문에 존재.
  • 세그먼트가 메인메모리에 존재한다면 유효 세그먼트 그렇지 않다면 불법 세그먼트
  • read/write/execute 특권 정보

페이징

• 크기가 고정적인 메모리 공간을 관리하는 기법
• 페이지 테이블을 통해 논리적 주소에서 물리적 주소를 찾아간다.
• 평균적으로 n/2의 크기가 낭비가 된다.
• 주소변환 기법: (비트 구성(32) = 페이지 크기(n) + 페이지 갯수(32-n))
  • Page offset: 페이지 크기가 커진다면
    • 페이지 크기가 클수록 입출력의 속도가 빨라진다.
    • 가용 공간이 늘어난다.
    • 남는 공간이 많이 생기게 된다. (내부 단편화가 심해진다)
  • Page number: 페이지 갯수

EDF: Earliest Deadline First 스케줄링

• 마감시간이 빠를수록 높은 우선순위를 부여
• 마감시간이 늦을수록 낮은 우선순위를 부여

Proportional Share 스케줄링

• 전체 시간 T중에서 각 그룹별로 할당하는 시간을 다르게 하여 스케줄링 하는 것
• 과정
  • 전체 T만큼의 지분이 시스템의 모든 프로세스에게 할당된다
  • N 지분을 요청한 프로세스만이 승인된다(N<T)
  • 각 프로세스는 전체 처리기 시간의 N/T 만큼 할당 받는다.

POSIX 실시간 스케줄링

• SCHED_FIFO: FIFO 큐와 FCFS 정책을 사용하는 스케줄링
• SCHED_RR: 라운드로빈 방식을 사용하는 스케줄링

운영체제 사례들

• Linux 스케줄링: 선점형, 우선순위 기반, 항상 상수 시간이 걸리는 O(1) 스케줄링 사용, 높은 우선순위가 큰 시간 할당량 q를 받음
  • 완전 공정 스케줄러(Completely Fair Scheduler, CFS)
  • 실시간 프로세스의 우선순위는 변화 하지 않지만 (0~99)고정
  • 일반 프로세스의 우선순위 값은 변화한다. NICE (+100~+140)동적 (희생: 본인의 우선순위를 일부로 낮춤으로써 다른 프로세스가 먼저 실행 될 수 있도록 함)
  • 우선순위가 높은 프로세스는 가상시계를 통해(virtual run time) 적은 주기를 할당한다. 
  • 리눅스는 숫자가 작을 수록 우선순위가 높다.

• windows 스케줄링: 선점형, 우선순위 기반, 디스패처가 스케줄러이다, 가변클래스(1~15), 실시간 클래스(16~31) 총 32단계 우선순위 배열로 구성 
  • 숫자가 클수록 우선순위가 높다.
  • real-time (31~16)
  • high (15~1)
  • above normal (15~1)
  • normal(15~1)
  • below normal (15~1)
  • idle priority (15~1)

• Solaris 스케줄링: 우선순위 기반 스케줄링, 6개의 스케줄링 클래스
  • 숫자가 클수록 우선순위가 높다. 
  • Real time (RT): 우선순위 1
  • System (SYS): 우선순위 2
  • Time sharing (TS): 우선순위 3, 다단계 피드백 큐를 사용
  • Interactive (IA): 우선순위 3
  • Fair Share (FSS): 우선순위 3
  • Fixed priority (FP): 우선순위 3

알고리즘 평가

• 결정론적 모델링
  • 분석적 평가의 한 부류
  • 특정 부하를 미리 정해 놓고 그 부하에 대한 각 알고리즘의 성능을 측정한다
  • 결정론적 평가
    • 각 알고리즘에 대해 평균 대기 시간의 최소 값을 구한다.
    • 간단하고 빠르지만 정확한 입력 수치를 필요로 하고 단지 그 입력에 대해서만 해당된다는 점이다

큐잉 모델

• 프로세스의 도착과 CPU와 I/O 버스트를 확률적으로 설명한다.
  • 보통 지수 분포를 가정하여 평균으로 기술한다.
  • 평균 처리량, 이용률, 대기 시간 들을 계산한다.
• 컴퓨터 시스템은 서버의 네트워크로 볼 수 있으며 각 서버는 대기 프로세스를 넣을 큐를 가진다.

시뮬레이션

• 제한적인 큐잉 모델을 대신하기 위해 고려됨
• 컴퓨터 시스템의 프로그램 모델
• 과정
  • 확률에 기초한 랜덤 넘버 발생
  • 수학적 혹은 경험적으로 정의된 분포
  • 실제 시스템의 이벤트를 차례대로 기록한 추적 테이프

Windows의 동기화

• 단일 처리기 시스템에서는 인터럽트 마스크를 사용
• 다중 처리기 시스템 에서는 스핀락을 사용
  • 스핀락을 사용하는 스레드는 절대 선점되지 않음
• dispatcher objects 제공
  • 뮤텍스
  • 세마포
  • event 및 타이머

리눅스의 동기화

• 버전 2.6 이전에는 비선점형 커널을 사용
• 이후 버전에서는 선점형 커널을 사용
• 지원도구
  • 스핀락: 단일 처리기 에서는 스핀락을 획득 하고 방출 하는 것이 커널 선점을 불가능하게하고 가능케 하는 것으로 바뀐다.
  • 세마포
  • 원자적 integer형
  • reader-writer 락

Solaris의 동기화

• 지원도구
  • turnstiles(우선순위 상속 프로토콜)
  • 적응형 뮤텍스
    • 표준 세마포 스핀락
    • CPU 바쁜 대기
  • 조건변수
  • readers-writers 락

Pthreads의 동기화

• 지원도구
  • 뮤텍스
  • 조건변수
• 지원 불가능한 확장 도구
  • reader-write locks
  • spinlocks

대처 방안들

• 트랜잭션 메모리: 메모리 읽기 쓰기 연산의 원자적인 연속적 순서
  • 한 트랙잭션의 모든 연산이 완수되어야만 확정
  • 만약 그렇지 못 한다면 상태 rollback
  • 소프트웨어 하드웨어로 구현
    • 소프트웨어 트랜잭션 메모리(STM)
    • 하드웨어 트랜잭션 메모리(HTM)
• OpenMP: 공유메모리 환경에서 병렬 프로그램을 지원하는 언어
• 함수형 프로그래밍 언어: 변수값이 변하지 않기 때문에 임계영역 문제를 고민하지 않아도 되는 언어

정의

• 프로세스 동기화를 위해서 각 프로세스 들이 접근시 다른 프로세스의 접근을 막아야 하는 코드 영역을 임계 구역이라 한다.
• 동기화가 필요한 이유: 만약 여러개의 프로세스 또는 스레드가 동시에 접근 하면 데이터 불일치가 발생 할 수 있기 때문이다.

임계 구역 해결안의 필요 조건

• 상호 배제(mutual exclusion): 한 프로세스가 임계구역에서 실행되면 다른 프로세스는 임계구역에 접근할 수 없어야 한다.
• 진행(progress): 모든 프로세스가 언젠가는 해당 임계 구역에 접근 할 수 있음을 보장 해 주어야 한다.
• 한정된 대기(bounded waiting): 각 프로세스들은 임계 영역에 진입 할 수 있는 횟수에 한계가 있어야 한다.

피터슨 해결안

do{
	flag[i] = true; // 진입여부
	turn = j; // 준비여부
	while(flag[j] && turn == j); 
		//critical section
	flag[i] = false;
		//remainder section
}while(true);

• 특정 변수를 사용하여 프로세스 별로 임계구역에 진입할 순번을 정한다.
• 상호배제, 진행, 한정된 대기 모두 지켜진다.
• 조건이 충족 될 때 까지 대기해야함

하드웨어적 동기화

// 순차적인 아닌 한번에 해당 명령이 실행
boolean test_and_set(boolean *target){
	boolean rv = *target;
	*target = true;
	return rv
}

• 원자적으로 교환 할 수 있는 특별한 하드웨어 명령어
• 과정
  • 메모리 검사 후 값을 지정
  • 두 메모리 워드 교환

Mutext Locks

do{
	get_Rock();
		//critical section
	release_Rock();
}while(true);

• 한 스레드가 임계영역에 진입 시 문을 잠그고 임계영역을 빠져나올시 다시 문을 여는 방식
• 단일 스레드와 공유 자원 간 상호 작용을 제어하는 데 사용
• 가용해지길 기다리는 프로세스들이 계속 회전하고 있기 때문에 스핀락이라 불리운다.
  • 락을 기다리는 동안 상당한 시간을 소모하는 문맥 교환이 전혀 필요하지 않다는 장점을 가진다.

Semaphores

• 뮤텍스와 유사하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화 할 수 있는 방법을 제공하는 강력한 도구
• 뮤택스와의 차이점은 정해진 수 만큼 한 번에 여러 개의 스레드가 공유자원에 접근 할 수 있도록 허용한다는 것
• 여러 개의 스레드와 공유 자원 간 상호 작용을 제어하는 데 사용

Monitors

• 고급 언어에서 사용되는 동기화 메커니즘
• 객체 지향 프로그래밍에서 상태(state)와 동작(operation)을 함께 캡슐화한 객체(object)에 대한 접근 제어를 제공하는 추상화된 데이터 타입
• 락과 조건 변수(condition variable)를 함께 사용하여 공유 자원에 대한 상호 배제 및 조건부 실행(conditional execution)을 지원한다.

DeadLock

• 두 개 이상의 프로세스 서로서로가 필요한 자원을 가지고 자원을 반환하기를 기다리는 상황 교착상태라고도 한다.
• 교착상태가 일어나는데 필요한 조건들
  • 상호 배제(유일하게 예방 불가능): 한 번에 한 프로세스만이 해당 자원을 사용할 수 있는 경우
  • 점유하며 대기: 프로세스가 최소 하나의 자원을 점유한 채 대기 하는 것 
  • 비선점: 자원을 선점 할 수 없는 것(중간에 자원을 뺏어 올 수 없는 것)
  • 순환 대기: 순환적으로 p1은 p2가 점유한 자원을 대기하는것 이 반복되는 것
• 교착상태 처리 방법
  • 교착상태를 예방하거나 회피하는 프로토콜 사용
  • 교착상태를 허용한 다음에 회복
  • 문제를 무시하고 발생하지 않은 척 한다.
• 교착상태가 발생하지 않도록 하는 방법
  • 예방: 필요조건 중 하나가 성립되지 않도록 보장한다
  • 회피: 프로세스가 일생동안 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구하고 운영체제가 해당 정보를 바탕으로 각 프로세스의 요청과 방출을 고려한다.

정의

• 일반적으로 운영체제에 대한 완벽한 정의는 존재하지 않음
• 컴퓨터 사용자와 컴퓨터 하드웨어 사이에서 중개를 하는 프로그램
• 자원을 제어하고 할당하는 공통 기능을 하나의 소프트웨어로 통합한 것

컴퓨터 시스템 구조

• 하드웨어: cpu, I/O 장치
• 운영체제: And, IOS, Window, Mac
• 응용프로그램: 메모장
• 사용자

운영체제가 하는 일

• 사용자 관점: 사용의 편의성 제공
• 시스템 관점: 자원 할당자, (i/o, 사용자 프로그램) 제어 프로그램
  • 프로세스 관리
  • 메모리 관리
  • 저장장치 관리
  • 보호와 보안

컴퓨터 시스템 연산

• 하드 디스크(영구 저장) → 메인메모리(RAM 휘발성) → 캐쉬(SRAM) → cpu 레지스터(실행)
• 사건 발생
  • 하드웨어: 인터럽트
  • 소프트웨어: 시스템 호출(System Call)
• 다중 처리기 시스템
  • 비대칭형 클러스터링: 한 컴퓨터(긴급 대기)만 감시하는 역활을 맡고 나머지는 실행
  • 대칭형 클러스터링: 모든 컴퓨터가 서로 서로를 실행하면서 감시

운영체제 서비스

• 사용자 인터페이스
• 프로그램 실행
• 입출력 연산
• 파일시스템 조작
• 통신
• 오류 탐지
• 자원 할당
• 회계
• 보호와 보안

• 사용자 스레드와 커널 스레드를 구분
• 스레드가 지원될 경우 스케줄링 대상은 프로세스가 아닌 스레드
• LWP에서 실행되는 사용자 스레드 스케줄링.
  • 범위: PCS 프로세스 경쟁 범위
• 카널 스레드 스케줄링
  • 범위: SCS 시스템 경쟁 범위

Pthread 스케줄링

• API를 사용하여 스레드를 생성시 PCS, SCS를 지정해야함

다중 처리기 스케줄

• 동일한 처리기: CPU가 기능상 거의 동일한 경우
• 비대칭 다충처리: CPU 하나만 하나의 자료구조에 접근 가능 한 것
• 대칭 다중처리(SMP): 모든 CPU가 자료구조에 자유롭게 접근이 가능 한 것
  • 현재 대부분의 운영체제가 선택한 방식
• 처리기 친화성: 프로세스가 현재 실행 중인 처리기에 친화성을 가지는 것
  • 연성 친화성: cpu를 바꾸어도 별 문제 없이 작동하는 것
  • 경성: 프로세스가 작동하기 적합한 하드웨어(cpu)가 따로있다.
  • 처리기 집합등의 변형
• Non Uniform Memory Acessece(NUMA): CPU의 Local 메모리는 빠르게 접근 할 수 있지만 다른 CPU의 Local 메모리에는 빠르게 접근하기 힘들다.

부하 균등(Load Balancing)

• SMP의 경우 효율적으로 작동하기 위해서는 모든 CPU에 작업이 공급되어야 한다.
• 부하 균등: 부하를 균등하게 분배
  • 푸시 이주: 부하가 많이 걸린 CPU의 태스크를 부하가 적게 걸린 CPU로 이동 시킨다.
  • 풀 이주: 일이 없는 처리기에서 대기 중인 태스크를 가져다 실행한다.

다중코어 처리기

• 동일한 물리적인 칩 안에 여러 개의 처리기 코어를 배치한다.
• 단일 코어 방식의 CPU 보다 빠르고 더 적은 전력을 소모한다.
• 코어 마다 여러 스레드를 지원하는 방식이 증가하는 추세

다중스레드 다중코어 시스템

• 거친 다중 스레딩

• 한 CPU에 하드웨어 스레드가 하나라면 연산하고(C) 쉬고(M)를 반복한다.
• 세밀한 다중 스레딩 

• 한 CPU에 여러 하드웨어 스레드가 존재한다면 연산하고(C) 쉬고(M)를 서로 반복하며 일을 시킨다.
• 위에 사례에서는 cpu가 쉬는 구간이 존재하지만 해당 사례에서는 cpu가 항상 일을 한다.

실시간 CPU 스케줄링

• 연성 실시간 시스템(소프트): 아주 중요한 실시간 프로세스가 언제 완료될지 보장하지 않음, 태스크의 마감시간이 정해져 있지만 조금 지체됨을 허용한다.
• 경성 실시간 시스템(하드): 일정 시간 내에 태스크가 반드시 완료가 되어야 함
• 발생할 수 있는 지연
  • 인터럽트 지연: 인터럽트가 도착해서 인터럽트를 서비스 하기 시작할 때까지의 시간 (하드웨어 또는 소프트웨어가 발생하는 이벤트에 대한 지연이며)
  • 디스패치 지연: 현재 프로세스를 중단시키고 새로운 프로세스로 전환하는데 걸리는 시간 (운영 체제가 프로세스를 중지하고 다른 프로세스를 실행하는 데 필요한 지연)
• 조건
  • 커널 모드에서 실행 중인 프로세스의 선점
  • 낮은 우선순위의 프로세스가 높은 우선순위의 프로세스가 요구하는 자원을 방출

우선순위 기반 스케줄링

• 처리시간 t, 마감시간 d, 주기 p로 이루어
• 주기적인 프로세스는 일정 간격으로 CPU를 요구한다.
  • 주기가 짧을 수록 빈도 수는 올라간다.

가상화와 스케줄링

• 여러 게스트를 CPU에 스케줄 하는 기법
• 각 게스트는 자신이 직접 스케줄 한다.
  • 자기가 가진 CPU가 없다는 것 조차 모름
  • 응답시간이 나빠질 수 있음
  • 게스트의 현재 시각에 영향을 줄 수 있음
• 게스트의 스케줄링 알고리즘의 좋은 결과를 되돌릴 수 있음

Rate Montonic 스케줄링

• 우선순위는 주기의 역순에 기반을 두고 부여된다.
  • 단순히 주기가 짧을 경우 우선순위를 높게 두고 스케줄링 하는 방식
• 주기와 우선순위 반비례 P1(50) P2(100)
• CPU 이용률: 20(P1)/50 + 35(P2)/100
• N 개의 프로세스: 최악의 경우 CPU 이용률 N(2^1/N -1) 해당 보다 이용률이 커진다면 cpu 데드라인을 지키지 못 한 경우가 된다. N-> 무한대로 간다면 값은 자연로그 2 (ln 2) -> 0.693147 이 된다.
  • h = 1/N 일때 N(2^1/N -1) -> (2^h-1)/h 로 변환되고 n->무한대 -> h->0 으로 변환된다.
  • 이때 우리는 수학적 정의를 통해 ln2값이 나온다. 

선입 선처리 스케줄링(FCFS)

• First Gome, First-Served Scheduling
• 프로세스가 도착한 순서 차례대로 작업을 하는 것
• 평균 대기 시간: (0<p1>+24<p2>+27<p3>)/3 = 17

만약 프로세스의 도착순서가 바뀐다면?

• 평균 대기 시간: (0<p2>+3<p3>+6<p1>)/3 = 3
• 위의 경우 보다 대기 시간이 훨씬 줄어들었다.(성능 향상)
  • 호위 효과(Convoy effect): 긴 프로세스 다음에 존재하는 짧은 프로세스들이 겪는 효과

최단 작업 우선 스케줄링(SJF)

• Shortest-Job-First Scheduling
• 예상 실행시간이 적은 작업 부터 우선 스케줄링 하는 기법
  • 단 예상이 틀릴 경우가 존재 할 수 있으므로 그러한 프로세스 들에게는 패널티를 주어야 한다.
• 평균 대기 시간: (0<p4>+3<p4>+9<p3>+16<p2>)/4 = 7
• CPU 버스트 길이의 근사 값을 계산해 가장 짧으 예상 CPU 버스트를 가진 스로세스를 선택한다.
• 지수 평균을 이용하여 CPU 버스트의 길이를 예상한다.
• 선점형, 비선점형으로 존재

최소 잔여 시간 우선 스케줄링(SRT)

• 선점형 SJF 알고리즘을 사용한 스케줄링 방법
• Shortest-Remaining Time First
• 평균 대기 시간: (10-1<P1>+1-1<P2>+17-2<P3>+5-3<P4>)/4 = 26/4 = 6.5
  •  프로세스 대기시간: 총 대기시간 - (도착시간 + 이미 진행된 시간)

우선순위 스케줄링

• 숫자가 작을 수록 우선순위를 높게 설정
• 선점형과 비선점형으로 나누어진다.
• SJF는 일종의 우선순위 스케줄링
• 문제점: 낮은 우선순위의 프로세스는 실행되지 않는 기아 문제
• 해결책: (노화) 시간이 흘러갈수록 프로세스의 우선순위를 증가시킨다.
• 평균 대기 시간: (0<P2>+1<P5>+6<P1>+16<P3>+18<P4>)/5 = 8.2

Round Robin (RR)

• 각 프로세스마다 일정 시간(time quantum) 동안만 CPU를 할당받고 해당 시간이 끝나면 다시 맨 뒤로 줄을 서는 방식(큐)
• 준비 완료 큐에 n개의 프로세스가 있고 시간 할당량이 q이면 각 프로세스는 최대 q 시간 단위의 덩어리로 CPU 시간의 1/n 을 얻는다.
• 각 프로세스는 자신의 다음 시간 할당량이 할당 될 때까지 (n-1)q 시간 이상을 대기하지 않는다.
• 시간 할당량이 경과될 때마다 인터럽트를 발생시킨다.
• 성능
  • q가 커진다면 → FIFO에 가까워짐
  • q가 적어질수록 → q는 문맥 교환 시간에 비해 충분히 커야 한다 그렇지 않으면 오버헤드가 너무 크기 때문에 비효율 적이기 때문이다.
• SJF보다 총처리시간은 크지만 응답시간은 더 좋다.

다단계 큐

• 준비 큐는 별개의 큐로 분할된다
  • foreground (RR)
  • background (FCFS)
• 큐와 큐 사이의 스케줄링도 정해야 한다.
  • 고정 우선순위 스케줄링: 기아가 발생 할 수 있음
  • 시간 할당(RR): 각 큐는 일정량의 비율의 CPU 시간을 할당 받는다.

다단계 큐 스케줄링(MQS)

• 각 큐마다 우선순위가 다르다는 것을 이용해 스케쥴링하는 것

다단계 피드백 큐(MFQS)

• 프로세스가 우선순위가 바뀜에 따라 여러 큐로 이동하는 것
• 노화를 이런 방식으로 구현할 수 있다.
• 매개변수
  • 큐의 개수
  • 각 큐에서 사용하는 스케줄링 알고리즘
  • 프로세스 업그레이드 시기를 결정하는 데 사용되는 방법
  • 프로세스를 강등시키는 시기를 결정하는 데 사용되는 방법
  • 프로세스가 서비스를 받기 위해 들어갈 큐를 결정하는 데 사용되는 방법
• 우선순위가 높은 큐일 수록 time quantum의 크기를 작게 한다.
• 마지막 큐일 경우에는 작업이 끝날 때 까지 계속한다.