개발공부 기록지

페이징 ?

프로세스의 주소 공간을 미리 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식

• 장점: 메모리에 올리는 단위가 동일한 크기의 페이지 단위여서  빈 프레임이 있으면 어떤 위치이든 사용될 수 있다.

1) 주소 변환 기법

모든 프로세스가 각각의 주소 변환을 위한 페이지 테이블(page table)을 가진다.

논리적 주소를 페이지 번호(p) 와 페이지오프셋(d)로 나누어 주소변환에 사용

기존 주소값에 변위르 더함으로써 요청된 논리적 주소에 대응하는 물리적 수소를 만들 수 있다.

2) 페이지 테이블의 구현

주소 변환을 하기 위한 자료구조

물리적 메모리에 위치

• 페이지 테이블 기준 레지스터 (page-table base register) - 메모리내에서의 페이지 테이블의 시작 위치를 저장
• 페이지 테이블 \길이 레지스터 (page-table length register) - 페이지 테이블의 크기를 저장
• 메모리 접근 연산 : (총 2번) 페이지 테이블에 접근 -> 변환된 주소에서 실제 데이터로 접근 
      -> 오버헤드가 뒤따른다.
  • 대안? TLB(translation Look-aside Buffer) 라는 고속의 주소 변환용 하드웨어 캐시 사용
    • 테이블 접근 오버헤드 줄이고 메모리의 접근 속도 향상
    • 가격적인 이유로 빈번하게 참조되는 페이지에대한 주소 변환 정보만 담음
    • 구현 - 병렬탐색이 가능한  연관 레지스터(associative register) 사용
      • 평균적인 메모리 접근 시간 (EAT),
        • EAT  = (1 + ε)α + (2 + ε )( 1- α) = 2 + ε - 2α
        • ε = 레지스터 접근시간, α = 요청된 페이지에 대한 정보가 레지스터에 있을 확률  

3)계층적 페이징

4GB의 메모리가 있다고 하면 대부분의 프로그램은 4GB 중 극히 일부만 사용

이를 위해 페이지 테이블을 위한 메모리 사용은 공간낭비

-> 페이지 테이블에 사용되는 메모리 공간의 낭비를 줄이기 위해 2단계 페이징(two-level paging)기법을 사용

• 2단계 페이징 기법
  • 방식: 외부 / 내부 페이지 테이블의 두 단계에 걸친 페이지 테이블 사용
    • 사용되지 않는 주소 공간 -> 외부 페이지 테이블을 NULL로 설정, 내부 페이지 테이블을 생성 안함
  • 장점 : 페이지 테이블을 위해사용되는 메모리 공간 감소 -> 공간적인 이득
  • 단점 : 주소변환을 위해 접근해야 하는 테이블 수가 증가 -> 시간적인 손해
• 위와 같이 다단계(계층적) 페이징은 메모리 공간을 감소를 통해 공간적인 이득을 가질수 있지만, 단계가 늘어날 수록 접근해야하는 테이블수가 증가하므로 시간적 손해가 커진다.

4) 역 페이지 테이블

메모리 공간의 낭비가 심한 이유
=> 모든 프로세스의 모든 페이지에 대해 페이지 테이블 항목을 다 구성해야 하기 때문
=> 논리적 주소에 다 구성

역 페이지 테이블은? 

• 프로세스마다 페이지 테이블을 두지 않고, 시스템 전체(system-wide)에 페이지 테이블을 하나만 생성
• 물리적 주소에 대해 페이지 테이블을 생성
• 주소 변환 작업이 물리적 주소로부 논리적 주소를 얻는 구조
  
  • 비효율적 : 주소 변환 요청이 들어왔을 때 물리적 메모리에 존재하는지 여부를 알기 위해 페이지 전체를 탐색해야함

5) 공유 페이지

공유코드를 담고 있는 페이지 ->  물리적 메모리에 하나만 적재되어 메모리사용이 효율적

공유코드?  여러 프로세스에 의해 공통으로 사용되는 코드

 - 재 진입 가능 코드 (re-enterant code)
-  순수 코드(pure code)

