이 글은 필자가 학교 수업(반효경 교수님의 '운영체제')을 듣고 수업 복습차 전체 정리한 글입니다. 추가하여, 박상수 교수님의 '임베디드 시스템' 과 연계되어 코드를 추가를 몇개 추가합니다.
Chapter 1. Introduction to Operating Systems
1. 운영체제(Operating System, OS)란?
- 커널: 운영체제의 핵심 부분으로 메모리에 상주하는 부분
- 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층
2. 분류
- 동시작업가능여부: single tasking / Multi-tasking
- 사용자의 수: single user / multi user
- 처리 방식: batch processing(일괄 처리, 일정량 모아서) / Time sharing(일정한 시간 단위로 분할) / Realtime OS(실시간으로 deadline 존재) – Hard Realtime System(엄청 시간 지키는) / Soft Realtime System(대강 지키는)
3. 프로세스의 특성 분류
- I/O Bound Process: I/O 중심 job
- CPU-Bound process: CPU 중심 job
Chapter 2. System Structure & Program Execution
1. 컴퓨터 시스템 구조
- CPU
> Interrput line: Interrupt가 들어왔는지 여부 check
> Mode bit: kernel mode(0: OS 코드 수행) VS user mode
> Registers
- Memory
- 분류: code + data + stack의 형식으로 저장
> User Physical Memory: Process Address Space 저장(code부분: 사용자 정의 함수 + 라이브러리 함수)
> Kernel Address Space (code부분: system call부분)
> Memory Controller
- Additional: Computer – I/O Device
> DMA Controller: 빠른 입출력 장치를 메모리에 가까운 속도로 처리하기 위해 사용(block 단위로 interrupt 발생해 처리)
> Timer: Time Sharing을 구현하기 위해(Mode bit과 연결)
- I/O Device
> Disk
> Device Controller: 해당 I/O 장치유형을 관리하는 작은 CPU(하드웨어임) (I/O가 끝나면 interrput로 CPU에 사실 전달)
- I/O 분류
> Synchronous I/O(일반적): I/0 기다릴 동안 다른 일 하다가 돌아옴
> Asynchronous I/O: I/O 요청하면서 결과 무관하게 일함
2. Interrput
-분류
> Interrput(하드웨어 인터럽트): 하드웨어가 발생시킴
> Trap(소프트웨어 인터럽트)
>Exception: 프로그램 오류
>System call: 프로그램이 운영체제의 서비스를 받기 위해 커널 함수 호출
- 인터럽트 처리 루틴
: 해당 인터럽트 벡트(처리 루틴 주소)에 접속
3. 프로그램의 실행 | 메모리의 load
① File System에서 불러서 프로세스 자체를 위한 Virtual Memory 형성
② Address Translation(주소 변환) / Swap Area에 필요없는 부분 저장
③ Physical Memory에 저장 – User Address Space(1번 프로세스 Virtual Memory), Kernel Address Space (Data에 PCB, Stack에 Kernel Stack)
» Procss Control Block(PCB): 운영체제가 프로세스를 관리하기 위해 프로세스당 유지하는 정보
ex. Process Sataus, Program Counter, Registers, Code/data/stack의 위치 정보, 파일 관련 정보 등등
4. 추가 정리
- Program(User mode) > CPU(kernel mode)
① Interrupt (Timer interrput 등)나 Exception이 발생
② 오래 걸리는 I/O 작업시 (자진)
- CPU(kernel mode) > Program(User mode)
: 그냥 OS가 넘겨줌
-Program(User mode) > Program(User mode): Context Switch
1) 원래 수행중인 건 PCB에 저장
2) 이제 시작할 건 PCB 읽기
Chapter 4. Process Management
1. Queue
: 프로세스들은 각 큐를 오가며 수행되는데, PCB의 Pointer를 통해 이동한다.
- Job Queue: 현재 시스템 내에 있는 모든 프로세스 집합 (Job Queue = Ready Queue + Deviece Queue)
- Ready Queue: 실행되기를 기다리는 프로세스 집합
- Device Queue: I/O 처리를 기다리는 프로세스 집합
2. Process State > Process Scheduling Queue
- 생성 시스템콜: fork()
운영체제로부터 자식과 부모는 같은 Address Space, 자식은 그 공간에 새로운 프로그램을 올림 / PID로 자식과 부모를 구분
- Ready: CPU 기다리는 중(메모리 다 만족하고!)
- Running(User mode + Monitor/kernel mode): CPU 잡고 수행중
- Blocked(wait, sleep): I/O 등의 (자신이 요청한) 이벤트를 기다리는 상태며, 이벤트 만족시 Ready
- Suspended(stopped): 외부의 이유로(ex. 사용자가 프로그램을 일시정지) 기다리는 상태며, 이벤트 만족시 Active
- 종료 시스템콜: exit()
자발적인 종료: 명령을 수행 / 비자발적인 종료: 부모 프로세스가 종료될 때 자식의 수행을 종료시킴(abort)
3. 스케줄러(Scheduler)
- ☆Long-term/Job Scheduler: (선) Ready 프로세스 중 어느 걸 Ready Queue로 보낼지 결정 + 프로세스에 Memory(및 각종 자원)을 주기
- ☆Medium-Term Scheduler/Swapper: (악) 여유공간을 마련하기 위해(degree of Multiprogramming을 제어하기 위해) 프로세스를 메모리>디스크로 보내기 + 프로세스에 Memory를 뺏기
- Short-term/CPU Scheduler: 어느 프로세스를 running에 올릴지 결정+ (Dispatcher를 통해)프로세스에 CPU를 주기
» CPU 스케줄링이 필요한 경우
① Running > Blocked (ex. I/O system call)
② Running > Ready (ex. timer interrupt)
③ Blocked > Ready (ex. I/O 완료 후 interrupt) preemptive
④ Terminate
(①④는 nonpreemptive / ②③는 preemptive)
4. Thread: a lightweight process
: code와 data를 공유, stack과 PC, Register set을 별도
- 스레드를 사용하면 병렬성을 높일 수 있으며, 메모리 절약과 성능 향상을 기대할 수 있다.
Chapter 5. CPU Scheduling
: 여러 종류의 job(=process)가 섞여 있기 때문에 CPU 스케줄링이 필요하다.
1. Scheduling Algorithm
- FCFS(First-Come First-Service)
먼저 온 순서대로 nonpreemptive / Bad: Convoy effect
- SJF(Shortest-Job-First)
CPU 시간이 짧은 프로세스 제일 먼저 스케줄 (Nonpreemptive SJF / Preemptive SJF:minimal waiting time을 보장)
- SRTF(Shortest-Remaining-Time-First)
- Priority Scheduling
- RR(Round Robin)
각 프로세스는 동일한 크기의 할당시간(q)을 가져, 할당시간이 지나면 프로세스는 선점당하고, ready queue의 제일 뒤에 가서 다시 줄을 선다. (q가 커지면 FCFS, 작으면 context switch 오버헤드가 커진다.)
- Multilevel Queue
Ready queue를 여러 개로 분할하여, 각 큐는 독립적인 스케줄링 알고리즘을 가진다. Foreground queue – RR, Background queue – FCFS 스케줄링 방법을 가진다.
- Multilievel Feedback Queue: 프로세스가 다른 큐로 이동이 가능한 방식
Chapter 6. Process Synchronization
0. 기본 단어
Execution-Box: 연산
Storage – Box: 데이터 저장하는 곳
Problem) Race Condition / Process Synchronization = The Critical-Section Problem
>> critical section(동시에 공유 데이터에 접근하는 상황)을막기 위해서 concurrent process는 synchronize해야
1. kernel 수행 중 인터럽트 발생시
: 인터럽트가 kernel 수행 중인 데이터에 접근할 때
2. Process가 System call을 하여 Kernel mode로 수행 중인데 Context Switch가 일어나는 경우
: System call에 Process에 수행 중인 데이터에 접근할 때
3. Multiprocessor에서 Shared Memory 내의 Kernel Data
: multiprocess 도중에 여러 CPU가 데이터에 접근할 때
Solution: Peterson’s Algorithm/Synchronization Hardware – Busy Waiting 방식 VS Semaphore – Block/WakeUp 방식
일반적으로 Block/Wakeup 방식이 더 좋음
Chapter 7. Deadlocks
1. Deadlock이란?
둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상 (교착상태)
* 발생 조건 4가지
- Mutual Exclusion: 매 순간 하나의 프로세스만이 자원을 사용할 수 있음.
- No preemption: 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
- Hold and wait: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
- Circular wait: 자원을 기다리는 프로세스간에 사이클이 형성 되어야 함
2. Monitor란?
동시 수행중인 프로세스 사이에 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
- 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능 (lock 코드가 필요 없다.)
- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
- Condition variable은 wait와 signal 연산에 의해서만 접근 가능 (잠든 프로세스를 깨우거나 잠들기의 함수로도 표현 가능)
3. DeadLock 감지하기: Resource-Allocation Graph
그래프에 cycle이 없으면 deadlock이 아니다.
그래프에 cycle이 있으면
if only one instance per resource type, then deadlock
if several instances per resource type, possibly or deadlock
4. Deadlock의 처리방법
- (예방) Deadlock Prevention: 자원 할당시 Deadlock의 4가지 필요 조건 중에 어느 하나가 만족되지 않도록 하기
- (예방) Deadlock Avoidance: 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
* 2가지 경우의 avoidance 알고리즘
- Single instance per resource type: Resource Allocation Graph algorithm 사용
- Multiple instance per resource types: Banker’s Algorithm 사용
Banker’s Algorithm: Need<=Avaliable인지 확인!
- Deadlock detection and recovery: Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
*Recovery시
- Process termination: abort all deadlocked processes (one process at a time)
- Resource Preemption: 비용을 최소화할 victim의 선정, safe state로 rollback 하여 process를 restart
- Deadlock Ignorance: Deadlock을 시스템이 책임지지 않음. 현재 많이 쓰이며, UNIX를 포함한 대부분의 OS가 채택
Chapter 8. Memory Management
0. 기본 개념
Logical(=Virtual) Address: 프로세스마다 독립적으로 가지는 주소 공간, cpu가 보는 주고
Physical Address: 메모리에 실제로 올라가는 위치
External Fragmentation(외부 조각): 프로그램의 크기보다 분할의 크기가 작은 경우(빈곳인데 프로그램이 올라갈 수 없는 작은 분할)
Internal Fragmentation(내부 조각): 프로그램의 크기보다 분할의 크기가 큰 경우(하나의 분할 내부에 발생하는 사용되지 않는 메모리 조각, 특정 프로그램에 배정되었지만 사용되지 않는 공간)
1. Address Binding주소 바인딩(physical 주소 결정하기)
- Compile Time Binding: 물리적 메모리 주소가 컴파일시 알려짐/시작 위치 변경시 재컴파일/컴파일러는 absolute code생성
- Load Time Binding: Loader의 책임 하에 물리적 메모리 주소 부여/ 컴파일러가 relocatable code 생성
- Execution Time Binding: 수행이 시작된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음/ 하드웨어(Memory-Management Unit, MMU)적인 지원이 필요
2. Memory Loading(프로세스를 메모리에 올리기)
- Dynamic Loading: 프로세스 전체를 메모리에 미리 다 올리는 것이 아닌 해당 루틴이 불려질 때 메모리에 load하는 것
- Overlays: 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림.
3. Swapping: 프로세스를 일시적으로 메모리에 backing store(swap area, 대부분 디스크)로 쫓아내는 것
- Swap in/Swap out: 일반적으로 중기 스케줄러(swapper)에 의해 swap out 시킬 프로세스 선정
4. Allocation of Physical Memory
- Contiguous allocation: 각각의 프로세스가 메모리(partition으로 나뉨)의 연속적인 공간에 적재되도록 하는 것
> Fixed Partition Allocation
: partition 분할 당 하나의 프로그램 적재/ internal fragmentation 발생
> Variable Partition Allocation
: 프로그램의 크기를 고려해서 할당/ partition의 크기, 개수가 동적으로 변함/ External fragmentation 발생
*Hole 발생 > 이를 해결하기 위한 Dynamic Storage-Allocation Problem (Sol: First-fit, Best-fit, Worst-fit)
- Noncontiguous allocation: 하나의 프로세스가 메모리(frame로 나뉨)의 여러 영역에 분산되어 올라갈 수 있음
> Paging
: Process의 virtual memory를 동일한 사이즈의 page 단위로 나눔, Page 단위로 noncontiguous하게 저장됨
virtual address = page number(p) + Page offset(d), Internal Fragmentation 발생
Page table/TLB의 search로 해당 frame에 접근
응용)Two-level Paging, Multilevel Paging, Inverted Page Table, shared page
> Segmentation
: 프로그램은 의미 단위(code, data, stack 부분 등등)인 여러 개의 segment로 구성
virtual address = segment-number + offset (segment-number <STLR), External Framgentation 발생
의미 단위이기 때문에 sharing과 protection에 있어 paging 보다 훨씬 효과적이다.
> Paged Segmentation: segment를 여러 개의 page로 구성
Chapter 9. Virtual Memory
0. 기본 개념
Page Fault: 요청한 page가 없는 경우, page fault trap가 발생되어 Free frame에 page 할당
Page Replacement: Free frame이 없는 경우 어떤 frame을 빼앗아올지 결정해야 함
1. Page Replacement
- Optimal Algorithm: 가장 먼 미래에 참조되는 page를 replace
- FIFO Algorithm: 먼저 들어온 것을 먼저 내쫓음
- LRU Algorithm: 가장 오래 전에 참조된 것을 내쫓기, Linked List 형식(O(1))
- LFU Algorithm: 참조 횟수가 가장 적은 객체를 지움(여럿일 때 가장 오래된 page), Heap 형식(O(log n))
*현실적으로 LRU, LFU 불가능: 운영체제가 가장 오래된/참조횟수가 적은 page를 알 수 없다.
> Clock Algorithm: reference bit과 modified bit을 이용해 교체 대상 페이지 선정, refence bit가 0인 것을 찾을 때까지 포인터를 이동
2. Thrashing: 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생
- Working-set Algorithm: 프로세스가 집중적으로 참도되는 해당 page들의 집합인 working set만을 메모리에 올리는 방식
- PFF Schema: Page-fault rate의 상한값과 하한값을 두어 page-fault rate에 따라 frame의 수를 조정한다.
Chapter 10. File Systems & File System Implementation
0. 기본 개념
File: 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 한다.
File attribute: 파일을 관리하기 위한 각종 정보들
File System: 파일을 관리하는 부분, 파일 및 파일의 메타데이터, 디렉토리 정보 등을 관리
Directory: 파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일
1. File Protection: 각 파일에 대해 누구에게 어떤 유형의 접근(read/write/execution)을 허락할 것인가?
- Access Control Matrix: 파일별로 누구에게 어떤 접근 권한이 있는지 표시
- Grouping: 전체 user를 owner, group, public의 세 그룹으로 구분 각각 3비트씩으로 표시
- Password: 파일마다 Password을 두는 방법
2. Allocation of File Data in Disk
- Contiguous Allocation(연속 할당): external fragmentation 존재, Fast I/O
- Linked Allocation: external fragmentation 존재 x, FAT로 응용
- Indexed Allocation: external fragmentation 존재 x, direct access 가능 (응용: Linked Schema, Multi-level index)
3. UNIX
- Bootblock: 부팅에 필요한 정보(bootstrap loader)
- Superblock: 파일 시스템에 관한 총체적인 정보를 담고 있다.
- Inode: 파일 이름을 제외한 파일의 모든 메타 정보를 저장
- Data block: 파일의 실제 내용을 보관
Chapter 12. Disk Management and Scheduling
1. Disk Structure
- logical block: 디스크의 외부에서 보는 디스크의 단위 정보 저장 공간들
- Sector: logical block이 물리적인 디스크에 매핑된 위치(header+실제 data+ trailer)
- physical formatting: 디스크를 컨트롤러가 읽고 쓸 수 있도록 섹터들로 나누는 과정
- Partitioning: 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
- Logical formatting: 파일 시스템을 만드는 것
- Booting: sector 0을 load하여 실행
2. Disk Scheduling: seek time을 최소화하기(seek time≒seek distance)
Access time
= seek time(헤드를 해당 실린더로 움직이는데 걸리는 시간)
+ Rotational Latency(헤드가 원하는 섹터에 도달하기까지 걸리는 회전지연시간)
+ Tranfer time(실제 데이터의 전송 시간)
- FCFS(First Come First Service)
- SSTF(Shortest seek time first): 가장 가까운 헤드 고르기(starvation문제)
- SCAN: disk arm이 디스크의 한쪽 끝에서 다른쪽 끝으로 이동하며 가는 길목에 있는 모든 요청을 처리
- C-SCAN: SCAN에 다른쪽 끝에 도달했으면 곧바로 출발점으로 이동하여 이동, SCAN보다 균일한 대기시간
- LOOK: 헤드가 진행중이다가 그 방향에 더 이상 기다리는 요청이 없으면 헤드의 이동방향을 즉시 반대로 이동
*RAID: 여러 개의 디스크를 묶어서 사용
**Embedded System과 연결되어 관련 코드를 첨부합니다.**
'Coding > Basic' 카테고리의 다른 글
| [백준] 1463번: 1로 만들기(JAVA) (0) | 2021.01.28 |
|---|---|
| [백준] 1541번: 잃어버린 괄호 (JAVA) (0) | 2021.01.26 |
| [Algorithms] Sorting정렬 한꺼번에 살펴보기 (0) | 2019.11.08 |
| [백준] 10773번: 제로 (0) | 2019.10.03 |
| [DataStructures] 정적/동적 메모리 할당 간단 개념 (0) | 2019.10.03 |