[운영체제] 2장. CPU 관리

해당 게시물은 조진성 교수님의 '운영체제' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 2장. CPU 관리

2-1. Processes
2-2. Threads & Concurrency
2-3. CPU Scheduling
2-4. Synchronization Tools
2-5. Synchronization Examples
2-6. Deadlocks

---

📌 2-1. Processes

* Program
- Executable file on a disk
- Loaded into memory and executed by the kernel

* Process
- Executing instance of a program
- The basic unit of execution and scheduling
- A process is named using its process ID (PID)

* Scheduling
- process의 실행 순서를 결정하는 작업

* job = task(IBM, RTOS) = process(unix)

* Process Address Space
- Stack : dynamically allocated memory <- SP
- Heap : dynamically allocated memory
- Static Data : data segment
- Code : text secment <- PC

* 모든 process의 제일 밑 주소는 0x00000000

* Process State
- State diagram
new -> ready : admitted
ready -> running : scheduler dispatch
running -> ready : interrupt
running -> waiting : I/O or event wait
waiting -> ready : I/O or event completion
running -> terminated : exit

- wait는 더이상 자발적으로 수행할 수 없는 상태
- ready는 자발적으로 수행할 수 있지만 다른 애가 실행중이기 때문에 기다리는 상태
- scheduling : ready 상태의 process 중에 하나를 고르는 것
- dispatch : 고른 process를 cpu에 올리는 것
- scheduler : 위의 두 작업을 수행하는 주체(운영체제 내부)

* Process State Transition

- Windows-작업관리자, Linux-PS

* Process Control Block (PCB)

- process와 관련된 모든 정보를 담고 있는 구조체

- task_struct : Linux의 PCB

* Context Switch (CPU Switch)

- process1이 수행되다가 interrupt 또는 system call에 의해 OS가 실행되고 다른 process2가 dispatch 되면서 CPU의 Context가 바뀌는 것.

- interrupt나 system call 발생시 CPU의 register 내부 값(process1 정보들)을 PCB에 저장해놓는다.

* Administrative overhead

- Context Swicth 수행 시 수수료
- Saving and Loading registers and memory maps
- Flushing and Reloading the memory cache
- Undating various table and lists, etc.

* Schedulers
- Long-term scheduler (or job scheduler) : 실행 요청이 들어온 processes 중 어떤 것들(여러개의 process)을 main memory에 올릴지(실행할지) 결정한다.
- Short-term scheduler (or CPU scheduler) : 실행중인 processes 중 어떤 것을 CPU에 올릴지 결정한다.
- Medium-term scheduler (or swapper) : 실행중인 processes 중 어떤 것을 File System으로 다시 내려보낼지 결정한다.

* Virtual Memory Management

- Long-term과 mid-term이 사라졌다. (모든 process가 실행 요청 시 Main Memory에 올라가기 때문)

* Idle Process

- 항상 ready 상태인 무한 루프 도는 No Operation Process

- Running할 Process가 없을  때 수행된다.

* Operation on Processes in Unix/Linx
- Process creation : fork()
- Process execution : exec()
- Process termination : exit(), _exit(), abort(), wait()
- Cooperating processes : Inter-Process Communication (IPC)

* int fork()

- 자기 자신과 똑같은 Process를 생성한다.

- Parent가 해놓은 작업을 Child가 그대로 받아서 계속 수행할 수 있는 장점이 있다.
- Create and initialize a new PCB
- Create and initialize a new address space
- Initializes the address space with a copy of the entire contents of the address space of the parent 
- Initializes the kernel resources to point to the resources used by parent (e.g., open files)
- Places the PCB on the ready queue.
- Returns the child's PID to the parent, and zero to the child

* int exec(char *prog, char * argv[])

- Process를 실행시키는 System call
- Stops the current process
- Loads the program "prog" into the process' address space
- Initializes hardware context and args for the new program
- Places the PCB on the ready queue
- 실행 성공시 return은 없고 실패시 return값이 있다.

* A Process Tree in Linux

- 모든 process는 parent-child 관계를 갖는다.

- windows에는 이런 관계가 없다. Linux의 이 모든 것은 fork()라는 시스템 때문이다.

* BOOL CreateProcess(char *prog, char *args, ...)
- Creates and initializes a new PCB
- Creates and initializes a new address space
- Loads the program specified by "prog" into the address space
- Copies "args" into memory allodcated in address space
- Initializes the hardware context to start execution at main
- Places the PCB on the ready queue

