운영체제: 한번에 정리하기

Operating System

운영체제는 하드웨어를 관리하고, 응용 프로그램과 하드웨어 사이의 인터페이스 역할을 한다. 또한 프로그램이 시스템 자원에 접근하고자 할 때 권한을 가지고 있는지를 파악한다.

 

프로세스와 스레드

프로세스 : 현재 메모리 상에 있으며 실행 중인 프로그램을 의미한다.

스레드 : 하나의 프로세스의 자원을 공유하며 독립적으로 실행될 수 있는 작업 단위이다.

 

프로세스는 프로세스 별로 메모리 공간을 할당받으면Code, Data, Heap, Stack으로 구분 된다.

• Code : 함수, 제어문, 상수 등을 할당하는 영역.

• Data : Global Variable, Static Variable, Array가 할당되는 영역.

• Heap : 동적 할당된 변수가 할당되는 영역.

• Stack : Local Variable, Parameter, Retrun value와 같은 임시로 사용되는 값이 할당됨

이와 달리 스레드는 Stack만 할당받고, 나머지 부분은 프로세스와 공유한다.

---

 

멀티 프로세스와 멀티 스레드

멀티 프로세스, 스레드는 동시에 여러 기능을 실행하는 것은 같다. 하지만 두 방식은 차이점을 가지고 있다.

 

멀티 프로세스 : 동시에 여러 기능을 실행하기 위해, 부모 프로세스가 자식 프로세스를 생성하여 `IPC(Inter Process Communication)`를 통해, 작업 과정을 공유할 수 있다.

멀티 스레드 : 하나의 프로세스에서 여러 개의 스레드를 생성해 동시에 여러 기능을 실행할 수 있다.

 

멀티 프로세스와 멀티 스레드의 차이

프로세스 별로 `PCB(Process Control Block)`을 가지고 있다. 따라서 사용 중인 CPU를 다른 프로세스가 사용하기 위해서는 현재 PCB의 상태를 저장하고, 다음에 작업하기 위한 프로세스를 가져오기 위한 `Context Switching`이 필요하다.

 

이와 달리 스레드의 경우 Stack을 제외한 프로세스의 모든 메모리 영역을 공유하기 때문에, 해당 프로세스의 접근을 하기 위해 PCB 상태를 저장하고 불러오는 일련의 과정(Context Switching)이 필요 없다.

 

따라서 멀티 스레드의 경우 공유 자원에 여러 스레드가 동시에 접근할 경우 데이터를 손실시킬 수 있는 `Race Condition`이 발생한다. 따라서 이를 해결하기 위해 임계 구역(Critical Section)을 지정하여, 해당 문제를 방지할 수 있다.

 

IPC

앞서 다룬 내용으로 알 수 있듯이, 프로세스는 스레드와 달리 상호 독립적이다. 따라서 프로세스 별로 자원을 공유하기 위해서는 통신 과정이 필요하며, 이를 `IPC(Inter Process Communication)`라고 부른다.

 

• Anonymous pipe

  • 부모-자식 프로세스 관계처럼 프로세스를 명확히 알 수 있는 경우에 사용하는 방식이다.

  • 하나의 프로세스는 쓰기, 하나의 프로세스는 읽기만 가능하므로 반이중 통신이라고 한다.

  • 만약 두 프로세스 모두 읽기/쓰기가 가능하려면 2개의 파이프를 연결하여야 한다.

• Named pipe

  • Anonymous piple와 달리, 부모-자식 프로세스 관계가 아닌 다른 프로세스와 통신을 하고자 할 때 사용하며 나머지는 동일하다.

• Message Queue

  • 입출력 방식은 pipe와 유사하지만, 메모리 공간이라는 차이점이 있다.

