공부하는 개발 블로그

가상 메모리: 각 프로세스는 0번지에서 시작하는 고유의 주소 공간을 가짐.

8.1 요구 페이징

당장 사용할 페이지만 메모리에 올림.

입출력 시간이 단축 -> 응답시간 단축. 더 많은 프로세스 처리.

적은 메모리 필요.

페이지 부재(page fault): 페이지가 메모리에 없다.

1) page fault 처리

(1) MMU(Memory Management Unit)이 page fault trap 발생

(2) CPU으 제어권이 커널모드로 전환. page fault 처리 루틴 호출

(3) 페이지에 대한 접근이 적법한지 체크: 사용되지 않는 주소 영역? 접근 권한이 있는가?

(4) 물리 프레임에서 비어있는 프레임을 할당받아 메모리를 읽어옴

(5) 빈 프레임 없으면 swap out and swap in. 디스크 작업은 오래 걸리므로 page fault가 발생한 프로세스는 CPU를 빼앗기고 봉쇄 상태가 됨. PCB에 CPU 레지스터 상태 및 프로그램 카운터 값 저장.

(6) 디스크 입출력 완료 -> 인터럽트 -> 유효 비트로 설정 -> 봉쇄된 프로세스를 준비큐로 이동.

2) 요구 페이징의 성능

page fault의 발생 빈도에 따라 성능이 결정됨.

EAT(effective access time):

p는 page fulat rate

(1-p) * 메모리 접근 시간 + p*(page fualt 처리 오버헤드 + swap out 오버헤드 + swap in 오버헤드 + 프로세스 재시작 오버헤드)

8.2. 페이지 교체

page fault율을 최소화하는 알고리즘이 목표

1) 빌레디의 오프라인 최적 알고리즘

가장 먼 미래에 참조되는 페이지를 swap out.

페이지가 참조되는 순서를 알고 있다는 가정. 이론적. 알고리즘 성능의 상하선 제공.

2) FIFO

가장 먼저 올라왔던 페이지를 먼저 swap out.

FIFO 이상현상(FIFO anomal): 메모리를 증가시켰음에도 오히려 page fault 증가

3) LRU(Least Recently Used)

시간 지역성(temporal locality) 이용.

가장 오래 전에 참조가 이루어진 페이지를 swap out.

4) LFU(Least Frequently Used)

페이지 참조 횟수가 가장 적은 페이지 swap out.

Incache-LFU: 페이지가 물리 메모리에 올라온 순간부터 1. swap out-in 되면 1부터 다시 시작.

Perfect-LFU: 누적 참조 횟수.

참조 횟수를 저장하는 오버헤드

5) clock algorithm(=second chance algorithm, NUR, NRU: Not Used Recently)

LRU를 근사한 알고리즘.

오랫동안 참조되지 않은 페이지 중 하나 swap out.

하드웨어 지원으로 동작 -> 빠름. 대부분 사용

페이지가 참조될때마다 참조 비트 1로 set

참조비트가 1인 경우 0으로 set.(-> 한 바퀴 돌때까지 0인 페이지를 못 발견한 경우를 위함)

참조 비트가 0인 페이지를 발견하면 교체.

8.3 페이지 프레임의 할당

1)균등 할당

2) 비례 할당(proportional allocation): 프로세스의 크기에 비례하여 할당.

3) 우선순위 할당(priority allocation): 당장 CPU에서 실행될 프로세스에 더 많은 페이지 프레임 할당.

프로세스별로 최소한으로 필요한 메모리 양, 반복문 여부 등을 고려해야 더 효율적

8.4 전역 교체와 지역 교체

전역 교체: 교체 범위가 메모리 전체

지역 교체: 같은 프로세스 안의 페이지 중에서 교체

8.5 스레싱(thrashing)

page fault가 크게 상승해 CPU 이용률이 떨어지는 현상

MPD(Multi-Programming Degree): 메모리에 동시에 올라간 프로세스의 수

MPD가 낮은 경우 CPU는 더 많은 프로세스를 메모리에 올림.

그런데 너무 많은 프로세스가 올라가면, page fault 증가 -> 디스크 I/O : 시스템은 page fault 처리에 분주, CPU 이용률 감소.

=> 운영체제는 메모리 상의 프로세스가 적다고 판단하고 프로세스를 더 올림. -> page fault 더 증가. 악순환

1) 워킹셋 알고리즘(working-set algorithm)

지역성이 있는 집합(locality set)을 메모리에 동시에 올라갈 수 있도록 하는 알고리즘.

working-set: 프로세스가 일정 시간 동안 원할히 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 페이지들의 집합.

working-set의 모든 페이지가 메모리에 올라갈 수 있는 경우에만 적재. 아니면 swap out.

workng-set window: delta

working-set: 시각 t에서 시간간격 [t-delta, t] 사이에 참조된 서로 다른 페이지의 집합. 페이지가 참조된 시점으로부터 delta시간 동안은 메모리에 유지되고, 그 시점이 지나면 swap out.

working-set의 크기의 합이 메모리보다 크면 일부 swap out

working-set window의 크기가 중요.

너무 작으면: 지역성 집합 수용 X

너무 크면: MPD감소 -> CPU 이용률 낮아짐.

working-set의 크기는 시간의 흐름에 따라 변함. 동적 프레임 할당의 기능까지 수행.

2) 페이지 부재 빈도 알고리즘(page-fault frquency algorithm)

