[Operating System] 운영체제 정리

Operating system: 컴퓨터 하드웨어를 관리하는 소프트웨어

Operating systemd의 목표

• 하드웨어와 소프트웨어의 인터페이스다.
• 편의를 위한 라이브러리를 제공한다.
• 마우스, 키보드 등의 관리를 편하게 해준다.

Process

Process: 실행 중인 프로그램 – 메모리에 올라가서 동작을 하고 있는 것을 말한다. 별도의 고유한 상태를 가지고 있다.

Program: 저장장치에 저장된 실행 파일을 말한다. 메모리에 올려서 실행 가능하게 만들어야 한다. 하나의 program 에는 여러 개의 process 가 존재한다.

 

Job: batch 시스템에서 다루는 일종의 process 라고 말할 수 있다.

Task: 일이 끝나고 기다리고를 반복하지 않고 전체를 조금씩 수행하는 것을 말한다. 하나의 하드웨어를 시간 단위로 공유하는 것을 timesharing 이라고 한다. (각각의 동작하는 단위를 task 라고 부릅니다)

job, task, process 는 프로그램을 바라보는 관점에 따라 다르게 해석한 것 물리적인 의미에서는 모두 같은 뜻을 가진다.

 

Multiprocessing: 여러 개의 cpu 가 있어서 각각이 프로세스를 실행하는 것

Multitasking: timesharing 을 사용하여 각각의 프로세스들이 동시에 실행되는 것처럼 보이게 하는 것 여러 개의 프로세스를 조금씩 수행하는 방식

 

Memory layout: text, data, heap, stac

• text: 프로그램 코드가 저장되는 것을 말한다.
• data: 정적 변수, 전역 변수, 문자열, 상수가 저장되는 것을 말한다.
• heap: 동적으로 생성되는 메모리 공간을 만드는 것을 말한다. Ex> c 언어 -> malloc, 자바 -> new
• stack: 함수의 매개변수, return 값 그리고 지역 변수들이 저장되는 것을 말한다.

stack 은 뒤에서부터 영역을 할당한다. 재귀함수를 잘못 호출하면 stack 에 함수가 계속 저장되어 heap 의 영역을 침범하면 stackoverflow 오류가 발생한다.

process state: New, Running, Waiting, Ready

• New: process 가 생성된 상태
• Running: 실행되고 있는 상태
• Waiting: 어떠한 I/O 나 이벤트를 기다리고 있는 상태
• Ready: 수행할 준비가 되었지만 다른 process 가 실행되고 있어 기다리고 있는 상태
• Terminated: process 가 종료된 상태

Process 는 혼자서 만들어질 수 없다. 모든 process 는 부모 process 가 존재한다.

Process Control Block (PCB) - 프로세스를 관리하기 위해 만든 구조체

Process Scheduling: 다음에 실행할 process 를 고르는 것, 코어에서 실행 가능한 process 를 선택한다.

• I/O bound process: 대부분의 시간을 I/O 을 처리하는 데 사용함 ex) 키보드, 마우스
• cpu bound process: 명령이 실행되면 사용자를 상관하지 않고 일을 처리하는 것 ex) 동영상, 인코딩

Scheduling Queues: process scheduling 을 위한 저장소를 말한다.

• Ready queue: process 의 상태가 ready 인 것들을 저장
• Wait queue: process 의 상태가 wait 인 것들을 저장, 원하는 이벤트가 들어오면 Ready queue 로 이동한다.

Process Lifecycle:

• 생성되자 마자 ready queue 에 저장된다. (new -> ready)
• 선택되어 Ready 에서 running 으로 바뀌는 것 과정 (dispatched)
• cpu 에 공간이 할당되어 process 를 실행한다.
  • I/O 요청이나 새로운 자식 process 가 생성되면 wait queue 로 이동한다. (자발적으로)
  • Interrupt 가 발생하였을 경우는 Ready queue 로 이동한다. (강제적으로) - Process 가 종료되어 PCB 와 자원들을 반납한다.

Context Switch: multitasking 에서 기존의 프로세스에서 다른 프로세스로 이동하는 것을 말한다. 현재 수행 중인 process 의 상태를 저장하고, 수행할 process 의 상태를 가져오는 것을 말한다.

기존의 프로세스: A, 바뀌는 프로세스: B

• A의 PC값 등 프로세스를 다시 시작하기 위해 필요한 값들을 저장한다.
• B 의 저장된 값들을 불러온다.