* Windows

- Windows는 thread를 사용한다.

- thread라는 시스템이 이미 나온 상태에서 만들어진 운영체제이기 때문에 fork 시스템이 필요없다.
- Unix/Linux 서버 프로그램에서는 사용자 connection이 들어오면 fork를 통해서 새로운 child process를 통해 명령을 수행한다.

 

* Unix/Linux Bash Process로부터 시작.
* Windows는 탐색기로부터 시작.

* Process Termination
- Normal termination : return from main() - calling exit(), calling _exit()
- Abnormal termination : calling abort() - terminated by a signal
- Wait for termination of a child process : calling wait(), If no parent waiting (did not invoke wait()), process is a zombie,
parent process가 수행중인데 child process가 종료되면 child process가 zombie가 된다.

* Inter-Process Communication (IPC) : Process 간 데이터를 주고 받는 것
- Communication models : message passing vs. shared memory
- Cooperating processes : Bounded buffer problem (Producer-Consumer problem) - shared memory
- Unix/Linux IPC : pipes, FIFOs, message queue, shared memory, sockets

* Client-Server Communication
- Sockets
- Remote Procedure Call (RPC in C/C++)
- Remote Method Invocation (RMI in Java)
- Marshalling parameters

---

📌 2-2. Threads & Concurrency

* Process : Heavy-weight
- A process includes many things
- Creating a new process is costly because all of the data structures must be allocated and initialized
- Inter-process communication is costly, since it must usually go through the OS

* Tread Concept (Key Idea)

- 그동안 실행 패스를 하나 더 만들기 위해서 프로세스를 만들었는데 결국 실행 패스만 더 만들면 된다라는 개념

- Separate the concept of a process from its execution state
- Process : address space, resources. other general process attributes (e.g., privileges)
- Execution state : PC, SP, registers, etc.
- This execution state is usually called : a thread of control, a thread, a lightweight process (LWP)

* 메모리 공간에서 여러개의 thread들이 code, data, heap을 공유하지만 각 thread 마다 stack을 갖고 있다.

* Concurrent Servers

- Multiprocess->Multithread
- Windows에서는 Multithread 모델만 가능하게 했다.

* Multicore Programming
- Single-Core system : Concurrent execution
- Multicore system : Parallel execution

* Data vs. Task parallelism
- Data Parallelism : 처리해야할 Data의 양이 아주 많을 때 ex. Deep Learning
- Task Parallelism

* Parallel Programming
- Pthreads (POSIX threads) : thread를 여러개 만드는 system call Task Parallelism
- OpenMP (Open Multi-Processing) : Data Parallelism
- Open MPI (Message Passing Interface) : Data Parallelism
- SIMD (Single Instruction Multiple Data) : Data Parallelism
- GPGPU (General Purpose computing on GPUs) - CUDA, OpenCL : 요즘 가장 많이 쓰인다. Data Parallelism

* Multithreading Models

- user thread와 kernel thread의 매칭 모델
- Many-to-One : 요즘은 거의 없다.
- One-to-One : Windows
- Many-to-Many : Solaris
- Two-Level : Many-to-Many + One-to-One

* POSIX (Portable Operating System Interface) : UNIX의 표준
- pthread_create 등등 p를 앞에 붙여서 표준이라는 표시를 한다.

* Threads Design Space- One thread, One process : MS/DOS
- One thread, Many processes : older UNIXes
- Many threads, One process : Java
- Many threads, Many processes : Mach, NT, Chorus, Linux, ...

---

📌 2-3. CPU Scheduling

* Process Execution
- CPU burst & I/O burst
- CPU-bound process : Long CPU burst
- I/O-bound process : Short CPU burst

* Dispatcher
- Dispatch
- Dispatch latency
- Scheduling vs. Dispatch

* Preemptive vs. Non-preemptive
- Preemptive scheduling : 다른 프로세스를 중단시키고 프로세스를 실행시킨다. (일반적)
- Non-preemptive scheduling : 다른 프로세스가 끝나기를 기다리고 프로세스를 실행시킨다.

* Schedulilng Criteria
- CPU utilization : Total burst time / Total time taken (max)
- Throughput : 단위 시간당 처리의 양 (max)
- Turnaround time : 실행부터 끝날때까지 시간 (min)
- Waiting time : ready 상태에서 기다린 시간 (min)
- Response time : 요청한 작업에 대한 응답이 오는 시간 (min)

* Scheduling Non-goals
- Starvation