프로세스별 page fault 비율을 조사해서,

시스템에서 정한 상한보다 높은 경우, 추가 프레임 할당. 추가할 빈 프레임이 없으면 일부 프로세스 swap out

시스템에서 정한 하한보다 작은 경우, 프레임 수를 줄인다.

CPU 스케줄
선점형 : CPU를 빼앗길 수 있다
비선점형 : CPU를 빼앗기지 않는다.
1)FCFS(First Come First Served)
프로세스가 하나씩 끝나므로 평균 대기시간/소요시간은 짧음.
프로세스별로 CPU 버스트/ I/O버스트 시간이 다른 경우 프로세스마다 편차가 심함.
대표적 단점
convoy effect(콘보이 현상): CPU 버스트가 짧은 프로세스가 나중에 도착해서 오랜 시간을 기다려야하는 것.
2.SJF(Shortest-Job First) : CPU 버스트가 짧은 순. 평균 대기시간이 가장 짧음(선점형/비선점형 중 비선점형이 더 짧음)
SRTF(shorted Remaining Time First): 도중에 CPU 버스트가 더 짧은 프로세스가 오면 CPU를 빼앗아서 할당함.
기아(starvation) 현상: CPU 버스트가 짧은 프로세스가 계속 도착하면, CPU 버스트가 긴 프로세스는 계속 처리되지 못함.
CPU 버스트 시간은 실제로 알 수 없으므로, 예측.
T_n+1 = alhpa * t_n + (1-alpha)*T_n
T_n: 예측시간, t_n: 실제 CPU 버스트 시간

3) 우선순위 스케줄링
aging(노화): 대기 시간이 길어지면 우선순위를 조금씩 높임.

4) 라운드 로빈
할당시간이 너무 긺: FCFS와 차이가 없음
할당시간이 너무 짧음: context switch 오버헤드가 크다.
-> 수십 ms: 대화형 프로세스의 대기시간이 너무 길지 않을 정도.
여러 이질적인 프로세스를 처리할때 유용
SJF보다 평균 대기시간은 길지만 응답시간은 짧음.
할당시간 초과: 타이머 인터럽트를 통해 CPU회수
중간 산출물이 없으므로 평균 대기시간/소요시간은 길지만, 응답시간은 짧음.


5) 멀티레벨 큐
준비큐를 여러개로 분할하여 관리하는 스케줄링 기법
성격이 다른 프로세스를 관리하기 위함.
전위 큐 : 빠른 응답이 필요한 대화형 프로세스. 라운드 로빈
후위 큐: 응답 속도가 주요하지 않은 계산 프로세스. FCFS

어떤 큐를 먼저 사용할것인가?
고정 우선순위 방식 : 전위 큐 > 후위 큐
타임 슬라이스 : 전위 큐 80%, 후위 큐 20%. 기아 현상 해결

6) 멀티레벨 피드백 큐
멀티레벨 큐 + 하나의 프로세스가 다른 큐로 이동 가능.
노화(aging) 등 구현 가능

7) 다중처리기 스케줄링(multi-processor scheduling)
CPU가 여러 개인 환경
-1) 대칭형 다중처리: 각 CPU가 알아서 스케줄링 결정
-2) 비대칭형 다중처리 : 하나의 CPU가 스케줄링 담당.

8) 실시간 스케줄링
경성 실시간 시스템(hard real-time system) : 정해진 시간 내에 완료되야하는 시스템
연성 실시간 시스템(soft real-time system) : 데드라인이 존재하지만 지키지 않는다고 위험 상황이 발생하지 않는 시스템
EDF(Earliest Deadline First): 데드라인이 얼마 남지 않은 요청 먼저
연성 실시간 + 일반 작업의 경우: 데드라인이 존재하는 프로세스에 우선순위 할당

5.스케줄링 알고리즘의 평가
큐잉 모델: 확률 분포를 통해 프로세스의 도착률과 CPU의 처리율을 바탕으로 CPU의 처리량(throughput). 프로세스의 평균 대기 시간 계산.
시뮬레이션
구현 및 실측
트레이스(trace): 실제 시스템에서 추출한 CPU 입력값. 몇 초에 어떤 프로세스가 도착하고 CPU 버스트 시간이 얼마이다.

운영체제(Operating System; OS)

컴퓨터 하드웨어 바로 윗단에 설치되는 소프트웨어

커널(kernel)

운영체제 중 항상 메모리에 상주하고 있는 부분

운영체제 전체가 메모리에 동시에 올라가기에는 용량이 너무 크기 때문에 일부만 상주한다.

운영체제의 기능

1) H/W : 시스템 자원 관리 (사용자가 알기 힘든 하드웨어 관리)

• 효율성
• 형평성 : 일부 프로그램/사용자에 몰리면 안됨

2) 사용자에게 편리한 인터페이스 제공

3) 보안

운영체제의 분류

1) 동시 작업

- 시분할 시스템(time sharing system) : CPU의 작업 시간을 나누어 쓰는 시스템

- 다중 프로그래밍 시스템(multi-programming system; 멀티프로그래밍) : 메모리 공간을 나누어 사용하는 시스템. 동시에 여러 프로그램이 메모리에 올라옴.

- 다중처리기 시스템(multi-processor system; 멀티프로세서): 하나의 컴퓨터에 여러개의 CPU

2) 작업 처리 방식

- 일괄 처리(batch processing)

- 시분할(time sharing)

- 실시간(real time)