운영체제 공부 기록

이 글은 '운영체제 - 이화여대 반효경 교수 강의'를 보고 학습한 내용을 정리한 글입니다. 본인을 위해 작성한 글이므로 여러분에게 도움이 안될 가능성이 높습니다

 

---

운영체제

 

모드비트 0과 1 - 운영체제와 사용자 프로그램의 경계, 사용자프로그램이 자신의 메모리공간만 참조할 수 있도록함

 

DMA - IO디바이스의 local 버퍼의 데이터를 직접 메모리에 올림 - 인터럽트를 줄이는 효과, 멤컨이 메모리 트랜잭션 중재자 역할 - 원래는 cpu가 버퍼에서 다 복사해야함(1바이트 입력인데도 인터럽트발생) 

 

사용자 프로그램이 I/O가 필요하면 운영체제 메모리 공간으로 점프하는 것이 아니라 인터럽트를 걸어서 운영체제에게 간접적으로 알림 - 운영체제는 인터럽트 라인에서 인터럽트 원인을 보고 사용자 프로그램을 위해 i/o를 수행함

 

인터럽트 - 인터럽트 당한 시점의 레지스터와 program counter를 save하고 cpu의 제어를 인터럽트 처리 루틴에 넘김

 

Trap - 소프트웨어 인터럽트 -> exception, system call

 

인터럽트 벡터 - 어떤 인터럽트가 들어왔는지 구분하기 위한 테이블 같은 것(주소를 가지고 있음)

인터럽트 처리 루틴 - 해당 인터럽트를 처리하는 커널 함수

 

cpu는 pc가 가리키는 메모리주소를 보고 인스트럭션을 수행만 함

 

사용자 프로그램이 실행될 때 마다 타이머가 세팅됨, 할당된 시간이 끝나면 인터럽트

 

 

동기식 입출력 (synchronous I/O) - I/O 요청 후 I/O가 완료된 후에야 제어가 사용자 프로그램에게 넘어감

비동기식 입출력(asynchronous I/O) - I/O가 시작된 후 입출력 작업이 끝나기를 기다리지 않고 제어가 사용자 프로그램에 즉시 넘어감

보통은 i/o 시키고 다른 프로세스로 cpu 넘김

 

 

 

Memory mapped I/o - I/o 디바이스의 메모리 공간도 따로 명령어를 두지 않고 주메모리의 연장선으로 이어서 생각함. 다른명령어 쓸 필요 없게함

 

—————————————————————————————————————————

 

Process1

 

프로세스의 문맥 - cpu수행상태를 나타내는 하드웨어 문맥(pc,각종 레지스터), 프로세스의 주소공간(code,data,stack), 프로세스 관련 커널 자료 구조(pcb, kernel stack)

 

프로세스의 상태 - running, ready, blocked(cpu가 주어져도 당장 실행불가상태 ex.I/O 실행중, 공유데이터접근) ,(new, terminated) + suspended(외부적인 이유로 프로세스의 수행이 정지됨, swap out, 사용자가 프로그램을 일시정시킴 컨트롤씨, 중기 스케줄러가 쫓아냄)

blocked와 suspended의 차이 -blocked(자신이 요청한 event가 만족되면 ready), suspended(외부에서 resume해줘야 active[running,ready,blocked]로 가능 )

 

PCB - process control block

 

Context switch - cpu를 한 프로세스에서 다른 프로세스로 넘겨주는 과정 

- 운영체제의 역할 1. cpu를 내어주는 프로세스의 상태를 그 프로세스의 pcb에 저장 2. cpu를 새롭게 얻는 프로세스의 상태를 pcb에서 읽어옴

레지스터에 저장되어있던 값, pc, 메모리 맵을 pcb에 저장.

pcb는 커널의 data부분에 저장됨 

캐시메모리 플러시도 일어남(프로세스 교체시에만)

 

 

스케줄러

장기 스케줄러 - 메모리에 프로세서가 얼마나 올라갈지 결정 - 타임쉐어링 시스템에는 장기스케줄러 없음(무조건 ready상태)

단기 스케줄러 - 어떤 프로세스를 다음에 running으로 바꿀지 결정, 충분히 빨라야함

중기 스케줄러(swapper) - time sharing system에서는 일단 모두 ready상태로 올려놓으니까 시스템을 살펴보다가 메모리가 부족하다 싶으면 프로세스를 통째로 메모리에서 디스크로 쫓아냄

 

 

 

 

 