* Scheduling Algorithms
- FCFS (First Come First Served) : 모든 scheduling algorithms에서 고려하는 알고리즘이다. 가장 공정하다. non-preemptive scheduling이다. waiting time 문제가 있다.
- SJF (Shortest Job First) non-preemptive
- SRTF (Shortest Remaining Time First) preemptive
- Priority
- Round Robin (RR)
- Multi-Level Queue
- Multi-Level Feedback Queue (MLFQ)

* FCFS Scheduling (FIFO)
- First-Com, First-Served
- Non-preemptive
- 장점 : 공정하고 굶어죽지 않는다.
- 단점 : waiting time이 커진다. = Convoy effect

* SJF Scheduling
- Shortest Job First
- Non-preemptive
- 장점 : average waiting time을 최소화 한다. waiting time 측면에서 optimal하다. (Best와는 다름)
- 단점 : CPU burst의 크기를 예측할 수 없다. 따라서 SJF와 SRTF는 컴퓨터에 적용이 안된다.

* SRTF Scheduling
- Shortest Remaining Time First
- Preemmptive SJF

* Priority Scheduling
- A priority number is associated with each process
- 장점 : CPU burst의 크기를 예측할 수 있다.
- 단점 : Starvation or Indefinite blocking
- 해결 : Aging = process가 기다린 만큼 priority값을 증가시킨다.

* Round Robin (RR) Scheduling
- Priority + Round Robin : 대부분 OS가 사용하는 Scheduling Algorithm이다.
- Priority 기반이고 priority가 같으면 Round Robin으로 돌아가면서 순서대로.
- Time quantum and Context switch time : waiting time vs. context switch overhead, Time Quantum의 크기를 어떻게 할 것인가. 크게하면 FCFS와 다를 게 없고(Convoy effect) 작게하면 Overhead가 커진다.
- A rule of thumb : 80% of the CPU burst

* Multilevel Queue Scheduling
- Ready : forground (interactive) / background (batch)
- foreground - RR / background - FCFS
- Fixed priority scheduling
- Time slice

* Priority
- System processes (Highest)
- Interactive processes
- Interactive editing processes
- Batch processes
- Student processes (Lowest)

* Multilevel Feedback Queue

- I/O bound process 인지 CPU bound process인지 알 수 없으니 Time quantum을 얼마나 사용했는지 확인하고 우선순위를 옮긴다.

* Multiple-Processor Scheduling
- Symmetric multiprocessing vs. Asymmetric multiprocessing
- Load balancing : Push vs. Pull migration
- Processor affinity : Soft vs. Hard affinity, 캐시메모리 성능때문에 존재하는 문제.

* Real-Time Scheduling
- Static priority scheduling : process 우선순위가 바뀌지 않는다. Rate-Monotonic algorithm. 단점, Deadline Miss 발생
- Dynamic priority scheduling : 실행 중에 우선순위가 바뀐다. EDF (Earliest Deadline First) algorithm. 데드라인이 얼마나 남았느냐에 따라서 프로세스의 우선순위를 바꾼다. 단점, Overhead가 크다. 이론적으론 optimal이지만 overhead가 커서 실제 운영체제에서는 사용하지 않고 있다.

* Operating System Examples
- Linux scheduling :
Real-time 클래스의 프로세스들은 Fixed priority Scheduling을 수행
Normal 클래스의 프로세스들은 CFS (Completely Fair Scheduling) 알고리즘 사용한다. (프로세스 별로 vruntime 변수를 비교해 우선순위 관리)
priority 0 ~ 99 Real-Time (higher), priority 100 ~ 139 Normal (lower), time quantum을 다 쓰면 priority가 낮아진다. Nice Value.
- Windows scheduling :
real-time / high / above normal / normal / below normal / idle priority windows는 priority 값이 클수록 중요하다. priority-RR을 수행한다.
- Solaris scheduling :
priority-RR을 수행한다. 개발 회사에서 closed 환경으로 개선중이다.

* Algorithm Evaluation
- Deterministic modeling
- Queueing models
- Simulation : Trace tape (or trace data) - real world input & data 실제환경과 비슷
- Implementation : 가장 좋은 방법이지만 시간이 오래걸림

* Emulation

- Simulation과는 다르게 실제환경과 똑같이 실행한다.

---

📌 2-4. Synchronization Tools

* Synchronization
- Threads cooperate in multithreaded programs
- For correctness, we have to control this cooperation

