Lemonyun

디스크의 파일 데이터에 접근하는 방법

하드 디스크는 읽기의 최소 단위가 block (512byte)

Contiguous Allocation

ㄴ 파일의 크기를 키우는데 제약이 있음

ㄴ 장점 : 짧은 I/O, direct access

하드디스크 연속적으로 할당하면 rotation/seek 시간이 짧음

realtime file이나 프로세스의 swap area용도로 적합

Linked Allocation

linked allocation의 개선한 시스템 -> FAT

부팅할 때 file-allocation table을 메모리에 올려놓음

파일이 시작주소를 가지고 table에서 왔다갔다 하면 됨

fat은 중요한 정보이므로 여러개 복제해서 보관

Indexed Allocation

파일이 인덱스 블록을 가리킴

UNIX 파일 시스템의 방식

Demand Paging 

실제로 필요할 때 page를 메모리에 올리는 것

메모리 사용량 감소

빠른 응답 시간

더 많은 프로세스를 메모리에 올릴 수 있다

위 그림에서 페이지 테이블은 사용가능한 가상주소영역의 크기만큼 만들어진다. (0번 ~ 7번 페이지)

프로그램을 구성하는 페이지는 0번 ~ 5번 페이지이지만 페이지 테이블은 0번 ~ 7번 페이지까지 만들어진다.

1번 3번 4번 페이지는 프로그램에서 사용되는 프로그램이지만 메모리에 올라가있지 않으므로 invalid

프로그램에서 사용되지 않는 6번 7번 페이지는 안쓰니까 invalid

주소 변환시 invalid page에 접근하게 되면 page fault가 발생 (요청한 페이지가 메모리에 없는 경우)

page fault가 발생하면 MMU가 trap(소프트웨어 인터럽트)를 발생시켜 cpu가 운영체제로 넘어가고 페이지를 올리는 작업을 수행함

Page fault 처리 과정

1. 적절한 주소인지 확인 -> 아닌경우 프로세스 abort() 

2. 메모리에 존재하는 비어있는 페이지 프레임을 찾는다. 

3. disk에서 memory로 페이지를 읽어온다. (disk I/O) 

4. disk I/O가 일어나므로 CPU를 뺏긴다. (block 상태)

5. disk 읽어서 memory로 읽어오면 페이지 테이블 새로운 엔트리에 페이지 프레임 번호 기록하고, valid로 세팅

6. ready queue에 프로세스를 넣기 (ready 상태)

비어있는 페이지 프레임이 없는경우

어떤 page frame을 쫓아낼 것인지 결정하는 replacement 알고리즘이 필요함

쫓아내는 과정

1. 쫓아내는 페이지 프레임을 swap area에 복사 (write 작업으로 페이지가 변경되어 swap area에 있는 데이터와 다를 수 있기 때문)

2. 해당 페이지 엔트리를 invalid로 세팅

3. 새로운 페이지를 swap에서 physical memory로 올림

4. 페이지 테이블에 새로운 엔트리에 대해 프레임 번호와 valid 세팅

Clock Algorithm (Second change algorithm)

Paging System에서 사용하는 replacement 알고리즘

LRU를 근사한 알고리즘

page fault가 나지 않으면 운영체제는 제어권을 얻을 수 없기 때문에 어떤 페이지가 최근에 참조되었는지(LRU) 어떤 페이지가 가장 자주 참조되었는지(LFU)를 알 수 없음

페이지 테이블 entry 마다 reference bit와 modified bit을 둔다. 

하드웨어는 메모리 참조가 일어날때 reference bit을 설정해두고

나중에 os가 빈페이지를 찾을 때 reference bit가 1로 되어있는거 0으로 바꾸면서 0을 찾는다.

페이지가 write으로 참조되는 경우 페이지의 modified bit을 1로 세팅

ㄴ 1로 세팅 되어있으면 나중에 이 페이지 쫓아낼 때에는 swap area에 복사가 필요

ㄴ 0이면 그냥 지워도 됨

페이지 프레임 할당 문제

얼마만큼의 페이지 프레임을 프로세스에 할당 해주어야 page fault가 덜 발생할 것인가?

local replacement - 미리 프로세스에 정해진 프레임 개수 할당하고 프로세스 별로 replace 알고리즘을 적용하는 방법

global replacement - 다른 프로세스에서 뺏을 수 있다.

Thrashing

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

Page fault rate가 높아짐

I/O 시간이 많아져 CPU 이용율이 낮아짐

swap in / swap out 하느라 시간을 다 씀

동시에 너무 많은 프로세스 안 올라오게 하는 global replacement 알고리즘

1. working set algorithm

