# Operating Systems

Virtual Memory: Issues of Implementation
Basic concepts Large and contiguous address space, process protection, execution of process only partially residing in memory 등을 제공하기 위해 VM이라는 테크닉을 사용한다. 그러나 이 방법론의 구현에 완벽한 합의점이 없기에 machine dependent하고, OS의 입장에서 porting을 위해선 HAL등이 필요하다. Main memory는 현재 진행중이 프로세스의 address space의 가장 자주 사용되고 있는 부분만을 담고 있으며, 나머지는 disk로 swapped out되어있는 것이 이상적인 형태이다. 이를 구현하기 위해 paging기법을 사용하고 있으며, Virtual Page Number(VPN)으로부터 Physical Frame Number(PFN)으로의 on the fly translation을 필요로 하는데, 이 translation 정보를 담고 있는

[OS] Operating Systems Introduction
💻 Operating systems defintion OS도 main함수가 있는 하나의 프로그램이다. computer H/W를 관리하고 프로그램의 실행을 제어하는 역할을 한다. > OS 가 관리하는 H/W CPU memory storage(HDD 등) IO device > OS 의 역할 I/O device에 접근 파일에 접근 accouting ( 통계정보를 보여줌 ) [example] 작업관리자: cpu performance(frequency를 통해)를 볼 수 있음. Error detection H/W 잘못 사용할 경우 에러를 출력 > 프로그램 실행제어 scheduling (프로그램 실행순서 결정) Error reporting > OS 의 위치 app H/W 하드웨어와 응용프로그램 사이에 위치한다. OS는 하드웨어에 접근하기 위한 유일한 방법이다. 응

File System Case Studies_운영체제(14)
UNIX FS On-disk layout Boot block : boot volume/boot loader를 가리키는 block Super block : 구성 정보(inode, freelist, datablock의 개수, 위치 등)를 담고 있는 block I-node List(Table) : 모든 inode는 같은 size이고, inode list의 index를 참조하는 block Data Blocks : 실제 데이터를 담고 있는 block I-node Ex) 4KB/block, 12개 → 4KB *

File System Internals_운영체제(13)
File system implementation file system을 향상시킬 때 On-disk, in-memory 두 part로 작업을 한다. Boot control block / Master Boot Record(MBR) : OS의 booting 정보가 담겨 있는 block, kernel 관련 정보 Volume control block(super block, master file table) : 여러 개의 독립된 file system(volume)들에 대한 정보를 담고 있는 block Directory : file name, inode # 등을 담고 있다. File Control Block(FCB) : file에 관한 metadata를 담고 있는 block File control block 
File Systems Interface_운영체제(12)
File system basics Basic Concepts File → 대용량의 정보를 지속적으로(persistence)하게 저장하기 위해 사용 HDD, SDD, CD ROM 등도 기한이 있어 주의해야한다. 정보를 file에 담아 여러 process가 공유하기 위해서 사용하기도 한다. File system file : 물리적인 저장 장치에 저장하는 것이 아닌 추상적인 관점에서 secondary storage를 운영 directories : 계층적으로, 논리적으로 file을 모아둔다. process, user, machine들 사이 data를 공유할 수 있도록 한다. 적법한 방법으로 data에 access하도록 security 기능도 존재한다. Storage : Logical View 
Page Replacement_운영체제(11)
Page Replacement page fault가 발생하면 OS는 fault page를 disk에서 읽고 check해서 memory frame에 올린다. process가 자신에게 할당된 page frame들을 전부 사용했다면 OS는 다른 page를 replace(evict)한다. victim page : evict 된 page 가장 필요 없을 것 같은 page frame을 evict해야한다. Evict the best page 앞으로 다시는 접근하지 않을 page를 evict하는 것 이러한 page를 아는 것은 불가능하기 때문에 예측을 하여 evict한다. 가급적 사용되지 않을 확률(정도)가 높은 page를 evict한다. Belady는 가장 오랫동안 사용되지 않을 page를 evict하는 것이 가장 optimal한 방법이다. Belady’s Algorithm 가장 오랫동안 사용되지 않을 page를 evict하는 방

