this.code();

<Resident Set>- memory에 들어있는 page들의 집합

Resident set size: memory에 있는 process들의 page의 개수

<Resident set size를 정해주는 방법>

Fixed-allocation: main memory의 정해진 개수의 frame을 process에게 주는 방법

[Local Scope]: page fault발생으로 replacement시 제거page를 갖고있는 page 중 선택

Variable-allocation: main memory의 frame을 상황에 따라 가변적으로 조절

[Local Scope]: 할당 후 page fault빈도에 따라 중간중간에 고정된 할당량을 변경(재조정)하는 것

[Global Scope]: page replacement시 모든 page를 대상으로 선택

<Page-Fault Frequency Scheme>: process에게 주는 frame수 조절

<Scheduling 종류>

process scheduling: process 즉, cpu 하드웨어자원을 어느 process에게 할당할 것인지 결정하는 것

§ CPU 하드웨어 대상 Scheduling_scheduler 실행 시간 간격이 기준

Long-term scheduling: 시간간격이 김

Medium-term scheduling: 시간간격이 중간

Short-term scheduling: 시간간격이 짧음 (우리가 말하는 process scheduling)

§ I/O 대상 Scheduling: I/O Scheduling: 입출력 요청시 어떤 I/O를 먼저 해줄 것인가

<Scheduler가 하는 일>- ready queue로 집어넣는데 processor의 것과 새로 queue로 들어온 것 비교.

if (processor의 process 우선순위 < 새로운 process 우선순위) => context switch

i) context saver: 실행상태 process context를 PCB에 저장

ii) scheduling algorithm: 다음 실행할 process 선택

iii) Dispatcher: process context된 새로운 process에 CPU를 배정

<Scheduler 호출시점은 언제인가?> => context 발생시점과 동일

§ preemptive: 원하지 않게 CPU를 뺏긴것

- ready 상태가 될 때 (block에서나 new상태에서 ready상태로 갈 때)

running => ready 상태 (time slice같은 때)

§ non-preemptive: 자발적으로 CPU를 놓음

running => blocked 상태 (I/O나 자원 요청)

terminated

<Scheduling 알고리즘>

사용자 관점: response time(사용자의 명령시작~system 반응전까지의 시간)이 짧을수록 좋음

System관점: throughput, cpu utilization이 높을수록 좋음

Priority: PCB의 priority로 비교 // 단점: starvation(우선순위가 너무 낮아 cpu 배정이 안되는 현상 발생가능)

<Scheduling Criteria: 성능 기준치>

[UNIX와 Linux 운영체제의 Scheduling: 529~531p]

Base Priority: 고정 우선순위, 불변값

Dynamic Priority: 동적 우선순위

둘 다 모두 PCB의 Priority에 저장됨

[Text Editor(우선순위가 높음) vs Compiler(우선순위가 낮음)]

input이 없다면 editor는 block상태가 되어버림. (text editor는 interactive, compiler는 batch)

input이 있다면 editor는 wake 즉, ready상태가 되어 preempted process인 compiler는 ready상태가 됨(compiler는 절대! block상태가 되지 않음)

editor의 동작이 끝나면 block 상태로 바뀌며 compiler는 다시 계속 실행된다.

<Multli-level Page Table>

process의 크기∝page table 크기∝page entry수 이기에 paging이 단점이 될 수 있다

<Two-Level in 32-bit address>

<Two-Level Paging>

<TLB: Translation Lookaside Buffer = associative memory>

최근에 access한 process page frame#을 저장하는 cache

page#과 Frame#을 한 쌍으로 저장하는 방식.

- 32bit address의 경우, page가 2계층인데 가상주소공간⇑=>page table⇑=>계층⇑=time consuming⇑

- 다계층 page table을 가진 demand paging방식에서 page table을 읽는데 걸리는 시간을 줄이는 방법

TLB hit: cache에 원하는 정보가 존재

TLB miss: cache에 원하는 정보X (outer page table-> page table-> process page로 메모리 access 필요)

<Effective Access Time: TLB의 process 접근 평균시간>- page fault 발생은 하지않을 때

RAM access time = 1 μs , TLB내용 읽는 시간 = ε , Hit ratio = α (0 ≤ α ≤ 1)

TLB hit = ε+1μs

TLB miss = ε+1μs+1μs (TLB에 있는지 확인 + memory에 있는 page table ＋ 실제 메모리)

EAT = (ε+1μs)α + (ε+1μs+1μs)(1-α) = 2μs + ε - α

단, TLB가 없으면 2μs이기에 α >> ε 임을 알 수 있다.

또한, for나 while과 같이 반복문에서 반복횟수가 늘어날수록 α⇑

 

 

 

 