특징

• 그 페이지를 공유하는 모든 프로세스의 주소 공간에서 동일한 페이지번호를 가져야 함
• 예시 그림

6) 메모리 보호

• 보호비트(protection bit) : 각 페이지에 대한 접근 권한의 내용 저장
  • 누가가 아니가 어떠한 접근을 허용하는지의 정보가 저장
  • 각 페이지에 대하 읽기-쓰기 / 읽기전용 등의 접권권한을 설정하는데 사용
• 유효-무효 비트 (valid-invalid bit) : 해당 페이지의 유효한지에 대한 내용 저장
  • 유효 : 해당 메모리 프레임에  그 페이지가 존재 -> 접근 허용
  • 무효 : 프로세스가  그 주소 부분을 사용하지 않거나 해당 페이지가 물리적 메모리에 올라와 있지 않음 -> 접근 불가

운영체제 상주 영역과 사용자 프로세스 영역

운영체제 - 낮은 주소 영역 사용

사용자 프로세스 - 높은 주고 영역 사용

프로세스를 메모리에 올리는 방식

1. 연속할당(contiguos allocation)
    물리적 메모리를 다수의 분할로 나누어 하나의 분할에 하나의 프로세스를 적재하도록 하는 방식
     

• 고정분할(fixed partition allocation) 방식 : 메모리를 고정된 크기로 미리 나누어 놓은 방식
  • 융통성 떨어짐 : 프로그램의 크기보다 작을 수도 클수도 있으므로
    • 외부조각(external fragmentation) : 프로그램의 크기가 미리 나누어둔 분할 보다 커서 적재를 못하여 발생하는 메모리 고간
    • 내부조각(internal fragmentation) : 반대 상황, 프로그램 크기가 작아서 발생하는 남는 메모리 공간
• 가변분할 (variable partition allocation) 방식 : 프로그램의 크기에 따라 동적으로 변하는 방식
  • 한번 할당한 메모리공간에 다른 프로그램이 적재 될시 해당 프로그램이 그 공간보다 크면 외부조각 발생
  • 해결방안 (새로운 프로그램의 크기가 n)
    1. 최초적합(first-fit) 방법 :크기가 n 이상인 가용공간들 중 가장 먼저 찾는 곳에 적재
    2. 최적합(best-fit) 방법 : 크기가 n 이상인 가용공간들 중 가장 작은 공간에 적재
    3. 최악적합(worst-fit) 방법: 크기가 가장 큰 곳에 적재
  • 그래도 외부조각이 발생시 해결방법
    • 컴팩션(compaction) : 실행시간 바인딩 방식이 지원되는 환경에서만 가능
      • 사용 중인 공간을 다 앞으로 모으로 안쓰는 공간을 다 모아서 하나의 공간으로 만드는 방법

2. 불연속할당 (noncontiguos allocation)
    하나의 프로세스가 물리적 메모리의 여러 위치에 분산하여 적재하는 방식
    - 페이징 기법 : 동일한 크기로 나누어 메모리에 올리는 기법
    - 세그멘테이션 기법 : 크기는 일정하지 않지만 의미있는 단위(코드 ,데이터, 스택등)로 나누어서 메모리에 올리는 기법

    - 페이지드 세그멘테이션 : 세그먼트 하나를 다수의 페이지로 구성하는 기법

1. 동적로딩( dynamic loading)

• 메모리사용의 효율성을  높이기 위한 기법
• 사용되는 환경 >> 여러 프로그램이 동시에 메모리에 올라가서 수행되는 다중 프로그래밍 환경
• 목적 : 메모리에 더 많은 프로세스를 동시에 올려놓고 실행하기 위한 용도
• 방식
  • [기존]  프로그램을 실행하기 위해 프로세스의 주소공간 전체가 메모리에 적재
  • [동적로딩]  프로세스의 해당 부분이 필요할 때만 (실행 될 때만) 메모리에 적재
    사용되지 않는 많은 코드가 메모리에 적재되는 것을 막아 메모리 효율적 사용 
• 운영체제의 지원없이 프로그램 자체에서 구현 가능