Address Translation_운영체제(10)
Page Tables Space over head of page tables 32 bit address의 page(0~11 : offset/12~31 : page#)를 table로 만들면 process당 4MB의 space 낭비가 심해서 table의 사용하는 부분만 구현을 하는 방식을 생각 Two-level Page Tables

Memory Management_운영체제(9)
Memory Management Goals programming을 하는데 있어서 편의성을 제공하는 것 한정된 memory를 여러 process가 최고의 performance를 수행하고 minimal overhead를 가지게 하는 것 각 process 사이에 철저한 isolation(보호, 독립) Single/Batch Programming OS를 제외한 나머지 영역은 하나의 process가 독점적으로 사용하는 방식 OS가 RAM, ROM 영역에 수반되어 있는 경우도 있었다. 조금 더 진화해서 Device Driver가 ROM에 수반되어 있는 것이 생겼다. 크게 memory management가 필요 없었다. Multiprogrammin

Deadlock_운영체제(8)
Deadlock 서로 협력하는(연결된) process들이 발생할 수 없는 사건을 기다리는 상태를 의미한다. deadlock 상태의 process는 계속해서 block 상태를 유지한다. network, speed 등 상황에 따라 한번씩 일어날 수 있어서 debugging이 어렵다. 두 개 이상의 자원을 확보해야하는 상황에서 deadlock이 언제나 발생할 수 있는 것을 유의해야한다. Deadlock Examples P1에서 A에 대한 lock을 가지고, P2는 B에 대한 lock을 먼저 가진다. 이후 다음

Threads_운영체제(7)
Why Threads? Process는 많은 정보를 포함하기 때문에 hevey-weight하다. Address space : code, data pages Hardware execution state(Context) : PCB 내부의 PC, SP, registers.. OS resources, accounting info. : open files.. 새로운 process를 create(fork)하는 것은 시간이 많이 걸리고 costly하다. 여러 프로세스는 각자 독립적인 영역을 가지기 때문에 Inter-Process Communication하는 것이 Costly하다. Cooperating Processes web server같은 경우는 자기 자신의 clone을 만들어서 동시에 작업을 하고 multiprocessor 환경에서 병행적인 프로그램으로 활용한다. data를 share하기 위한 같은 address spac
[운영체제] 6. Process Synchronization
- 데이터 접근 Execution-Box: CPU, 컴퓨터내부, process Storage-Box: Memory, Disk, process 주소 공간 Process Synchronization Problem > 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요 => 조율 Race Condition > #### Storage-box를 공유하는 Execution-box가 여럿 있는 경우 발생 가능 _여러 개의
[운영체제] 5. CPU Scheduling
CPU Scheduling CPU & I/O Bursts in Program Execution : CPU burst(load store, add store, read...) -> I/O burst(wait for I/O) -> CPU burst(store increment, index, write to file) -> I/O burst -> CPU burst -> I/O burst ... > 여러 종류의 job(=process)이 섞여 있기 때문에 CPU Scheduling이 필요하다. CPU burst time : process 수행 중 I/O 등 다른 요청 없이 CPU만을 잡고 한 번에 지속적으로 쓰려고 하는 time interval 프로세스 특성 I/O-bound process: CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job (many short CPU bursts) ex) TV 채널 전환 CPU-bound
[운영체제] 4. Process Management
Process Creation & Termination 프로세스 생성 : 부모 프로세스가 자식 프로세스 생성 (fork) 트리(계층 구조) 형성 프로세스는 자원을 필요로 함: 운영체제로부터 받는다 / 부모와 공유한다 자원의 공유: 부모와 자식이 모든 자원 공유하는 모델 / 일부 공유 모델 / 전혀 공유하지 않는 모델(일반적) 수행(execution): 부모와 자식은 공존하며 수행되는 모델 / 자식이 종료될 때까지 부모(shell)가 기다리는(wait) 모델 ex) top 명령어 주소 공간(address space): 자신은 부모의 공간을 복사하고 그 공간에 새로운 프로그램을 올림 ex) UNIX (1) fork() system call이 새로운 process 생성 : PCB가 부모를 그대로 복사(OS data except PID + binary), 주소 공간 할당 (2) fork 다음에 이어지는 exec()
[운영체제] 3. Process
Process > #### " Process is a program in execution " counter.c (프로그래밍) ---(컴파일)---> counter (기계어코드) ---(실행)---> process 프로세스의 문맥 (context) CPU의 수행 상태를 나타내는 하드웨어 문맥. 특정 시점에서 어디까지 수행했는지. ( program counter: 프로그램 중 몇번째 line 수행하는지 가리킴 register: code 수행 시, 사용되는 data ) => 저장, 관리 잘하면 context switching 용이 프로세스 주소 공간: code, data, stack(user mode call stack 저장) 프로세스 관련 커널 자료 구조: PCB, Kernel stack > > 1 (사용자 모드): 사용자 프로그램 수행. 제한된 접근. 일반 명령. 0 (모니터/커널/시스템 모드): OS 코드 수행. 메모리 접근, I/O device 접근 가능. interrupt나 exception 발생 시, 하드웨어: mode bit -> 0 사용자 프로그램에게 CPU 넘기기 전, mode bit -> 1 특권 명령 (privileged instruction): 보안 목적. 커널 모드에서만 수행 가능 Timer : 정해진 시간 경과 후 운
[운영체제] 1. Introduction to OS
운영체제 > 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어(internet browser)와 하드웨어를 연결하는 소프트웨어 계층 협의의 운영체제 (커널): 운영체제 핵심. 메모리에 상주 광의의 운영체제: 커널 + 주변 시스템 유틸리티. 메모리에 상주하지는 x 운영체제의 목적 > 컴퓨터 시스템을 편리하게 사용할 수 있는 환경 제공 동시 사용자 / 프로그램들이 각각 독자적 컴퓨터에서 수행되는 것 같은 환상 제공 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행 > 컴퓨터 시스템 자원의 효율적 관리 프로세서, 기억장치, 입출력 장치 등의 효율적 관리 사용자 간의 형평성 있는 자원 분배: 주어진 자원으로 최대한의 성능 (실행 중인 프로그램들에 짧은 시간씩 CPU 번갈아 할당, 메모리 공간 적절히 분배) 사용자 및 운영체제 자신 보호 프로세스, 파일, 메시지 (SW 자원) 등을 관리