<Page Replacement>

demand paging의 경우 필요한 page를 메모리에서 그때그때 가져와야 하는데, 만약 memory frame에 빈공간이 없으면 들어와 있는 memory를 보조기억장치로 보내고 빈공간을 만들어야해서 page replacement algorithm이 사용된다.

 

가상메모리의 경우, disk같은 보조기억장치의 가상주소공간을 만들어 필요한 page만 메모리로 가져와 실행하는데, 만약 메모리 frame이 다 차버리면 어떤 것을 replace 할것인지 중요하다.

<EAT_Demand paging>

page fault: process가 실행시 주소를 access할 때, 대상 page가 메모리에 없을 때 발생

page fault가 발생할 확률 page fault rate를 p라 하자. 이때 EAT는 다음과 같다.page fault: process가 실행시 주소를 access할 때, 대상 page가 메모리에 없을 때 발생한다.

page fault가 발생할 확률 page fault rate를 p라 하자. 이때 EAT는 다음과 같다.

EAT = (1-p)⦁memory access + p⦁{page fault overhead + [swap page out] + swap page in ＋ restart overhead }

이때, 1-p일 때, memory access는 disk에 갈 필요가 없기 때문이고

page fault overhead는 page fault interrupt 처리+replacement algorithm 시간

swap page out은 쫓아내는 시간으로 modified bit=0일 때, 생략될 수 있다.

swap page in은 필요한 page를 읽어오는 시간이며

restart overhead는 instruction을 재실행하는데 걸리는 시간이다.

<Degree of multiprogramming>: main memory에 들어있는 process 수로 

고정분할, 동적분할방식에 비해 가상메모리 방식을 사용할 때가 더 값이 큼

<Thrashing>

CPU utilization이 갑자기 떨어지는 구간으로 다음과 같은 원인이 있다.

locality(working set) 크기 > 전체 memory 크기

[locality]: process에서 code, data같은 반복적으로 access해야하는 부분

<Thrashing 해결책: Process Suspension>

보조기억장치로 이동시키는 방법으로 swap out, swap to disk라 표현하기도 한다.

낮은 우선순위, 현재 page fault된 process, 가장 큰 크기 process와 같은 기준으로 process suspension 진행

<Address Binding> = Address translation = instruction이나 data주소를 알아내는 것

instruction의 내부는 모두 logical address이다. (399~402p)

Compile time: 컴파일러 logical address 생성시, physical과 동일하게 주소를 넣어주는 것

Load time: process를 메모리에 넣어줄 때(load 시) physical address로 바꾸는 것

Execution time: compile, load 시에는 그대로 logical이지만, instruction 실행시 physical address를 알아내는 것

<Relocation>

swapping이나 compaction을 이용해 절대적 메모리 공간을 차지하게 하는 것

compile, load binding 시에는 process code 내 physical address가 나오면 안됨

execution binding 시에는 process code 내 physical address가 바뀌어도 괜찮음

<Addresses>

<Paging>: external fragment를 사용할 수 없을까?에서 착안된 방식

page: process의 전체공간을 작은 크기의 메모리 조각으로 나누는 것

(page) frame: memory를 나눈 것으로 frame 안의 process조각을 page라 하는 것

logical address는 page# (page number)과 offset으로 이루어져 있다.

<Paging Table>★★★★★★★

process마다 하나씩 만들어지기에 PCB에 저장된다.

<Virtual Memory>: disk같은 보조기억장치에 가상메모리를 생성, 실행필요부분만 main memory에서 실행

메인+보조로 마치 메모리가 늘어난 것처럼 사용해 실행대상의 ready상태 process가 많아져 better throughput의 장점이 있다.

process가 main memory크기에 구애받지 않고 실행가능한데 이를 portability라 한다.

Real memory = main memory // real address = physical address = absolute address

Virtual memory = secondary storage(disk) // logical address = virtual address

<Address Translation in Demand Paging>

page table의 시작주소는 main memory의 PCB에 저장되는데 이를 가져오기엔 시간이 오래걸린다.

- context switch 발생 시, CPU에 있는 page table base register에 page table 시작주소를 저장한다.

<Page Table Entry>: page table의 한 칸을 Entry라 한다.

cf. modify bit의 page table: 빈공간이 없을 때, 메모리에서 빼서 보조기억장치로 write해야하는데,

만약 변경내용이 달라지지 않아서 disk write를 하고싶지 않다면?

=> 시간의 절약을 위해 변경의 유무를 modify bit에 표시해 disk write를 안해도 되는 page를 구분.

 

 

 

 

<Sharing of Pages>

shared memory와는 다른데,

