운영체제

6 : Process Synchronization

Critical Section 동시 접근 문제

• kernal 수행 중 인터럽트 발생 :
  커널 내 c.s 수행 중 인터럽트 봉쇄
  turn -> process x

while(turn != 0)
c.s
turn = 1

• process의 system call로 kernel mode 중 context switch 발생
  : 커널 내 c.s 수행 중 CPU 뺏기지 않도록 함
  : 커널 모드 수행 중 프로세스 할당 시간이 끝난 경우 kernal mode 작업이 끝날 때까지 context switch 연기
  flag -> process x

flag[i]=true
while(flage[j]);
c.s
flag[i]=false

• Multiprocessor가 shared memory 내의 kernel data 접근
  : kernal 내 c.s 진입시 lock 걸기
  turn + flag -> progress 0

flag[i]=true
turn=j
while(flag[j]& turn = j);
c.s
flag[i]=false

Reader - Writers Problem

• writer : starvation 발생 가능
• 동시에 여러명 read 가능

공유 Data

• readcount : 공유 변수로 여러 reader 동시에 DB 접근 가능
  Semaphore 아님. 공유 변수임.
• DB : 공유하는 data

Semaphore

• mutex : readcount 접근 : binary
• db : DB 접근 : binary

프로그램적 해결법

	starvation	deadlock	busy wait
알고리즘1 (turn)	.	.	O
알고리즘2 (flag)	.	.	O
알고리즘3 (turn & flag)	.	.	O
test and set (Hw 지원)	.	.	O
Bounded buffer	X	X	O
Readers-writer	O(writer)	X	O
Dining philosopher	O	O	O
Bounded buffer (Monitor)	O	O	X
Dining Philosopher (Monitor)	O	X	X

Monitor

• 모니터에서 활성화되는 process는 최대 1개
  -> lock 필요 X, c.s 진입
• condition variable에 wait()연산
  -> 잠듬 / suspended / variable que에 대기

Block & Wait 방식

• s.list : 자원 여분 없어 잠든 process 줄세우기 (process wait-que)
• s.value : wait-que에서 대기 중인 process 갯수
• s<0에 대한 P 연산 -> wait que에 추가하고 block
• s<=0에 대한 V 연산 -> wait-que에서 process 한 개wakeup

8 : Memory Management

Swapping

• 프로세스를 memory -> backing store (디스크)로 통째로 쫓아냄
• 중기 스케줄러가 쫒아낼 프로세스 선정
• Execution time binding과 함께 쓸 때 효율적

Fragment

• external fragement : 분할 size < 프로그램 size
  segment, 연속할당(고정, 가변)
• internal fragement : 분할 size > 프로그램 size
  paging, 연속할당(고정), segment with paging

TLB

• T : TLB 접근 시간
• M : 메모리 접근 시간
• R : hit ratio : associative register에서 찾아지는 비율
• P : paging level
• EAT : Effective Access Time
  R*(M+T)+(1-R)*(M+P*T)

• TLB : Logical / Physical address 모두 가짐
• Page Table : Index 자체가 logical page number이고 해당 index에 할당된 값으로 physical address 존재

bit

• protection bit :
  다른 프로세서로부터의 접근 제어 보안 용도 X
  해당 page에 대한 read/write/read only의 접근 권한 제어
• valid / invalid bit :
  해당 주소 frame에 맞는 유효한 process 내용 있음 -> 1
  해당 page가 물리적 메모리의 frame에 올라와 있음 -> 1
  해당 page 가 page table에 올라와 있음 -> 0

Re-entrant Code : shared page의 shared Code

• read-only : 하나의 code만 메모리에 올림
• 동일한 logical address space에 위치

• segement는 의미 단위로 분할, paging은 동일한 크기로 분할
  -> segement가 더 sharing, protect에 강함

9 : Virtual Memory

페이지 참조 스트링에 대한 알고리즘

• FIFO : 먼저 들어 온 것이 먼저 나감
  (frame 증가 -> page fault 증가)
• OPT (MIN) : 가장 먼 미래에 참조되는 page를 replace
• LRU : 가장 오래 전에 참조(재사용)된 page 지움
• LFU : 참조 횟수 가장 적은 page 지움
  (장기적인 시간 규모 고려 O, 최근성 반영 X)