Process 2

 

쓰레드 - 프로세스 내부에 cpu 수행 단위가 여러개 있는 것 - lightweight process라고도 부름

스레드는 각각의 스택공간을 가지고, 각각의 pc와 레지스터를 갖는다

코드와 데이터, OS resources는 공유

하나의 스레드가 blocked 되어있어도 동일한 태스크의 다른 스레드가 실행되어 빠른 처리(낮은 응답시간)를 할 수 있다 

장점 - 응답성(이미지 로딩동안 텍스트라도 보내줄수있음), resource sharing(자원을 공유함->공간효율), 경제성(프로세스 만드는 것의 오버헤드보다 작음, 프로세스 컨텍스트 스위치보다 스레드 컨텍스트 스위치가 오버헤드 적음), 멀티코어에서 병렬적으로 빠르게 수행가능

 

 

Process management 1

 

프로세스 생성 - 부모 프로세스가 자식 프로세스를 생성 (복제생성)

프로세스의 트리(계층구조) 형성

자식은 부모의 공간을 복사 후 새로운 프로그램을 메모리에 올림 ( fork()  -> exec() 둘다시스템콜 )

프로세스 종료 - 자발적 ( exit() 시스템콜 ), 비자발적 (부모가 종료시킴 or 부모가 종료됨 or 자식이 할당 자원의 한계치를 넘어섬 abort() )

 

 

Process management 2

 

: 4가지 시스템콜

 

fork()

자식 프로세스는 fork()의 결과(pid)로 0을 부여받음, 부모는 양수

자식은 프로그램 카운터까지 모두 복제되기 때문에 fork() 바로 이후부터 실행하게됨

 

exec()

exec() 시스템콜을 하면 이전의 기억을 모두 잊고 새로운 프로그램으로 새출발하게 됨(환생) - 매개변수로 프로그램(경로)을 입력

다시 돌아올 수 없음 - 레지스터, pc 등 모두 날아가기 때문

 

wait()

프로세스를 sleep 시킴 (block상태 - 자식만들면서 wait하고 자식이 죽으면 커널이 다시 ready시킴)

 

exit()

프로세스를 종료시킬때 호출하는 시스템콜 - 없어도 컴파일러가 알아서 메인함수가 끝날 때 넣어줌

비자발적 종료 - 부모가 자식을 죽임, 자식에게 할당된 태스크가 더이상 필요없음, 사용자가 컨트롤씨로 종료, 부모가 종료됨(자식이 먼저죽게됨)

 

 

프로세스간 협력 - 

 

독립적 프로세스, 협력적 프로세스 두 종류가 있음

프로세스는 각자의 주소공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 못 미침

 

메세지 전달방식 - 메세지를 전달하려면 커널을 통해 통신해야함 - 직접통신과 간접통신(mailbox, 커널에 존재)으로 나눠짐

주소공간 공유방식(shared memory) - 서로 다른 프로세스 간에도 일부 주소 공간을 공유하게 하는 shared memory 메커니즘이 존재

shared memory를 쓰려면 그냥 알아서 쓰는게 아니라 커널한테 시스템콜로 알려서 미리 공간을 매핑해놓고 사용해야함, 일단 매핑되면 커널의 도움 없이 프로세스끼리 알아서 쓰면됨

 

Thread는 사실 하나의 프로세스이므로 프로세스간 협력으로 보기는 어려움.

 

 

 

 

 

대망의 Cpu scheduling

 

여러 종류의 job(process)이 섞여서 실행되기 때문에 스케줄링이 필수적.

cpu와 I/o장치 등 시스템 자원을 골고루 효율적으로 사용.

 

Cpu scheduler - ready 상태의 프로세스 중에서 이번에 cpu를 줄 프로세스를 고른다.(OS 역할)

Dispatcher - cpu를 누구한테 줄지 결정했으면 cpu를 넘겨주는 역할을 하는 친구. (OS 역할), 이 과정을 context switch라고 함

 

스케줄링은 - Nonpreemptive(스스로 반납 - i/o 요청 시스템콜, terminate), preemptive(강제로 cpu 빼앗음 - 타이머인터럽트, i/o완료 인터럽트) 두 종류

 

스케줄링 성능 척도(scheduling criteria)

1. cpu utilization(이용률) - 전체 시간 중 cpu가 놀지 않고 일한 시간의 비율(중국집 주방장이 일한 시간의 비율)
2. throughput(처리량) - 단위 시간당 처리하는 일의 양 (한시간에 짜장이 몇개 나오나)

