선장 일지

가상 메모리란?

보조 기억장치에 비해 상대적으로 작은 크기를 가지고 있는 메인 메모리를, 더욱 더 효율적이고 대용량의 프로그램을 사용하기 위해 사용하는 기술입니다.
특정 시점마다 실제 사용하는 메모리는 그렇게 크지 않다는 점에 착안해서 고안된 기술입니다. 

가상 메모리를 사용하게 되면 프로세스 간 공간 분리를 하게 되는데 이를 통해 프로세스 간 메모리 영역 침범 이슈를 방지할 수 있고, 보조 기억장치를 활용하면서 메모리 용량 부족에 대한 이슈도 해결할 수 있습니다.

가상 메모리 기법을 사용하게 되면 CPU는 메모리의 실제 주소인 Physical Address 대신 Virtual address에 먼저 접근하게 됩니다. 이때 페이지 테이블을 참조하여 Virtual Address를 Physical Address로 변환하여 실제 메모리에 접근하게 되는데 이러한 변환 과정이 굉장히 빈번하게 일어나고 속도가 굉장히 중요하므로 MMU라는 하드웨어 칩의 지원을 받습니다.

MMU란?

MMU는 Memory Management Unit으로 CPU가 코드를 실행하며 가상 메모리 주소에 접근할 때 가상 메모리 주소를 실제 물리적인 주소로 변환해주는 하드웨어 장치입니다.

Page란?

가상 메모리 기법을 사용할 때 어느정도의 크기씩 실제 메모리에 올려놓는 기본 단위가 되는 것이 페이지입니다. 

페이지 단위로 관리하게 되며 페이지 번호를 바탕으로 가상 메모리 주소와 실제 메모리 주소를 매핑하여 페이지 테이블에 기록하고 관리하게 됩니다.

가상 메모리 주소 = (p, d)로 이루어져있고, p는 가상 메모리 페이지, d는 distance로 p 내 offset을 의미합니다.

가상 메모리 기법의 흐름

지금까지 배운 가상 메모리 기법의 흐름을 정리해보면, CPU가 명령어를 실행하던 중 가상 메모리 주소를 참조하게 되면 하드웨어 칩셋인 MMU를 거쳐서 실제 메모리에 올라가있는 페이지 테이블을 참조하여 실질적인 메모리 주소로 변환하게 되고 메모리에 접근하게 됩니다. 메모리에 반복적으로 접근하고 데이터를 읽어오게 되는데 이러한 속도는 CPU나 레지스터 처리 속도에 비하면 굉장히 느린 속도입니다. 이 부분에서 성능 향상을 위해서 TLB라는 하드웨어를 사용하게 됩니다.

TLB(Translation Lookaside Buffer)란?

TLB란 최근에 접근한 페이지 정보를 기록하는 하드웨어 칩셋입니다. 즉, 가상 메모리 주소가 한번 물리 주소로 변환되면 TLB에 기록하고 그 다음부턴 MMU가 페이지 테이블을 참조하는 것이 아닌 TLB를 통해 물리 주소를 먼저 찾습니다. 이를 통하여 상대적으로 속도가 느린 메모리에 접근하는 횟수를 줄여 성능을 향상 시켜줍니다.

페이지 폴트(Page fault)란?

가상 메모리 주소를 통해서 실제 물리 주소를 얻고 메모리에 접근했지만 내가 원하는 페이지가 실제 메모리에 적재되어 있지 않을수도 있습니다. 이렇게 내가 찾는 페이지가 실제 메모리에 현재 적재되어 있지 않을 때를 페이지 폴트라고 합니다. 페이지 폴트가 발생하면 보조기억장치에서 지금 내가 필요한 페이지를 가져오게 됩니다. 보조 기억장치는 메모리보다 속도가 더 느리기 때문에 자주 참조하면 성능이 떨어지게 됩니다. 따라서 페이지 폴트를 줄이기 위해서 다양한 기법들이 사용됩니다. 

페이지 교체 알고리즘

