DaHoon06
[OS] Operating System
운영체제 또는 오퍼레이팅 시스템(Operating System)은 시스템 하드웨어를 관리할 뿐만 아니라 응용 소프트웨어를 실행하기 위하여 하드웨어 추상화 플랫폼과 공통 시스템 서비스를 제공하는 시스템 소프트웨어이다.
최근에는 가상화 기술의 발전에 힘입어 실제 하드웨어가 아닌 하이퍼바이저 위에서 실행되기도 한다.
소프트웨어 : CPU,메모리,보조기억장치,네트워크 등의 자원들을 잘 관리하여 응용 소프트웨어들에게 제공해주는 역할
하드웨어 추상화 플랫폼 또한 중요한 개념!
추상화는 프로그래밍에 있어서 매우 중요하고 유용한 개념이다.
컴퓨터 과학에서 추상화 (abstraction)
: 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것을 말한다.
운영 체제에서의 추상화 (abstraction)
: 운영체제는 하드디스크에 대해 파일, 네트워크에 대해 포트, 메모리에 대해 주소, CPU에 대해 프로세스
라는 추상화된 접근 방법을 제공한다. 이 개념은 수학적 추상화의 유추로부터 유래되었다.
응용 소프트웨어를 개발할 때 파일 접근이 필요하면 보조 기억 장치가 어떤 장치인지 몰라도 이용할 수 있고, 물리 메모리가 부족하여 스왑핑이 일어나더라도 직접 보조 기억 장치에 페이지 내용을 복사하는 작업 등을 할 필요가 없다.
단지, OS에게 요청하면 알아서 처리된다.
개요
사용자가 운영 체제와 맞닿아 있는 부분을 사용자 인터페이스(User Interface)라고 하며, GUI 또는 CUI로 나뉜다.
실제 서비스를 받기 위한 방법으로 시스템 콜(System Calls)들이 제공된다. 윈도에서는 WinAPI라는 이름으로 불린다.
프로세스
프로세스 생애주기
프로세스는 프로그램의 인스턴스로 운영 체제에서 가장 기본적인 실행 단위이다. 각 프로세스는 메모리를 차지하고, 일정 상태 주기를 가진다. 어떻게 프로그램을 실행되게 만들었는냐에 따라 다르지만 보통 지역 변수나 함수 호출로 인한것은 스택 영역에서 메모리가 할당되고, 동적 메모리 할당은 힙 영역에서 메모리가 할당된다.
** Stack과 Heap 이해
Stack
- 함수나 지역 변수들에 대한 정보를 저장
- 읽는 것이 빠르다. 변수의 크기를 제한할 수 있다.
- 함수가 종료되면 모든 변수가 스택에서 팝되고 결국 모든 데이터가 사라진다.
Heap
- 자동으로 관리 안되고 엄격하게 관리안하는 메모리 영역
- 제대로 관리하지 않으면 메모리 누수가 발생
- 포인터를 통해 접근하는데 그것으로 인해 조금 속도가 느리다.
- 힙의 변수는 본질적으로 전역을 뜻한다.
메모리 누수(memory leak)
컴퓨터 프로그램이 필요하지 않은 메모리를 계속 점유하고 있는 현상이다.
할당된 메모리를 사용한 다음 반환하지 않는 것이 누적되면 메모리가 낭비된다.
전역 변수에는 static 전역변수와 heap전역변수로 나뉜다.
- 전역변수의 의미는 쉽게 말해 스택에 들어가지 않는 모든 변수를 말한다.
- 전역변수 중 static 이 붙어 있는 변수는 JVM 실행시 부터 클래스 메모리에 할당된다.
- 전역변수 중 static 이 붙어 있지 않는 변수는 동적으로 new 될 때 heap에 할당된다.
프로세스는 보통 5가지 상태 중 하나의 상태로 존재한다. 처음 프로그램을 실행하기 위해 OS에게 요청하면 프로세스를 new 상태로 생성하고 실행 가능한 상태가 되면 ready 상태가 된다. ready 상태의 프로세스는 스케줄러에 의해 running 상태가 되어 실행되다가 I/O 혹은 이벤트 대기에 의해 waiting 상태가 되거나 interupt에 의해 ready 상태가 된다.
waiting 상태였던 프로세스는 I/O나 이벤트가 완료됨에 따라 다시 ready 상태가 된다. 실행중이던 프로그램이 종료되면 terminated 상태가 되고, 곧 OS에 의해 자원이 회수된다.
위의 프로세스 메모리 구조는 프로세스 자체의 인스턴스이고, 운영체제에서는 각 프로세스를 관리하기 위한 PCB(Process Control Block) 이라는 별도의 자료 구조로 프로세스들을 관리한다.
PCB에는 프로세스가 실행되는 동안 필요한 정보인 Program Counter나 레지스터 값들, 가상 메모리를 위한 페이지 테이블, 열었던 파일 목록 등이 포함된다.
어떤 프로세스가 실행되다가 다른 프로세스가 실행되어야 할 때 문맥 전환(Context Switching)이 일어난다.
문맥 전환을 하고 나면 완전히 다른 프로세스가 실행 가능해야 한다. 어떻게 이것이 가능할까 싶지만 Program Counter를 포함한 레지스터 값들과 파이프라이닝 장치들, 컨트롤 장치의 값 등이 복구되면 완전히 다른 프로세스를 실행하게 된다.
그러나 값들을 다시 복사해야 한다는 점에서 직지 않은 오버헤드다. 문맥 전환은 자주 일어나기 때문에 빠르면 빠를수록 좋다.
문맥 전환이 가능하도록 도와주는 것이 PCB
: 기본 동작하고 있던 Process의 정보를 PCB에 저장한 후 새로운 Process에게 CPU를 건내준다. 그 이후 다시 이전 Process가 동작하기 위해 PCB 정보를 읽고 동작하도록 할 수 있다.
스케줄링 방법은 선점형(preemtive)과 비선점형(non-preemtive)으로 나뉜다. I/O 작업이나 wait 시스템 콜로 waiting 상태가 되는 경우 비선점형 스케줄링 방식이라고 하며, 프로세스가 실행 중에 timeout등으로 인해 waiting 상태로 변경될 수 있다면 선점형 스케줄링이라고 한다.
** CPU를 사용하다가 뻇을 수 있냐 없냐가 중요한 기준!!!
선점형(preemtive)은하나의 프로세스가 다른 프로세스 대신에 프로세스(CPU)를 차지할수 있다는 뜻이다.
대표적 : Round Robin방식(RR)
-시간 단위가 설정되어 각 시간동안 프로세스를 실행하고 시간이 지나면 다음 프로세스로 전환되게 된다.
전체적인 응답 속도가 빨라질수도 있으나, 시간 단위마다 프로세스를 전환할때 문맥 전환에 따른 오버헤드가
발생할 수 있기 때문에 적당한 시간 단위를 설정하여야 한다.
비선점형(non-preemtive)은하나의 프로세스가 끝나지 않으면 다른 프로세스는 CPU를 사용할 수 없다.
대표적 : FIFO: 대기 큐에 먼저 들어온 작업순으로 CPU를 할당
SJF(Shot Job First) : 소요시간이 짧은 작업순으로 할당
HRN: 우선순위와 대기 시간에 따라 작업을 할당
프로세스 연산들
주요 프로세스 연산은 프로세스 생성과 종료이다.
리눅스에서 프로세스를 생성하는 방법은 보통 fork류 시스템 콜을 호출하여 프로세스를 복사한 뒤, 자식 프로세스로서의 실행을 하거나 exec류 시스템 콜을 호출하여 다른 프로그램으로 바뀌어 실행하는 방법이다.
만약 부모프로세스가 자식 프로세스의 종료를 기다리고 싶다면 wait 시스템 콜을 호출, main 함수가 종료되기 전에 임의로 프로세스를 종료하고 싶다면 exit 시스템 콜을 호출한다. exit 시스템 콜은 정수 인자를 받는다. 이는 main 함수에서 반환하는 값과 같은 의미인데 프로세스의 종료 결과를 알려주는 방법이다. 예를 들어 프로세스가 0을 반환하고 종료하지 않은 경우 에러가 발생했다는 의미가 약속되어 있다.
프로세스 간 통신
프로세스 간 통신(InterProcess Communication)은 운영체제의 도움이 필요하다.
프로세스는 보안 등의 문제로 각자 독립된 메모리 공간을 가지기 때문에 단순 메모리 값 변경은 다른 프로세스에게 데이터를 전달하는 방법으로 사용될 수 없다.
첫번째. 공유 메모리(Shared-Memory Systems)를 사용하는 방법
: OS에게 어떤 영역의 메모리를 다른 프로세스와 공유하고 싶다는 요청을 하는 것이다.
-> 구현이 어려움, 시스템 콜 요청이 적음, 공유변수 사용시 동시화 문제 발생 가능
두번째. 메세지 전달(Message-Passing Systems)을 사용하는 방법
: 프로세스와 프로세스 간에 메세지를 전달할 수 있는 방법을 만드는 것, 메세지 전달 방법은 OS에서 내부적으로 메세지 큐를 두는 방법, 파이프를 만드는 방법, 소켓을 이용하는 방법등 여러가지 방법으로 구현될 수 있다.
-> 구현이 쉬움, 시스템 콜을 많이 호출함
쓰레드(Thread)
어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위
쓰레드 마다 실행 흐름을 가지기 때문에 각자 레지스터 집합과 스택 영역을 가지며 힙 영역은 공유된다.
여러 쓰레드가 동시에 실행하는 방법은 I/O 작업과 같이 시간이 오래 걸리는 작업 중에 CPU 사용이 많은 작업을 하고 싶을 때와 같은 상황에 유용하게 쓰일 수 있다. 또한, 서버 프로그램과 같이 워커(Worker)가 여럿 필요한 경우에도 유용하다.
만약 멀티 프로세서 환경에서 어떤 작업들이 서로 의존성이 없다면 동시에 실행함으로써 처리 속도를 향상할 수도 있다. 쓰레드는 실행 흐름은 독립적이지만 메모리 공간은 공유하고 있기 때문에 경량 프로세스(Light Weight Process)라고 부르기도 한다.
멀티 쓰레딩을 지원하는 방법으로는 다대일, 일대일, 다대다 방법이 있다.
일반적으로 사용자가 생성하는 쓰레드는 유저 수준 쓰레드라고 분류하고 실제 시스템 실행되는 쓰레드를 커널 수준 쓰레드라고 하는데, 유저 수준 쓰레드와 커널 수준 쓰레드를 어떤 방식으로 맵핑하느냐의 차이이다.
다대일 모델은 여러 유저 수준 쓰레드를 하나의 커널 수준 쓰레드에 사상
일대일 모델은 각 유저 수준 쓰레드마다 커널 수준 쓰레드에 사상
다대다 모델은 여러 유저 수준 쓰레드를 여러 커널 쓰레드에 사상
한 유저 수준 쓰레드에서 blocking 연산을 하는 경우 다른 모든 유저 수준 쓰레드가 멈춘다는 점에서 다대일 모델은 통용되기 어렵다. 커널 수준 쓰레드는 생성하기에 오버헤드가 있으므로 일대일 모델보다는 현실적으로 다대다 모델이 사용된다.
동기화(Synchronization)
프로세스 내에 여러 실행 흐름이 존재할 수 있게 되면서 동기화 문제가 대두된다. 여러 쓰레드가 공유 자원을 동시에 접근하려는 경우 발생하는 경쟁(Race condition) 때문이다. 이러한 경쟁 상태를 일으키는 코드 영역을 임계 구역(Critical Section) 이라고 한다.
임계 구역(Critical Section)
여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분
공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.
경쟁 상태가 일어나지 않게 하기 위해서는 다른 쓰레드가 이미 작업 중인 경우 작업이 끝날 때까지 기다릴 수 있도록 지원해줘야한다. 현실적으로 별도의 하드웨어 지원을 받지 않는 이상 어떤 알고리즘도 경쟁 상태로부터 자유로울 수 없다. 하드웨어 지원을 통해 어떤 변수의 값 수정을 원자적으로 가능하게 함으로써 뮤텍스 락(Mutexlocks)이나 세마포어(Semaphore)와 같은 해결 방법을을 제안한다.
세마포어(Semaphore) : 공유된 자원의 데이터를 여러 프로세스 또는 쓰레드가 접근하는 것을 막는 것
(즉, 동기화 대상이 하나 이상)
뮤텍스(Mutex) : 공유된 자원의 데이터를 하나의 프로세스 또는 쓰레드가 접근하는 것을 막는 것
(즉, 동기화 대상이 하나)
그러나 로킹(Locking) 방법은 데드락(Deadlock, 교착상태)을 일으킬 수 있다. 서로 공유 자원을 점유하고 있는 상황에서 서로의 공유 자원을 얻으려 할 때 데드락이 발생한다.
데드락(Deadlock, 교착상태)
운영체제에서 데드락(교착상태)이란, 시스템 자원에 대한 요구가 뒤엉킨 상태
즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황
발생조건)
1. 상호 배제
한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
2. 점유 대기
자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
3. 비선점
이미 할당된 자원을 강제로 빼앗을 수 없다(비선점).
4. 순환 대기
대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
데드락에 대한 해결방법
- 데드락이 발생하지 않도록 예방(prevention) 하기
- 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
- 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기
데드락의 발생조건 4가지 중 하나라도 발생하지 않게 하는 것이 데드락을 예방하는 방법이다 즉, 각각의 조건을 방지(부정)하여 데드락 발생 가능성을 차단한다.
메모리(Main Memory)
프로그램 로딩
고수준 언어로 작성된 소스 코드는 컴파일러와 어셈블러에 의해 목적 프로그램으로 컴파일 된다. 위 사진에서 Object module이 컴파일된 단계에 해당된다. 목적 프로그램은 linkage editor 라는 프로그램에 의해 여러가지 다른 목적 프로그램과 연결된다. 각 소스 파일별로 목적 프로그램이 만들어지게 되는데, 다른소스에 있는 함수를 참조하려면 링킹(linking)이 필요한 것이다. 연결이 완료되고 나면 loader라는 프로그램에 의해서 실제로 물리 메모리에 로딩된다. 이때, 동적 로드하기로 되어있는 시스템 라이브러리 등이 동적 링킹 된다. 최종적으로 로딩된 프로세스는 CPU에 의해 실행된다.
linker 또는 linkage editor
: 컴퓨터 과학에서 컴파일러가 만들어낸 하나 이상의 목적 파일을 가져와 이를 단일 실행
프로그램으로 병합하는 프로그램
주소 변환
프로세스에서 물리 메모리로 직접 접근 가능하도록 하지는 않는다. 가장 기본적인 주소 변환 방법은 base와 limit 레지스터를 이용한 하드웨어를 사용하는 방법이다.
어떤 주소에 대해 base보다 높고 base + limit 보다 낮은 주소를 참조해야만 하도록 하는 하드웨어다. 만약 base보다 낮은 주소나 base + limit 보다 높은 주소를 참조하려고 하면 trap을 작동 시켜 에러가 나도록 한다.
스왑핑(Swapping)
물리 메모리에 공간이 부족해지면, 실행 중이던 프로그램이 손상되어선 안되므로 OS에서는 스왑핑이라는 기법으로 실행 중이던 프로그램의 메모리 보조 기억 장치에 저장시키고 메모리를 비운 뒤 사용하는 방법을 이용한다.
보조 기억 장치는 매우 느리기 때문에 스왑핑이 일어나는 것은 성능에 큰 영향을 끼친다. 예를 들어 프로세스가 전체 물리 메모리를 다 사용하도록 하는 시스템이라면 다른 프로세스가 실행될 때마다 물리 메모리 전체를 보조 기억 장치에 복사하는 작업을 수행해야 할 것이다.
하드 디스크가 20MB/s 정도의 쓰기 속도를 보이므로 4GB메모리를 복사한다고 하면 약 200초가 걸린다.
연속적인 메모리 할당
보통 메모리를 딱 한 워드만 요구하지 않기 때문에 연속적인 공간을 할당해줄 수 있어야 한다.
크게 First Fit, Best Fit, Worst Fit 3가지 방법이 있다.
First Fit
: 여유 공간 중 첫번째로 충분한 공간을 선택해서 할당하는 방법
Best Fit
: 딱 맞는 여유 공간을 선택해서 할당하는 방법
Worst Fit
: 가장 여유 있는 공간을 할당하는 방법
시뮬레이션에 의하면 First Fit이나 Best Fit 방법이 시간과 스토리지 사용량에 대해서 나은 결과를 보였다.
First Fit 과 Best Fit 둘 다 스토리지 사용량은 비슷하나 First Fit이 할당할 공간을 더 빠른 시간 내에 찾았다.
할당 방법에 따라 파편화(Fragmentation)가 생긴다. 어떤 공간에 메모리를 할당하게 되면 할당한 공간을 제외한 부분이 남게 된다.
이것을 파편화라고 하는데, 항상 딱 맞게 할당하는 것이 아니기 때문에 곳곳에 파편화된 메모리 공간들이 존재하게 된다. 언젠간 파편화가 너무 심해져서 더 이상 할당을 할 수 없게 되기 때문에 압축(compaction) 작업은 불가피하다.
세그먼테이션(Segmentation)
각 함수나 변수마다 하나의 메모리 조각(segment)으로 생각하는 경향이 있다. 예를 들어 C 컴파일러는 유저 코드, 라이브러리 코드, 전역 변수, 스택, 힙을 각각의 조각으로 분리할 수도 있다. 이러한 관점과 앞서 기본적인 주소 변환 하드웨어를 결합한 것이 세그먼테이션 방법이다.
세그먼테이션 방법에서는 각 세그먼트마다 limit과 base가 존재하여 메모리 곳곳에 메모리 조각을 둘 수 있다. 그러나 세그먼테이션 방법에서도 각 메모리 조각은 연속된 공간에 할당되어야 하며, 그에 따라 파편화 문제는 해결되지 않는다.
페이징(Paging) -> 추가 공부사항(Demand Paging)
페이징 방법은 연속적인 할당조차 필요 없게 만들어준다. 페이지 테이블을 구성하고 메모리를 페이지라는 단위로 나누어 논리 주소를 물리 주소로 변환한다. 메모리 주소의 앞쪽 bit들은 페이지 번호로, 뒤쪽 bit들은 페이지 내의 offset으로 사용된다.
페이지를 찾는 작업은 메모리에 접근할 때마다 발생하므로 매우 빠르게 수행되어야 한다. 이를 위해 하드웨어 지원을 받는데, TLB 캐시를 둠으로써 주소 변환을 빠르게 한다. 만약 TLB에 접근하는데 20 나노초가 걸리고 메인 메모리에 접근하는데 100나노초가 걸리며 TLB 히트율이 80%라고 하면 데이터를 가져오는데 평균적으로 0.80 * 100 + 0.20 * 200 = 120 나노초가 걸린다. 이는 20% 정도 성능 저하가 된다는 것을 뜻한다. 만약 TLB 히트율이 99%가 되면 101 나노초만 걸리는 것으로 오버헤드가 매우 적음을 알 수 있다.
TLB(Translation-Lookaside Buffer)
페이지 테이블은 메인 메모리에 저장되기 때문에 프로그램에 의한 모든 메모리 접근은 최소한 두번 필요하게 된다.
(왜냐하면 주소변환을 위한 메모리 내의 페이지 테이블 접근 한번, 실제 데이터를 가져오기위한 메모리 접근 한번)
접근 성능을 높이기 위한 핵심은 페이지 테이블에 대한 참조의 지역성에 달려 있다. 어떤 가상 페이지 번호의 변환이 사용되면 페이시 상의 워드 참조는 공간적 지역성과 시간적 지역성을 갖기 때문에 그 페이지는 또 다시 참조될 가능성이 높다. 따라서 이를 위한 캐쉬로 변환 참조용 버퍼(Translation-Lookaside Buffer, TLB)라고도 한다.
여기서 변환은 가상메모리의 주소 변환을 의미한다. 페이지를 참조할때마다 TLB의 가상 페이지 번호를 같이 검사한다. 만약 TLB에 존재하면, 메모리 접근은 TLB에 저장된 실제 페이지 주소로 접근하는데 한번만 하면 된다. 만약 TLB에 존재하지 않는 경우, 페이지 테이블로 가서 실제 페이지 주소를 찾게 되는 것이다.
1단계 캐쉬로 TLB를 쓰고 2단계 캐쉬로 메모리상의 페이지 테이블을 이용하는 것이다. 페이지 테이블도 TLB도 둘다 공통적으로 플래그 비트로 Valid 비트, Dirty 비트, Reference 비트가 있다. Valid 는 유효 비트로 해당 데이터가 의미가 있는 데이터인지 쓰레기 값인지 판별해준다. Dirty는 갱신 비트로 해당 데이터가 쓰기에 의해 쓰였는지를 판별해준다. Reference 비트는 참조가 되었는지를 보여주는 비트이다. 참조시 TLB를 참조한다고 했는데, 만약 TLB에 원하는 페이지의 주소가 없을 경우에는 페이지 테이블을 참조하여, 실제 페이지의 주소를 TLB에 적재하고, 실제 페이지의 주소를 찾는 것을 동시에 진행한다. 만약 페이지가 페이지 테이블에 조차 없을 경우에는 page fault가 되는 것이고, 예외 처리를 통해서 운영체제가 문제를 해결한다.
(해당하는 페이지의 디스크 주소로 부터 페이지를 메모리에 적재시키고 페이지 테이블을 적재된 메모리의 주소로 업데이트 시키는 것이다.)
페이지 테이블에는 유효 bit를 둔다. 프로세스가 모든 메모리를 항상 참조하는 것은 아니기 때문에 어떤 페이지는 물리 메모리에서 내려둘 수도 있다. 이때는 원래 페이지가 다른 프로세스에 의해 점유될 것이므로 그 메모리 보호를 위해서는 페이지 테이블의 유효 bit만을 고쳐주면 된다.
만약 접근하려는 페이지의 유효 bit가 유효하지 않다고 설정되어 있다면 해당 페이지만을 다시 스왑핑하면 될 것이다. 이는 요구 페이징과도 연관된다.
또한, 페이지를 공유할 수 있다. 시스템 라이브러리와 같이 거의 대부분의 프로세스들이 공유하게 될 메모리는 애초에 공유 페이지로 설정되어 굳이 프로세스마다 중복되게 페이지를 로드하지 말고 이미 로드되어 있는 메모리를 참조하게 하는 것으로 메모리를 절약한다.
페이지 테이블 구조 -> 페이지 테이블이 커서 생긴 문제를 해결하는 방법들
현대 OS는 최소 주소를 32bit로 표현한다. 페이지 크기는 보통 4KB 정도로 설정하는데, 그러면 페이지 테이블은 2의 20승만큼의 항목을 갖게 되고, 항목당 4byte만을 가진다고 해도 페이지 테이블의 크기는 4MB가 된다. 이는 또다시 1024개의 페이지로 구성되어야 함을 뜻한다.
프로세스가 전환될 때마다 페이지 테이블도 전환되어야 하는데 한 번에 이렇게 큰 용량을 전환하는 것은 비용이 너무 크다.
페이지 테이블을 두 단계로 나누는 방법이 있다. 첫 10bit를 외부 페이지 주소로, 다음 10bit를 내부 페이지 테이블 주소로 설정하여 일부 내부 페이지 테이블만을 로드하는 방법이다. 64bit 운영 체제는 52bit를 페이지 번호로 지정하는데, 이 경우 두 단계로 페이지 테이블을 나눈 것도 너무 크기 때문에 세 단계로 나누기도 한다.
다른 접근 방법으로는 페이지 번호를 해싱하여 해시값을 페이지 주소로 사용하는 방법이 있다. 또는, 역 페이지 테이블 접근 방법도 있다. 논리 주소에 프로세스 id를 사용하고, 페이지 테이블에서 pid를 이용하여 페이지를 찾게 한 다음 그 페이지의 테이블상 위치 값을 이용하여 주소를 변환하는 방법이다.
페이지 교체(Page Replacement)
원하는 페이지가 물리 메모리에 존재하지 않으면 어쩔 수 없이 어떤 페이지는 내려놔야 한다. 원하는 페이지가 물리 메모리에 없으면 페이지 폴트(Page fault)가 일어났다고 하고, 물리 메모리에서 내려갈 페이지를 Victim이라고 한다. Victim을 선택하는 알고리즘은 여러 가지가 있다.
LRU(Least Recently Used) 가장 과거에 참조했던 페이지를 victim으로 결정하는 알고리즘이다.
오랫동안 참조하지 않았으면 앞으로도 참조하지 않을 가능성이 높다는 차원에서 그럴듯하다. 문제는 LRU를 구현하는 방법이다.
Counter 방법이나 Stack 방법으로 가능한데, Counter 방법은 페이지에 접근할 때마다 counter를 올리고, victim을 찾을 때 counter가 가장 작은 것을 찾는 방법이다. Stack 방법은 페이지에 접근할 때마다 스택에 페이지 번호를 push 한다. 만약 스택에 이미 그 페이지 번호가 있었다면 꺼내어 다시 top에 푸시한다. 결국 스택의 바닥에 가장 과거에 참조했던 페이지 번호가 위치하게 될 것이다. 문제는 이러한 작업들이 메모리 접근을 할 때마다 이뤄져야 한다는 것이다. 만약 소프트웨어 수준에서 이 방법을 지원하기 위해서는 성능 저하가 너무 심해질 것이다. 따라서 하드웨어의 지원 없이는 불가능하다.
유사 LRU(LRU-Approximation) 알고리즘은 LRU 방식을 일부 적용하는 알고리즘이다. 기본적으로 참조 bit를 따로 둬서 덜 참조된 페이지를 victim으로 결정하는 방식이다.
- Additional-Reference-Bits Algorithm : 참조 bit를 더 많이 두고 bit들을 매번 오른쪽으로 shift하면서 페이지에 접근할 때마다 가장 왼쪽의 bit를 1로 변경한다. 참조 bit들을 정수로 읽었을 때 값이 가장 작은 것이 LRU에 가깝게 될 것이다.
- Second Chance Algorithm : 순환 큐에 페이지 항목들과 참조 bit를 둔다. 참조 bit가 설정되지 않은 페이지는 바로 victim으로 결정되고, 참조 bit가 설정된 페이지는 참조 bit를 초기화한다.
- Enhanced Second-Chance Algorithm : 참조 bit 뿐만 아니라 수정(Dirty) bit를 둔다. 수정된 페이지는 보조 기억 장치에 쓰기 작업이 필요하므로 선택 우선순위에서 떨어진다.
참조 횟수가 가장 적은 페이지를 victim으로 결정하는 LFU 알고리즘(Least Frequently Used)과 참조 횟수가 가장 많은 페이지를 victim으로 결정하는 MFU 알고리즘(Most Frequently Used)도 있다. MFU 알고리즘은 가장 작은 참조 횟수를 가진 페이지가 가장 최근에 참조됐기 때문에 가장 적게 참조됐고, 앞으로 사용될 것이라는 판단에 근거한 알고리즘이다. 그러나 이 알고리즘은 빠르게 수행되게끔 구현이 어려울뿐더러 OPT 알고리즘에 가까운 성능을 보이지도 못하기 때문에 잘 사용되지 않는다.
쓰레싱(Thrashing)
동시에 더 많은 프로세스를 실행한다고 해서 CPU 사용량이 계속 증가하기만 하는 것은 아니다. 아무리 좋은 페이지 교체 알고리즘을 사용하더라도 프로세스들이 메모리를 많이 쓰면 Page Fault가 일어나 Swapping을 할 수밖에 없고, Swapping을 위한 I/O 작업이 많이 발생하면 CPU 사용량이 떨어진다. 이때, CPU 사용량이 급감하기 시작하는 것을 쓰레싱이라고 한다.
커널 메모리 할당
프로세스가 유저 모드에서 실행되면서 추가적인 메모리를 요청하면 커널이 비어있는 페이지 중 하나를 할당해준다.
페이지 하나를 덜컥 할당해주는 것이기 때문에 내부 파편화 문제는 어쩔 수 없이 발생한다. 이는 메모리 할당을 빠르게 해주기 위해 어쩔 수 없다. 메모리 할당은 매우 빈번하게 일어나고 매번 복잡한 알고리즘으로 수행한다면 성능이 떨어질 것이다. 커널 메모리는 유저 모드 프로세스의 메모리 할당과 다르게 메모리 풀을 이용해서 메모리를 할당한다. 커널 메모리를 다른 방식으로 할당하는 이유는 아래 2가지가 중요하다.
커널에서 사용하는 자료 구조들은 크기가 다양하고 페이지보다 용량이 적다. 조심스럽게 메모리 할당을 하지 않음녀 파편화로 인해 메모리를 많이 낭비하게 된다. 많은 OS가 커널 코드나 데이터에는 페이징을 적용하지 않고 있다.
커널(kernel)
컴퓨터의 운영 체제의 핵심이 되는 컴퓨터 프로그램의 하나로, 시스템의 모든 것을 완전히 통제한다.운영 체제의 다른 부분 및 응용 프로그램 수행에 필요한 여러 가지 서비스를 제공한다.핵심이라고도 한다
커널은 컴퓨터 하드웨어와 프로세스의 보안을 책임진다.
- 보안
한정된 시스템 자원을 효율적으로 관리하여 프로그램의 실행을 원활하게 한다. 특히 프로세스에 처리기를 할당하는 것을 스케줄링이라 한다.
- 자원 관리
같은 종류의 부품에 대해 다양한 하드웨어를 설계할 수 있기 때문에 하드웨어에 직접 접근하는 것은 문제를 매우 복잡하게 만들 수 있다. 일반적으로 커널은 운영 체제의 복잡한 내부를 감추고 깔끔하고 일관성 있는 인터페이스를 하드웨어에 제공하기 위해 몇 가지 하드웨어 추상화(같은 종류의 장비에 대한 공통 명령어의 집합)들로 구현된다.
- 추상화
이 하드웨어 추상화는 프로그래머가 여러 장비에서 작동하는 프로그램을 개발하는 것을 돕는다. 하드웨어 추상화 계층(HAL)은 제조사의 장비 규격에 대한 특정한 명령어를 제공하는 소프트웨어 드라이버에 의지한다.
유저 모드 프로세스에게 할당된 메모리는 물리적으로 연속이지 않아도 큰 상관이 없다. 그러나 커널 메모리 공간은 하드웨어 장치로부터 직접적으로 물리 메모리에 접근되기 떄문에 물리적으로 연속적일 필요가 있다.
이러한 이유 때문에 커널 메모리는 다른 전략으로 관리된다. 그 중 Buddy System과 Sla Allocation 방법이 있다.
Buddy System
: 물리적으로 연속된 메모리 공간을 2의 지수로 쪼개어 사용하는 방법이다.
커널에서 요구하는 메모리 크기보다 같거나 큰 덩어리를 할당한다. 예를 들어 21KB를 요청받으면 32KB 덩어리를 할당한다. 형제 노드를 buddy라고 하는데, 형제 노드가 모두 메모리 해제되면 둘은 합병(Coalescing)된다. 이로써 나중에 더 큰 물리적으로 연속된 메모리를 할당할 수 있게 된다. Buddy System 전략으로 메모리를 할당하면 외부 단편화를 해결할 수 있다
Slab Allocation
: 슬랩 단위로 메모리를 관리하면서 내부 단편화를 해결하면서 초기화 속도 등을 향상하는 방법이다.
기본적인 아이디어는 메모리를 커널에서 사용하고 있는 자료 구조들의 객체로 취급하는 것이다. Slab cache 체인은 각각 slab 목록을 포함하는데, 일반적으로 slab 목록은 물리적으로 연속된 메모리이다. slab은 완전히 할당이 완료되었거나(slabs_full), 일부만 할당되었거나(slabs_partial), 비어있는(slabs_empty) 상태 세 가지로 나뉜다. 커널의 자료 구조에 대한 메모리 할당을 요청받으면 Slab allocator는 미리 메모리를 할당해둔 slab 속의 메모리를 준다. 미리 할당해둔 메모리를 주기 때문에 물리 메모리 상의 빈 공간을 찾기 위한 시간이 들지 않고, 메모리를 반환할 때도 Slab allocator에게 반환하여 후에 재활용하기 때문에 실제로 메모리 할당을 위한 비용이 줄어들게 된다.
파일 시스템 (File System)
파일 시스템 구현
파일 시스템은 볼륨마다 boot block, master file table(superblock)을 두고 파일마다 FCB(File Control Block)을 둔다. FCB는 파일에 대한 자세한 정보가 있는 테이블이다. UNIX에서는 inode에 FCB를 저장한다.
시스템에서는 메모리에 마운트 테이블, 최근 접근한 디렉터리 정보 캐시, 시스템 차원의 열린 파일 테이블과 프로세스당 열린 파일 테이블을 관리한다. 아래 사진은 열린 파일 테이블이 어떻게 사용되는지에 대한 그림이다.
VFS
리눅스에서는 VFS(Virtual File System)이라는 추상화 계층을 둔다. 파일 시스템 인터페이스 하에 추상계층을 두고 추상 계층을 통해 각 파일 시스템이 이용된다. 리눅스의 VFS는 inode 객체, 파일 객체, superblock 객체, directory 객체를 기반으로 운영된다.
VFS(Virtual File System)
: 실제 파일시스템에 관계 없이 공통된 인터페이스로 파일시스템에 접근하도록 하는 계층을 가상 파일시스템(Virtual Filesystem Switch, VFS)이라고 한다.
저장 장치의 공간 할당
메모리 때와 마찬가지로 저장 장치의 공간을 할당하는 방법도 고민의 대상이다. 기본적으로 저장 장치는 블록이라는 단위로 나뉜다. 파일을 블록들을 물리적으로 연속하여 위치하도록 하면 당연히 좋겠지만 현실적으로 모든 블록을 연속적으로 두는 것은 어렵다. 각 디스크 블록을 연결된 리스트로 두는 방법도 있다. 하지만 이 방법은 중간 접근을 위해 각 블록을 순차적으로 읽어야 하기 때문에 성능 저하를 일으키게 된다. 곧바로 임의 위치 블록을 찾아 이동할 수 있도록 하기 위해 인덱스를 할당하는 방법이 대안이다. 다만 인덱스를 두는 블록을 어떻게 관리하고 구현할지가 문제가 된다. Linked Scheme, Multi-Level Index, Combined Scheme 등의 접근 방식이 존재한다. 디스크 블록을 읽어 들이는 작업은 매우 느리기 때문에 무엇보다도 디스크 접근을 최소화하는 방법이 성능상의 우위를 보이게 될 것이다. 아래 사진은 UNIX의 inode 관리를 위해 사용되는 Combined Scheme 방식을 보여준다.
성능
파일 시스템에 있어서 성능은 무조건 보조 기억 장치에 접근을 최소화하는 것이다. 파일 시스템에서 읽어온 데이터를 캐시 해두고 있다면 저장 장치에 접근하지 않아도 되기 때문에 성능상에 큰 이득을 볼 수 있게 된다. 디스크 블록을 캐시 해두는 것을 buffer cache, buffer cache를 페이지처럼 쓸 수 있게 따로 연결해두는 것을 page cache라고 한다. buffer cache와 page cache 둘이 중복으로 저장해두는 것은 메모리 낭비를 일으키므로 이를 해결하기 위한 unified buffer cache 방식으로 캐시 하기도 한다. unified buffer cache 방식에서는 memory-mapped I/O와 일반 I/O를 수행할 때 통합된 buffer cache에 접근하게 된다.
page cache를 관리하는 전략으로 Free-behind 방식과 Read-ahead 방식이 있다. 둘은 LRU에 기반한 아이디어로 Free-behind는 다음 페이지를 접근하자마자 이전의 페이지를 내려놓는 방식이다. 이미 읽은 데이터를 다시 필요로 할 가능성이 낮기 때문이다. Read-ahead 방식은 다음 페이지를 미리 읽는 방식이다. 순차적으로 데이터를 읽고 있는 상황에서 다음 페이지에 접근하게 될 가능성이 높다고 예상되기 때문이다.
디스크에 쓰기 작업을 하는 것도 동기 방식과 비동기 방식으로 나뉠 수 있다. 디스크에 쓰기 하려고 할 때 바로 쓰기 작업을 수행하는 것을 동기, 쓰기 요청을 캐시 해뒀다가 좀 더 효율적인 스케줄로 쓰기 작업을 수행하는 것을 비동기 방식이라고 한다. 시스템은 상황에 따라 적절한 방법을 선택할 수 있도록 기능을 제공한다.
'CS > OS' 카테고리의 다른 글
| 프로세스의 컴파일 (0) | 2023.10.15 |
|---|---|
| [OS] CPU란? (0) | 2021.09.08 |
| [OS] 프로세스와 쓰레드 (0) | 2021.08.22 |
| [OS] 메모리 구조(Memory Structure) (2) | 2021.08.21 |
| [OS] 메모리(Memory) (0) | 2021.08.21 |