• Clock :
  참조 : 1 , 참조 x : 0 , 이동 중 : 1 -> 0
  dirty bit = 0 => disk write 없음

Page Fault

1. invalid page 접근 (invalid bit 상태) -> MMU의 trap
2. kernel mode에서 page fault handler 작동
3. invalid reference ? abort process
4. get/replace empty page frame
5. process : block (CPU 빼앗김)
   page : disk->memory
6. page table entry 기록 : valid=1
7. insert readyque
   process : ready
8. process가 CPU 잡고 running

Reference bit / dirty bit

• 참조 = read or write
• dirty bit = 1
  : 메모리에 올라온 이후 적어도 한 번 쓰기 참조 발생
  : 추후 메모리에서 쫓겨날 때 그 전에 disk에 변경사항 write 해줘야함
• reference bit =1
  : 최근에 참조 발생 (0)
  : 가장 최근에 참조 발생 (X) ->모름

Page Frame Allocation

• PFF scheme : Page Fault rate Frequency 보고 frame 할당 정도 조절
• Working set Algorithm : window set size로 할당하는 page 수 조절
• 공통점
  : multi programming degree 조정 가능
  : 메모리 공간 부족 시 통째로 swap out 가능

Thrashing

• 최소한의 page frame 할당 받지 못해 원활한 process 수행 어려움
• high : Page fault rate, CPU Utilization, Multi programming, swap in/out 빈도
• low : process 당 할당된 page frame 수, throughput

page size 낮음

• 높음 : page 수, page table 크기, 메모리 효율성
• 낮음 : 내부/외부 조각, disk transfer 효율성, locality

10 & 11 : File System & Implementation

• Direact / Random Access
  continous allocation, indexed allocation, Unix, FAT (MS-DOS)
• Sequential Access
  Linked allocation

• VFS : 다른 File System을 동일 시스템 콜 인터페이스로 접근
• NFS : 분산 시스템, 네트워크로 파일 공유

• Buffer Cache : File system I/O 연산은 memory 특정 영역인 buffer cache 사용

• Memory mapped I/O : File 일부를 virtual memory에 mapping하고 이에 대한 메모리 접근 연산은 File system I/O 수행 (System call 아니라 memory 읽고 씀.. 그러나 file에 쓴 것처럼 보임)

• read()로 읽으려는 block이 memory에 존재 X : 1번의 disk 접근
memory에서 file 위치 찾기 -> disk에서 실제 data 읽기

• read()로 읽으려는 block이 buffer cache에 존재 0 : 0번의 disk 접근

• memory mapped I/O 사용시 disk 접근 없이 memory 접근만으로 disk data 읽고 쓸 수 있지만 Page Fault의 경우 disk 접근 필요함

12 : Disk Management / Scheduling

디스크 관리 절차

1. physical formatting (low level formating)
2. partitioning
3. logical formatting
4. booting

Scheduling Algorithm

• C : 반대방향으로 돌아갈 때 요청 처리 X
• Look : 요청 없으면 방향 전환 vs Scan : 요청 없어도 꼭 끝까지

• FCFS : 순서대로
• SSTF : Starvation : 지금 당장과 가장 가까운 곳
• SCAN : 출발점 -> 요청 없어도 꼭 끝점 : 요청 처리 O
• C-SCAN : 출발점 -> 요청 없어도 꼭 끝점 -> 출발점 이동 : 요청처리 X
• N-SCAN
• LOOK, C-Look : 출발점 -> 끝점 방향 이동 : 그 방향에 요청 없으면 방향전환

충분히 많은 요청에 대해

• Look : 헤드 이동 거리 가장 짧음
• C-Scan : 헤드 이동 거리 가장 길음
• SSTF, Scan : 요청들이 기다린 시간의 편차가 큼

SWAP AREA

• physical disk 내 일부를 차지하는 logical disk로서 file system과 swap area 존재
• disk를 memory의 연장 공간으로 사용

RAID

• 여러 개 독립적인 disk 묶어서 사용
• 디스크 처리 속도 향상 : interleaving, striping
• 신뢰성 향상 : Mirroring, Shadowing