2. 동적연결 (dynamic linking)

• 연결(linking) 
  코드를 컴파일하여 생성된 
            목적 파일
  (프로그래머가 작성한 소스코드)
                + 
        라이브러리 파일
       (라이브러리 코드)
                ↓ 
     하나의 실행파일을
         생성하는 과정
• 동적연결 (dynamic linking) 
  • 목적 파일과 라이브러리 파일 연결을 프로그램의 실행 시점까지 지연시키는 방법
  • 해당 라이브러리가 실행이 되는 시점에 연결이 되어 실행파일 생성
    사용되는 라이브러리를 한 번만 메모리에 적재
  • 운영체제의 지원 필요
• 정적 연결 (static linking)
  • 프로그래머가 작성한 코드 와 라이브러리 코드를 모두 합쳐서 실행파일 생성
     

3. 중첩 (overlays)

• 사용되는 환경 : 단일 프로세서만을 메모리에 올려놓는 환경
• 목적 : 메모리 용량보다 큰 프로세스를 실행하기 위한 방법
• 방법 : 프로세스의 주소공간을 분할해 실제 필요한 부분만 메모리에 적재

4. 스와핑 (swapping)

• 메모리의 사용자공간에 올라온 프로세스의 주소 공간 전체를 디스크의 스왑영역에 일시적으로 내려놓는 것
• 메모리에 존재하는 프로세스의 수를 조절하는 역할 
  • 프로그램이 종료되어 그 주소 공간을 디스크로 내쫓는 것이 아님
  • 특정한 이유로 프로세스를 잠시 메모리에서 디스크로 내려 놓는것 (swap in)
        -> 디스크에서 메모리로 올릴 수도 있다. (swap out)
• 스왑영역(swap area, 휘발성 저장공간)?
      백킹스토어(backing store)라고도 불리는 이 영역은
      디스크 내에 파일 시스템(비휘발성 저장공간)과는 별도로 존재하는 일정 영역
      프로세스가 수행되는 동안에만 디스크에 일시적으로 저장이 가능한 영역
• 일어나는 과정
  •  스와퍼(swapper) 라는 중기 스케줄러(midum-term scheduler)에 의해 swap out 시킬 프로세스를 선정
     중기 스케줄러:  2023.12.13 - [책/운영체제와 정보기술의 원리] - 5 장 프로세스 관리  
    • 중기 스케줄러:  프로세스의 수를 동적으로 조절하여 메모리 조절하는데 이때 swap out을 사용
• 바인딩 방식에 따른 swap in
  • 컴파일 타임 바인딩 - 꼭 원래 존재하던 메모리 위치로 다시 복귀
  • 로드 타임 바인딩 -꼭 원래 존재하던 메모리 위치로 다시 복귀
  • 실시간 바인딩 - 빈 메모리 영역 아무 곳에나 프로세스 올리기 가능
• 소요시간 : 디스크 섹터에서 실제 데이터를 읽고 쓰는 전송(transfer) 시간이 대부분을 차지

컴퓨터에서 메모리의 주소는 이진수로 매겨진다.

32비트 혹은 64비트를 사용

- (예) 32 비트의 주소 체계 :  \(2^{32}\) 가지의 서로 다른 메모리 위치 구분

현실에서도 행정구역을 나누듯 컴퓨터도 영역을 나누어서 32비트를 사용

- 4KB = \(2^{12}\)byte 단위로 묶어서  page 라는 하나의 영역을 만들어서 사용 - 한 페이지에 12비트

1. 주소 바인딩

- 논리적 주소를 물리적 주소로 연결시켜주는 작업

• 논리적 / 가상 주소 ( logical / virtual address)
  • 각각 의 프로세스 -> 독립적으로 가짐
  • 이 주소에 근거하여 CPU가 기계어 명령을 실행
    -> 해당 주소가  물리적 메모리의 어느위치에 매핑되는지 확인도 필요
  • 0 번지 부터 시작 
• 물리적 주소 (physical address)
  • 물리적 메모리에 실제로 올라가는 주소
    • 메모리의 낮은 주소 : 운영체제
    • 메모리의 높은 주소 : 사용자 프로세스
