Published 2020. 12. 18. 20:22

운영체제 요약 노트

🚦 Server/Operating System

개요

An operating system is a program acts as an intermediary between a (user/application) and ( hardware )
The operating system ( ) the system and ( ) applications.
대부분의 프로세서는 (general purpose processor ) 이다.
멀티 프로세서 시스템은 (parallel system) 이거나 (multicore system)이다.
(폰노이만 아키텍쳐) : Stored-program computer model
( Asymmetric multiprocessing ) : Each processor is assigned a specific task.
( Symmetric multiprocessing ) : Each processor performs all tasks
Each ( device controller ) is in charge of a particular device type.
Each device controller has a ( local buffer ).
Device controllers are connected through a ( common bus ) providing access to shared memory
CPU and Device Controller move data from/to main memory to/from ( local buffer ).
Device controller notifies CPU of events by generating an ( interrupt ).
( Word ) = A computer architecture’s native unit of data.

폰노이만 아키텍쳐 : 프로그램과 데이터를 메모리에 저장하여 사용하는 방식

정답 보기

between a user/application, the computer hardware
protects , serve
general-purpose processor
parallel system, multicore system
폰노이만 아키텍쳐
Asymmetric Multiprocessing
Symmetric Mulltiprocessing : 여러개의 프로세서가 서로 같은 메모리를 쓰는 구조
device controller : 특정 장치를 관리함. 마우스를 클릭하면 event가 발생하여 controller에 신호가 간다.
local buffer : 각각 조그만 양의 메모리가 붙어있다. 그것이 buffer 이다. controller가 event가 발생했다고 써주는 곳
common bus
local buffer
interrupt : 인터럽트는 Device controller가 받아서 CPU에게 전해준다.
Word

Operating System

CPU operates in ( User mode ) and ( Kernel mode ).
( Mode bit ) allows to distinguish on which mode system is running.
Some ( privileged instruction ) are only excutable in the kernel mode.
May generate an ( exception ) if and application tries to run a privileged instruction in user mode.
Exception : (trap ) = expected, intended, ( fault ) = unexpected
User mode에서 Kernel mode로 들어오는 방법 : ( interrupt, System Call )
( System Call ) : Programming interface to the services provided by the OS.
Mostly accessed by programs via a high-level ( API ) rather than direct system call use.
OS에서 제공되는 서비스
1. Program excution : 프로그램 실행
2. I/O operation : 입력을 받고 처리해 주는 것
3. File-system manipulation : 읽고 쓰고 하는 것
4. Communication : 컴퓨터 내에 혹은 다른 컴퓨터로 네트워크를 통해 정보를 전송하는 것
5. Error detection : 에러 잡아주는 것, 디버깅
6. Resource allocation : 리소스를 할당받고 다른 곳에 주고
7. Accounting : 리소스를 얼마나 썼고 누가 썼고 관리하는 것
8. Protection and security
User mode에서 System call을 요청하는 메커니즘은 interrupt와 동일하다. System call도 소프트웨어 인터럽트 이다.

정답 보기

User mode, Kernel mode
Mode bit : Mode bit를 읽어보면 내가 User mode인지 Kernel mode인지 알 수 있다.
Privileged instruction : 커널모드에서 돌아가는 명령어. 조심해야 하는 것들, 저장하거나 입력을 처리하는 것들
Exception : user mode에서 privileged instruction을 실행하려고 하면 CPU가 exception을 날린다.
소프트웨어 interrupt라고도 불린다.
Trap, fault
1. Trap = 의도적으로 발생시킨 exception
2. Fault = 잘못돼서 발생된 exception
interrupt, System Call
System Call : 운영체제가 제공하는 서비스를 부르기 위한 프로그래밍 인터페이스.
API : Application Programming Interface

Operating System Structures (1)

Basic Input Output System
1. 전원이 켜지면 CPU는 부트스트랩 프로그램인 Basic Input Output System 을 실행한다.
2. Boot Strap Program이 실행이 되면 시스템을 초기화한다.
3. BIOS에 시스템 주변 장치들을 초기화하는 코드가 들어있다.
4. 초기화가 끝나면 운영체제가 로딩한다.
5. 운영체제는 Boot Loader를 통해 로딩한다.
운영체제 디자인
1. Policy : 뭐가 수행되어야 되냐?
2. Mechanism : 어떻게 수행할까?
3. Mechanism을 잘 구현해 놓으면 다양한 Policy를 설정할 수 있다.
4. Policy에 맞는 Mechanism을 사용하면 된다.
CPU scheduler
1. Policy (what)
  1. 스케줄링 알고리즘 (FIFO, SJF 등)
  2. Quantum size
2. Mechanism (how)
  1. Dispatcher
  2. Priority queue

BIOS -> Bootloader

( ) decisions are important for all resource allocation and scheduling problems.

( ) : The tool for implementing a set of policies

Lowest levels in ( ).

Main body in ( ).

Policy, Mechanism, assembly, C

Operating System Structure (2)

운영체제 종류
1. MS-DOS : Single structure
2. UNIX : Monolithic
3. Layered Approach : Abstraction based
4. Mach : Microkernel
MS-DOS : Single structure
1. System이 켜지면 Command Interpreter인 Shell이 켜진다.
2. User mode, Kernel mode가 없다.
3. application program이 kernel에 직접 접근이 가능하다.
Layered Approach : OS 복잡도를 낮추기 위한 방안
1. 자기 바로 위 아래 레이어들만 interaction 할 수 있다.
  - 제일 바깥쪽 = Layer N = User interface
  - 제일 안쪽 = Layer 0 = Hardware
2. 장점 : Layer의 수정이 다른 Layer와 독립적이다.
UNIX : Monolithic kernel : 커널의 모든 서비스가 같은 Adress Space에 위치한다.
1. System call과 Hardware 인터페이스를 하나의 공간에서 처리한다.
  1. 장점 : 어플리케이션과 모든 kernel 서비스가 하나의 공간에 있기 때문에 데이터 전달시 overhead가 적다.
  2. 단점 : 작은 부분이 잘못되면 전체가 잘못된다. 유지보수가 어렵다.
Mach : Microkernel
1. Kernel 서비스를 기능에 따라 모듈화하여 독립된 주소공간에서 실행시키자.
2. 이러한 모듈을 커널 서버라고 하며, 커널 서버들은 독립된 프로세스 구현, 커널들은 서로 다른 Address space 사용
3. Microkernel은 서버간의 통신(IPC) 같은 단순한 기술만 제공
  1. 장점
    1. 커널 서비스가 따로 구성되어 서로간의 의존성이 낮다.
    2. 커널의 개발 및 유지보수가 용이하다.
    3. Monolithic보다 안정적이다.
  2. 단점
    1. 독립된 서버들간의 context-switching 때문에 overhead가 크다.