Context: PC, register 와 같은 프로세스를 다시 시작하기 위해 필요한 값을 말한다. 

Pure overhead: switch 에 필요한 시간이 많아서 자주 일어나게 되면 원래 필요한 시간보다 오래 프로세스를 실행할 수 있다. 따라서 응답성과 처리량의 trade off 가 존재

 

Process Creation:

• process 는 반드시 다른 process 가 생성해줘야 한다. 최초의 process 는 제외
• 각각의 process 는 고유한 아이디를 가진다.
  fork(): process 를 생성한다.
  exec(): 프로세스의 메모리 공간을 새 프로그램으로 대체
  wait(): 자식 process 가 종료되면 부모 process 가 호출하는 함수

Process Termination:

• exit()를 사용하여 실행 종료
• main 함수의 return 으로 인한 실행 종료

위 2 가지의 경우는 모두 process 가 없어지지 않고 상태가 Terminate 로 변한다. Process 를 완전히 없애려면 wait 를 실행해야 한다. 부모 process 에서 wait 실행을 위해 무기한으로 기다려야하는 process 를 zombie process 라고 말한다. (대부분 개발자의 실수로 만들지 않도록 유의해야한다)

Interprocess Communication(IPC): 다수의 process 가 메모리를 공유하기 위한 방법을 말한다.

• shared memory: 특정한 메모리 영역을 2 개의 process 가 접근할 수 있도록 한다. 다른 컴퓨터나 다른 os 에서 실행되고 있다면 사용할 수 없다. (공책을 공유하는 방법)
• message passing: 특정한 영역을 만들어 놓고 모든 process 들이 열람할 수 있는 형태로 메모리를 공유한다. 다른 컴퓨터에서도 메모리 공유가 가능한다. 일반적인 의미의 IPC 를 말한다. (칠판을 공유하는 방법)
  

message passing은 shared memory와는 다르게 여러 개의 process에 동시에 정보를 제공할 수 있다.

Blocking: 메시지 수신에 올때까지 작업을 멈추는 것

Non-Blocking: 메시지를 보낸 후에 작업을 멈추지 않고 계속하는 것

 

🧨  Non-Blocking이 좋을 것 같지만 메시지를 보낸 후 수신 자원이 필요하는 작업이 있을 경우 프로그램이 정상적으로 실행되지 않을 수 있음 따라서 개발할 때 유의하여 코드를 작성해야함.

 

Pipe: 프로세스가 통신할 수 있도록 하는 통로 역할을 말한다.

• Ordinary pipes: 자식 process를 만들면서 연결하는 것, 단방향 연결, 부모-자식 관계가 아니면 사용할 수 없다.
• Named pipes: 별도의 파이프로 존재, 양방향 연결, 부모-자식 관계가 아니어도 사용할 수 있다.

Thread: 같은 process 내에 일정 부분은 공유하고 특정한 내용은 공유하지 않은 단위를 말한다.

• Code, data, files를 공유하고, registers, pc, stack은 공유하지 않는다. Ex) 크롬 창 10개 생성 후 크롬 종료 -> 모든 창이 날라감
• 같은 process 내에 일정 부분은 공유하고 실행 context는 다른 것을 말한다.

Process의 생성은 무겁고, Thread의 생성은 가볍다. 따라서 웹서버에서 Thread를 많이 사용한다. 요청이 들어오면 Thread를 생성해서 요청을 처리하게 하고 다시 요청을 받을 준비를 한다.

Thread의 장점

• 응답 속도가 빠르다.
• Process의 메모리를 공유하므로 공유 메모리나 메시지 전달보다 메모리 공유가 편하다.
• Code, data와 같은 내용을 공유하기 때문에 context switch보다 휠씬 빠르다.

Multicore Programming:

• Concurrency: 하나 이상의 작업 진행을 할 수 있는 것을 의미한다.
• Parallelism: 시스템이 동시에 두 가지 이상의 작업을 수행할 수 있음을 의미한다.

Multicore programming에서는 Parallelism을 사용한다.

• Data parallelism: 큰 데이터를 여러 코어들이 나누어서 관리하는 것 ex) 긴 배열을 더하는 예제
• Task parallelism: process마다 전혀 다른 일을 부여할 수 있는 것

Multicore는 test, debugging 하기에 어렵다.

Multithreading Models:

