OS Summary
OS
•
하드웨어를 관리 – I/O 디바이스와 file에 접근, 하드웨어 접근 시 에러 탐색.
•
프로그램 수행 – 스케줄링, 프로그램 수행 간 에러 발생 시 에러 리포팅.
•
Kernel
OS의 역할
•
User program을 쉽게 사용할 수 있도록 해준다.
•
System을 편리하게 사용할 수 있도록 해준다.
•
하드웨어를 효율적으로 관리해준다.
DMA (Direct memory access)
•
I/O 디바이스가 실행될 때마다 cpu가 관여를 하면 시간적으로 비효율적. 그래서 DMA가 존재
•
I/O structure : I/O transaction은 Bus를 통해 수행된다
-> Bus : 주소, 데이터, 제어신호를 옮기는 선, cpu에서 다른 device에 접근할 수 있는 통로
•
System bus : cpu와 I/O bridge를 연결
•
Memory bus : I/O bridge와 Memory 연결
•
CPU와 I/O device는 동시에 수행이 가능
•
하나 이상의 cpu와 device controller는 공통된 버스를 통해 공유 메모리와 연결된다.
•
Device controller는 I/O operation이 끝나면 interrupt를 통해 작업종료를 알린다.
- device controller가 device operation이 끝나면 cpu에 interrupt를 보낸다.
- interrupt신호를 받은 cpu는 하던 작업을 멈추고 현재 수행중인 process를 메모리(kernel 영역)
PCB영역에 정보를 저장한다.
- cpu는 kerner level로 들어가서 interrupt vector를 통해 ISR을 찾아 수행한다.
- ISR이 끝나면 기존의 process를 수행한다.
•
하드웨어 : interrupt(ctrl+c), 소프트웨어 : trap(system call, segmentation fault
Multiprocessor : cpu를 여러 개 둔 구조
•
장점 : 성능향상, 경제성(여러 cpu가 하나의 메모리 공유), 신뢰성(하나의 cpu가 고장나도 다른 cpu가 처리가능)
•
비대칭 멀티프로세싱 : 하나의 Master cpu와 여러 개의 Slave cpu가 존재. Master cpu는 메모리 전체에 접근이 가능하고 Slave cpu는 각자에 주어진 메모리 공간에만 접근.
•
대칭 멀티프로세싱 : 모든 cpu가 수평적인 구조이고 전체 메모리 영역을 공유한다.
Multiprogramming : cpu와 I/O device가 항상 일을 하도록 하는 구조
☞ CPU 스케쥴링 : cpu에게 할당해주기 위한 작업
☞ Job 스케쥴링 : 메인 메모리에 할당할 job 선택
☞ Virtual memory : 가상 메모리는 실제 메모리와 달리 디스크에 존재한다.
Dual-mode operation : User level(bit 1), Kernel level(bit 0)
☞ cpu에서 제공해주는 명령어(privileged instruction)을 User로부터 보호하기 위해 두개의 모드가 존재한다.
OS의 서비스
☞ User interface 제공, 프로그램 실행, 외부 디바이스 지원, file system관리, 프로세스들간 통신, 에러 탐색, 듀얼 모드로 보호, 잘못된 I/O의 접근 방지
System call
•
운영체제로부터 서비스를 받고 싶을 때 호출하는 유일한 메커니즘
•
라이브러리로부터 간접적으로 System call 호출(호환성과 효율성)
•
System call 호출과정 : System call 호출 시 라이브러리를 통해 System call number를 가지고 kernel level의 interrupt vector table에서 가지고온 number를 토대로 system call handler를 수행
IPC
•
Message passing : 프로세스 간 메시지를 주고받는 방식. 메시지를 주고받을 때마다 System call을 호출하여 overhead가 발생하지만 구현이 간단하다.
•
send와 recive 두개의 system call 사용
•
mailbox 방식과 직접 전송 방식이 존재
•
직접 전송 방식은 두개의 프로세스가 고유의 link를 가지고 그 통로를 통해 데이터 전송. 데이터에 서로의 이름을 명시한다.(파이프라인)
•
mailbox는 데이터 전송 시 수신자가 아닌 mailbox를 향해 전송. 메일 박스는 고유의 ID를 가지고 여러 프로세스가 사용할 수 있다.
•
Shared memory : 메모리의 일정 영역을 공유하는 방식. 메모리를 공유하므로 system call호출이 적지만 동기화문제를 해결해야한다.
•
producer-consumer problem : 생산만 하는 프로세스와 소비만 하는 프로세스
•
buffer가 비어있다면 consumer가 대기, buffer가 꽉 채워져있으면 producer가 대기
Multi-thread
•
stack 영역을 제외한 data, heap, code 영역을 공유하여 병렬적으로 작업을 수행한다.
CPU 스케쥴러
•
I/O bound가 CPU bound보다 우선순위가 높다.(waiting time이 적기 때문)
•
스케쥴러는 결정을 내리고 CPU에 할당은 Dispatcher가 해준다.
•
스케쥴링이 발생하는 경우 : running -> waiting, running -> terminate(Non-preemtive)
Running -> ready, wating -> ready(preemptive)
Dispatcher :
•
context switching, switching to user mode, context switching 종료 후
Scheduling Algorithm
•
FCFS : 먼저 들어온 순서대로 작업 수행 (convoy effect : 수행시간이 긴 작업우선 시 발생하는 부정적인 영향)
•
Short job First : 수행시간이 짧은 작업 우선. 최적의 스케쥴링 방식. 현재 남은 CPU burst time으로 우선순위 판단하는 선점형과 비선점형이 존재.
•
하지만 미래의 CPU burst time을 알 수 없기 때문에 Exponential Averaging 기법 사용
•
Priority : task에게 우선순위를 부여해 CPU burst한다.
우선순위가 낮은 task가 CPU를 할당받지 못하는 starvation현상이 발생한다.
Aging 기법을 사용해 지속적으로 수행되지 않는 task의 우선순위를 높여준다.
•
Round-Robin : FIFO구조로 각 task는 일정시간 CPU burst를 받고 맨 뒤로 보내진다. 할당 시간에 따라 단순 FCFS가 될수도 context switching이 너무 자주 발생할 수도 있다.
Multilevel queue
•
Ready queue가 분리되어 각 queue마다 다른 스케쥴링 방식을 가진다.
•
Task마다 들어갈 queue가 정해져있다.
Multilevel Feedback queue
•
프로세스들이 다양한 큐로 이동할 수 있다.
•
스케쥴러는 큐의 개수, 각 큐의 스케쥴링 알고리즘, 프로세스 이동, 프로세스가 서비스를 받고 싶을 때 어디 큐로 갈 것인지를 정의
Race condition
•
프로그램의 결과가 수행에 따라 달라질 수 있다. 선점형에서 발생가능
•
Critical-section영역은 Atomic해야 한다.
Deadlock Problem
•
Deadlock detection : 데드락 발생을 발견
•
Deadlock avoidance : 데드락이 발생할 것 같으면 회피하는 것
•
Deadlock recovery : 데드락이 발생 후 해결하는 것
•
Deadlock prevection : 데드락이 발생하는 원인 제거하는 것
Deadlock 발생 조건
•
Mutual exclusion : 하나의 자원에 여러 프로세스의 동시접근 불가
•
Hold and wait : 하나의 자원을 가지고 있을 때 다른 프로세스가 가진 자원을 기다림.
•
No preemption : 자원을 임의로 뺏을 수 없다.
•
Circular wait : 프로세스와 자원사이에 싸이클이 생기는 경우
•
4가지 모두 발생하여야 Deadlock
Deadlock prevention
•
데드락 발생조건 4가지중 한가지를 제거하자는 아이디어
•
Mutual exclusion을 제거하면 공유자원을 부정하는 것이기 때문에 불가능
•
Hold and wait를 제거하면 요청하는 모든 자원이 동시에 이용가능할 때만 자원을 이용가능 하기에 starvation의 위험이 있다.
•
Preemption이 가능하면 우선순위에 따라 필요자원을 가져오므로 해결가능
•
Circular wait를 제거하면 R1과 R2의 우선순위를 부여해 R1을 가진 프로세스만 R2를 가질 수 있도록 구현하여 해결가능
Deadlock avoidance
•
Banker`s Algorithm
- Available : Resource Type마다 k개의 instance가 사용가능하다.
- Max : Max[i,j] = k 일 때, Pi는 Rj에 대해서 최대 k개의 자원을 요청할 수 있다.
- Allocation : Allocation[i,j] = k 일 때, Pi는 현재 k개의 instance를 Rj로 부터 할당받고 있다.
- Need : Need[i,j] = k 일 때, 작업이 끝난 후 Pi는 k개 이상의 instance를 필요로 한다.
- Need[i,j] = Max[i,j] - Allocation[i,j]
- 은행원은 최소 하나의 고객이 돈을 갚을 수 있는 여유 돈을 남겨두어야한다. 그래야 돌려받고 다른 고객에게 빌려줄 수 있다.
Memory Management Strategies
•
Virtual address를 Physical address로 변환하는 Address Translation이 핵심
•
메인 메모리를 디스크의 캐쉬로 사용.
•
Address Translation은 매우 빠르게 이루어져야 하므로 MMU의 도움을 받는다.
•
MMU는 TLB(VA를 가지고 Entry 확인 후 hit면 바로 메모리 접근)와 Register(page table존재)로 구성
•
base 레지스터는 프로세스의 시작 주소를 담고 limit 레지스터는 프로세스의 크기를 담고 있다. Base, limit 레지스터는 MMU의 도움으로 메모리 접근 없이 메모리 주소에 대해 파악할 수 있다.
Fragmentation
•
External Fragmentation : 새로운 프로세스가 할당될 때 여유 공간은 충분하지만 연속적이지 않아 적재를 못하는 현상.
•
Internal Fragmentation : page와 같은 최소 단위의 공간을 전부 채우지 못하는 현상.
Paging
•
n개의 page를 메인 메모리에 올리려면 n개의 frame만큼 공간이 있어야 한다.
•
메모리에 Page table을 두어 VA를 PA로 변환한다.
•
VA를 page 사이즈로 나누어 page number를 구하고 PCB내부의 page table을 토대로 frame number를 구한다. 이 frame number에 frame number 사이즈를 곱하면 실제 메모리의 시작주소가 나온다. 그리고 VA를 page 사이즈로 나눈 나머지가 offset이다.
•
page table의 valid bit가 0인(메모리에 존재하지 않는)페이지에 접근 시 trap이 발생하여 OS가 디스크에 pager를 요청한다. 해당 page는 메모리에 적재되고 이는 page table에 올라가 valid bit를 1로 설정하고 cpu에 할당된다. #참조의 지역성
•
page replacement : 메모리가 꽉 찬 경우 victim frame을 선택하여 디스크에서 필요한 page와 swap한다.
•
victim frame 결정 알고리즘
•
FIFO(먼저 들어온 frame 보냄), optimal(가장 오래 cpu 할당을 받지 못한 frame 보냄), LRU(page가 참조될 때 시간기록, 혹은 stack 구조의 가장 위에 위치)
•
second chance algorithm : FIFO기반이지만 Reference bit가 1이면 0으로 바꾸고 다음 frame 조사
Segmentation
•
프로그램을 세그멘트 단위로 분할. 페이지나 프레임과 달리 고정 사이즈가 아닌 논리적 분할 사이즈.
Demand Paging
•
실행중인 프로세스가 필요한 페이지만 올리는 것.
•
Lazy Swapper = pager, Swapper는 프로세스를 적재하고 page는 페이지를 적재