4. Shared memory 방식이 아닌 Message passing 방법을 이용한다.

Process

프로세스 : 프로그램을 실행하면 객체화, 실체화되는 것
프로그램 : .exe 파일로 존재하며, 해당하는 클래스를 malloc을 통해 만들어진 것이 프로세스이다.
1. 프로그램을 깔면 디스크로 간다.
2. 프로그램을 실행시키면 인스턴스화(프로세스) 되어서 로딩이 되면 메모리를 차지한다. (프로그램은 메모리를 잡아먹지 않는다)
3. 같은 프로그램을 여러번 시키면 별도의 프로세스가 작동한다. 섹션이 같을지라도 Data, Heap, Stack은 다를 수 있다.
프로세스의 구성 (각자 자신의 4가지 Address Space가 따로 있다.)
1. Program Counter
2. Code : text section
3. Data : containing global variable
4. Stack : containg temporary data
5. Heap : containg memory dynamically allocated during run time. heap에서부터 할당 시작
프로세스의 상태 (5가지 transition)
1. New : 프로세스가 만들어짐
2. Ready : 프로세스가 실행할 준비가 됨 = 프로세스가 CPU에 할당되기를 기다리는 상태
3. Running : 스케줄러가 Ready 상태 중 하나의 프로세스를 CPU에 넣고 돌린다.
4. Waiting : interrupt가 오면 Running 상태의 프로세스를 Waiting 상태로 바꾼다.
5. Terminated : 프로세스의 실행이 종료된 상태
6. I/O event wait : 프로세스가 입출력 처리를 해야하는 상황일 때 Running 상태에서 Waiting 상태로 바뀐다.
  스케줄러에 의해 선택될 수 없다. Ready 상태로 가야한다.
7. I/O event completion : 입출력이 끝난 프로세스는 Waiting에서 Ready 상태로 바뀐다.
  스케줄러에게 선택될 수 있다.
프로세스의 실행
1. fork()
  1. 프로세스가 하나 더 생긴다.
  2. 새로운 프로세스를 위한 메모리 할당
  3. pid_t = 프로세스의 번호를 저장하는 타입
  4. 자식프로세스와 부모프로세스의 순서는 스케줄러가 결정한다.
2. exec() : 생성되는 프로세스는 없다.
  1. 메모리를 할당하지 않고 exec()에 의해 호출된 프로세스만 메모리에 남는다.
  2. 호출된 프로세스는 exec()를 호출한 프로세스의 PID가 그대로 적용된다.
  3. 새로운 프로세스에 의해 덮어 쓰여지게 된다.
3. exit() : 프로세스가 끝나면 exit()해서 종료를 시켜야 죽는다. 혼자 죽는 것이 아니다. 그리고 리턴값을 반환한다.
4. wait() : 프로세스가 종료되면 반환값이 나오는데 parent가 wait()로 받아간다.
프로세스의 종료
1. Voluntary (자발적으로 죽음)
2. Involuntary (비자발적으로 죽음)
3. Jombie Process : 자식이 죽었는데 부모가 wait()를 안하고 있음, 한없이 대기타는 프로세스
  부모가 wait() 해주면 좀비프로세스는 사라진다.
4. Orphan Process : 부모가 죽은 프로세스
  1. Cascading termination : 부모프로세스가 죽으면 자식프로세스 트리를 다 날려버린다.
  2. Reparenting : 최초의 프로세스인 init 에 입양 보낸다, 붙여준다.
PCB(= Process Control Block) : 프로세스 제어 블록
1. 프로세스의 모든 정보를 갖고 있다.
2. 하나의 프로세스는 하나의 PCB를 갖는다.
3. 스케줄러가 프로세스의 ready 상태의 프로세스의 PCB를 보고 최적인 애들을 실행시킨다.

IPC (Inter-Process Communication)

IPC : 프로세스들 간의 데이터 및 정보를 주고 받기 위한 메커니즘
1. 커널에서 IPC를 위한 도구를 제공하며, System call 의 형태로 프로세스에게 제공된다.
2. IPC에는 두가지 모델이 있다.
  1. Shared Memory
  2. Message Passing
Shared Memory : 운영체제야 단톡방 파줘!
1. 두개 이상의 프로세스들이 주소 공간의 일부를 공유하며, Read, Wirte를 통해 통신을 수행한다.
2. Shared Memory가 설정되면 커널의 관여없이 진행된다.
  1. 장점 : 운영체제의 관여없이, 커널의 관여없이 메모리를 직접 사용하여 속도가 빠르다.
  2. 단점 : 여러 프로세스가 사용하므로 구현이 어렵고 관리가 힘들다.
  3. (부록) IPC를 많이한다고 context switching이 많이 일어나진 않는다.
  4. (부록) 메모리 영역에 동시에 접근하기 위해서 lock이나 semaphore를 사용한다.
Message Passing
1. 커널을 경유하여 메시지를 주고 받으며, 커널에서는 데이터를 버퍼링한다.
  1. Sender
  2. Receiver
    1. 장점 : 구현이 간단하다.
    2. 단점 : 커널을 공유하므로 속도가 느리다.
    3. (부록) 해당 프로세스 입장에서 IPC는 일종의 입출력으로 보인다. 따라서 context switching이 발생한다.
Signal : 어떤 프로세스가 다른 프로세스에게 뭔가의 정보, 상황을 알려주는 것
(pid를 아는 특정 프로세스에게 커널을 통해 이벤트를 전달하는 방법)
1. Synchronous signal
2. Asynchronous signal
3. PCB 마다 Signal handler가 있다.
  1. Signal handler : 어떤 Signal을 받았을 때 특정 동작을 하도록 내가 정의하고 싶을 때, 함수를 지정해 줄 수 있다.
    sigaction이라는 함수로 구현 가능하다. 오버라이딩할 수 있다.
RPC (Remote Procedure Calls) : 다른 프로세스에 있는 함수를 내 프로세스의 함수처럼 쓰고 싶어
1. 메모리 공간에 순차적으로 쓰는 것 = [위]0A 0B 0C 0D[아래] : Big-endian
2. 메모리 공간의 제일 앞부분이 가장 밑에 있도록 하는 것 (실제로 이렇게 쓰임) = [위]0D 0C 0B 0A[아래] : Little-endian
  1. Little endian 쓰는 이유 : 하위 비트들만 사용할 때 별도의 계산이 필요 없다.