페이지 폴트가 발생했을 시 물리 메모리에 비어있는 프레임이 있다면, 비어있는 프레임에 원하는 메모리를 보조 기억장치에서 가져오면 됩니다. 하지만, 프레임이 가득 차 있을 시에는 페이지 교체 알고리즘을 통해 빈 프레임을 만들어주고 보조 기억장치에서 원하는 메모리를 가져와 적재해야 합니다. 페이지 교체 알고리즘에는 FIFO, LRU 등이 있습니다.

FIFO는 가장 먼저 물리 메모리에 적재된 페이지를 선택하는 방식입니다.
LRU는 Least Recent Used의 약자로 가장 오랫동안 사용되지 않았던 페이지를 선택하는 방식입니다.

동기와 비동기

동기

• 직렬적으로 작업을 수행합니다. 즉, 작업은 순차적으로 실행되며 어떤 작업이 수행중이면 다른 작업은 대기하게 됩니다.
• 서버에서 데이터를 가져와 화면에 표시하는 작업을 수행할 때, 서버에 데이터를 요청하고 응답이 올 때까지 이후의 작업들은 Blocking됩니다.

비동기

• 병렬적으로 작업을 수행합니다. 즉, 작업이 종료되지 않은 상태라도 대기하지 않고 다음 작업을 실행합니다.
• 서버에서 데이터를 가져와서 화면에 표시하는 작업을 수행할 때, 서버에 데이터를 요청하고 응답이 올 때까지 기다리지 않고(Non-Blocking) 이후의 작업을 수행합니다. 만약, 서버로부터 응답오게되면 이벤트가 발생하고 이벤트 핸들러가 데이터를 가지고 수행할 작업을 연속적으로 수행합니다.

프로세스 동기화

• 프로세스는 서로 메세지를 보내고 프로세스 내부에서는 스레드끼리 자원을 공유하면서 동기화에 대한 문제가 항상 발생할 수 있습니다. 즉, 공유된 자원에 여러 프로세스, 여러 스레드가 동시에 접근하면서 문제가 발생합니다.

Critical Section(임계 구역)

• Critical Section은 멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역입니다. Critical Section은 시간이 지나면 종료되며 어떤 프로세스가 Critical Section에 접근하기 위해서는 지정된 시간만큼 대기해야 합니다.
• 이 때, 스레드나 프로세스가 사용권을 보장받기 위해서 세마포어 같은 동기화 메커니즘이 사용됩니다.

Critical Section 문제를 해결하기 위한 3가지 조건

1. Mutual Exclusion(상호 배제)
   • 하나의 프로세스가 임계 구역에 들어가 있으면 다른 프로세스는 임계구역에 들어갈 수 없다.
2. Progress (진행)
   • 임계 구역에 들어간 프로세스가 없다면 어떤 프로세스가 임계 구역에 들어갈지 선택해야한다.
3. Bounded Waiting (한정 대기)
   • 기아 상태를 방지하기 위해 이미 한 번 들어간 프로세스는 다음에 들어갈 때 제한을 준다.

동기화를 제공하는 방법

• Lock
  • 하드웨어 기반 해결책으로써 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section에 진입하는 프로세스는 Lock을 획득하고 Critical Section을 빠져나올 때 Lock을 풀어줌으로써 동시 접근이 불가능하게 합니다.
• 세마포어
  • 동시에 리소스에 접근할 수 있는 허용 가능한 개수를 가지고있는 counter로 보면 됩니다. 
  • counter의 개수에 따라 1개일 경우 이진세마포어(뮤텍스), 2개 이상일 경우 카운팅 세마포어라고 부릅니다.
• 세마포어와 뮤텍스의 차이
  • 공유 자원에 대한 접근권한, Lock이라는 키를 한개만 가지고 있는 것은 뮤텍스이고, 키를 여러개 가질 수 있는 것은 세마포어 입니다.

교착 상태(Deadlock)

• 서로 상대방의 작업이 끝나기만을 기다리는 두 개 이상의 작업이 서로 종료되지 않아 작업 진행이 불가능한 상태를 말합니다.

교착 상태 발생 조건

• Mutual Exclusion (상호 배제)
  • 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
• Hold ans Wait (점유 대기)
  • 프로세스가 자원을 할당한 채로 다른 자원을 기다린다.
• No Preemption (비선점)
  • 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
• Circular Wait (순환 대기)
  • 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.