ㄴ working set window를 사용하여 최근에 사용한 n개의 페이지 집합을 유지하고, 집합의 크기보다 비어있는 페이지 프레임 수가 작으면 워킹셋에 있는 페이지 전부 swap out 시키고 프로세스 suspend 상태로 전환

2. PFF(page-fault-frequency) algorithm

ㄴ page fault rate에 상한값가 하한값을 두어 프로그램마다 할당하는 frame의 수를 줄인다.

page size

가 작으면 

전체 페이지 수가 증가하므로

페이지 테이블 크기도 증가

disk tansfer 효율성 떨어짐 - seek/rotation 비용이 커짐

locality성이 떨어짐

주소 바인딩 (=주소 변환)

주소 바인딩 : 논리적 주소(가상 주소)를 physcial 메모리 주소로 매핑하는 작업

주소바인딩이 일어나는 시점에 따라 3가지로 분류 가능

1. 컴파일 타임 바인딩

ㄴ 물리적 메모리 고정 위치에 프로그램이 올라가는것

2. 로드 타임 바인딩

ㄴ 실행될 때 프로그램이 올라가는 위치가 결정됨

3. 실행 중 바인딩

ㄴ 실행될 때, 실행중 프로그램이 올라가는 위치가 결정되고 바뀔 수 있다.

용어 : dynamic loading과 dynamic linking

dynamic loading : OS가 프로그램 일부 필요한 부분만 메모리에 올리는 것은 운영체제가 지원 해주는 페이징 시스템

비슷한 말인데 dynamic loading은 프로그래머가 os 라이브러리를 사용해서 구현하는 개념

static linking

ㄴ 라이브러리가 프로그램의 실행 파일 코드에 포함되어 실행 파일의 크기가 커짐

ㄴ 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비

dynamic linking (윈도우 dll 파일) (shared library)

ㄴ 라이브러리가 실행시 연결(link)됨 

ㄴ 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠

ㄴ 라이브러리가 메모리에 이미 있으면 그 주소로 가고 없으면 디스크에서 읽어옴

ㄴ 운영체제의 도움이 필요함

물리적 메모리에 프로세스를 할당하는 방법

1. 연속 할당

ㄴ 고정분할, 가변분할 방식

ㄴ 운영체제는 메모리에 어떤 공간이 할당되어 사용하고 있는지, 가용 공간(hole)인지 정보를 유지해야 함

2. 불연속 할당

ㄴ paging, segmentation, paged segmentation

Paging

ㄴ process의 virtual memory를 동일한 사이즈의 page 단위로 나눔

ㄴ virtual memory의 내용이 page단위(물리적 메모리의 frame과 같은 단위)로 저장됨 

ㄴ 일부는 backing storage(swap area)에, 일부는 physical memory에 저장

ㄴ 페이지 테이블을 이용함

ㄴ 프로그램마다 페이지 테이블을 가질 수 있음

두개의 레지스터 사용

PTBR(page table base register) : 페이지 테이블의 주소

PTLR(page table length register) : 페이지 테이블의 크기

TLB

CPU와 page table(main memory) 사이에 있는 캐싱 역할을 하는 하드웨어 

빈번히 참조되는 entry 몇개에 대해서만 내용을 저장하고 있음

TLB 내용 전체를 탐색해야 하기 때문에 Parallel search가 가능한 Associative register를 사용

TLB 탐색했는데 없으면 page table 보면 됨

TLB는 context switch 때 flush

2단계 페이지 테이블(계층적 구조)

ㄴ page tabe 자체를 page로 구성

ㄴ 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL

ㄴ 64-bit 명령어 기계에서는 적합하지 않음

ㄴ 2단계 페이지 테이블을 사용하지 않는 페이지에 대해서는 안쪽 테이블이 만들어지지 않음

Inverted page table

ㄴ 전체 시스템에서 페이지 테이블이 하나만 존재

ㄴ 물리적 메모리 페이지 프레임 개수만큼 페이지 테이블의 엔트리가 존재

ㄴ 하나의 페이지 프레임 엔트리는 PID와 가상 주소를 가짐

ㄴ 물리적 메모리에 연속적으로 저장된 테이블에서 PID와 가상주소가 일치하는 인덱스를 찾아 물리적 주소로 변환

ㄴ 페이지 테이블을 associative register로 병렬 탐색해야함 (비용 발생)

Memory Protection

페이지 접근 권한에 대한 bit

ㄴ read/write/read-only

ㄴ 프로그램의 code는 내용이 바뀌지 않아야 하므로 read-only

ㄴ 프로그램의 data는 읽기 쓰기 가능해야하므로 read/wirte

페이지 테이블의 valid-invalid bit

valid-bit

ㄴ 주소 변환이 가능한 경우

invalid-bit

ㄴ 프로세스가 그 페이지를 사용하지 않는 경우

ㄴ 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