• Many-to-One: 다수의 user thread와 하나의 kernel thread, 따라서 블로킹 방법을 사용한다.
• One-to-One:  user thread 하나 당 kernel thread 하나를 매칭한다.
• Many-to-Many: 다수의 user thread와 다수의 kernel thread 2개의 개수는 같지 않다.

Thread Pools: 미리 여러 개의 Thread를 생성해 놓고 필요할 때 사용하고 반납하는 형식

OpenMP: 프로그래머가 #pragma omp parallel를 사용하여 병렬처리 부분을 인지할 수 있도록 하는 방식

CPU Scheduling

CPU Scheduling: Timesharing을 사용하여 여러 개의 process가 동시에 일어나는 것처럼 보이게 해주는 multiprogramming의 핵심 알고리즘을 말한다. 최대한 cpu의 활용력을 높이기 위해 사용

• CPU burst: 실제 process가 cpu를 사용하는 시간을 말한다.
• I/O burst: process가 I/O를 위해 기다리는 시간을 말한다.

🧨  process는 CPU burst와 I/O burst를 번걸아가면서 반복한다.

CPU Scheduler: CPU를 사용할 수 있을 때 ready queue에 있는 어떤 process를 선택할 것 인지를 결정하는 것

1. running 상태에서 I/O를 위해 waiting 상태를 이동한 경우
2. Timesharing에 의해 할당된 시간을 전부 사용하여 running 상태에서 ready 상태로 이동한 경우
3. Process의 일이 끝나서 terminated가 된 경우
4. waiting 상태에 있던 것이 어떠한 조건이 만족하여 ready 상태로 이동한 경우

🥈  Nonpreemtive: 한번 process가 cpu를 장악하면 자신이 cpu를 그만 쓰지 않을 때까지 다른 process가 cpu를 사용할 수 없는 것, 다음은 Nonpreemtive에서 cpu를 그만 쓰는 경우

• 스스로 cpu 사용을 하지 않겠다고 할 경우
• 자신에게 할당된 시간을 전부 소모한 경우

🥈  Preemtive: process를 수행하는 중간에도 외부에서 process를 종료할 수 있다. 언제든지 빼앗길 수 있다.

Dispatcher: context switching 수행 간에 process를 재시작하기 위한 자원들을 저장하는 것.

• 빠르게 수행하면 프로그램이 동시에 수행되는 것처럼 보이게 된다.
• 너무 많이 수행하면 실제 프로그램 수행 시간보다 dispatcher를 하는데 사용하는 시간이 더 크다.

Scheduling Criteria:

• CPU utilization: cpu를 최대한 바쁘게 사용했는지
• Throughput: 전체 process가 수행되는데 걸리는 시간
• Turnaround time: 각각의 process들의 실행하는 데 걸리는 평균 시간
• Waiting time: process가 ready queue에서 기다린 시간
• Response time: 요청이 온 후 첫 번째 응답이 생성될 때까지 걸리는 시간

Scheduling Algorithms

< Process: 이름, Burst Time: process를 완료하는데 걸리는 시간 >

First-Come, First-Served (FCFS): 먼저 온 process를 먼저 수행하는 것을 말한다.

• Convoy effect: 완료시간이 긴 process를 먼저 수행하게 되면 다른 process들의 wait time이 증가한다.

Shortest-Job-First (SJF): 수행 시간이 작은 process를 먼저 수행하는 것을 말한다.

• Burst time을 정확하게 알 수 있는 방법이 없기 때문에 사용할 수 없다.
• Burst time을 예측하여 사용한다.

Shortest Remaining Time First: SJF의 Preemptive 버전

• 새로운 process가 도착하면 일단 process를 멈추고, 기존 process 남은 시간을 비교해서 바꾼다.

Round Robin (RR):  FCFS의 preemptive와 time slice를 사용한 버전, 들어온 순서대로 실행

• 하나의 process는 한 번에 일정 시간 이상을 수행할 수 없다.

Priority Scheduling: priority를 할당하여 priority가 높은 순으로 process를 실행

• Burst time을 priority로 두면 SJF와 동일하게 동작한다.

🥈 Starvation: process가 실행되지 않고 무한 대기하는 경우

• process의 priority가 낮게 생성되었는데 후에 들어오는 process의 priority가 계속 더 높은 경우

🥈 Aging: starvation의 해결책

• 일정 시간이 지나면 priority를 계속 높여주는 방법