[Book] 운영체제: 아주 쉬운 세 가지 이야기
1. 책 사진 다시보니 참 그립고 정겹게 생긴 표지라는 느낌을 받는다. 향수에 젖는다. 2. 정보 책 이름: 운영체제: 아주 쉬운 세 가지 이야기 저자: Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau 옮김: 원유집, 박민규, 이성진 3. 학습 내용 운영체제 공부 내용만 따로 정리한 노트가 있었는데 지금은 안 보인다. 본가에 있는 듯 하여 돌아가서 가져오면 다시 정리하려 한다. 4. 생각  사실 운영체제 책은 이미 정답이 정해져 있다고 얘기해도 될 정도로 유명한 책이 있다. 흔히들 공룡책이라 부르는 Abraham Silberschatz 선생님의 운영체제가 제일 유명하다. 아직 공룡책은 읽어보지 않았으나 필자가 가지
[Operating Systems] Deadlock Detection
Bug Detection Approach Resource Deadlock|Communication Deadlock| ---|---| Basic Potential Deadlock Detection Algorithm, GoodLock Algorithm|CHECKMATE Basic Potential Deadlock Detection >Cyclic Deadlock Monitoring Algorithm 런타임에 프로세스가 lock을 획득하고 해제하는 행동을 관찰한다. Lock Graph(N, E) (Directed Graph) 스레드가 lock X를 획득하면 노드 Nx를 생성한다. 스레드가 lock X를 획득한 상태에서 lock Y를 획득하면 (Nx, Ny) 엣지를 생성한다. 스레드가 lock X를 해제하면 노드 Nx와 Nx의 incoming edge와 outcoming edge를 모두 지운다. 런타임에 그래프 내에 사이클이
[Operating Systems] Deadlock & Starvation
Deadlock 두 개 이상의 프로세스들이 결코 일어나지 않을 사건을 기다리는 상태를 교착 상태(deadlock)이라고 한다. 예를 들어, 프로세스 P1이 자원 A를 가지고 자원 B를 기다리며 프로세스 P2는 자원 B를 가지고 자원 A를 기다리는 경우가 있을 수 있다. >교착 상태가 되기 위한 필요 조건 상호 배제: 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 점유와 대기: 하나 이상의 자원을 가진 프로세스가 존재하고 다른 프로세스는 그 자원을 기다리고 있는 상태다. 비선점: 프로세스에 의해 점유된 자원은 강제로 뺏을 수 없다. 환형 대기: 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있다. 1~3번이 만족하면 교착 상태가 발생할 수 있다. 교착 상태를 해결하는 방법으로는 예방, 회피, 탐지 및 회복이 있다. 예방 교착 상태의 네 가지 조건이 하나라도 발생하지 않도록 한다. 상호