ㄴ 주소 변환시 invalid bit이 set 되어 있으면 page fault가 발생

Shared pages

ㄴ 같은 프로그램을 여러개 돌리는 경우 프로세스들의 code 부분은 똑같기 때문에 하나만 메모리에 올리는 기법

ㄴ shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함

Segmentation

ㄴ 프로그램을 의미 단위로 (크기는 균일하지 않음) 잘라서 물리 메모리에 올린다.

ㄴ 함수, 전역 변수, 스택, symbol table, 배열 등의 단위로 나눌 수 있다.

ㄴ protection bit를 세그먼트 별로 줄 수 있어서 paging 보다 효과적인 protection이 가능하다. sharing면에서도 paging보다 효과적이다.

ㄴ 세그멘테이션 테이블에는 시작 위치와 세그먼트 길이가 기록됨 (페이지와는 달리 길이가 일정하지 않기 때문에)

STBR(segment table base register) : segment table의 주소

STLR(segment table length register) : 프로그램이 사용하는 segment의 수

deadlock은 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다.

deadlock의 발생조건 4가지

1. mutual exclusion

2. no preemption

3. hold and wait

4. circular wait

circular wait을 확인하기 위해 자원할당 그래프를 그려 확인 할 수 있다.

deadlock의 처리 방법 4가지

1. 예방 - deadlock의 발생조건 4가지를 막는 방법 - 비효율적

2. 회피 - 자원 할당그래프 알고리즘, bankers 알고리즘을 통해 최악의 상황에 deadlock이 발생할 수 있는지 여부 파악해서 프로세스에게 자원 줄지 안줄지 결정

3. 탐지 & 복구 - 연관된 프로세스 죽이기, 연관된 프로세스의 자원 뺏기

4. 무시 - 현대 OS 방식, 사용자가 처리하도록 놔둠, 나머지 방식이 오버헤드가 크기 때문에

Race Condition

storage를 공유하는 둘 이상의 입력이 있는 경우 발생할 수 있음

1. 여러개의 CPU가 메모리에 접근하려는 경우

2. 공유 메모리 주소 공간에 여러개의 Process가 접근하려는 경우

구체적인 상황

1. 프로세스 A에서 커널의 코드가 실행중(커널의 데이터를 쓰는 중)에 인터럽트가 발생하여 프로세스B로 넘어가고 B에서 커널의 코드가 실행되어 커널 주소공간의 커널의 데이터를 쓰는 경우

ㄴ 커널의 데이터를 쓰는동안 interrupt를 비활성화하는 방법으로 해결

2. 프로세스 A에서 커널의 코드가 실행중인데 타이머 interrupt로 인해 context switching이 일어나는 경우

ㄴ 커널모드가 끝날때까지 기다렸다가 CPU를 뺏는 방법

Critical Section(임계 구역)

공유 데이터를 접근하는 코드

하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

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

1. mutual exclusion

ㄴ 한 프로세스가 자원을 쓰고 있으면 다른 프로세스는 들어오면 안됨

2. progress

ㄴ 자원을 아무도 안 쓰고 있으면 들어가야 함

3. bounded Waiting

ㄴ 기아가 되는 프로세스가 없어야 함

소프트웨어적 해결

 Peterson's Algorithm -> Busy waiting (무한반복문 대기 : CPU와 메모리를 쓰면서 wait)

하드웨어적 해결

읽기와 쓰기를 한번에 하는(atomic) Test_and_set instruction을 사용하면 됨

세마포어

추상 자료형

세마포어 변수는 정수값을 가짐 (남아 있는 자원의 개수)

세마포어 변수에 대해서 P 연산 V 연산을 수행할 수 있음 P(s)는 자원을 하나 가져가는 것 V(s)는 자원을 하나 반납하는 것

P 연산과 V 연산의 구현은 시스템에 따라 다르게 구현될 수 있는데, 앞서 말했던 busy waiting 방식과 block & wakeup 방식이 있다. block & wakeup 방식은 기다리는 프로세스를 커널 데이터에 구현되어 있는 Resource queue로 보내 block(sleep)되게 하는 것임

일반적으로는 block/wakeup 방식이 좋지만 critical section의 길이가 매우 짧은 경우 busy-wait 오버헤드보다 block/wakeup 오버헤드가 커지는 경우도 있다.

Counting semaphore

ㄴ 0이상의 정수 값을 가짐

ㄴ resource counting에 사용

Binary semaphore (=mutex)

ㄴ 0 또는 1값만 가질 수 있는 semaphore

ㄴ 주로 lock unlock에 사용

세마포어를 이용해서 프로그래밍 할 때 프로그래머 논리적으로 코딩하지 않으면 deadlock 문제가 생길 수 있음