Synchronization

Race Condition: 여러 process가 동일한 데이터에 동시에 접근하여 결괏값이 특정한 순서에 의존하는 것을 말한다.

Synchronization: 한 번에 하나의 process가 shared data를 조작하는 것을 말한다. Race Condition의 해결방법이다.

🥈 Critical Section: process가 shared data를 조작하는 코드 영역을 말한다.

🥈 Critical Section Problem:

• Mutual exclusion: 어떤 process가 critical section을 사용 중이라면 다른 process는 critical section을 사용할 수 없다.
• Progress: critical section에 진입하려는 process가 존재하는 경우 process는 critical section에 들어와야 한다. (deadlock)
• Bounded waiting: process는 일정한 시간 또는 정해진 순서 안에 critical section에 입장해야 한다. (starvation)

Peterson’s Solution: critical section을 구현하는 방법

• turn: process가 critical section에 들어왔는지 확인하는 변수
• flag: process가 critical section에 들어올 준비가 됐는지 확인하는 변수

Out-of-order Execution: Instruction 수행 순서를 CPU에서 내부적으로 변경

• 준비된 Instruction을 먼저 수행하여, 전체 Program의 실행 시간을 단축
• 순서를 바꾸어도 문제가 없는지를 판단하는 복잡한 Logic이 필요

Memory Barrier: 명령어를 교환할 수 없는 선을 만드는 것 (Out-of-order Execution을 사용할 수 없도록 만듬)

🥈 Mutex: 특정 thread 단독으로 critical section에 들어갈 수 있도록 사용되는 동기화 기법입니다. (소프트웨어 레벨에서 해결)

• critical section에 하나의 thread 밖에 사용하지 못한다는 단점이 있다.

Semaphores: 여러 개의 thread가 resource를 사용할 수 있도록 해줍니다. (mutex의 단점을 보안) 여러 개의 resource를 사용할 때 race condition을 조정해주는 것을 말합니다.

Deadlock

Deadlock: 모든 thread가 명령을 수행을 위해 무기한 기다리는 상황을 말한다. (어떠한 thread도 실행될 수 없다)

🥇  Necessary conditions for deadlock: deadlock이 발생할 수 있는 조건 (모두 만족해야 한다)

• Mutual exclusion: 한 번에 하나의 thread가 resource를 사용할 수 있다.
• Hold and wait: 한번 thread가 resource를 잡으면 일을 끝날 때까지 다른 thread가 접근할 수 없다.
• Circular wait: 서로가 서로의 resource를 필요로 하는 상황을 말한다.

Resource-Allocation Graph: T -> R은 요청 그래프, R -> T는 할당 그래프

• cycle이 존재하지 않으면 deadlock이 발생하지 않음
• cycle이 존재하고, cycle 과정에서 resource가 1개인 것이 있다면 deadlock이 발생함

Deadlock Prevention: deadlock이 발생하지 않게 원천봉쇄를 한다.

• Mutual exclusion: race condition 문제 때문에 사용할 수 없다.
• Hold and wait: starvation 문제 때문에 사용하기 어렵다.
• No preemption: mutex locks과 semaphores 또한 빼앗길 수 있기 때문에 사용할 수 없다.
• Circular wait: resource에 우선순위를 만들어서 해결한다.

Deadlock Avoidance: deadlock이 발생하지 않도록 관리해준다.

• thread가 일을 수행하는데 필요한 최대의 resource의 개수를 알아야한다.
• safe, unsafe 상태를 나누어서 관리한다. safe일 경우에 resource를 할당한다.

Banker’s Algorithm: 여러 종류의 resource를 모두 고려하는 알고리즘

• allocation: 할당된 resource의 개수
• need: 남아있는 resource의 개수
• notation: X 요청하는 resource의 개수, Y 남아있는 resource의 개수
• X = (0, 3, 2, 1) and Y = (1, 1, 3, 2), then not X ≤ Y | False
• X = (0, 3, 2, 1) and Y = (1, 7, 3, 2), then X ≤ Y | True

Deadlock Detection: deadlock을 허용하고 발생하면 해결하는 방법

Wait-for Graph: Thread로만 관계를 표현한다.

Deadlock Recovery:

• 연관된 process를 모두 종료시킨다.
• Deadlock이 없어질 때까지 process를 1개씩 종료시킨다.