• 주소 바인딩 방식 -  물리적 메모리의 주소가 결정되는 시기에 따라 분류
  • 컴파일 타임 바인딩 (compile time binding)
    • 프로그램을 컴파일하는 시점에 물리적 메모리에서의 주소 결정
    • 위치를 변경하고 싶을때 마다 리 컴파일 필요
      -> 비현실적, 시분할 컴퓨팅 환경에서 사용 X
  • 로드 타임 바인딩 (load time binding)
    • 프로그램이 실행 될때 물리적 메모리에서의 주소 결정 
    • 프로그램이 종료 될때까지 메모리 주소 고정
    • (?) 컴파일러가 재배치 가능 코드를 생성한 경우에 가능한 방식
  • 실행시간 바인딩 (execution time binding / run time binding)
    • 프로그램이 실행된 후에도 프로그램의 물리적 메모리상의 주소가 변경될 수 있는 방식
    • CPU가 주소를 참조할 때 마다 해당 데이터가 물리적 메모리의 어느 위체 존재하는지
      주소 매핑 테이블 (address mapping table)을 이용해 바인딩을 점검
    • 지원 필요
      • 기준(base) 레지스터 혹은 재배치(relocatable) 레지스터
      • 한계 레지스터
      •  MMU(memorry management unit: 메모리 관리 유닛)
        • MMU : 논리적 주소를 물리적 주소로 매핑(mapping) 해주는 하드웨어 장치
         

• MMU 기법 (scheme)
  • 논리적 주소  + 기준 레지스터 값 = 물리적 주소 -> 메모리 
  • CPU 가 논리적 주소 123 번지에 있는 내용 요청
    -> 기준 레지스터에 저장된 23000 값을 더함
    -> 물리적 메모리 23123 번지에 있는 내용 참조
  • 문제
    • 더 한 결과가 해당 프로세스의 주소공간을 벗어 남 -> 다른 영역에 침범 가능 -> 메모리 보안 문제 발생
    • 한계 레지스터를 사용하여 발생을 방지 -> 메모리 영역에 대한 보안을 유지
      • 한계 레지스터에 있는 프로세스의 크기보다 크면 트랩발생 -> 프로세스 강제 종료 

CPU는 기계어 명령을 셀제로 수행하는 컴퓨터 내의 중앙 처리 장치

동작원리

1. 프로그램이 시작되어 메모리에 올라가면,
2. 프로그램 카운터(program counter, PC)라는 레지스터리가 현재의 CPU에서 수행할 코드의 메모리 주소값을 가지고 있다.
3. 메모리 주소값의 기계어 명령을 하나씩 CPU가 실행

기계어 명령의 종류

• 사용자 프로그램이 사용가능한 일반 명령
  • CPU내에서 수행되는 명령 : Add
  • 메모리 접근을 필요로 하는 명령: Load, Store 
• 커널영역에서만 수행하는 특권명령
  • 입출력을 동반하는 명령: Disk I/O

CPU 버스트와 I/O 버스트

• CPU 버스트 : I/O을 수행한 후 다음 I/O이 수행 전 까지 CPU를 가지고 수행하는 작업
  
  • 디스크 쓰기/읽기 명령, store 명령, Add 명령, Load 명령
• I/O 버스트 : I/O 작업이 요청을 수행하고 나서 CPU 버스트를 수행하기 전까지의 작업

CPU 바운드 프로세스 와 I/O 바운드 프로세스

• CPU 바운드 프로세스 : I/O 요청이 거의 일어나지 않아  CPU 버스트가 길게 나타는 현상
  • 계산위주의 프로그램
• I/O 바운드 프로세스 :  I/O 요청이 빈번하여 CPU 버스트가 짧게 나타나는 현상
  • 대화형 프로그램(interactive program)

CPU 스케쥴링이 필요한 이유

• CPU 버스트의 길이가 프로세스마다 다르므로 효율적인 CPU 할당 필요
  • 대화형 작업(CPU버스트가 짧음)에서는 사용자에 대한 빠른 응답 중요 -> 우선적으로 할당 
  • I/O 바운드 프로세스가 우선순위 -> CPU를 잠깐만 사용한 후 반환

