[Interview] Operating System 운영체제

작성일 | In

PCB: 각 process별로 다른 정보를 모아두는 repository

  • process ID
  • process state
  • Program Counter
  • Register value
  • 등

TCB: 각 thread별로 다른 정보를 모아둠

  • TID
  • PC
  • Registers
  • pointer to PCB

Context switch는 현재 돌고 있는 Process/Thread의 정보(State)를 PCB/TCB에 저장하고 바꿀 Process/Thread의 PCB/TCB 정보를 로드하는 과정이기 때문에 저장하는 정보가 적은 Thread의 오버헤드가 훨씬 적다.

Multithreading을 하면 하나의 thread가 I/O에 의해 blocking되었을 때 switching을 해줌으로써 더 높은 throughput을 낼 수 있다(concurrency)

Zombie process: 작업이 끝났지만 parent에 의해 아직 wait()되지 않은 proess
Orphan process: Parent가 wait()을 하기전에 죽어버린 process

  • 주로 init process가 parent로 re-assign되어 wait()해준다.

Scheduler의 종류

  • Long-term Scheduler(Job Scheduler): Disk에 있는 job중 어떤 job을 메모리로 가지고 올지
  • Short-term Scheduler(CPU Scheduler): Memory에 있는 job중 어떤 job에게 CPU를 할당해줄지
  • Mid-term Scheduler: 메모리가 부족할 때 잠시 어떤 job을 Disk로 swapping할지

Scheduling Queue 종류

  • Job queue: set of all processes in the system
  • Ready queue: set of all processes in main memory, ready and waiting to execute
  • Device queue: set of processes waiting for an I/O device

Scheduling 방법

  • Shortest Job first
  • FCFS
    • Convoy effect: 들어온 순서대로 처리되므로 앞쪽에 느린 process가 들어오면서 전체 process의 wait time이 길어지는 현상
  • Priority
  • RoundRobin

Race condition: 어떤 process가 먼저 작업을 마치느냐에 따라 결과가 달라지는 것
Critical section: shared data에 access하는 code
Atomic operation: 외부의 방해없이(switching없이) 끝까지 실행하는 operation

Synchronization 방법

  • Mutex Lock: lock(), unlock() 한번에 하나의 process/thread가 접근가능
  • Semaphore: wait(), signal() 한번에 허용한 갯수의 process/thread가 접근가능
  • Spinlock: busy-waiting - mutex는 thread를 sleep/wake하는 overhead가 있기때문에 잠깐만 기다리는 경우 spinlock이 더 효율적일 수 있다.

Starvation: process의 처리 순서가 밀려 계속 처리되지 못하고 기다리는 현상
Deadlock: 내가 필요한 resource를 다른 process가 가지고 있어 더이상 진행이 불가능한 상황

Deadlock 발생조건

  • 상호배제(Mutual exclusion): 동시에 여러 프로세스가 하나의 자원을 access할 수 없다
  • 점유대기(Hold and wait): 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스이 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야한다
  • 비선점 (No preemption): 다른 프로세스에 할당된 자원은 사용이 끝날때까지 강제로 빼앗을 수 없어야 한다.
  • 순환대기 (Circular Wait): 각 프로세스는 순환적으로 서로가 점유한 자원을 요구해야하낟.

Deadlock 예방법(prevention): 위 4가지 조건을 부정. 하나만 제거해도 됨
Deadlock 회피법(avoidance): 교착 상태가 발생하면 피해나가는 방법
은행원 알고리즘:

  • 알고리즘이 제대로 수행되기 위해서는 3가지가 필요하다
    1. 각 고객이 요구할 수 있는 Maximum 돈
    2. 각 고객이 빌려간 돈이 얼마인지 (Allocated)
    3. 은행이 현재 남아있는 돈이 얼마인지 (Available)
  • 안전 상태: 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해줄 수 있는 안전순서열이 있는 상태
    • 어떠한 프로세스1(P1)에게 남아있는 리소스를 빌려주면 P1이 완료되어 반환된 자원으로 다음 프로세스를 완료시켜 모든 프로세스를 만족시킬 수 있는 것
  • 불안전 상태: 안전순서열이 존재하지 않는 상태 https://jhnyang.tistory.com/102

External Fragmentation: memory가 process가 요구한 만큼 비어있지만 연속되지 않아 사용하지 못하는 경우
Internal Fragmentation: process가 request한 memory보다 더 큰 메모리를 할당받아서 남는 메모리

Paging: Logical memory를 page들로 나누고, physical memory를 page와 같은 사이즈의 frame들로 나눔. Page table을 사용하여 logical address를 physical address로 변환한다.

  • Page number로 page table에서 base physical address를 찾고, 거기에 page offset을 더해 실제 physical address를 구한다

Segmentation: segment(main program/function/object/var 등)별로 저장을 하고 logical address를 <segment # / offset >으로 나누어 segment table에서 segment #로 검색을 하여 limit(length)와 base를 가져온다. segment는 base + offset ~ base + offset + limit에 있음.

Copy-On-Write: 일반적인 fork()는 process를 생성하고, 메모리를 복사하고, exec()을 통해 덮어씌우는데 overhead가 크다. 따라서 새로 process를 만들때, page table만 만들고 같은 page를 가리키다가, 만약 어떤 process가 page를 수정하면 수정하는 process가 page를 다른 곳으로 복사하고 복사된 frame을 수정하고 그 frame을 가리킨다.

Demand Paging: execution 중에 page가 필요하면 load함

Page Replacement Methods\

  • FIFO
  • Optimal Algorithm
  • LRU
    • Counter implementation: Memory access마다 clock을 증가시키고, access된 page의 page table entry의 clock을 업데이트. 가장 작은 값이 LRU page이다.
    • Stack Implementation: Page가 reference되면 stack의 가장 위로 올린다.
  • LRU Approximation
    • Reference Bit Algo: HW가 관리하는 reference bit을 두고 reference되면 1
    • Referene Byte Algo: 위의 reference bit algorthm은 참조된 순서나 횟수는 알 수 없으므로, 8비트짜리 reference byte를 놔두고 주기마다 reference bit을 기록하고 오른쪽으로 shift한다. 최근에 access되면 더 높은 bit가 1이므로 unsgined int기준으로 더 큰 숫자가 된다.
    • Second Chance Algo: 처음에 page의 reference bit들을 1로 세팅하고 fault가 발생하면 victim pointer부터 순회하며 1이면 0으로 바꾸고 0이면 replace.
  • LFU
  • MFU

Thrashing: A process is spending more time swapping pages in and out than executing because process didn’t get enough frames

FCB: information about files
Directory: 각 파일의 FCB를 관리하는 구조로서 파일이름과 FCB를 가리키는 포인터로 이루어짐

Windows FS(File-Allocation Table):

  • 실제 data는 Data Area의 block/cluster에 저장하고 다음 block의 위치는 FAT에서 찾는다.
  • directory에서 첫 block index(a)를 가지고 있고 FAT에서 a번째 index를 접근하면 block a 다음이 있다면 index, 없으면 EOF를 가지고 있다.

Unix FS(i-node):

  • directory가 file name과 pointer를 가지고 있어 i-node(FCB)를 가리키고 있으며, i-node에는 file의 attribute들과 함께 direct block, single indirect, double indirect, triple indrect 포인터들을 가지고 있다.