shared memory는 사람이 필요에 의해 OS에 요청하는 것이지만

Sharing page의 경우 OS의 메모리관리기능이 알아서 해주는 것이다.

<Device Driver>_ 351~357 참고

kernel과의 communication을 위해 switch table을 이용

file_operations에 함수들(read, write, ioctl, open, release)의 시작주소가 들어있음

이런 함수들은 새로운 device driver를 구현할 때 반드시 필요하다!

[구조]

Interface for initialization: 초기화 함수로 device driver초기화 및 kernel에 등록

Interface for file system: file system과 interface하는 함수

Character driver: open, release, read, write, ioctl...

Block driver: open, release, ioctl...

Network driver: open, close, transmit, ioctl...

Interface for hardware: 하드웨어와 interface하는 함수

<RAID>-Redundant Array of Inexpensive(Independent) Disks

즉, 저렴한 디스크 여러개를 사용하는 효과이다. (359~368p 참고)

[RAID 0] - non redundant

연속된 저장단위 strip이 분산된 disk에 저장되며 1/disk개수로 나눠서 저장, 추측을 통한 일부복원이 가능

[RAID 1] - mirrored

RAID 0번 방법이 2번, 중복되게 사용하여 신뢰성을 높임 (but, disk가 2배로 필요하다.)

[RAID 2] - RAID 1번 방법에서 Disk 개수를 좀 줄여보자는 측면

Hamming code(오류탐지 및 수정)으로 계산대상 data bit조합을 다르게 해서 parity bit를 저장

but, 1bit가 아닌 문제발생 시 문제발생만 탐지, 어디서 문제발생인지 모름 (∵bit조합이기 때문)

[RAID 3] - Bit Interleaved Parity

연속된 bit들을 disk 여러개에 배치, 단! 같은 자리에 배치! (parity 1개만 사용)

예를 들어 1011이면 1, 0, 1, 1을 따로따로 나누어 동일한 disk의 상대적 위치에 배치하며

parity를 계산한 값도 같은 위치에 배정, parity를 이용해 복구가능, 문제발생위치도 알 수 있다!

[RAID 4] - block level parity

1011처럼 연속된 bit들을 한 뭉탱이로 disk에 넣으며 분리된 I/O를 병렬적으로 진행

parity에서 block 0~3이 모두 관련없는 정보라도 같은 위치로 읽어 parity를 계산

[RAID 5] - block level distributed parity

RAID 4와 비슷하지만 parity를 각 disk에 여러 disk에 분산시켜 저장한다.

[RAID 6] - dual redundancy (P와 Q에 짝수parity와 홀수parity를 분산한다.)

RAID 5와 비슷하며 신뢰성을 높이기 위해 같은 정보에 대해 parity를 2번 계산

[RAID 01, RAID 10] - RAID 0과 RAID 1을 조합하여 만든 것, (요즘 사용되는 RAID)

<Memory Management>- 메모리 할당과 보호역할을 함.

memory allocation: main memory를 subdivide하여 할당함

memory protection: process가 할당이 허용된 메모리 영역에만 접근하도록 하는 것

<Memory Management가 필요한 상황들>

Relocation: location 즉, 주소값을 다시 잡아주는 것으로 swapping과 compaction에서 필요

swapping: process가 우선순위높은 process실행을 위해 기존 process가 메인 보조간 이동하는 것

compaction: process간 빈 공간을 합치기 위해 process를 이동시 주소를 이동시켜야 하기에 필요

Sharing: 2개 이상의 process들이 같은 memory공간을 접근하도록 하는 것.

<Memory Partitioning: Fixed Partitioning (고정분할식 메모리 할당방법)>

한정된 메모리를 여러 process에 분배하는 것으로 다음 2가지가 있다.

Equal-size partitions: 일정한 크기로 분할해서 메모리에 들어있는 프로그램수 파악이 간단

단점: 메모리 이용효율↓ , process내부 fragment가 생기는 현상인 internal fragmentation현상이 발생한다. (활용되지 못하는 메모리공간)

Unequal-size partitions: 일정하지 않은 크기로 분할

단점: fragment를 줄일 뿐, internal fragmentation 발생을 없애지는 못하였다.

<Memory Partitioning: Dynamic Partitioning (가변동적 메모리 할당방법)>

process에게 필요한 만큼만 할당하는 방법으로 고정분할보다 메모리 활용도가 높다.

external fragmentation: process 외부에 fragment가 생기는 현상

(시작주소와 길이가 있는) 비어있는 메모리 table을 이용해 빈 메모리를 찾는다.

<Dynamic Partitioning Placement Algorithm>

First-fit algorithm: 처음에 맞는 공간 찾기.