1. CPU 스케줄러 (운영체제 코드)

CPU 스케줄링이 필요한 경우

1. 실행 상태에 있던 프로세스가 I/O요청 등에 의해 봉쇄(blocked) 상태로 바뀌는 경우
2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
3. I/O 요청에 의해 봉쇄상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비상태로 바뀌는 경우
4. CPU에서 실행 상태에 있는 프로세스가 종료되는 경우

CPU 스케줄링 방식

• 선점형(preemptive): CPU를 계속 사용하길 원하더라고 강제로 빼앗는 방식
  •  경우 2 와 3
• 비선점형 (nonpreemptive) :  CPU를 사용하는 프로세스가 스스로 반납하기 전까지 기다리는 방식
  • 경우 1 와 4

2.디스패처 (운영체제 코드)

CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고 나면

디스패처(dispatcher)가 프로세스에게 CPU를 이양하는 작업을 한다.

방식

1. 수행 중(CPU를 사용 중)인 프로세스에 타이머 인터랩트 발생
2. 디스패치 작업 수행
   1. 수행 중인던 프로세스의 문맥을 그 프로세스의 PCB(프로세서 제어 블록)에 저장
   2. 새롭게 선택된 프로세스의 문맥을 해당 PCB로 부터 복원
   3. 새로운 프로세스에게 CPU를 넘기는 작업을 수행

디스패치 지연시간 ( dispatch latency)?

• 디스패처가 하나의 프로세스를 중지 시키고 다른 프로세서에게 CPU를 이양하는데 걸리는 시간
• 대부분은 문맥교환 오버헤드에 해당
  • 이유 
    • 문맥을 교환하는 동안에는 유용한 작업을 수행할 수 없기 때문에, 일종의 오버헤드에 해당
    • 문맥을 교환에 따른 추가적인 시간소비와 시스템 자원(메모리) 사용이 발생하므로 오버헤드에 해당

문맥교환 오버헤드??

- 컴퓨터 시스템에서 발생하는 작업 전환이나 문맥 전환에 따른 추가적인 시스템 자원 및 시간 소비를 의미

• 오버헤드 : 함수 호출 또는 다른 처리를 수행하기 위해 필요한 간접적인 처리 시간 및 메모리 소비를 말함
• 오버헤드 발생 이유 (주로 운영체제에서 관리)
  • 문맥교환 시간
    • 프로세스 전환이 필요할 때, 현재 실행 중인 작업의 상태를 저장하고 다음 작업의 상태를 복원-> 이때 발생하는 시간 소요가 문맥 교환 시간으로 오버헤드가 발생
  • 시스템 활용 불가능 시간
    • 문맥 교환 동안 시스템은 유용한 작업을 수행 못함 ->  이 시간 동안 시스템 자원이 소멸 
  • 오버헤드 해결 방안 
    • 다중 프로그래밍 수준을 낮추어 문맥 교환 발생 빈도를 감소
    • 스레드를 이용하여 문맥 교환 부하를 최소화

3. 스케쥴링의 성능 평가

시스템관점

• CPU 이용률
  전체 시간 중 CPU가 일을 한 시간의 비율 -> CPU가 휴면(idle)상태에 머무르는 시간을 최대한 줄이는 것이 목표
• 처리량(thorughout)
  주어진 시간동안에 준비 큐에 있는 프로세스 중 몇개를 처리하였는가, 즉 CPU 버스트를 완료한 프로세스 갯수

사용자관점

• 대기 시간
  - CPU 버스트 기간 중 프로세스가 준비큐에서 CPU를 얻기위해 기다린 시간
  - 준비 큐에 들어온 시간 직후 부터 이번 CPU 버스트가 끝날 때까지 준비 큐에서 기다린 시간의 합
  • 한번의 CPU 버스트가 한번에 완료되지 않고 여러번에 걸쳐서 완료될 수도 있음 - 시분할 시스템 때문