3. 중립된 방식으로 쓰는 것 : External Data Representation (XDR)
Pipe : 한 프로세스가 다른 프로세스로 데이터를 직접 전달하는 방법
1. Unidirectional : 한쪽 끝에 넣으면 반대쪽으로 나온다.
2. Bidirectional : 양쪽 끝에 넣을 수 있고 양방향으로 나온다.
3. Half duplex : 양쪽 끝에 넣을 수 있고 반대방향 쪽으로만 나온다.
4. Pipe는 부모, 자식 프로세스에서만 사용이 가능하다.
5. Ordinary Pipe : 한쪽 write end에서 read end로 빠져나오는 Pipe
6. Pipe 작동 원리 코드 ****

Thread (1)

Thread
1. 하나의 프로세스에는 하나의 control만 존재하기 때문에 프로세스는 한번에 하나의 일만 처리할 수 있다.
2. 그러나 쓰레드를 사용함으로써 Parallelism하게 사용할 수 있다.
3. 프로세스와 마친가지로 스케줄링 단위(Excution Unit)이다. 프로세스보다 더 작은 단위이다.
4. 프로세스로부터 Excution state(실행 상태)를 뽑아내서 만든다.
5. 프로세스의 Code 영역, Data 영역, Heap 영역은 thread 간에 공유된다.
6. 하지만 Stack은 쓰레드 각자 따로 있다. 그래서 쓰레드는 Stack을 공유하지 않는다. 상대 Stack을 읽을 순 있다.
7. 쓰레드끼리는 IPC없이 통신할 수 있다. 같은 Address space를 공유한다.
8. 쓰레드끼리는 같은 메모리를 사용하므로 switch 비용이 적다.
9. Process들은 각자 자기의 Thread를 가지고 있다. 여러개의 Thread를 가질 수 있다. 다른 Process로 옮겨가진 않는다.
10. 스케줄러는 Thread 단위로 Excution state가 있고, Thread 단위로 Processor에 넣어서 스케줄링한다.
Thread의 종류
1. Single-threaded process : main 함수가 한개 있는 것
2. Multi-threaded process : 여러개의 실이 main 함수를 돌고 있음. 한 프로세스에 여러개의 main함수
Concurrency : 여러개를 돌아가면서 조금씩 하는 것
Parallelism : 동시에 하는 것
1. Data Parallelism : 하나의 데이터를 여러개로 쪼갠 후, 같은 Operation을 Parrallel하게 처리하는 것
2. Task Parallelism : 하나의 데이터를 다른 Operation으로 처리하는 것
Amdahl's Law : Maximum speed 구하는 공식
- N = 코어를 몇개 쓸것인가.
- S = serial portion
- S + (1-S)/N = 실행시간
- 1/실행시간 = 스피드업
- 그래서 maximum 스피드업은 1/S가 된다.

Thread (2)

Pthread (POSIX thread) : 병렬적으로 작동하는 소프트웨어의 작성을 위해서 제공되는 표준 API이다.
즉 쓰레드를 편하게 만들 수 있도록 도와주는 API이다.
Multithreading model
1. User thread
  1. Kernel 영역 위, User space에서 동작하는 thread
  2. User thread가 작동하기 위해서는 Kernel thread와의 매핑이 이루어져야 한다.
  3. 즉 User thread는 Kernel thread를 통해서 프로세서를 사용할 수 있다.
2. Kernel thread
  1. Kernel 영역에서 동작하는 쓰레드
  2. 운영체제가 Kernel 영역에서 쓰레드를 생성 및 관리한다.
  3. 운영체제가 스케줄링하는 Thread 단위는 Kernel thread이다. ****
  4. CPU 스케줄링에서 프로세스가 기본 단위이지만, 쓰레드를 고려한다면 Kernel thread가 CPU 스케줄링의 기본 단위이다.
  5. 스케줄링은 프로세스를 누가 사용할지 결정하는 것이다.
User thread - Kernel thread 간의 mapping
1. One to One
  1. 하나의 User thread가 하나의 Kernel thread와 매핑되는 형태
  2. User thread가 형성되면 그에 따른 Kernel thread가 생성된다.
    1. 장점 : 여러개의 쓰레드를 동시에 수행할 수 있다.
    2. 단점 : Kernel thread 도 한정되어 있어서 무한정으로 생성할 수 없다.
2. Many to One
  1. 여러개의 User thread가 하나의 Kernel thread에 매핑되는 형태
  2. thread 관리는 User level에서 이루어진다.
    1. 장점 : 운영체제가 커널을 하나만 스케줄링 했을 때 context switch가 잘 된다.
    2. 단점 : 한번에 하나의 thread만 Kernel thread에 접근할 수 있으므로, 하나의 thread가 System call을 호출하는 등 Kernel에 접근하면 나머지 thread들은 대기하여야 한다.
3. Many to Many
  1. 여러개의 User thread가 여러개의 Kernel thread에 매핑되는 형태
  2. Many to One 처럼 하나의 thread가 System call을 호출할 경우 다른 thread가 block되거나 waiting하는 현상을 보완함
  3. Many to One과 One to One의 문제점을 해결한다.

Thread (3)

Implicit Threading : 쓰레드의 스케줄링을 사용자가 하는 것이 아니라 운영체제 또는 컴파일러에게 맞기는 것이다.
Thread Pool
1. 쓰레드를 만들고 제거되는 상황에서, 쓰레드를 만드는 시간이 동작하는 시간보다 오래 걸릴 수 있다.
  시스템의 동작을 보장하는 최대한의 쓰레드 수에 대한 제한이 필요하다.
2. 쓰레드가 필요하면 Thread Pool 에서 가져오고, 다 쓰면 Thread Pool에 돌려놓는다.
3. 쓰레드를 만들고 없에는 과정을 분리시킬 수 있다.
Fork Join : 메인 쓰레드가 task를 수행할때 쓰레드를 fork로 쪼개서 수행하고, task가 끝나면 join으로 재결합해서 가져온다.
OpenMP : Shared Memory를 이용한 멀티쓰레딩 프로그램 만들 때 쓰이는 프로그램
Issue in Threading : fork(), exec()는 프로세스를 기준으로 만들어졌다. 그래서 Thread 처리할 때 문제가 있다.
1. 하나의 프로세스 안에 세 개의 쓰레드가 존재하는 경우,
  하나의 쓰레드가 fork()를 한다면 쓰레드 하나 짜리 프로세스를 만들어야 하는가?
  아니면 쓰레드 세 개 짜리 프로세스를 만들어야 하는가?
2. 하나의 프로세스 안에 세 개의 쓰레드가 존재하는 경우,
  하나의 쓰레드가 exit()을 한다면 exit()을 호출한 쓰레드만 종료시켜야 하는가?
  아니면 프로세스 전체를 종료시켜야 하는가?