• Shared Memory

  • 앞의 방식들과 같이, 데이터 자체를 공유하는 방식이다.

  • 프로세스 별 공유 메모리 영역을 지정하여, 해당 영역을 액세스함으로써 빠르게 동작한다.

  • 스레드와 마찬가지로 Critical Section에 대한 예외들을 처리해 주어야 한다.

• Memory map

  • 공유하 고자는 매체가 파일일 경우에 사용하는 방식이다.

• Socket

  • 클라이언트 서버가 소켓을 통해서 통신하는 구조이다.

  • 원격에서 프로세스 간 데이터 공유를 하고자 할 때 사용한다.

 

DeadLock

멀티 스레드 또는 공유 메모리(Shared memory)와 같이 공유 자원에 접근하는 데 있어, 데드락이 발생할 수 있다. 데드락은 특정 조건으로 인해, 모두 공유 자원에 접근할 수 없어 작업이 진행되지 않는 상황을 말한다.

 

• Mutual exclusion

  • 한 번에 하나의 프로세스만 공유 자원을 사용할 수 있다.

• Hold and Wait

  • 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 있는 자원을 점유하기 위해 대기하는 프로세스가 있다.

• Non-Preemptive

  • 다른 프로세스에 할당된 자원의 사용이 끝날 때까지 강제로 선점할 수 없다.

• Circular wait

  • 프로세스들 중에서 순환 형태로 자원을 대기하고 있어야 한다.

 

위의 조건을 모두 만족한다면, 프로세스들은 데드락에 빠지게 된다. 데드락을 발생시키지 않기 위해서는 Prevention, Avoidance, Detection, Recovery와 같은 방식을 통해 해결할 수 있다.

• Prevention

  • 데드락을 발생시키는 4가지의 조건이 발생하지 않도록 사전에 방지하는 것이다.

    • 모든 조건을 부정함으로써 사전에 방지할 수 있다.

• Avoidance

  • 교착 상태가 발생하면, 이를 회피하는 방법이다.

  • Banker's Algorithm

    • 프로세스가 자원 할당을 요구할 때, 데드락이 발생하지 않는 안전상태인지 확인한 후 자원을 할당한다.

    • 안전상태가 아니라면, 안전 상태가 될 때까지 대기하였다가 자원을 할당하여 데드락을 회피한다.

• Detection

  • 자원 할당 그래프를 통해 교착 상태를 탐지한다.

  • 자원 요청이 발생하면, 탐지 과정을 거쳐야 하므로 이에 대한 오버헤드가 있다.

• Recovery

  • 데드락을 발생시킨 프로세스를 종료하거나, 할당된 자원을 선점하여 복구시키는 방법이다.

  • 데드락을 해결하기 위해 모든 프로세스를 종료하거나, 데드락이 해소될 때까지 프로세스를 종료하는 방식으로 나뉜다.

  • 자원 선점을 통한 복구 방법은 공유 자원을 선점하여, 우선순위에 따라 재할당한다.

---

CPU Scheduling

 특정 프로세스에만 CPU가 할당되지 않고, 프로세스 별로 균등하게 CPU를 할당하기 위해 필요하다. 적절한 CPU 스케줄링은 스케줄링을 작업을 위한 CPU 사용률을 줄여, 프로세스가 사용할 수 있는 CPU 사용률을 늘이고 기아 현상을 줄이는 것이다. 따라서, CPU 스케줄링의 효율성을 판단하기 위해서는 `Response Time`: 작업이 실행되기까지 걸린 시간., `Turnaround Time`: 작업이 완료되는데 까지, 실행 시간, 대기 시간을 합산한 시간. 을 통해 판단한다.

 

Preemptive / Non-preemptive

 CPU 스케줄링 방식은 크게 2가지로 나뉜다. 첫 번째는 특정 프로세스가 CPU를 사용할 수 있음에도 필요에 따라 강제로 사용 권한을 박탈하는 선점(Preemptive) 방식이다. 두 번째는 특정 프로레스가 자체적으로 CPU 자원을 반납하여야 다른 프로세스가 CPU를 점유할 수 있는 비선점(Non-preemptive) 방식이다.

 