• 소요 시간(turnaround time)
  - 준비 큐에서 기다린 시간 + CPU를 사용한 시간(반납) -> 하나의 CPU 버스트가 완료될 때까지 소요된 시간
  - 대기 시간 + CPU를 사용한 시간
• 응답 시간
  - 프로세스가 준비 큐에 들어온 직후 부터 첫 번째 CPU를 획득하기까지 기다린 시간
  - 대화형 프로그램/시스템에 적합한 성능 척도 

4. 스케줄링 알고리즘

1)선입선출 스케줄링  (first-come first-served: FCFS)

• 먼저 기다리는 프로세스에게 먼저 CPU를 할당하는 방식
• 일상 생활 : 은행, 공항, 화장실 등
• 단점 : CPU 버스트가 긴 프로세스가 먼저 온 경우 나머지 프로세스가 기다려야한다.

FCFS 방식의 예

예 1) P1 -> P2 -> P3 

• 대기시간: P1 =0, P2 = 12, P3 = 15
• 평균 대기시간 : 9

예 2) P2 -> P3 -> P1

• 대기시간 : P2 =0, P3 = 3, P1 = 6
• 평균 대기시간: 3

예 1) 에서 콘보이 현상 발생 ( Convoy effect) : CPU 버스트가 짧은 프로세스 (P2)가  CPU 버스트가 긴 프로세스(P1)보다 늦게 도착하여 기다려야하는 상황

2) 최단작업 우선 스케줄링 (Shortest-job First: SJF)

- 평균 대기시간을 제일 짧게하는 알고리즘
- 시스템에서 평균 대기시간을 줄이는 것이 항상 좋은 방식은 아님

종류

• 비선점형
  • 먼제 실행 중인 프로세스가 마칠때 까지 기다리는 방식
• 선점형
  • 다른 프로세스가 실행 중이여도 새로운 프로세스의 CPU 버스트가 더 짧으면 중단하고 새로운 프로세스에 CPU 할당
  • 작업이 끝나거나 새로운 프로세스가 들어오면 CPU 버스트 시간을 비교
  • 단점:  CPU 버스트가 긴 프로세스는 준비 큐에서 무한정 기다려야하는 문제 -> 기아현상(starvation)

현실적으로 어려운 부분은 프로세스의 CPU 버스트 시간을 미리 알 수 없다는 점

3) 우서순위 스케줄링 (Priority scheduling)

- 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU 할당

종류 : 비선점형, 선점형 방식

단점

• 기아현상: 계속해서 우선순위가 높은 프로세스가 오면 우선순위가 낮은 프로세스는 무한정 기다려야하는 문제점

해결방법

• 노화(aging)기법 : 기다리는 시간이 길어지면 점점 우선순위를 올려주는 기법

4) 라운드 로빈 스케줄링 ( Round Robin Scheduling)

- 시분할 시스템의 성질을 가장 잘 활용한 방식
- 각 프로세스마다 CPU를 사용할 수 있는 할당시간(time quantum) 존재

• CPU를 연속으로 사용할 수 있는 할당시간이 지나면 준비 큐에서 제일 뒤에서 대기
• 준비 큐에서 다음 순서의 프로세스에 CPU를 할당
• 단점 : 할당시간이 너무 짧으면 문맥교환의 오버헤드가 발생
• 장점 : 대화형 프로세스의 빠른 응답시간을 보장 가능
• 작동원리
  • 할당시간이 만료 -> 타이머 인터럽트사용하여 CPU 회수
  • 할당시간 만료전에 완료 -> CPU 자진 반납
• SJF 와 비교
  • 평균 대기시간 측면 => SJF win
  • 응답 시간 => 라운드 로빈 스케줄링 win
  • 소요 시간 => 할당시간에 따라 변경
  • 효율성 => SJF win
  • 형편성 => 라운드 로빈 스케줄링 win