Next-fit algorithm: first-fit과 비슷, 직전 알고리즘때 찾은 위치 다음부터 찾는 것 (작은 메모리 공간이 곳곳에 분산되게 하여 앞부분 한 곳에 몰리지 않기 때문에 first-fit보다 좋음)

Best-fit algorithm: index 0~끝까지 모두 조사, 필요한 크기에 제일 맞는 것 찾기

Worst-fit algorithm: best-fit과 정 반대, 크기가 가장 차이나는 것 사용 (남은 공간이 많아 다른 process의 활용 가능성이 커진다.)

<Buddy System> 요즘 사용되는 방식으로 internal fragmentation(고정)과 가변동적할당방법을 합친 방식 (고정+가변)

2^U만큼 빈 공간에 대해 재귀적으로 할당하는 방식 (buddy는 같은 것에서 쪼개진 같은크기 공간)

할당할 process의 크기를 s라 할 때, 2^(U-1) < s <= 2^U를 만족한다면 2^U를 모두 할당

즉, process크기가 할당할 공간의 크기의 절반을 초과하면 할당한다는 뜻

만약 2^U를 넘지 못한다면 조건식을 만족할 때 까지 U값을 줄이면서 재귀적 실행

free list의 길이가 길면 좋지 않기에 되도록 큰 메모리공간으로 남겨두자는 것이 핵심!

(internal fragmetation발생을 무시하고 속도를 높이는게 더 효율적이라는 마인드)

<Memory Address의 종류>

- Physical address: memory unit 하드웨어가 이용하는 주소

- Logical address: 논리적연산에 이용, program instruction(=process가 이용하는 주소)내에 등장하는 주소

- Virtual address: 가상메모리에서 사용하는 logical address

address translation: logical address -> physical address

relative address: 정해진 위치를 기준으로 “주소를 매기는 방식, logical은 process 시작지점기준

Logical = Physical인 경우: [compile-time / load-time] address binding

Logical ≠ Physical인 경우: execution time address binding

<Virtual Address Space (VAS)>

cpu는 main memory만 읽기 때문에 VAS를 main memory에 복사해줘야함.

 

VAS는 보조기억장치에 생성되며 process마다 하나씩 생성된다.

code, data, bss의 시작과 끝 주소는 process의 고유정보이기에 PCB에 저장된다.

0~3G-1(0xbfffffff)는 사용자가 사용하는 주소공간, user context (user mode)이다.

3G~4G-1(0xffffffff)는 kernel이 사용하는 주소공간, System context (kernel mode)이다.

이런 [user+system] context를 process context라 부른다

32bit address computer는 32bit 즉, 4Byte로 메모리 주소값을 표현한다.

실제로 disk공간을 차지하고 있는 것은 stack, data, (code)이다.

code는 실행파일과 공간을 공유(code가 바뀌지 않기 때문에) 실질적으로 disk공간은 stack과 data로

프로그램 실행시 계속 바뀌기 때문에 차지하고 있다.

clock interrupt로 인해 mode change가 발생 (user code ⇋ OS(kernel) code)

VAS는 new상태에서 main memory로 이동(physical address)하면서 실행가능한 ready상태가 되는 것이다.

<Interrupt Handling>

device가 자신에게 어떤일이 발생했음을 OS(kernel)에 처리해달라 요청하는 것.

<Interrupt_ Kernel entry points (kernel 실행코드에 진입방법 – 3가지)>

Interrupt

Trap (software interrupt)

System call (user process의 요청)

<Interrupt, Interrupt Handling: 누가 interrupt를 걸었는지 조사>

주변장치(peripheral device)가 비동기적 event 발생을 OS에게 알리는 것.

cf. asynchronous event: event 발생시점이 명확히 정해져 있지 않은 것.

clock: 1ms마다 interrupt를 거는데 user와 kernel(모두 실행 후 user로 돌아감)을 반복한다.

if. tty가 신호를 주면 cpu에서 받은 신호의 register값을 kernel stack에 저장, mode change로 kernel에 진입한다.

ISR ⊂ IDT(IVT)

IDT: kernel에서 interrupt entry값 번호를 받는 table

ISR: 특정장치의 interrupt를 처리하는 함수, urgent part(interrupt가 급한일 먼저 실행)와 remaining part(안급한일) 존재.

<interrupt 이후 하는 일> => 구 후 user mode로 돌아감

남은 부분 처리 (remaining parts of interrupt routines)

새 signal, process 조사

 

<Trap Handling>

synchronous software event(사실은 cpu 하드웨어가 interrupt를 거는 것, 사실 trap과 interrupt는 같은방식)