3. fork()
  1. 하나의 프로그램 내의 thread가 fork를 호출하면 모든 thread를 가지고 있는 프로세스를 만들 것인지 아니면 fork를 요청한 thread만을 복사한 프로세스를 만들 것인가의 문제
  2. pthread 에서는 fork로 불렀던 쓰레드 하나만 복사한다. ****
  3. UNIX 에서는 fork로 부르면 모든 쓰레드 다 복사한다. fork1 은 하나만 복사한다.
4. exec()
  1. fork를 하여 모든 thread를 복사 했을 경우 exec을 수행하면 모든 thread들은 새로운 program으로 교체가 됨
  2. 교체될 thread의 복사는 불필요한 작업으로 판단해여, 현재 address space가 싹 날아가고 새로 만들어진다.
Signal Handling : 일반적으로 한 프로세스에 있는 쓰레드들 끼리는 Signal Handler를 공유한다.
Thread Cancellation : thread의 작업이 끝나기 전에 외부에서 작업을 중지시키는 것
1. Asynchronous Cancellation : 한 thread가 target thread를 종료시킨다. (얘가 문제)
2. Deferred Cancellation : target thread가 주기적으로 자신이 종료되어야 되는지 확인한다. cancellation point를 확인한다.
Thread Local Storage (TLS) : thread들은 프로세스의 데이터를 공유하지만, 자기만 access 할 수 있는 데이터를 TLS라고 한다.
Thread in Linux
1. 리눅스에서 thread 라는 것이 없고 대신 task라고 불린다.
2. 리눅스에서 Process 는 address space를 공유하는 task들의 집합체라고 불린다.
3. task를 만들 때는 clone() 을 이용한다.

Process Scheduling (1)

Process Scheduling
1. 프로세스 안에는 Code, Data, Heap, Stack이 있고, Excution state를 담당하는 PC counter, SP가 있다.
2. 프로세스들는 서로 다른 Address space를 가지고 있고 하나의 컴퓨터에서 동시에 돌아갈 수 있다.
3. 하나의 프로세서로 여러개의 프로세스를 돌리고 싶다면? Concurrent하게 해야한다. 이것을 Process Scheduling 이라고 한다.
4. "어떻게 프로세스에게 CPU를 할당할 것인가?"
  1. Ready Queue에 있는 프로세스들 가운데 하나에게 CPU를 할당한다.
  2. Scheduler 를 통해 프로세스의 context를 바꿔가며 돌게한다.
Process Scheduling 의 목적
1. 적은 Processor로 많은 Process를 실행하자.
2. CPU 이용률(utilization) 및 처리량(throughput)의 최대화
프로세스는 두 Burst를 번갈아가면서 실행한다.
1. CPU Burst : CPU로 연산을 수행하는 시간
2. I/O Burst : I/O 처리를 위해 기다리는 시간
프로세스 분류에 따른 CPU Burst의 특징
1. CPU-Bounded Process : CPU가 돌아가는 시간이 긴 프로세스
  1. 짧은 주기의 긴 CPU Burst
  2. 기다리는 시간이 짧고 CPU를 많이 사용한다.
2. I/O-Bounded Process : I/O가 많고 CPU가 돌아가는 시간이 적은 프로세스
  1. 긴 주기의 짧은 CPU Burst
  2. 기다리는 시간이 길고 CPU를 적게 사용한다.
Context-Switch
1. CPU가 A process에서 B process로 넘어갈 때 현재 프로세스 상태를 PCB에 저장하고 다른 프로세스의 상태를 꺼내오는 것
2. 현재 돌고있는 상태를 PCB에 저장하고 다른 프로세스의 상태를 PCB에서 가져오면서 Context Switching 한다.
3. Ready Queue : 바로 다음에 돌릴 수 있는 프로세스를 관리한다.
4. I/O Queue

Process Scheduling (2),(3)

Starvation : CPU가 바빠서 프로세스가 CPU를 할당받지 못하는 것
Preemptive Scheduling
1. OS 가 현재 사용하고 있는 프로세스를 멈출 수 있다.
2. CPU가 프로세스를 처리하는 도중에 프로세스를 빼버림.
Non-Preemptive Scheduling
1. CPU를 사용하고 있는 프로세스가 자발적으로 CPU 사용을 해제함
2. 멀티프로그래밍에서는 기본적으로 Preemptive Scheduling 사용
Batch System : 최대한 처리를 많이해야 하는 시스템, Throughput, CPU Utilization이 중요한 시스템
Interactive System : 성능이 아니라 Response time이 중요한 시스템
스케줄링 기준
1. 높으면 좋은 것
  1. CPU Utilization (CPU 이용률)
  2. Throughput (프로세스 처리율)
2. 낮으면 좋은 것
  1. Turnaround time : 완료되는 시간
  2. Waiting time : 대기시간
  3. Response time : task가 도착해서 잠깐 기다리다가 assign 되고 실행될 때까지 걸리는 시간
스케줄링 종류
1. 계산법
  1. T waiting : 각 프로세스가 들어온 시간부터 실행시작 전까지 걸리는 시간의 합 / 프로세스 개수
  2. T turnaround : ++(프로세스가 끝난 시간 - 프로세스가 들어온 시간) / 프로세스 개수
2. FCFS (= First Come First Served)
  1. 먼저 온 프로세스부터 처리하는 것
  2. Non-preemptive (뺏지 않음)
  3. Starvation이 없다. 내 순서가 오면 내가 할당되기 때문
3. SJF (= Shortest Job First)
  1. CPU burst가 가장 짧은 것부터 처리하는 것
  2. 가장 짧은 waiting time을 보장한다.
  3. Non-preemptive (뺏지 않음)
  4. Starvation 발생할 수 있다. CPU burst 큰 것 계속 들어오면 할당 못해준다.
4. SRTF (= Short Remaining Time First)
  1. SJF의 preemptive version
  2. Preemtive (뺏음)
  3. CPU를 할당받아 수행중이더라도 CPU Burst time이 현재 남은 시간보다 짧으면 넘겨준다.
5. Priority Scheduling
  1. 우선순위(Priority)에 따라 CPU를 할당하는 것
  2. Preemtive, Non-preemtive 둘다 존재한다.
  3. 문제점
    1. Starvation : 낮은 Priority를 가지면 할당되지 못할 수 있다.
      - 해결법
        
        Aging : 기다리는 시간에 따라 Age를 부여하여 Priority를 높여준다.
        Priority Boosting
    2. Priority Inversion : 제 3의 task가 끼어들어 높은 Priority task를 진행하지 못하게 한다.
      - 해결법
        
        Priority Ceiling Protocol (PCP) : Shared resource를 잡을때마다 즉시 priority를 미친듯이 높여주고 필요 없으면 다시 놓아주는 방식
        
        Priority Inheritance Protocol (PIP) : 낮은 Priority의 프로세스를 높여주는 방식