* Synchronization Problem
- race condition : Shared Data를 보호하지 않는다.
- Critical section problem, 똑같은 말.

* Process model - massage passing

* Multithread model - shared memory

* Requirements for Synchronization Tools
- Mutual Exclusion : 한 번에 하나의 프로세스만 사용한다. = mutually exclusive access
- Progress : 아무도 안쓰고 있으면 바로 사용해야 한다.
- Bounded Waiting : 누가 쓰고 있으면 기다려야한다.

* Synchronization Tools
- Locks (spin lock) - (low level mechanism) - busy wait
- Shared memory를 현재 쓰고 있는 동안 Lock을 한다.
- critical section : shared data를 사용하는 code segment
- critical section 앞에서 lock을 걸고 뒤에서 unlock을 한다.
- Mutex lock (blocked lock) : mutual exclusion - (high level mechanism)
- Semaphores - (high level mechanism)
- Monitors - (high level mechanism)
- Messages (in distributed systems) - (high level mechanism)

* 현재 운영체제가 lock을 구현하는 방법이 두 가지다.
- Hardware atomic instructions : cpu가 두 개 이상일 때 사용하는 방법.
- TestAndSet : 현재있는 값을 1로 저장하고 리턴한다.
- CompareAndSwap : 두 개의 변수를 바꾼다. = intel(x86)
- Disable/re-enable interrupts : 운영체제가 High level mechanism의 프로세스에서 짧은 구간에만 사용한다. cpu가 한 개일 때만 사용하는 방법.

* Semaphores

- shared data의 개수. 두 개의 operation만 가능.
- wait or P : Decrement
- signal or V : Increment
- Binary Semaphore : 0 또는 1, critical section을 보호. / Counting Semaphore : integer 변수
- 구조체
typedef struct {
int value;
struct process *L;
} semaphore;

* Monitors

- mutual exclusion이 되도록 programming language에서 지원하는 방안. java에서만 지원하는 방법이다.

* Mutex Lock

- binary Semaphore와 같다.

* Deadlock

- lock이 안풀리는 상황

* Starvation

- 앞에서만 계속 service해서 영원히 service 안되는 상황, indefinite blocking.

---

📌 2-5. Synchronization Examples

* Bounded-Buffer Problem
- shared data 보호 문제, busy waiting 문제
- Producer (in) <-> Consumer (out)
- busy waiting을 해결하기 위해 Semaphore(Binary, Counting) 구현 (mutex, empty, full)
- MutexLock과 Condition Variable을 사용해서 구현할 수도 있다.
- Readers and Writers Problem
- critical section에서 write 중일 때는 다른 thread에서 read & write 둘다 불가능한데 read 중일 때는 read는 가능하다.
- lock unlock 구현
- semaphore 구현

* Dining-Philosophers Problem
- chopstick = shared data => binary semaphore로 구현
- deadlock 문제 : 특정 타이밍에 발생한다.
- deadlock을 해결하기 위해 chopstick 두 개를 동시에 들고 동시에 내려놓도록 구현한다. chopstick 별로 semaphore를 만들지 말고 철학자 별로 semaphore를 만든다.
- Deadlock-free version : starvation이 발생할 수 있다.
- 해결 : age 변수를 만들면 된다.
- monitor와 condition variable을 이용해서 구현하는 방법도 있다.

---

📌 2-6. Deadlocks

* Deadlock Problems
- 서로 waiting 상태에서 영원히 깨어나지 못한다.

* Deadlock Characterization

- deadlock에 빠지면 아래 네 가지는 무조건 참이다.
- Mutual exclusion
- Hold and wait
- No preemption : resource를 한 번 잡으면 내려놓지 않는다.
- Circular wait

* Handling Deadlocks
- Deadlock prevention : deadlock이 일어날 가능성을 원천 봉쇄한다. (개발자)
- Deadlock avoidance : 알고리즘 (운영체제)
- Deadlock detection and recovery : 알고리즘 (운영체제)
- Deadlock ignorance : 현재 운영체제는 deadlock 관련하여 아무 행동도 하지 않는다. 발생 확률도 크지 않을 뿐더러 overhead가 크기 때문이다. 따라서 개발자가 deadlock prevention을 해야한다.

* deadlock prevention
- Hold and wait 없이 알고리즘을 만든다. (젓가락을 두 개를 동시에 들고 동시에 내려놓도록 구현한다.)
- No preemption이 없도록 구현하는 방법은 어렵다.
- Mutual exclusion과 Circular wait은 없앨 수 없다.

---