Preemptive Scheduling

• FCFS(First Come First Served)

  • 큐에 도착한 순서대로 CPU를 할당하는 방식이다.

  • 앞의 처리하고자 하는 작업의 실행시간이 길다면, 뒤의 작업들의 평균 대기 시간이 길어진다.

• SJF (Shortest Job First)

  • 수행 시간이 가장 짧다고 판단되는 작업부터 우선적으로 CPU를 할당한다.

  • FSFS 보다는 평균 대기시간이 짧지만, 현실적으로 해당 방식은 불가능하다.

    • 어떤 작업이 짧게 끝날지 판단할 수 없기 때문이다.

       

Non-preemptive Scheduling

• Priority

  • 우선순위를 부여하여, 우선 순위가 높은 것을 먼저 처리하는 방식이다.

  • 우선 순위가 낮은 프로세스는 Starvation에 빠질 수 있다.

    • 이를 해결하기 위해 Wating이 길어지면, 우선 순위를 높이는 Aging을 사용한다.

• RR (Round Robin)

  • 모든 프로세스가 동일한 작업시간(Time Slice)을 사용하는 방식이다.

  • 할당 시간이 크면 FCFS와 같으며, 할당 시간이 짧다면 빈번한 Context Switching이 발생하여 성능 저하가 될 수 있다.

• Multi-level Queue

  • 프로세스에 따라 우선순위가 다른 큐에 배치하는 방식이다.

  • 큐들은 우선순위에 따라 서로 다른 Time Slice를 가지며, 우선순위가 높을수록 할당되는 Time Slice의 크기가 크다.

---

 

Paging

연속 메모리 할당을 통해 메모리 단편화(외부 단편화)가 발생하며, 반복될 경우 메모리의 사용의 효율성을 저해한다. 따라서 프로세스를 연속적인 공간에 할당하지 않고, 프로세스를 작은 크기로 나눠 여러 부분에 할당함으로써, 연속 메모리 할당 문제를 해결하고자 하는 것을 페이징(Paging)이라고 한다.

 

Address Translation

프로세스는 Physical memory에서는 분리된 공간에 할당되지만, CPU는 연속된 공간의 메모리를 할당하여 사용하는 것처럼 관리한다. 이는 MMU(Memory Management Unit)을 통해 논리 주소와 물리 주소를 나누었기에 가능하다.

 

 즉 프로세스는 연속된 논리 주소(Logical Address)를 가지지만, 분리된 물리 주소(Physical Address)를 가지며 페이지 테이블을 통해 논리 주소를 물리 주소로 변환하여, Memory에 접근한다.

 

Page Table

페이지 테이블은 메모리 또는 CPU에 상주(컴퓨터 부팅 후 계속해서 유지함.) 시킬 수 있다. CPU에 페이지 테이블을 유지할 경우 빠른 속도로 페이지 테이블에 접근할 수 있지만, 한정된 CPU 레지스터로 인해 이와 같은 작업을 하는 것은 불가능하다.

 

이와 달리 메모리에 페이지 테이블을 유지할 경우, CPU와 달리 속도는 느리지만 상대적으로 많은 페이지 테이블을 할당할 수 있다는 장점이 있다. 따라서, 현재 페이지 테이블은 메모리에 상주한다.

 

TLB

CPU와 메모리 사이에 `TLB(Translation Look-aside Buffer)`를 두어, 메모리에 페이지 테이블을 유지하더라도 효율성을 높인다. `EMAT(Effective Memory Access Time)`을 계산하여 TLB의 효율성을 알 수 있다.

 

Segmentation