multiprogramming: 여러 개의 프로그램을 동시에 수행하는 것, 동시에 수행하기 위해서는 메모리에 프로그램들이 존재 해야하기 떄문에 VA와 PA로 나누어서 메모리를 저장하게 됨, 프로그램을 수행하는데 해당 프로그램이 끝나지 않아도 다른 프로그램을 실행할 수 있는 것

memory protection: base와 limit 값을 확인하여 다른 process의 memory 접근을 막아주는 것

logical address: 프로그래머가 생각하는 주소

physical address: 실제 주소

MMU: logical address를 physical address로 바꿔주는 것

• address translation: logical address를 physical address로 계산하는 것

hole: process를 종료하는 과정에서 생긴 memory 여유 공간

• first-fit: process가 할당될 수 있는 가장 첫번째 hole에 할당한다.
• beat-fit: process가 할당될 수 있는 가장 작은 hole에 할당한다.
• worst-fit: process가 할당될 수 있는 가장 큰 hole에 할당한다.

external fragmentation: 전체 영역은 충분하지만 연속적인 영역이 충분하지 않은 것

• compaction: 흩어져 있는 영역을 하나의 영역으로 합치는 것

internal fragmentation: 할당된 frame 중에 사용되지 않는 공간이 발생하는 현상

• frame의 크기를 줄이는 것으로 해결할 수 있지만 page table이 커져서 사용하지 않는다.

paging: process의 memory를 연속적으로 할당하는 것이 아니라 일정 크기로 나누어서 할당하는 것

• page: logical address를 나누는 것, 프로그래머의 관점으로 볼 때
• frame: physical address를 나누는 것, physical address의 관점으로 볼 때

page table: logical address에 따른 physical address정보를 가지는 테이블

• process 마다 하나씩 가지고 있어야한다.
• offset: 상대적인 위치를 나타낸다. 따라서 address translation에 참여하지 않는다.

address binding:

• compile time: 컴파일 단계에서 address binding 실행
• load time: 프로그램이 시작할 때 address binding 실행
• execution time: 프로세스가 시작할 때 address binding 실행

page-table base register: page table의 시작 주소를 가르키는 것, context switching을 할 때 PTBR 값이 바뀐다.

TLB: Page Table 접근 시간을 줄이기 위해서 자주 사용되는 정보를 속도가 빠른 저장장치에 보관하는 방법

TLB는 page table과는 다르게 모든 PA 대해서 저장하는게 아니기 때문에 PA 중에 무엇을 사용하는지 모르기 때문에 VA을 따로 저장한다.

• page table은 모든 page에 대한 정보를 가지고 있기 때문에 frame number만 저장하고, TLB는 소수의 정보만을 저장하기 때문에 page number와 frame number를 저장한다는 것에서 차이가 있다.

demand paging: 필요한 page만 memory에 할당하는 것, valid config를 넣어준다.

Page Fault: 접근하려는 위치의 page가 memory에 없는 경우에 발생합니다. address translation을 할 때 page가 memory에 없는 것

page fault handling:

1. page table에서 값이 있는 지 확인한다.
2. page fault가 발생한다. os가 page fault를 처리한다.
3. storage를 확인하여 memory에 page 정보를 넣는다.
4. page table에서 valid 값을 갱신한다.
5. page fault 떄문에 중단된 명령어를 다시 실행한다.

Page Swap: memory에서 page를 제거하고, 이를 storage에 저장하는 것을 말합니다. 이미 page swap을 통해 storage에 저장된 page가 다시 필요하게 된다면 다시 생성하는 것이 아니라 storage에서 가지고 옵니다. (처음은 생성해주고, 처음이 아니라면 storage에서 가지고 온다 page swap의 일련의 과정을 Demand Paging 기법이라고 한다)

copy-on-write: 부모와 자식 process가 write를 하기 전까지 동일한 page를 공유하는 것

thrashing: process를 실행보다 page fault를 처리하는데 더 많은 시간을 소요하는 것을 말한다.

• cpu는 utilization이 떨어질 때 새로운 process를 추가하려고 하기 때문에 발생한다.
• 해결 방법으로는 working set을 활용하는 방법이 있습니다.
• working set이란
  • 임의의 시점에서 참조한 page의 집합을 말합니다.
  • program이 원활하게 실행되기 위해 필요한 page의 개수를 말합니다.

🧨 2021년 2학기 임베디드 시스템 수업 내용을 정리한 것입니다.