• 위의 네 가지 조건을 모두 충족시킬 때 교착 상태가 발생할 수 있습니다. 위 네 가지 조건 중 하나라도 충족되지 않으면 교착 상태는 발생하지 않습니다.

프로세스 스케줄러

스케줄러란 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 코드를 의미합니다. 스케줄러는 역할과 목적에 따라서 단기 스케줄러, 중기 스케줄러, 장기 스케줄러로 구분됩니다.

단기 스케줄러

• 단기 스케줄러는 미리 정한 스케줄링 알고리즘에 따라 실행할 프로세스를 선택합니다.
• CPU와 메모리 사이의 스케줄링을 담당합니다.
• ready queue에 존재하는 프로세스 중 어떤 프로세스를 실행할지 결정합니다.
• 프로세스에게 CPU를 할당합니다.
  • ready -> running(dispatch)
• 프로세스의 상태의 변화 ready -> running -> waiting(block) -> ready

장기 스케줄러

• 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(디스크)에 임시로 저장됩니다. 대용량 메모리에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할을 합니다.
• 메모리와 디스크 사이의 스케줄링을 담당합니다.
• 하드 디스크에 있는 프로그램을 메모리에 로드하는 역할을 담당합니다.
• 메모리에 몇개의 프로그램이 올라갈 것인지 제어합니다.
• 프로세스의 상태의 변화 new -> ready

중기 스케줄러

• 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 역할을 합니다.
• 메모리의 여유 공간을 마련하기 위해서 프로세스를 통째로 디스크로 쫓아냅니다. (swapping)
• 프로세스의 상태의 변화 Ready -> suspended

스케줄링 알고리즘

• CPU는 하나의 프로세스 작업이 끝나면 다음 프로세스 작업을 수행해야 합니다. 이때 어떤 프로세스를 다음에 처리할 지 선택하는 알고리즘을 스케줄링 알고리즘이라고 합니다.
• 스케줄링 알고리즘에는 비선점 스케줄링 방식과 선점 스케줄링 방식이 있습니다.

비선점 스케줄링

• 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시간까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식입니다.
• 모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만 짧은 작업을 수행하는 프로세스가 긴 작업을 하는 프로세스 종료 시까지 대기해야할 수도 있습니다.
• 알고리즘 : FCFS, SJF, 우선순위 등

FCFS(First-Come-First-Served) 알고리즘

• 먼저 들어온 프로세스가 먼저 처리되는 알고리즘입니다. 흔히 많이 보던 FIFO, Queue와 같습니다.
• 장점
  • 가장 간단한 스케줄링 알고리즘으로 구현이 쉽습니다.
• 단점
  • 비선점식 알고리즘이기 때문에 대화식 프로세스에 적합하지 않습니다.
  • 긴 작업을 해야하는 프로세스가 먼저 온 경우 짧은 작업으로 완료되는 프로세스의 대기시간이 길어지게 됩니다.

SJF(Shortest Job First)

• 실행 시간이 가장 짧은 프로세스에게 자원을 할당하는 알고리즘입니다.
• 장점
  • 실행 시간이 짧은 작업을 먼저 실행하기때문에 평균 대기시간이 다른 알고리즘에 비해 짧아집니다.
• 단점
  • 짧은 작업들이 계속 생기는 경우 작업 시간이 긴 프로세스가 너무 오래 기다리는 현상이 발생합니다.
  • 짧은 작업에 최우선으로 CPU를 할당하기 때문에 공평하지않습니다.

우선순위(비선점)

• 프로세스마다 우선순위를 부여하여 높은 우선순위를 가진 프로세스에게 먼저 자원을 할당하는 방법입니다.
• 우선순위 알고리즘은 선점과 비선점이 있습니다.
• 비선점 우선순위 스케줄링은 실행중인 것과 무관하게 우선순위가 높으면 큐의 가장 앞에 위치합니다.
• 장점
  • 각 프로세스의 상대적 중요도를 명시할 수 있습니다.
  • 실시간 시스템에 유리합니다.
• 단점
  • 높은 우선순위 프로세스가 계속 들어올 경우 우선순위가 낮은 프로세스가 너무 오래기다리는 현상이 발생합니다.

선점 스케줄링