• FCFS 와 비교
  • 예) 같은 시각에 CPU 버스트 시간이 10인 프로세스가 10개 도착
    • 평균 대기시간, 평균 소요시간 => FCFS
      • (이유) 라운드 로빈 스케줄링은 마지막에 모든 프로세스가 마치므로 비효율적
    • 평균 응답시간 => 라운드 로빈 스케줄링
  • CPU 버스트 시간이 다 같지 않다면
    • 라운드 로빈 스케줄링 : CPU 버스트 시간이 짧은 프로세스들은 빠르게 완료, 시간이 긴 프로세스는 오래 대기
    • FCFS : 모든 포로세스의 소요되는 시간 편차가 매우 큼
    • 라운드 로빈 스케줄링이 합리적

5) 멀티레벨 큐

- 준비 큐를 여러 개로 분할해 관리하는 스케줄링 방식
- 성격이 다른 프로세스를 별도로 관리 -> 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 준비

• 예시 : 대화형 작업 과 그렇지 않는 작업
  • 전위 큐(라운드 로빈) : 대화형 작업 담기
    - 응답시간을 빠르게 하기 위해 라운드 로빈 사용
  • 후위 큐(FCFS) : 계산 위주의 작업
    - 응답시간이 중요하지 않으므로 FCFS이용하여 오버헤드 줄이는 방식

- 큐 자체에 대한 스케줄링도 필요: 어느 큐에 먼저 CPU를 할당할 것인가?

• 고정 우선순위 방식 : 우선 순위가 높은 큐에 먼저 CPU 할당, 낮은 큐는 우선순위가 높은 큐가 비어있을 때 할당
• 타임 슬라이스 방식 : 기아현상을 해소하는 방법, 각 큐에 CPU를 적절한 비율로 할당

6) 멀티레벨 피드백 큐

- 멀티레벨 큐와 동일 : 프로세스를 여러 큐에 줄 세운다는 점 
- 차이점 : 프로세스가 하나의 큐에서 다른큐로 이동가능

상위에 있는 큐 일수록 우선순위가 높으며 상위 2개의 큐는 각각 할당시간이 5 와 10 인 라운드 로빈 스케줄링을 사용한다. 

=> CPU 사용시간이 짧은 대화형 프로세스들은 우선순위가 높은 큐( 라운드 로빈) 에서 빨리 서비스받고 작업을 완료.

이때, CPU 버스트 시간이 길어서 5만큼의 시간동안에 완료를 못하는 경우면 10에서 대기를 한다.
10만큼의 시간동안에 작업을 완료 못하면 -> 계산 위주의 프로세스로 간주 -> FCFS에서 대기 

7) 다중처리기 스케줄링

- CPU가 여러 개인 개인 시스템 = 다중처리기 시스템 (multi-precessor system)
- 프로세스를 준비큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내어가도록하는 시스템
- (예) 공항에서 체크인을 위해 기다리는 줄

문제점 : 반드시 특정 CPU에서 수행되어야하는 프로세스가 많은 경우 -> 특정 CPU에 작업량이 편중

해결책 : 부하균형(load balancing) 메커니즘- CPU별 부하가 적절히 분산되도록 하는 메커니즘

스케줄링 방식

- 대칭형 다중처리(symmetric multi-precessing) : CPU가 각자 알아서 스케줄링을 결정하는 방식
- 비대칭형 다중처리(asymmetric multi-precessing) :  하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지는 따라 움직는 방식

8) 실시간 스케줄링

- 각 작업마다 주어진 데드라인 안에 반드시 작업을 처리해야 함
- 데드라인이 얼마 남지 않은 요청을 먼저 처리 (EDF : Earlist Deadline First)

종류

• 경성 실시간 시스템 (hard real-time system) : 반드시 시간(데드라인) 을 정확하게 지켜야 하는 시스템,(ex) 미사일 발사 시스템
• 연성 실시간 시스템 (soft real-time system) : 데드라인이 존재하지만 넘겨도 위험한 상황 X (ex) 멀티미디어 스트리밍 시스템

5. 스케줄링 알고리즘 평가

• 큐잉모델 (queueing model) : 이론가들이 수행하는 방식
• 시뮬레이션 (simulation) : 구현가들이 수행하는 방식
• 구현 및 실측 (implementation & measurement) 방식