6. Round Robin Scheduling
  1. CPU를 time quantum(시간단위)으로 할당하며, 할당한 time quantum이 되면 강제로 CPU 사용을 해제한다.
  2. Starvation이 발생하지 않는다.
  3. Preemtive (뺏음)
  4. 특징
    1. Ready quque 내의 프로세스 수 = n
      time quantum = q
      각 프로세스의 대기 시간 = 최대 (n-1)*q
    2. q가 클 경우 FCFS와 같아지게 된다.
      q가 작을 경우 context switching이 많아진다.
7. Mutilevel Queue Scheduling
  1. 각각의 큐 마다 서로 다른 Scheduling 방법을 쓰게하자.
  2. 큐 간의 Scheduling policy를 고려해야 한다.
  3. Multilevel Feedback Queue (MLFQ)
    1. 실행해보고 상황을 봐서 피드백을 받고 Scheduling 방식을 바꾸자.
    2. 리눅스는 MLFQ를 사용한다.

Process Scheduling(4)

Proportional Share Scheduling
1. 큐마다 다른 비율로 각각의 프로세스를 나눠서 쓰는 것
2. time quantum으로 프로세스를 나눠주는 법
3. Lottery Scheduling : 티켓을 나눠준 개수에 비례해서 프로세스를 나눠주는 법
Real-time Systems : 실행이 완료되어야할 dead line이 있는 프로세스
1. Soft real-time systems: task 처리 시간이 달라지면 성능이 감소하는 경우 (streaming video 등)
2. Hard real-time systems: task 처리 시간이 달라지면 실패하는 경우 (자동차의 air-bag 등)
3. t ≤ d ≤ p
  1. 주기 = p
  2. CPU burst = t
  3. Deadline = d
Rate Monotonic Scheduling (RMS)
1. 들어오는 주기가 짧은 프로세스에 우선순위를 부여한다.
2. preemptive
3. Worst case utilization
  1. N = Process들의 갯수
  2. CPU Utilization의 합 > N x (2^(1/N) - 1) 이면
  3. RMS로는 스케줄링이 안되는 경우가 발생할 수 있다.
Earlisest Deadline First (EDF)
1. Deadline이 가장 빠른 프로세스에 우선순위를 부여한다.

Synchronization (1)

Quiz

When threads can concurrently access and change shared variables, we say that part of code is a ( ) and it may lead to a ( ).

To make the program run correctly, we need a mechanism to ( ) threads.

A ( ) is one of such mechanisms. A correct implementation should provide ( ), ( ), and ( ) properties.

Answer

critical section , race condition

synchronized

Lock, mutual exclusive, progressive,bounded waiting

Synchronization (동기화)
1. 논리주소 공간을 공유하는 협렵적 프로세스의 질서 있는 실행(orderly excution)을 보장하며, 데이터의 일관성(consistency)을 유지할 수 있으며, 이를 Synchronization 이라고 한다.
2. 여러 프로세스가 동시에 실행되게 되면, 여러 프로세스가 공유하는 데이터의 무결성에 문제를 일으킬 수 있다.
3. concurrency 때문에 프로그램의 행동이 non-deterministic하게 바뀔 수 있다.
4. 프로세스 또는 쓰레드들이 shared memory에 접근할 때, 그들의 순서를 조절해 주는 것 = Synchronization
5. Synchronization 하기위해 처리해주는 장치 = Lock
  1. aquire() : 화장실 문 열기
  2. release() : 안에 있는 사람 나오기
Race condition : 2개 이상의 concurrency한 쓰레드들이 공유된 자원에 접근할 때 Synchronization 메커니즘 없이 접근하려는 상황
Critical section
1. 여러 프로세스들이 공유하는 데이터에 접근하는 코드 영역
2. Critical section 에서 Race condition 이 발생한다.
3. 한번에 오직 하나의 프로세스만이 Critical section에 접근해야 한다.
4. Race condirion 의 해결 조건
  1. Mutual Exclusion
    1. 만약 프로세스 A가 Critical section에 진입해 있다면, 다른 모든 프로세스는 진입할 수 없어야 한다.
    2. 어떤 프로세스도 Critical section에 못 들어가도 Mutual Exclusion은 만족한다. 그럼 어떻게? -> Progress
  2. Progress
    1. 만약 어떤 프로세스도 Critical section 내에 있지 않고, Critical section에 집입하려는 프로세스가 존재한다면
      실행 중이 아닌 프로세스들중 누가 진입할 지 결정할 수 있어야 한다.
    2. 결정은 무한히 연기될 수 없다.
  3. Bounded Waiting
    1. 프로세스가 Critical section에 진입할 때까지 걸리는 시간에 limit가 존재하여야 한다. 안그러면 Starvation 발생
      1. 프로세스의 개수 = n
      2. time quantum = q
      3. limit = (n-1) x q
5. Race condition 해결 방법
  1. Spinlock
    1. 문이 잠겼는지 안 잠겼는지 계속 확인하는 것
    2. while문을 돌면서 lock이 1이면 계속 기다리고 lock이 0이면 들어갈 수 있다.
    3. 단점 : 0번이 끝나고 1,2번이 Mutual Exclusive 할 수 있다 >> 문고리 동시에 잡아버린다.
  2. Software-only Alogorithm
    1. 상대방 = other, 나 = my_id. 를 통해 상태를 알린다.
    2. 단점 : 서로 기다리는 상황이 발생할 수 있다 >> Progress 가 제공이 안될 수 있다.
  3. Peterson’s Algorithm
    1. turn = other를 통해 먼저 양보하는 방법
    2. 단점 : atomic 하지 않은 곳에 쓸 수 없다.
  4. Synchronization Hardware
    1. Disabling Interrupt
      1. 인터럽트를 끄는 것.
      2. scheduler가 관여하지 못한다.
      3. 단점 : 안정성을 해친다, 보안이 약하다.
    2. Test-And-Set(변수의 위치, 새로 바뀔 값)
      1. 쪼개지 않고 한번에 수행하는 방법.
      2. 문고리를 잡고, 문을 잠그는 것을 쪼개지 않고 동시에 한다.
      3. 테스트해서 원하는 값이면 새로운 값으로 바꾸겠다.
    3. Compare-And-Swap
      1. 세개의 변수를 이용해서 처리한다.