• 현재 CPU가 할당된 프로세스의 작업이 종료되지 않아도 다른 프로세스에게 CPU를 할당하는 스케줄링 방식입니다.
• 알고리즘 : 우선순위(선점), 라운드로빈(RR)

우선순위(선점)

• 하나의 프로세스가 CPU를 차지하고 있어도 우선순위가 높은 다른 프로세스가 대기하는 경우 현재 프로세스를 중단 시키고 우선순위가 높은 프로세스에게 CPU를 할당하는 스케줄링 방식입니다.
• 장점
  • 응답이 빠릅니다.
• 단점
  • 처리 시간을 예측하기 힘듭니다.
  • 우선순위 프로세스들이 계속해서 들어오는 경우 오버헤드가 발생합니다.

RR(Roung-Robin)

• 현대적인 CPU 스케줄링 방식으로 각 프로세스는 동일한 할당 시간을 갖게되고 할당 시간이 지나고 나면 ready queue 맨 끝으로 가서 다시 CPU의 할당을 기다립니다.
• 장점
  • 모든 프로세스가 공정하게 시간을 할당받습니다.
  • 프로세스 최악의 응답시간을 아는데 유리합니다.
• 단점
  • 하드웨어 타이머가 필요합니다.
  • 작업 시간을 너무 짧게한 경우 Context Switching이 빈번하게 일어나 오버헤드가 발생합니다.

MLQ(Multilevel Queue)

• 준비 상태 큐를 여러 종류별, 단계별로 분할해두고 자신만의 독자적인 스케줄링 구현이 가능합니다.
• 각 큐는 절대적인 우선순위를 가지며 우선순위가 높은 큐가 모두 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행할 수 없습니다.
• 장점
  • 응답이 빠릅니다.
• 단점
  • 여러 준비 큐와 스케줄링 알고리즘을 사용하기 때문에 추가 오버헤드가 발생합니다.
  • 우선순위가 낮은 큐의 프로세스가 오래 기다리는 현상이 발생합니다.

프로세스

• 프로세스(process)란 일반적으로 CPU에 의해 처리되는 사용자 프로그램으로 실행중인 프로그램을 의미합니다.

프로세스와 프로그램

• 프로그램은 일반적으로 하드 디스크 등에 저장되어 있는 실행 코드를 말합니다.
• 프로세스는 프로그램을 구동하여 프로그램의 상태가 메모리 상에서 실행되는 작업 단위를 지칭합니다.
• 프로그램은 보조 기억장치에 존재하며 실행되기를 기다리는 명령어와 정적인 데이터의 묶음입니다.
• 이 프로그램의 명령어와 정적 데이터가 자원을 할당받고 메모리에 적재되면 프로세스가 됩니다.

프로세스의 특징

프로세스는 각각 독립된 영역(Code, Data, Stack, Heap)을 할당 받습니다.

• Code 영역
  • 실행 명령을 포함하는 코드들이 들어가는 영역입니다.
  • 프로그램을 시작할 때 컴파일한 프로그램(기계어)이 저장되어 있고, 읽기 전용 영역이기때문에 프로세스가 함부로 변경할 수 없고 변경 시 오류를 발생시킵니다.
• Data 영역
  • 프로그램이 실행될 때 생성되고 프로그램이 종료되면 시스템에 반환됩니다.
  • 전역변수, 정적변수, 배열, 구조체 등이 저장됩니다.
• Heap 영역
  • 메모리를 동적으로 할당할 때 사용되는 메모리 영역입니다.
• Stack 영역
  • 프로그램이 자동으로 사용하는 메모리 영역입니다.
  • 함수 호출과 관계되는 지역변수와 매개변수가 저장됩니다. 함수 호출 시 생성되고 함수가 끝나면 반환됩니다.

멀티 프로세스

• 멀티 프로세스(Multi Process)란 하나의 응용 프로그램을 여러 개의 프로세스로 구성하여 각 프로세스가 하나의 작업을 처리하도록 하는 것 입니다.
• 장점
  • 멀티 프로세싱은 여러 개의 자식 프로세스 중 하나에 문제가 발생해도 다른 프로세스들에게 영향이 확산되지 않습니다.