cf. synchronous event: event의 발생, 도착의 시간이 정해져 있음.

<Trap Handling의 예>

분모가 0인 경우(div_by_zero) , instruction 안의 machine code가 invalid

메모리 주소가 잘못됨 (segmentation fault) , 정보 보호 오류 (protection fault)

메모리에 안들어와 있음 (page fault)

 

<System calls Handling>_ kernel함수를 불러 user process에게 도움을 요청

sys_call_table을 IDT에 모두 넣을 수 없어 system call로 불러 사용하는 방식.

 

<I/O Control>: OS가 장치의 상채를 check하면서 제어하는 방법 (3가지)

Polling: Programming I/O

Interrupt-driven(기반) I/O

Direct Memory Access (DMA)

 

 

<Polling>: status register bit값을 check하면서 상태를 확인하는 방법 (process switch는 발생하지 않음)

원인: cpu가 device driver instruction을 반복적으로 실행

device driver는 장치의 controller내부 state register에서 장치가 일하는지 알기위해 busy bit를 읽는다.

이때, busy bit=1: busy state, 0: 안바쁜 상태

- OS는 이런 bit가 0일 때, write bit을 1로 만든다.

그 후 data-out register에 bit를 저장

command-ready bit을 1로 설정

busy bit도 1로 설정

I/O가 모두 끝나면 ready-bit와 busy bit을 0으로 설정

 

device 상태를 계속 check함(Polling)의 효율성

효율적: I/O가 빨리 끝나는 장치

비효율적: I/O가 늦게 끝나는 장치

 

<Interrupt-driven I/O>: 장점: 주어진 시간내 더 많은 process 실행 가능 / 장점과 단점이 polling과 반대.

cf. Context Switch 4가지 中 7~12과정으로 인해 block->ready가 된 것이다.

 

<Direct Memory Access (DMA)>

cpu 반복은 cpu 효율이 안좋아지며 DMA controller라는 별도의 processor로 단위시간당 사용가능한 user process 수가 많아진다.

 

 

 

 

 

<Disk 구조 및 용어>

sector: 제조사가 정의한 물리적 저장 최소단위, block(4096B)과 맵핑해줘야 함

surface: disk*2개로 위 아래면이 있다.

track: 디스크의 한줄의 띄로 surface를 나눈 것

cylinder: 같은 track의 집합

disk arm과 head: track을 이동하며 정보를 읽음

sector와 block 크기가 같다면 sector와 block은 일대일 맵핑됨(실린더 단위로 맵핑 후 disk축으로 들어가는 방식)

 

<Timing of a Disk I/O Transfer>

arm이 읽을 sector가 있는 track으로 이동, arm 끝의 head가 해당 track으로 이동

[Seek time]: arm이 track까지 이동하는데 걸린 시간

[Rotational delay]: head가 회전하는 disk에서 sector와 만나는데 걸리는 시간

[Device Busy]: Seek -> Rotational Delay -> Data transfer까지 걸리는 시간

 

<Disk Scheduling> , rotational delay: 도는데 걸리는 시간(평균=0.5바퀴)

결과적으로 Seek time이 성능을 좌우해서 Disk scheduling을 사용해야 한다!

 

<Disk Scheduling Policies> track order: 55, 58, 39, 18, 90, 160, 150, 38, 184

 

 

 

<Disk Cache = buffer cache = page cache>: 저속저장장치로 main memory에 사본을 caching함.

disk에 직접접근할 필요없이 memory 사본접근으로 훨씬 빠름.

 

<Cache Replacement>: memory의 disk사본저장공간이 꽉 차있을 때, 어떤 block을 없애고 빈자리로 해야하는가

LRU(Least Recently Used): 시간기준, 가장오래된 것 삭제

LFU(Least Frequently Used): 횟수기준, 적은 것 삭제

 

 

<Data Blocks>

File 내용을 저장하는 저장단위 (1개 block크기 = 4096bytes)

File Allocation: file 만들 때 file 내용을 담을 file datablock을 어떻게 연결할 것인가

<Contiguous allocation>: 연속된 block의 할당

장점: file을 읽고 쓰는데 시간이 적게 걸림 / good data safety

단점: External fragmentation (특정파일 외부에 fragment가 생기는 현상)

- fragment: 저장공간(메인메모리, 보조기억장치)에 “작은 빈 공간”이 생기는 것

만약, file크기가 늘어나야 한다면, 다른곳에 복사해야 해서 시간이 오래걸림

<Chained allocation>: contiguous allocation의 file size문제를 해결한 파일할당방법

장점: file size가 쉽게 늘어나며 external fragmentation를 우려할 필요가 없다.