Synchronization (2)

Mutex Lock (Mutual Exclusive Lock)
1. Mutual Exclusive propoerty를 제공하는 Lock
2. Spinlock
  1. 문고리를 계속 돌려보는 방법
  2. 장점 : context-switch가 일어나지 않는다.
  3. 단점 : 계속 돌려봄으로써 리소스를 계속 요구하므로 CPU 낭비가 심하다.
3. block : aquire 한번만 해보고 점잖게 기다리는 것
Semaphore
1. Shared data의 개수를 의미한다.
2. S 변수 : 공유자원의 개수를 나타내는 변수
  1. S값을 1로 주면 lock과 똑같다.
3. Wait() : Shared data가 없으면 기다린다.
4. Signal() : 나 다 썼으니 너 써! 라는 신호
5. Semaphore의 종류
  1. Binary semaphore (= mutex)
    1. S값이 1인 경우
  2. Counting semaphore
    1. S값이 N인 경우

Deadlock

Deadlock
1. 2개 이상의 task들이 1개 이상의 resource를 요청하며, 서로 resource를 받기를 기다리고 있을 때 Deadlock이 발생한다.
Deadlock 발생 조건 4가지
1. Mutual exclusion
  1. 두 개 이상의 task들이 서로 share 해서 쓸 수 없는 resource 여만 한다.
  2. (하나의 쓰레드가 어떤 자원을 사용하고 있다면, 다른 쓰레드는 요청을 하고 반납이 될 때까지 대기해야 함)