세그먼테이션은 프로세스가 사용하는 메모리 공간을 페이징과 같이 일정한 크기로 나누는 것이 아닌, 용동에 맞게 가변적으로 메모리를 할당한다. 따라서 가변적인 크기에 대한 정보를 유지하고 획득하기 위해 세그먼트 테이블을 유지하여야 한다. 세그먼테이션은 페이징을 사용하지 않을 때와 마찬가지로 여러 크기의 단편화가 발생하므로 페이징 기법을 많이 사용한다.

---

 

Virtual memory

부족한 메모리를 대신하여, 상대적으로 사용할 수 있는 공간이 큰 보조 저장장치(SSD, HDD)를 사용하는 것이 가상 메모리이다. 한 번에 프로그램의 모든 부분을 적재하는 것이 아닌, 현재 작업 처리에 필요한 부분만 적재하는 것과 마찬가지로 메모리가 부족할 경우 프로세스가 사용 중이지 않는 부분을 보조 저장장치로 보내어 공간을 확보한다.

 

Page Fault

프로세스의 요구에 따라 페이지 테이블에 접근하였을 때 해당 페이지가 invalid 상태(메모리에 적재되지 않은 상태)라면 해당 페이지를 불러들이는 작업이 필요하다. 이와 같이 접근하고자 하는 페이지가 invalid인 경우를 Page Fault라고 한다.

 

Page Fault가 발생할 경우 동작하는 일련의 과정은 다음과 같다.

1. 페이지 테이블의 valid-bit를 통해 접근하고자 하는 페이지가 메모리에 존재하는지 확인한다.

2. valid-bit가 0이라면 trap을 통해 커널로 진입한다.

3. 커널은 해당하는 페이지를 보조 저장장치에서 탐색한다.

4. 메모리에 해당 페이지를 할당한다.

5. 할당된 페이지에 대한 정보를 페이지 테이블에 갱신한다.

6. Page Fault를 발생시킨 명령어를 수행한다.

    

Page Replacement

현재 할당된 페이지 중에 victim page(교체할 대상)을 선정하는 방식은 다음과 같다.

• FIFO

  • 가장 먼저 할당된 페이지를 할당 해제하는 방식이다.

  • 가장 간단한 방식으로 초기화 과정의 코드는 더 이상 불필요할 것이라는 아이디어에서 설계되었다.

  • 단순히 할당된 순서에 따라 victim으로 선정하게 되면 오히려 페이지 교체가 빈번하게 발생한다.

  • Belady's Anomaly

    • 페이지를 할당할 수 있는 공간을 늘렸음에도 불구하고, FIFO를 통해 페이지를 교체할 경우 여전히 page fault 빈도가 증가하는 현상을 말한다.

• OPT

  • 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선정하는 방식이다.

  • 향후에 어떤 데이터를 사용할지 알 수 없기에 실제로는 구현이 불가능한 방식이다.

• LRU (Least Recently Used)

  • 가장 최근에 사용되었다면, 향후에도 사용될 가능성이 크다고 판단하여 최근에 사용되지 않은 페이지를 교체 대상으로 선정하는 방식이다.

  • 실제로 구현하고 사용할 수 있는 페이지 교체 방식 중 가장 많이 사용되는 방식이다.

---

 

Disk Scheduling

• FCFS (First-Come First-Served)

  • 가장 먼저 요청된 작업을 먼저 처리하는 방식.

• SSTF (Shortest Seek Time First)

  • 요청된 작업 중 헤드의 움직임이 가장 짧게 움직이는 작업부터 처리하는 방식

• SCAN

  • 엘리베이터처럼 한 방향으로 탐색을 하고, 다시 다른 방향으로 탐색을 하는 방식

• C-SCAN

  • SCAN 알고리즘에서 한 방향으로 탐색이 끝나면 반대 방향으로 가면서 데이터를 읽는 것이 아닌, 즉시 시작 위치를 반대로 옮겨서 탐색을 진행하는 방식

• C-LOOK

  • 0번에 데이터가 존재하지 않더라도, 탐색을 지속하는 Scan의 단점을 보완한 방식