시스템 입장에서의 성능척도

————————————

1. Turnaround time(소요시간, 반환시간) - cpu를 쓰러 들어와서 I/o를 하러 나가기까지의 시간(process 총 소요시간 아님)
2. Waiting time(대기시간) - ready 큐에서 기다린 시간의 양(중국집 코스요리 중간중간 모두 합친 시간)
3. Response time(응답시간) - cpu를 쓰겠다고 ready 큐에 들어오고 처음으로 cpu를 얻게 된 시간까지의 차이(중국집 단무지)

프로세스 입장에서의 성능척도

 

 

 

스케줄링 알고리즘

 

1. FCFS(first-come first-served)

먼저온 순서대로 처리함 - 실세계와 가장 닮음(은행 번호표, 화장실 등) - 비선점형(새치기없음)

맨 앞의 프로세스가 오래 걸리면 전체 프로세스의 wating time이 길어짐 (convoy effect)

 

1. SJF (shortest job-first)

빨리 끝나는 작업부터 먼저 처리함

Average wating time이 스케줄링 방식 중 가장 짧음

구현방식 두 가지 : 

nonpreemptive - cpu 일단 잡으면 cpu 안뺏김

preemptive - cpu 잡아도 더 짧은 프로세스가 도착하면 뺏김 (SRTF - Shortest-remaining-time-first 라고도 불림)

문제점1: startvation 발생가능 - cpu사용시간이 긴 프로세스는 이론상 영원히 cpu를 못 받을 수도 있음

문제점2: cpu를 얼마나 쓸지 미리 알 수 없음 - 그래서 사용하기 어려운 스케줄링 알고리즘임. 대략 예측만 해서 사용하기도 함(과거의 i/o burst time, cpu burst time 을 활용해서 예측)

 

1. Priority scheduling

우선순위가 높은 프로세스에게 cpu를 주겠다.

A프로세스가 cpu 사용중에 우선순위가 A보다 높은 B프로세스가 도착하면 빼앗는 선점형, 반대의 비선점형으로 구현 가능

SJF도 일종의 priority scheduling임(cpu 사용시간기준)

문제점: starvation - 우선순위 낮은 프로세스는 영원히 실행 불가능할 수도

해결책: aging - 시간이 지날수록 프로세스의 우선순위 높이기

 

1. Round robin (RR)

현대 시스템에서 사용하는 방식, preemptive(cpu 뺏을 수 있음)

각 프로세스는 동일하게 cpu 할당시간을 가짐 (10 ~ 100ms), 할당시간이 모두 끝나면 프로세스가 안끝나도 cpu 뺏기고 ready 큐 맨 뒤로 

응답시간이 빠름

성능: 할당시간을 크게 잡으면 FCFS, 작게 잡으면 context switch 오버헤드

SJF보다 average turnaround time은 길지만 response time은 짧다

 

1. Multilevel queue

레디큐를 지금까지 한줄로 섰다면 이젠 여러 줄로 서 보자 - 대신 줄 마다 우선순위는 있음 (foreground(interactive), background(batch) 로 구분)

Foreground job들은 RR로 처리, background job들은 FCFS로 처리

System process -> interactive process-> interactive editing process -> batch process -> student process

High ——————————————————————priority—————————————————————————> low

노비레벨의 큐는 우선순위를 극복하지 못할 수도 있음(starvation) 그래서 multilevel feedback queue 처럼 한번씩 승격도 시켜줌

아니면 각 ready 큐에 각각 cpu time을 적절한 비율로 할당 (system process 80%, 노비 process 20%)

멀티레벨피드백큐는 일단 프로세스를 가장 높은 우선순위의 큐에 할당하고, 그 다음엔 2번째 우선순위의 큐, 다음엔 FCFS 큐에 할당

 

 

 

< cpu가 여러개 있을때의 스케줄링 - multiple-processor scheduling >

 

Homogeneous proessor인 경우 - ready 큐에 한줄로 세워서 프로세서를 밀어넣고 cpu가 알아서 꺼내가게 할 수 있음, 그러나 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있으면 복잡해짐

Load sharing - 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요 (별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법)

Symmetric multiprocessing(SMP) - 각 프로세서가  각자 알아서 스케줄링 결정

Asymmetric multiprocessing - 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

 

 

<real-time scheduling>

Hard real-time systems - 반드시 정해진 시간 안에 끝내도록 스케줄링