단점: 순차접근만 가능(No directed access)하며 중간에 끊기면 그 뒤 block에 접근불가

- linked list 방식으로 다음 block의 주소값을 저장한다.

<Indexed allocation>: chained allocation의 순차접근,단절문제를 해결한 파일할당방법

장점: file의 내용이 아닌 file들의 주소저장을 통한 Direct access가 가능!

단점: file 저장을 위해 index block이 별도로 필요해서 공간이 그만큼 필요해짐

block number를 file table에 저장시켜 direct access 및 병렬적 연결로 문제해결.

Q. file system 전체 (Disk)의 빈공간에 대해서는 어떻게 처리(관리)할 것인가?

<Counting>: contiguous을 빈 data block 관리에 적용한 것

<Linked list (free list)>: chained를 빈 data block 관리에 적용한 것

중간에 끊기면 chained처럼 뒤 빈공간에 접근 불가

단, chained와 달리 direct access문제는 상관X (빈공간이라 그냥 순서대로 배정)

<Grouping>: indexed를 활용한 것으로 비어있는 block번호를 index block에 저장

<Bit vector (bit map)>: Linux system에서 사용하는 방식

장점: 효율적으로 빠르게 free를 찾기 가능 [0: 사용중(occupied) / 1: 비어있음(free)]

단점: 많은 메모리공간 차지 가능

<UNIX File management> cf) link count: file을 가리키는 directory의 개수

일반파일(Regular), 특수파일(Special file), 디렉토리(Directory) 3가지 타입파일 존재

FCB를 inode라 부르며 대표적으로 link count, file addresses가 있다.

<Linux의 Virtual File System>

논리적인 filesystem(filesystem 종류에 상관없이 linux에서 모두 접근해 읽을 수 있음)

OS가 모든 file system의 코드를 가질 필요가 없게 해줌 =>main memory 차지비중↓

user process가 physical filesystem 접근을 위해 System call을 모두 만들필요X

<Linux inode>

128byte의 ext2, ex3와 256byte의 ext4라는 file system으로 구성

Unix와 다르게 12direct Blocks로 되어있음

<File Operations>: 지정한 file타입에 따라 OS가 알아서 File연산을 실행해줘야함

OS는 file타입별로 해당 file의 연산을 함수로 구현, 함수의 주소를 table에 기록함

cf. NULL이라 표기된 것은 함수가 없다 즉, 추가로 실행할 필요가 없다는 뜻 

<File Operations>: 지정한 file타입에 따라 OS가 알아서 File연산을 실행해줘야함

OS는 file타입별로 해당 file의 연산을 함수로 구현, 함수의 주소를 table에 기록함

<I/O Devices>: register를 읽고 쓰는 방식으로 입출력 장치를 제어

OS의 명령으로 control register가 특정 bit값을 1로 setting

<I/O System 구성>

[kernel과 device 간의 연결]

module로 kernel과 연결

그 둘 사이의 communication은

device-driver interface로 합침

<Kernel I/O Management (Kernel I/O Subsystem)>

<File>

- 보조기억장치 내부에 저장되서 전원이 없어도 지워지지 않는 정보 단위

보통 Input, Output과 같은 입출력함수에서 많이 활용됨

<File 2가지 관리대상>

Files

File system

<FCB> - File Control Block

PCB처럼 OS가 File 생성 시 같이 생성됨

단, main memory에 저장되는 PCB와 다르게 FCB는 보조기억장치에 저장됨

File attribute들이 FCB라는 자료구조 안에 저장됨

<File attributes>

<File 타입>

일반파일: Regular file

특수파일: directory, device file, link, socket, pipe

<File Operations>

open: OS 준비하고 찾고싶은 파일의 존재 유무를 check

close: 파일의 변경된 내용을 main memory의 FCB 복사본을 disk에 저장하는 역할

<Device File>

<Directory>

- File에 대한 정보(file attrubutes)를 담고 있는 특수 파일 (파일 안의 파일!!)

File attributes들은 중복저장할 수 없다.

<Hierarchical Directory>

가장 많이 사용되는 디렉토리 방식으로 경로이름을 가진다.

current directory = working directory로 현재 작업을 하고 있는 디렉토리를 의미.

hierarchical directory 예시

<Acyclic-Graph Directories>

sub디렉토리와 file을 공유하는 것으로 dangling pointer라는 문제가 있다.

(dangling pointer: file이 지워져도 이어져있던 링크가 남아있게 되는 문제)

<Acyclic-Graph Directories의 Dangling pointer 문제 Solution>

OS는 아무것도 하지 않음(user가 해결)

Entry-count solution: link 추가시 link count값을 1 증가시킴