• 단점
  • Context Switching 과정에서 캐시 메모리 초기화 등 무거운 작업이 진행되고 많은 시간이 소모되는 등 오버헤드가 발생합니다.
  • 프로세스는 각각 독립된 영역을 가지고 있기 때문에 프로세스 사이에서 공유하는 메모리는 없습니다. 따라서 Context Switching이 발생하면 캐시에 있는 모든 데이터를 모두 리셋하고 다시 캐시 정보를 불러와야 합니다.
  • 독립된 영역 때문에 프로세스간의 통신이 필요합니다.

스레드

스레드(Thread)란 어떠한 프로세스 내에서 실행되는 흐름의 단위입니다.

스레드의 특징

• 스레드는 프로세스 내에서 각각 Stack만 따로 할당받고 Code, Data, Heap 영역은 공유합니다.
• 스레드는 한 프로세스 내에서 동작되는 여러 실행의 흐름으로 프로세스 내의 주소 공간이나 자원(Heap 공간 등)을 같은 프로세스 내에 스레드끼리 공유하면서 실행됩니다.
• 같은 프로세스 안에 있는 여러 스레드들은 같은 Heap 영역을 공유합니다. 반면 프로세스는 다른 프로세스의 메모리에 직접 접근할 수 없습니다.

멀티 스레드

• 멀티 스레드(Multi Thread)는 하나의 프로그램을 여러 개의 스레드로 구성하는 방식입니다.
• 장점 
  • 멀티 스레드는 Stack을 제외한 자원들을 공유하고 있기 떄문에 Context Switching 시에 캐시 메모리를 비울 필요가 없고 이를 통해서 자원을 아낄 수 있습니다.
  • Stack 이외의 메모리를 공유하고 있기 때문에 통신의 부담도 멀티 프로세스에 비해 적습니다.
• 단점
  • 내부의 메모리를 공유하고 있기때문에 한 프로세스의 스레드가 문제가 생길 시 해당 프로세스 안의 다른 스레드에도 문제가 생깁니다.
  • 같은 데이터를 공유하기에 데이터 동기화에 신경을 써야합니다.

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

멀티 스레드는 멀티 프로세스보다 적은 메모리 공간을 차지하고 Context Switching이 빠르다는 장점이 있지만, 하나의 스레드가 문제가 생길 시 다른 스레드에 문제가 생길 수 있다는 치명적인 단점과 동기화의 문제를 가지고 있습니다. 반면 멀티 프로세스는 하나의 프로세스가 문제가 생기더라도 다른 프로세스에 영향을 끼치지 않는 장점이 있지만, 멀티 스레드보다 많은 메모리 공간과 CPU 시간을 차지한다는 단점이 있습니다.

동시에 여러 작업을 수행할 수 있다는 점에서 동일하지만 적용해야 하는 시스템에 따라 멀티 프로세스와 멀티 스레드 중 잘 선택해야하는 장, 단점이 존재합니다.

Context Switching

Context Switching이란 하나의 프로세스가 CPU를 사용중인 상태에서 다른 프로세스에게 CPU를 넘겨주기 위해, 이전의 프로세스 상태를 보관하고 새로운 프로세스의 상태를 적재하는 작업을 말합니다. 여기서 한 프로세스의 상태는 프로세스 제어 블록인 PCB에 적재되어 있습니다.

P1 -> P2, P2 -> P1 의 Context Switching 과정은 다음과 같습니다.

1. P1의 실행 중에 Interrupt 또는 System call 이 발생하면 P1은 idle 상태가 됩니다.
2. P1이 executing 상태에서 idle 상태로 변할 때 프로세스와 실행에 대한 데이터는 레지스터에 존재하는데 이 데이터를 메모리에 저장합니다.(save state into PCB1)
3. 그 다음 P2가 실행되는데 P2가 실행되기 위해서 메모리에 존재하는 P2에 대한 데이터를 레지스터에 올려야 합니다.(reload state from PCB2)
4. P2가 실행되었다가 다시 idle 상태로 변경되면서 자신의 데이터를 메모리에 저장합니다.(save state into PCB2)
5. 다음에 P1이 실행되는데 P1의 데이터를 메모리에 저장했었다. 이 데이터를 읽어서 레지스터에 올리고 P1을 이전에 멈추었던 시점에서 이어서 실행합니다.