Soft real-time computing - 일반 프로세스에 비해 높은 priority를 부여

 

 

<thread scheduling>

Local scheduling(user level scheduling) - 사용자 수준의 thread library에 의해 어떤 스레드를 스케줄할지 결정 (운영체제는 스레드를 모르기 떄문에 프로세스만 신경씀, 프로세스가 알아서함)

Global scheduling(kernel level scheduling) - 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정 (운영체제가 함)

 

 

Process synchronization 1 

 

Race condition - memory address space를 공유하는 cpu가 여럿 있는 경우 race condition의 가능성이 있음(커널의 데이터 등)

1커널모드에서는 컨텍스트 스위치를 막는다

2해당 공유데이터에만 락을 건다

 

Critical section: 각 프로세스에서 공유데이터를 접근하는 코드

하나의 프로세스가 critical section에 있을 때 다른 프로세스는 들어갈 수 없게 해야 한다. 알고리즘 1,2,3

 

프로그램적 해결법의 충족 조건

1. Mutual exclusion(상호 배제)

어떤 프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스는 critical section에 들어가면 안됨

1. Progress(진행)

아무도 critical section에 있지 않은 상태에서 어느 프로세스가 critical section에 들어가고자 하면 들어가게 해줘야한다

1. Bounded wating(유한대기)

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때 까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야함(starvation이 생기면 안된다 - 언젠가는 들어가는 것이 보장되어야한다)

 

피터슨 알고리즘(3) - 작동 잘 하지만 스핀 락

하드웨어적으로 read & modify를 atomic하게 수행할 수 있도록 지원하면 싱크 문제가 간단히 해결됨.( test_and_set() )

하지만 개발자 입장에서는 번거로움 - semaphore 등장. 단, 추상적 개념일 뿐임(연산이 atomic함을 보장하기만 하면 됨)

세마포어 - 공유자원을 획득하고 반납함 - P는 획득, V는 반납

여전히 P 과정에서 스핀락

Block & wakeup 방식의 슬립락 방식으로 구현할 수도 있음 - P연산에서 자원을 얻지 못하는 상황이면 block상태로. 다른 프로세스가 V연산으로 반납하고 block 큐에 프로세스가 있으면(value가 0 이하면 - 내가 V연산으로 +를 했음에도 누군가 P 연산으로 값을 빼고 기다리고 있다는 상태를 의미) wakeup시켜줌

 

Critical section의 길이가 길면 block/wakeup 방식이 적당 - 일반적으로 더 좋음

짧으면 busy wait가 나을 수도 있음 - 프로세스를 블록시키고 꺠우는 과정의 오버헤드가 있으므로

 

Mutex = binary semaphore(0또는 1만 가지는 세마포어, 주로 mutual exclusion (lock/unlock)에 사용)

 

데드락

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 - 두 리소스가 충족되어야 일이 시작되는데 서로 하나씩 갖고 양보 안함

기아현상

특정 프로세스들만 자원을 갖고 본인은 평생 자원을 못가짐. 일종의 데드락이라고도 볼 수 있기는 함 - 그러나 데드락이 아니어도 기아현상 발생 가능

 

Bounded-buffer problem (producer-consumer problem)

원형 공유메모리 버퍼가 있음

 

Reader-writers problem

읽기-쓰기 문제

한 프로세스가 write 중일때  process가 접근하면 안됨

read는 괜찮다

Writer 기아 발생가능, 신호등 두면 됨

 

Dining-philosophers problem

데드락 - 모두가 동시에 배고파서 왼쪽젓가락 집고 놓지 않음

해결방법 - 4명의 사람만 앉게한다, 두개 모두 집을 수 있을 때만 집게한다, 비대칭(짝수사람은 왼쪽, 홀수사람은 오른쪽부터 집도록)

 

Monitor - 세마포어의 번거롭고 실수할 수 있는 부분을 해결

동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

모니터 내부에 공유데이터를 두고 내부의 operation을 통해서만 접근할 수 있게 - 클래스의 멤버변수와 getter 같은 느낌인듯

락을 고려할 필요 없음. 모니터가 알아서 함 - oop좀 아시는구나

엔트리 큐(컨디션)가 존재하는데, 프로세스가 줄 서있음. wait와 signal 함수로 관리함

모니터 내에서는 한번에 하나의 프로세스만 활동가능

 

 

 

데드락(교착상태)

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

 

데드락의 발생조건 4가지 - 4가지중 하나라도 만족 못하면 발생X