만약 file이 지워져 2개의 링크 중 하나가 지워지면 link count값 1 감소시킴

<File Sharing>

- 2개의 문제점

1. 접근권한 (access rights)

2. 동시 접근 시의 관리방법 (simultaneous access)

<Simultaneous Access>

보통 user에게 맡기며 file 접근에 lock을 거는 방식으로 해결

<Access Rights>

접근권한의 종류로는 read, write, execute가 있으며

user class는 owner access, group access, public(others) access 3개가 있다.

<File Systems>

일종의 자료구조로 보조기억장치에 저장되며 다음과 같은 구조를 갖는다.

Boot block

Super block (Partition control block)

Directory structure

(컴퓨터에 따라 있을수도, 없을수도 있음)

File control blocks

Data blocks (실제 파일내용 저장)

<Boot Block>

boot media 내부 특정부분에 boot block이 저장 (270p)

<Partition Control Block (Super Block)>

file system의 제어정보를 가지며 다음과 같은 정보를 갖는다.

<File control blocks (inode list)>

inode의 배열로 inode의 index number (고유한 식별자)를 갖는다.

<Deadlock>

이때, Get B의 경우 process Q에 들어 있어 사용할 수 없다.

B 자원이 사용가능해질 때까지 process P를 block (=sleep, wait)상태로 만든다.

이는 Get A에서도 마찬가지다.

=> 따라서 P,Q의 block상태의 지속으로 resource를 계속 갖는 상태로 실행이 안되어 중단되는, deadlock 상태가 발생한다.

<Deadlock의 발생예시> - 3,4의 경우 deadlock이 발생하게 된다.

<computing 자원의 분류>

재사용 가능 자원: hardware들이 해당된다.(cpu, semaphores, memory...)

소비성 자원: 한 process가 사용하면 사라지는 자원들이다.

<Reusable Resources의 Deadlock 예시>

200Kbyte memory에 할당되어있을 때, 다음 상황을 보면

=> 150Kbyte memory가 다른 process에서 사용될 수 없는, deadlock 상태가 되어버린 것이다

<Consumable Resources 예시>

=> 대기상태의 지속으로 인해 resouce를 서로 사용하지 못하는

deadlock 상태가 되어버린 것이다

<Resource Allocation Graph>

<Deadlock발생 4조건> - 동시에 모두 만족해야함

Mutual exclusion: 한 자원에 대한 독점적 사용

Hold and wait: 어떤 자원을 가진 상태에서 다른 자원을 요청하는 것

No preemption: 이미 차지하고 있는 자원을 타 process가 강제로 빼앗아 오는 것

Circular wait: Hold-and-wait이 모든 process에 적용되는 것.

<Deadlock Handling>

Deadlock이 발생하기 전 OS가 사전에 예방

Deadlock이 발생해도 OS가 recover 시켜주는 방법

OS가 아무것도 하지 않음(관리자가 해결)

<Deadlock Prevention_4조건 break>

Mutual exclusion을 break: 자원을 다른 process가 동시에 써야함 (불가능)

Hold and wait을 break: 자원을 기다리지 않고 처음부터 모든 자원을 받아 처리 (가능, but 현실적으로는 안좋음)

Preemption 수행: 상대 process의 자원을 강탈하면 혼란스러움. (가능, but 효율성↓)

Circular wait break: 가능! 위 3경우보다 좋음. 하지만 불편하다는 단점

<Deadlock이 발생한 후의 전략>

모든 deadlock process들을 종료(abort)

deadlock process들 중 하나만 골라서 종료(abort)

<Dining Philosophers Problem>

<Hardware를 이용한 critical section 보호방법>

[Interrupt Disabling]

- atomic operation을 이용한 interrupt 비활성화로 critical section이 아닌,

entry section에서 일어난다.

Test and Set 함수(atomic하게 실행, interrupt 비활성화)

hardware 해법에서는 critical section을 atomic하게 하는 것이 아닌특별한 함수인 testset함수를 사용해 entry section을 구현해 atomic하게 만드는 것이다.

 

장점: software에 비해 while 한문장으로 효율적인 코드로 짤 수 있다.

단점1. Busy-waiting: cpu를 반복적으로 사용해 cpu점유 문제 발생

단점2. Bounded waiting의 보장이 안될 수 있다.

단점3. Deadlock이 발생가능하다.

[Deadlock]

- PL이 critical section에 존재 --> PH가 PL의 cpu를 빼앗고 running상태가 됨

- PL은 ready 상태가 되어버리고 critical section 안에 들어있고 나가지 못함

- PH는 critical section에 들어가지 못하고 둘의 상태가 고착되어 버림