2. Hold and wait
  1. 어떤 resource가 필요한데 acquire하는 도중에, 다른 resource가 필요하면 내가 가지고 있는 것은 든 상태로 기다린다.
  2. (쓰레드는 반드시 적어도 1개의 자원을 가지고 있어야 하며, 추가적인 자원을 얻기 위해서는 다른 쓰레드의 사용이 끝나길 대기해야 함
3. No preemption
  1. 어떤 resource를 줬으면 함부로 뺏어가지 않는다.
  2. (사용중인 자원은 중간에 뺏어갈 수 없다.)
4. Circular wait
  1. P1부터 PN까지의 task가 있는데 언젠가는 circular한 상황이 발생한다.
도로와 차의 관계에서 Deadlock
1. Mutual Exclusion : 도로는 두 차가 다 차지할 수 없으므로, 도로는 Mutual Exclusive 한 resource이다.
2. Hold and Wait : 내가 도로를 차지한 상황에서 다음 도로를 가져가야 한다.
3. No preemption : 내가 도로를 차지한 상황에서 다른 차가 내 도로를 차지할 수 없다.
4. Circular Wait : 돌고 돌아서 대기중인 상태이다.
어떻게 하면 Deadlock이 발생하지 않을까?
1. Deadlock Prevention
  1. Deadlock의 조건 중 하나라도 발생 안 되게 하면 된다.
  2. Mutual exclusion 부정
  3. Hold and wait 부정
    1. 단점
      1. 자원 활용성이 떨어진다 : Resource를 계획적으로 쓰지 않아서
      2. Starvation이 발생할 수 있다 : 요구하는 resouce가 적은 task들이 계속 가져간다면
  4. No preemption 부정
    1. preemptive하게 만들어주면 된다.
  5. Circular wait 부정
    1. total ordering 부여 : 한 방향으로 리소스를 잡게끔 만들어준다.
2. Deadlock Avoidance
  1. Safe한 상태
  2. Unsafe한 상태 : 모두가 필요한 리소스를 배분해줄 수 없을 때
  3. Unsafe할 때 리소스를 주지 않고 Safe할 때만 리소스를 준다.
  4. Banker’s Algorithm
    1. safe sequence가 있다면 할당해주는 방법 (그림 참조)
    2. 단점 : 최대 자원 요구량을 미리 알아야 한다.
3. Deadlock Recovery
  1. Deadlock이 발생한 상황을 알아내고 해결하는 것
  2. Process termination
  3. Resource preemption
4. Ignoring Deadlock
  1. 처음부터 Deadlock 안나게 하는 것

Address Space

Address
1. Physical address / Logical address
2. Absolute address / Relative address
Physical Address
1. 컴퓨터의 메인 메모리에 접근할 때 사용되는 주소
Logical Address
1. 프로세스 관점에서 사용되는 주소
2. CPU에 의해 발생한다.
Memory Management Unit (MMU)
1. Logical Address 를 Physical Address로 translate 시킨다.
2. 서로 다른 프로세스가 서로 같은 Logical Address를 쓸 수 있지만, MMU를 통해 서로 다른 Physical Address에 매핑되어있다.
Fixed Partition : 고정되게 메모리 쪼개기
1. Physical Address = Base Address + Logical Address
2. 장점
  1. Base register 값을 읽거나 주면 되므로 구현이 간단하고 Context switch가 쉽다.
3. 단점
  1. Partition Size
  2. Internal Fragmentation : 메모리를 프로세스에게 exclusive하게 나눠준거라서 남은 공간을 다른 프로세스가 할당 받지 못하게 된다.
Variable Partition : 다양하게 메모리 쪼개기
1. 일정 크기로 쪼갤 필요 없이, 프로세스가 얼마나 필요한지 알고, 비어있는 부분을 프로세스에게 주는 것
2. 메모리 사이즈를 체크해서 할당하므로 Internal fragmentation이 발생하지 않는다.
3. 단점
  1. External Fragmentation : 메모리가 쪼개져서 프로세스 하나가 그만큼의 크기의 메모리를 할당받지 못한다.
4. 해결책
  1. Compaction : 앞으로 밀착시켜서 Contiguous하게 만든다.
  2. Paging : 아예 작게 잘라서 조금씩 준다.
Segmentation : Variable Partition의 확장
1. Address space의 4가지인 Code, Data, Heap, Stack을 서로 다른 Segment로 놓는다.
2. 모두 다르게 allocation 할 수 있다.
3. 프로세스는 자신의 Address space를 Segment의 collection으로 본다.
4. 따라서 자신의 Segment Table을 참조해야 한다.
5. 단점
  1. 여전히 External Fragmentation이 발생한다.
  2. Segment Table을 새로 바꿔야할 수도 있다.

대부분의 모든 프로세스는 ( ) address로 동작한다.
Fixed Partition에서 Physical address = ( ) address + ( ) address

Logical
base, logical

Paging and Page Tables

Contiguous memory allocation
1. Fixed partition : Internal fragmentation
2. Variable partition : External fragmentation
3. Segmentation : External fragmentation
Paging
1. Physical Address를 non-contiguous하게 쪼개는 것
2. 고정된 사이즈로 잘리며, “Frame” 으로 불린다.
3. Logical Address는 “Page” 로 쪼개진다.
4. Page 사이즈가 클수록 Internal fragmentation이 날 가능성이 크다.
5. External fragmentation 이 일어나지 않는다.
Page Table
1. OS 가 관리한다.
2. MMU 가 Translate한다.
3. Virtual address는 Page Table을 통해 Physical address로 translate 된다.
4. 각각의 프로세스는 자신만의 Page Table을 갖는다.
5. 쓰레드들은 Address space를 공유하므로 Page Table을 공유한다.
6. 프로세스 수준에서 정의된다.
7. 프로세스A는 프로세스B의 Page Table을 읽을 수 없다.
Page Table Entry : Page Table의 각 행
1. VPN (Virtual Page Number)
2. PFN (Physical Frame Number)
3. Virtual Address = < VPN | Offset >
4. Physical Address = < PFN | Offset >
5. Page Table은 VPN을 PFN으로 translate 한다.
6. Offset 부분은 그대로 가지고 온다.
Linear Page Table
1. PTBR(Pasge Table Base Register)로 읽어서 처음부터 차례대로 보자
Hierarchical Page Table
1. Page Table도 Contiguous 하게 있을 필요가 없으므로 Page 단위로 쪼개자.
2. Outer Page Table을 하나 더 두어서 Page Table을 가리키도록 한다.
3. PTBR은 Outer Page Table 의 시작을 가리킨다.
4. Virtual Address = < Outer page number | Page number | Offset >
  1. Page 크기에 따라서 Offset 크기가 결정된다.
  2. 하나의 Page에 몇개의 PTE가 들어가냐에 따라서 나머지가 결정된다.
5. Hierarchical Page Tables Example
  1. 53 bit Address space, 8KB pages, 8byte/PTE
    1. Page 크기에 따라서 Offset의 크기가 결정되므로
      Offset의 크기 = 8 KB = 2^13 = 13 bit
    2. Page 하나의 크기 = 8 KB
      PTE 하나의 크기 = 8 byte
      8 KB / 8 byte = 1 K = 2^10개의 PTE가 들어갈 수 있다.
      따라서 10 bit 를 하나의 level에 할당한다.
    3. 아직 53 bit - 13 bit - 10 bit = 30 bit가 남아있으므로 계속 할당해준다.
    4. 10 + 10 + 10 + 10 + 13 = 53 bit
    5. translate는 + 의 개수만큼 해야하고, 따라서 4 level page table 이다.
    6. 하나의 VPN을 translate 하기 위해서 4번 access 해야 한다.
  2. 48 bit Address space, 4KB page, 한 level의 폭 = 9 bit
    1. Offset = 4 KB = 12 bit
    2. Page = 4 KB = 12bit
      48 bit - 12 bit = 36 bit
    3. 한 level의 폭이 9 bit이므로 한 level 당 2^9 개의 PTE가 할당된다.
    4. PTE 하나의 크기 = 한 Page 의 크기 / PTE 개수 = 4KB / 2^9 = 2^3 = 8 byte
    5. 4KB Page에 PTE 하나는 8 byte이다.
6. 장점
  1. 하드웨어 구현이 간단하다. MMU 만들기가 쉽다.
  2. Physical memory를 관리하기 쉽다.
  3. Externel Fragmentation 이 발생하지 않는다.
7. 단점
  1. 복잡하다.
Hashed Page Table
Inverted Page Table
1. PFN의 어디에 매핑이 되어있나
Translation Look-aside Buffer (TLB)
1. Hierarchical Page Table은 translation 하려면 메모리 access가 필요하기 때문에 조금 줄여보자.
2. 하드웨어 로직이다.
3. TLB는 MMU의 일부로 구현되어 있다.
4. Context switch 돼서 프로세스가 바뀌면 Page Table도, TLB도 무효화된다.
  1. 그러면 flush 해야한다. 아니면 잘못된 Page Table을 참조할 수 있다.
  2. 해결책 : Address-space Identifiers(ASID) : Process ID, Address ID를 TLB를 적어준다.

Example PTE

Virtual Address 의 Size가 32 bit이고

Virtual Address 의 단위인 Page Size (4KB)로 나눠주면 2^20 개의 Page가 나오며

Physical Address 의 Size는 20 bit이고

Physical Address 를 Page Size (4KB)로 나눠주면 2^8개의 Frame이 나오며

Page Table은 2^20개의 Page 개수에 맞게끔 2^20개의 Page Table Entry가 필요합니다.

또한 2^8개의 Frame 수에 맞게끔 Page Table Entry의 크기는 8 bit 인 것까지 이해가 됩니다.

Page table의 size는 PTE의 개수(2^20개) * PTE의 크기(8bit) = 2^23 bit

Demand Paging and VM Features

Swapping : 메모리를 추가적으로 쓰고 싶을 때, 프로세스 전체를 backing store로 내보내는 방법
Demand Paging
1. Page 단위로 필요할 때만 swapping 하는 것
2. Swap file 이라는 디스크에 있는 저장 장치로 빼버린다.
3. Swap file 은 ~~메모리~~가 아닌 Disk 에 있다.
4. Page Table Entry 값을 Swap Entry 로 바꾼다.
5. 프로세스가 원하는 파일이 Swap file 에 있다면?
  1. Swap out 돼 있으므로 MMU가 translate 하지 못한다.
  2. Page fault 를 날린다.
  3. 프로세스는 메모리에 있는 정보만 읽고, 디스크를 바로 읽을 수 없다.
  4. 그러므로 victim frame이나 victim page를 정해서 Swap file에 가져다 놓고 다시 필요로 하는 정보를 메모리로 가져와야 한다.
Demand Paging 작동 기반 = principle of locality
1. The principle of locality : 사용된 애들이 더 자주 사용 될 것 같다.
2. Temporal locality : 시간상 이때 다시 일어날 것 같다. 좀 이따가 또 발생할거 같다.
3. Spatial locality : 그 주변에서 다시 일어날 것 같다.

운영체제가 메모리를 관리하는 핵심 아이디어는 일정크기의 Page를 잘라서 Paging을 하는 것이고

Page Table을 통해서 Translation을 해가면서

MMU가 Translate 해서 동작을 시키는 거고

거기에 약간 양념을 가미해서 Page Table을 운영체제가 일부 고쳐서

Swapping, Demand Paging을 통해 필요한 것만 넣게한다.

PTE가 invalid하면 Page fault를 날리고 하드웨어가 그것을 알아서 처리해준다.

이 모든 것을 Virtual Memory를 사용한다고 말한다.

Shared Memory : 메모리를 효과적으로 사용하는 수단
1. 프로세스가 서로 같은 Page를 보게 만든다.
2. 프로세스는 원래 각각 자신의 Address space를 가지고 있다.
3. Virtual address space = User address space + Kernel address space
4. 운영체제는 모든 프로세스를 공통적으로 Kernel address에 매핑하여서 동작한다. ★
5. User process 들은 같은 Kernel address space를 공유한다. ★
Copy-on-Write
1. fork가 완료된 시점에서 child가 자신의 값을 바꿔도 부모에게 적용되면 안된다. 이때 Copy-on-Wirte 쓴다.
2. Page allocation을 미루고 같은 내용을 최대한 공통적으로 사용하게 만들어 보자
3. 사용법
  1. fork 할 때 같은 Page를 보도록 Sharing을 한다.
  2. Write permission을 다 꺼버린다.
  3. 만약 Write를 하여 덮어쓰면 parent와 같은 값을 갖게 되므로, 그러면 안된다.
  4. 대신 새로운 Page에 Copy 를 해서 Write를 가능하게 한다.
  5. Map count를 이용해서 새로운 Page를 사용한다.
    1. Page fault handler에서 Page fault가 났을 때, Page를 복사할지 말지 새로운 것을 만들 지 결정해야 하기 때문

정리 :

Page Table에는 Write 못하게 막아놨어. 어떡해? 너가 처리해줘 >> Page fault가 발생한다.

그러면 운영체제가 Page fault handler를 사용해서

야 이거 Copy-on-Write 때문에 꺼져 있는거야!

새로운 페이지 하나 할당 받아서 원래 내용 복사해놓고 Page Table도 Write 할 수 있게 만들어 준다.

VM Features

Code
1. File-backed page : 디스크로부터 읽어져 오는 Page
2. Code는 File-backed page에서 온다.
3. swap file에 백업을 해 놓을 필요가 없다.
Stack,heap
1. anonymous page
2. swap file에 백업을 해놔야 한다. 원본을 살릴 방법이 없기 때문이다.
Data
1. Data는 File-backed page에서 오지만
2. overwrite를 하면 copy-on-wirte 로 동작한다.
Frame allocation : Page Frame을 나눠주는 방법
1. Equal allocation
2. Proportional allocation
3. Priority allocation
Page Replacement (victim을 뽑을 때)
1. Global replacement : 전체에서 잘 안쓰는 Page가 빠진다.
2. Local replacement : 너가 안 쓰는 것 중에서 가져다 써라.
Working set : 프로세스가 사용하고 있는 page set
1. physical memory가 working set을 다 커버하지 못할 수 있다.
Buddy System Allocator
1. External fragmentation을 관리해주는 것
2. allocation할 때 쪼개면서 free 하고
3. 다시 합칠 때는 free를 합쳐가면서
Slab allocator : 일정 크기의 오브젝트를 빨리 할당할 수 있는 allocator
1. 특정 크기의 allocation을 빨리 할 수 있게 최적화 되어 있다.
Prepaging
1. Page fault를 처리할 때, 그 주변의 것들도 참조해서 가져오는 방법

Page Replacement

Page Replacement : victim page를 선택하는 방법
1. Page fault rate를 최소화 시키기 위한 목적
2. OPT
  1. Page replacemet policy 중 가장 좋은 방법
  2. 가장 Page fault가 낮다.
  3. Belady’s Algorithm
    1. 가장 나중에 참조될 것 같은 애를 뽑아내는 방법
    2. 미래에 무엇이 참조될 지 알기 힘들기 때문에 현실적으로 불가능하다.
    3. 이상적인 Page ratio를 알기 좋기 때문에 평가 기준으로 사용된다.
3. First-In First-Out (FIFO)
  1. 가장 옛날에 들어온 것을 빼는 것
  2. Belady’s Anomaly에 굉장히 좋지 않다.
  3. Belady’s Anomaly : Page를 더 증가시켰는데 Page fault가 증가하는 현상
4. Least Recently Used (LRU)
  1. 가장 최근에 사용되지 않았던 것을 빼는 것
  2. 과거의 행적을 보고 미래를 판단한다.
  3. 최근에 참조된 것은 위로 올려준다.
  4. Belady’s Anomaly를 겪지 않는다.
  5. Page fault가 증가하지 않는다.
  6. LRU의 구현방법
    1. Linked list 이용
      1. 장점 : 누굴 뽑아내는지 바로 알 수 있다.
      2. 단점 : overhead가 크다.
    2. Clock or Counter 이용
    3. Additional-Reference-Bit Algorithm 이용
      1. 원래 Page Table을 Reference bit을 주기적으로 초기화 해준다.
      2. 그리고 새로운 Page Table에 Reference bit을 shift해서 넣어준다.
      3. 2진수로 쌓이게 되고, 숫자가 작은 것이 옛날 것이다.
    4. Second-Chance Algorithm
      1. 누군가를 빼야되는 상황이 오면 1로 reference bit이 된 것을 0으로 clear만하고 빼지 않는다.
      2. handle이 가리키면서 동작한다.
      3. 현재가 가리키고 있는 reference bit이 1이면 0으로 만들고 지나간다. 기회를 주는 것
      4. reference bit이 0인 것을 빼는 방식이다.
      5. 시계처럼 돌아가면서 동작한다.

File System

File
1. 관계가 있는 정보를 모아서 이름을 붙여 놓은 것
2. 파일 내부에 있는 identifier 로 구분한다.
3. Open-file table : 운영체제가 열려있는 파일을 관리하는 법
4. File descriptor table : 각 프로세스를 관리하는 법
Directory
1. 파일이나 디렉토리를 묶어 놓은 것
2. 운영체제 입장에서는 Metadata 로 구분한다.
3. File 이름을 Metadata로 mapping 시켜주는 것이 Directory의 역할이다.
4. Directory는 File의 Metadata를 모아놓고 있는 또 다른 File에 불과하다.
5. attribute를 보여준다. attribute중 하나가 identifier
6. /spell/mail/exp
  1. / : Root directory를 연다.
  2. spell 이라는 file의 identifier를 찾는다.
  3. / : spell 은 directory이므로 또 Root directory를 연다.
  4. mail 이라는 file의 identifier를 찾는다.

'🚦 Server > Operating System' 카테고리의 다른 글

24. File System (0)	2020.06.24
23. Page Replacement (0)	2020.06.24
22. VM Features (0)	2020.06.23
21. Demand Paging and VM Features (0)	2020.06.21
20. Page Tables (0)	2020.06.20