Mutual exclusion(상호배제) - 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

No preemption(비선점) - 프로세스는 자원을 스스로 내어놓을 뿐 강제로 뺏기지 않음

Hold and wait(보유대기) - 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유자원을 놓지 않고 계속 가지고 있음

Circular wait(순환대기) - 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

 

데드락 처리방법 

1. Deadlock prevention - 자원 할당 시 Deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것
2. Deadlock Avoidance - 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원할당 / 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원할당

뱅커스 알고리즘

1. Deadlock detection and recovery - 데드락 발생은 허용하되 그에 대한 detection 루틴을 두어 데드락 발생시 recover

Recovery - process termination(데드락프로세스 다 죽임), resource preemption(비용 최소화victim 선정, 동일한 프로세스가 victim(starvation))

1. Deadlock ignorance - 데드락을 시스템이 책임지지 않음, 대부분의 OS가 채택

데드락이 드물게 발생하므로 탐지와 조치 자체가 오버헤드, 사람이 직접 이상함을 느끼고 프로세스 킬

 

 

 

 

Memory management 1

 

Logical address(=virtual address)

프로세스마다 독립적으로 가지는 주소공간

각 프로세스마다 0번지부터 시작

cpu가 보는 주소는 logical address

 

Physical address

메모리에 실제 올라가는 위치

 

주소 바인딩 : 주소를 결정하는 것

Symbolic address(프로그래머의 변수,함수) -> logical address -> physical address

 

주소바인딩

Compile time binding

Load time binding

Execution time binding - 하드웨어 필요(MMU - memory management unit, 레지스터 2개 필요)

Dynamic loading -프로세스 전체를 메모리에 미리 올리는게 아니라 해당 루틴이 불려질때 메모리에 load하는 것, 많은 코드가 가끔 사용되는 경우 유용(ex.오류처리코드)

Overlays - 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림 - 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현 - 운영체제의 지원 없음(수작업)

Swapping - 프로세스를 일시적으로 메모리에서 backing store(swap area)로 쫓아내는것 - 중기 스케줄러가 priority가 낮은 프로세스를 내쫓음, priority가 높은 프로세스를 불러옴

Dynamic linking - static linking(라입러리가 프로그램의 실행파일 코드에 포함, 파일크기커짐, 메모리낭비), dynamic linking(라이브러리가 실행시 연결(link)됨, OS도움필요, )

링킹? - 여러군데 존재하던 컴파일된 파일들을 묶어서 하나의 실행파일로 만드는 과정

 

 

 

Allocation of physical memory

메모리는 일반적으로 두 영역으로 나뉘어 사용

OS상주영역 - 낮은 주소

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

프로세스 연속할당방법(구형,고정분할방식,가변분할방식)

외부조각(공간이 작아서 사용이 안됨),내부조각(사용(할당)하고 남는 공간)

 

불연속할당방법(현대시스템,페이징,세그멘테이션,페이지드세그멘테이션)

페이징 - 주소공간을 페이지단위로 잘라서 올리기 - 주소변환이 복잡

세그멘테이션 - 주소공간을 의미 단위로 잘라서 올리기

 

 

Paging

로지컬메모리 -> 페이지테이블 -> 피지컬메모리

페이지테이블은 피지컬메모리에 존재함. 즉 메모리 접근을 위해서는 페이지테이블접근 1회, 실제 메모리접근 1회 = 총 2회

Page-table base register(PTBR)가 page테이블을 가리킴, Page-table length register(PTLR)가 테이블 크기를 보관 (2개의 레지스터)

속도 향상을 위해 translation look-aside buffer(TLB)라 불리는 고속의 룩업하드웨어 캐시 사용

메모리 참조 전에 빠른 TLB를 먼저 찾아봄 - 있으면 바로 주소변환(메모리 한번만 접근하게됨)

Parallel search 가능, context switch 때 flush됨

 

2단계 페이지테이블

공간복잡도를 줄이기 위함. 사용 안되는 outer-page table(NULL)에 대해서는 inner page table 생성 안돼서 효율적

 

Multilevel paging

다단계 페이지 테이블 - 메모리접근 더 많음 - TLB 활용

 

페이지테이블의 Valid/invalid 비트. protection 비트

 

Inverted page table

시스템에 페이지테이블 단 하나 - 물리적인 메모리의 페이지프레임 갯수만큼 엔트리 존재