<Semaphore>: 정수형 변수와 자신만의 큐가 만들어진 특수한 변수

testset함수를 사용하는 hardware의 단점을 극복하는 또다른 hardware 지원방법

mutual exclusion, progress, bounded waiting 3가지 조건을 모두 만족

<하드웨어의 지원을 받는 semaphore 함수>- atomic하게 실행됨

(interrupt가 걸려도 나중에 처리)

※semWait(s) - semaphore의 값을 1 감소시키는 함수

※semSignal(s) - semaphore의 값을 1 증가시키는 함수

충돌을 어떻게 막을까?

 

 

★★★<mutual exclusion using semWait, semaSignal Code>★★★

 

semWait과 semSignal은 atomic하게 실행, instruction이 하나인 것처럼 interrupt가 걸려도 함수 종료 후 처리.

 

 

<semaphore의 활용_critical section problem>

 

<Pairing Semaphores> - semWait과 semSignal의 개수가 같아야 한다!

 

<reader/writer 문제에 semaphore 사용>

 

 

 

<Binary Semaphore, Lock>

0: 바구니에 돌이 없다는 뜻으로 자원 사용을 하지 못함

1: 바구니에 돌이 있다는 뜻으로 자원 사용이 가능함

mutual-exclusion semaphore (mutex)라고도 불림

예시: pthread_mutex, pthread_mutex_lock(=binary semaphore)

pthread_mutex_unlock(자는 process를 하나 깨워 돌을 집어 넣음)

 

<Monitors>

고수준의 동기화 방법으로 concurrent process과 ADT사이 safe sharing을 하게 함

하나의 process만이 monitor를 실행할 수 있다.

 

다수의 thread가 concurrent하게 실행 => thread 충돌문제 발생이 가능하다.

cf. single thread의 경우, process 충돌이라고도 부른다.

<핵심용어>

- race condition: 2개 이상의 process가 같은 메모리를 거의 동시에 접근(access)할 때 값을 바꾸는 것을 예측할 수 없는 경우

- mutual exclusion: 2개 이상의 process가 같은 메모리를 거의 동시에 접근할 때 한번에 한 process씩 접근하게 함(상호배척)

- critical section: 다른 process와 공유하는 메모리(resource)를 접근하게 하는 코드

- starvation: 자원이 배정되지 않고 오래 기다리는 상태

- deadlock: 영원이 자원이 배정되지 않는 상태(starvation이 지속)

mutual exclusion이 보장되게 critical section을 잘 짜서 race condition이 발생 안하게 해야함

<Race condition>: cpu가 여러개가 아닌 1개일 때도 발생가능

producer process와 consumer process끼리 정보전달을 위해서 IPC를 이용해야 함

=> IPC(shared memory)를 사용할 때 충돌(race condition)이 발생가능하다.

<processor가 1개일 때의 Race condition>

load: register를 불러옴

store: 증가시킨 register값을 critical section(counter)에 저장

<Interrupt>: 컴퓨터 하드웨어 장치가 cpu에게 event 발생을 알리는 방법

- interrupt가 걸릴 수 있는 곳을 왼쪽에 표시한 것. (2번째에서 interrupt가 걸린것)

interrupt 종류에 따라 바뀔 수 있고 위의 그림은 producer->consumer로 바뀐 것.

- Multi threading의 경우에도 global variable에 race condition이 발생가능

(따라서 하나의 process에서 여러 thread를 사용해도 race condition이 발생가능)

<race condition을 어떻게 막을 수 있을까?>

atomic operation: critical section을 assembly 전체를 실행

--> assembly instruction이 여러줄이면 interrupt 지연으로 문제발생이 가능

2. fence: critical section 주변에 fence를 만들기

--> mutual exclusion보장 가능하며 실행동안 interrupt가 걸리기에 context switch가

가능하다 (atomic operation이 아님).

<Three Requires: critical-section>- 아래 3가지 모두를 만족해야 한다.

Mutual Exclusion: 하나를 실행중일 때 다른 process 실행X

Progress: 아무도 공유data를 접근하지 않을 때, 나의 critical section data를 진행해서 공유 data를 쓸 수 있어야 한다.

Bounded Waiting: 누가 공유data에 접근해있고, 기다릴 때 그 시간이 정해져 있다.

<Software Solution>- code 설계하는 법 

[software solution-1]

if가 아닌 P0가 아닌 P1이 먼저 실행되면

P1은 while문에 걸려 fence 안으로 들어갈 수 없다.

[software solution-2]

- 3가지 require들을 만족한다.

- but, 3개 이상의 process에서는 만족X

[software solution-3]

- 3개 이상의 process에서도 만족

- 하지만 실용적이지 않아 사용X