현대의 CPU는 Preemptive 스케줄링(CPU 자원을 뺏을 수 있는)이며 Round Robin 방식을 사용한다.

스케줄링 알고리즘은 multilevel feedback queue 방법을 사용한다.

Multi level feedback queue

CPU ready queue를 여러개 두는 방법, 각 큐마다 priority가 달라 우선순위가 높은 큐에 들어온 프로세스가 먼저 처리됨

CPU burst 시간이 긴 프로세스들은 특정 기간 내에 작업이 끝나지 않아 priority가 더 낮은 큐로 강등당함

I/O burst 시간이 긴 대화형 작업들은 강등당하기전에 끝나기 때문에 보통 빠른 시간내에 결과를 받을 수 있다.

Starvation 문제가 있다. -> 주기적으로 모든 프로세스를 가장 높은 우선순위의 큐로 이동시키는 방법으로 해결

다양한 변수 설정이 가능하다.

1. 사용할 큐의 개수

2. 큐당 타임슬라이스의 크기

3. 우선순위 상향 조정 기간

CPU가 여러개인 경우의 스케줄링

1. Homogeneous Processor인 경우

ㄴ Queue에서 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.

2. Load sharing

일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요

3. Symmetric Multiprocessing

ㄴ 각 프로세서가 각자 알아서 스케줄링을 결정

4. Asymmetric Multiprocessing

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

스레드 스케줄링

Local Scheduling

ㄴ 유저 레벨 스레드의 경우 사용자 수준의 스레드 라이브러리에 의해 어떤 스레드를 스케줄할지 결정

Global Scheduling

ㄴ 커널 레벨 스레드의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정

스케줄러의 종류

1. Long-term scheduler

ㄴ 어떤 프로세스를 메모리에 올릴 것인가?

2. Short-term scheduler

ㄴ 어떤 프로세스에게 CPU 제어권을 줄 것인가?

3. medium-term scheduler(Swapper)

ㄴ 어떤 프로세스를 swap area로 빼고 올릴 것인가? (Suspended된 프로세스를 먼저 뺀다)

ㄴ degree of multiprogramming을 제어

부모 프로세스가 자식 프로세스를 생성할 때 자식은 부모의 주소 공간을 복사함 (fork)

자식은 그 공간에 새로운 프로그램을 올림 (exec)

Copy-on-write : 자식 프로세스는 부모 프로세스의 code data stack을 쓰다가 write이 발생했을 때, 부모의 code data stack의 필요한 부분을 복제하여 메모리에 올린다.

프로세스 관련 시스템 콜

fork() -> 복제

exec() -> 덮어 쓰기

exit() -> 프로세스의 종료. 자식 프로세스의 경우 부모 프로세스엑 output data를 보냄 

abort() -> 부모가 자식을 강제 종료

ㄴ 자식이 자원의 할당 한계치를 넘어서는 경우

ㄴ 자식이 더 이상 필요 없는 경우

ㄴ 부모가 종료(exit)하는 경우

wait() -> 부모 프로세스에서 실행하면 Child Process가 종료될 때 까지 block(sleep)상태로 대기, 종료되면 ready상태

프로세스간 자원의 공유

메세지를 전달하는 방법 : message passing : 커널을 통해 메세지 전달

주소 공간을 공유하는 방법 : shared memory : 서로 다른 프로세스 간에도 일부 주소공간을 공유

스레드

스레드는 프로세스 하나에 CPU 수행단위를 여러개 두는 것이다.

스레드는 같은 프로세스의 다른 스레드와 프로세스의 code, data, os 자원을 공유한다. (= task)

프로세스 주소 공간 내부에 각각의 스레드별로 스택이 존재한다. PCB에도 각각의 스레드를 위한 PC 및 다른 레지스터 값들에 대한 정보를 담고 있다.

스레드의 장점

1. 하나의 스레드가 Blocked 상태인 동안에도 동일한 task 내에 다른 스레드가 실행(running)되어 빠른 처리를 할 수 있다.

2. 병렬성을 높일 수 있다. -> CPU가 여러개인 경우 여러개의 CPU에서 스레드가 병렬적으로 실행될 수 있다.

3. 메모리 낭비를 줄일  수 있다. -> 동일한 작업을 스레드가 아닌 프로세스 단위로 나누면 code data 부분이 중복되기 때문에

4. 비용적으로 좋다. -> 프로세스간의 CPU switching보다 스레드간의 CPU switching이 더 빠르다. 바꿔줘야 할 문맥이 적기 때문에

커널 스레드와 유저 스레드

커널 스레드: 운영체제가 스레드를 지원, 스레드 스케줄링을 커널에서 지원

유저 스레드: 운영체제는 스레드의 존재를 모름, 유저 라이브러리를 사용하여 알아서 처리