공간을 많이 줄일 수 있음, 시간오버헤드(전부다 search를 해봐야함) 그래서 TLB parallel 서치랑 같이 활용

 

Shared page

다른 프로세스와 공유할 수 있는 페이지

A프로세스와 B프로세스에 같은 코드가 존재한다면 하나의 코드만 메모리에 올림, 모든 프로세스의 논리적 주소에서 동일하게 매핑되어야함

Read-only로 세팅해야함

 

 

Segmentation

프로세스를 의미 단위인 segment로 구성

세그먼트 테이블 <segment-number, offset>

Base, limit 레지스터

Read/write/execution 권한비트

allocation 문제

테이블엔트리가 작으므로 메모리차지 적음

프로세스끼리 sharing이 수월함

 

 

 

Paged segmentation

세그먼트 하나가 여러 페이지로 구성됨

allocation 문제 사라짐

 

 

cpu가 주소를 갖고 메모리 접근을 하는 것은 OS도움 없음 MMU 하드웨어가 함

주소변환은 무조건 하드웨어

OS는 I/O가 있을때 끼어들음

 

 

 

 

 

 

대망의 버츄얼 메모리

 

Demand paging - 요청이 있으면 페이지를 메모리에 올림

I/O 감소, Memory 사용량 감소, 빠른 응답시간, 더 많은 사용자 수용

invalid 비트(페이지폴트) 접근 -> MMU가 트랩 발생시킴-> 운영체제가 스왑영역(I/O) 접근해서 메모리에 올림

페이지폴트 비율을 줄여야함(I/O 빈도를 줄여야함)

 

Page replacement - 빈페이지가 없으면 뭔가(victim) 쫓아내야함(OS의 업무)

Replacement algorithm - 가급적 페이지폴트 비율을 낮추는 것이 목표 - 평가 = 주어진 page reference string에 대해 page fault를 얼마나 내는지

 

Optimal algorithm(Belady’s algorithm) : 가장 먼 미래에 참조되는 page를 replace - 미래를 알아야 하므로 실제 사용은 어렵 - 다른 알고리즘과 비교하는 성능지표로 사용됨

FIFO algorithm : 먼저 들어온 것을 내쫓음 - 프레임이 늘어났는데 폴트가 늘어나는 이상현상 발생가능

LRU algorithm : 가장 오래전에 참조된 것을 내쫓음 O(1)

LFU algorithm : 가장 참조횟수가 적은 페이지 내쫓음 - 힙으로 구현 O(log n)

 

Paging system에서 LRU,LFU 사용 가능한가? - 하드웨어로 참조하는데 운영체제가 참조횟수나 시기를 알 수 있나? - 가상메모리 시스템에서 어차피 불가능

 

Clock algorithm - LRU의 근사 알고리즘 (second chance algorithm, NRU(not used recently) algorithm)

서큘러 리스트 사용

참조되면 Reference bit 1로 설정 - 하드웨어가 함

운영체제는 페이지를 돌면서 reference bit이 1이면 0으로 바꾸고 다음 기회를 줌, 0이면 쫓아냄

Modified bit - 수정되었는지 확인하는 비트 - 1이면 쫓아낼때 디스크에 쓰고 쫓아내야함 - 비용 더 높음 -> 쫓아낼 우선순위 낮음

 

 

 

 

Allocation problem - 각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인가

균등할당, 크기비례할당, 우선순위비례할당

 

Thrashing - 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우에 발생

프로세스 증가, 할당된 프레임수 감소, Page fault rate 높아짐, cpu utilization 낮아짐, OS는 multiprogramming degree를 높여야한다고 판단, 프로세스 증가, 악순환

이걸 막기 위해서는 multiprogramming degree를 낮춰야함 

-> working-set model 페이지 부족하면 부족한채로 실행하지 않고 통째로 반납하고 swap out(suspended)

-> PFF(page-fault frequency) scheme - page-fault rate의 상한과 하한값을 둠 - rate 높으면 frame 더 할당, 낮으면 줄임, 빈프레임 없으면 swap out

 

페이지 사이즈 줄이면 메모리 이용은 효율적, 내부조각 감소하지만 - 페이지 수 증가, 테이블크기 증가, 전송 효율성 감소

그래서 요즘은 페이지 크기가 커지는 추세

 

 

 

 

 

 

 

 

http://www.kocw.net/home/search/kemView.do?kemId=1046323 

운영체제

 

https://hyonee.tistory.com/95

[운영체제(OS)] 면접 예상 질문과 답변