[기술면접] 운영체제 면접 대비

반응형

운영체제 면접 대비

운영체제란

운영체제란 하드웨어와 응용프로그램 사이에서 인터페이스 역할을 하며 시스템의 동작을 제어하는 시스템 소프트웨어이다.

• 자원을 효율적으로 관리한다. (자원 관리)
• 추상화된 인터페이스를 통해 프로그램을 사용할 수 있도록 한다. (시스템 관리)

운영체제는 자원 관리자라고 불리며 커널 함수를 실행하면서 스위칭한다.

기능

• 프로세스 관리
  • 프로세스 스케줄링 및 동기화
  • 프로세스 생성 제거, 시작과 정지
  • 스케줄링
  • IPC 통신 : 프로세스들끼리 통신하는 것
• 기억장치 관리
  • 메모리 관리
  • 가상메모리
  • 파일시스템
• 네트워킹
  • TCP/IP 및 기타 프로토콜 지원
• 사용자 관리
  • 계정관리
  • 접근 권한 관리
• 디바이스 드라이버
  • 시스템의 자원, 하드웨어를 관리한다.

프로세스와 스레드의 차이

프로세스 vs 프로그램

프로그램은 passive 객체로서 디스크에 저장되어있다.

프로세스는 active 객체로서 실행 시퀀스에 저장된다.

프로그램은 메모리에 실행 가능한 파일이 적재되는 순간 프로세스가 되며 하나의 프로그램은 여러 개의 프로세스가 될 수 있다.

프로세스 vs 스레드

프로세스랑 운영체제로부터 자원을 할당 받는 작업의 단위이다.

스레드는 프로세스 내부에 위치한 실행 단위이다.

프로세스 안에서 실행되는 여러 단위를 스레드라고 하며 기본적으로 프로세스 마다 메인 스레드를 포함하여 최소 1개의 스레드를 갖는다.

 

	프로세스	스레드
정의	운영체제로부터 자원을 할당 받는 작업의 단위	프로세스 내부에서 실행되는 단위
구성	힙, 데이터, 메모리, 코드	스레드 ID, 프로그램 카운터, 레지스터 집합, 스택
공유	x	데이터 섹션, 코드와 같은 운영체제 자원
생성	느리다. 각각 별도의 주소 공간을 할당 받아야한다.	빠르다. stack만 할당 받고 나머지 자원은 내부 스레드들끼리 공유할 수 있다.
스위칭	오버헤드 더 큼, 바꿔야하는 거 많음	오버헤드 더 작음
독립적	O , 다른 프로세스에게 영향을 받지 않는다.	X, 자원을 공유하기 때문에 다른 스레드에 영향을 받는다.

프로세스

프로세스는 실행 중인 프로그램으로 운영체제로 부터 자원을 할당 받는 작업의 단위를 말한다. 프로세스는 운영체제로부터 주소공간, 파일, 메모리 등을 할당 받는다.

구성

• 스택 : 함수의 매개변수, 지역변수, 반환 주소와 같은 임시 자료가 저장된다.
• 힙 : 프로세스 실행 중에 동적으로 할당되는 메모리이다.
• 데이터 : 전역 변수들을 저장한다.
• 코드 : 코드 자체를 구성하는 메모리 영역이다.

call stack

함수의 실행 순서를 제어하기 위해 흔히 스택을 사용한다. 프로그램의 서브루틴 정보를 저장하는 스택 데이터 구조이다. OS에서는 그냥 스택이라고 부른다.

• 반환 주소
• 결과값
• 매개변수

stack 포인터를 가지고 현재 스택의 top을 가리킨다. 스택은 frame으로 이루어져 있는데 frame의 크기는 가변이기 때문에 이전 frame의 주소를 가리키는 current frame pointer도 사용한다.

스레드

프로세스의 실행단위

하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것을 멀티스레딩이라고 한다. 이 경우 각각의 스레드는 독립적인 작업을 수행해야하기 때문에 각자의 스택과 PC 레지스터 값을 가지고 있다.

스택 각자 가지고 있는 이유

스택은 함수 호출시 매개변수, 지역수, 반환 주소 등 임시 자료를 저장하기 위한 메모리 공강니므로 스택 메모리 공간이 독립적이야 독립적인 함수 호출이 가능하다.

PC register 각자 가지고 있는 이유

스레드가 명령어의 어디까지 수행했는지를 저장하기 때문에 독립적이어야 스레드가 CPU를 할당 받았다가 스케줄러에 의해 선점 당했을 경우 나중에 나머지를 완료할 수 있다.

멀티 스레드

프로세스를 이용하여 동시에 처리하던 일을 스레드로 구현할 경우 메모리 공간과 시스템 자원의 소모가 줄어들게 된다. 스레드는 할당 자원들은 내부 스레드끼리 공유하면서 실행하기 때문이다. 프로세스의 경우 IPC를 이용해 통신하지만 스레드의 경우 별도의 자원을 사용하지 않고 전역 변수의 공간이나 힙 영역을 공유하여 데이터를 주고 받을 수 있기 때문에 시스템 콜과 통신 비용이 줄어들게 된다. 스레드의 context switch의 경우에도 캐시메모리를 비울 필요가 없기 때문에 더 빠르다.

따라서 시스템의 처리 능력이 향상되고 자원 소모가 줄어들어 프로그램의 응답 시간도 단축된다.

단 멀티 프로세스 기반일 때는 프로세스 간 공유 자원이 없기 때문에 동일한 자원에 동시에 접근하는 일이 없었지만 멀티 스레드 기반의 경우 서로 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 어떤 스레드가 다른 스레드가 사용 중인 변수나 자료구조에 접근하여 엉뚱한 값을 읽어오거나 수정할 수 있다.

따라서 동기화 문제에 신경써야한다. 즉 작업의 처리 순서를 컨트롤하거나 공유 자원에 대한 접근을 컨트롤한다. 하지만 이로 인해 병목 현상이 발생해 성능이 저하될 수 있기 때문에 과도한 락으로 인한 병목 현상이 생기지 않도록 주의해야한다.

싱글 스레드 vs 멀티 스레드

 

	싱글 스레드	멀티 스레드
동작	하나의 프로세스에서 하나의 스레드 실행	하나의 프로세스에서 여러 개의 스레드 실행하며 자원을 공유한다.
장점	동기화 문제에 신경쓰지 않아도 된다. context switch가 필요 없다	여러 작업을 동시에 처리할 수 있다.
단점	여러 CPU를 활용하지 못한다.	동기화 문제에 신경 써야한다. context switch에 시간이 걸릴 수 있기 때문에 오히려 싱글 스레드보다 느릴 수 있다.
예시	Node.js 자바스크립트를 실행하는 스레드는 하나이기 때문에 Node를 싱글 스레드라고 하며 바로 이벤트 루프이다.	여러 요청을 동시에 처리하는 웹 서버의 대부분 (대표적으로 스프링), 여러 client들에게 요청이 날아왔을 때 사용자가 원하는 작업을 바로 할 수 있다.

Node.js가 싱글 스레드?

자바스크립트 엔진은 memory heap과 call stack으로 이루어져있다. 자바스크립트 엔진 자체는 콜 스택에 쌓인 실행 컨텍스트에 따라 위에서부터 차례로 실행이 일어나는 곳이기 때문에 비동기 처리를 할 수 없다.

비동기 처리가 필요할 경우 Node api를 통해 libuv 라이브러리에서 제공하는 비동기처리를 하게 된다.

Node.js는 싱글 스레드 논블로킹 모델이다. 하나의 스레드로 동작하지만 비동기 I/O 작업을 통해 요청들을 서로 블로킹하지 않는다. 따라서 어떤 작업이 수행 중일 때 다른 작업을 할 수도 있다. 즉 동시에 많은 요청들을 비동기로 수행함으로써 싱글 스레드임에도 불구하고 논블로킹이 가능하다.

스케줄러의 종류

프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업이 스케줄링이다. CPU나 자원을 효율적으로 사용하기 위한 정책으로 오버헤드를 줄이고 CPU 사용률을 높여 기아 현상을 줄이는 것을 목표로 한다.

크게 3가지로 나눌 수 있다.

장기 스케줄러

메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리에 임시로 저장된다. 장기 스케줄링은 이 중에 어떤 프로세스를 메모리에 할당하여 ready queue로 보낼지 결정하는 역할을 한다. 즉 system에 프로그램이 들어갈지 아닐지를 결정한다.

• 프로세스에 각종 리소스를 할당
• 메모리와 디스크 사이의 스케줄링을 담당
• multiprogramming 정도 제어
• 프로세스 상태를 new => ready

중기 스케줄러

어떤 프로세스들이 CPU를 할당 받을 것인지를 결정하는 작업을 의미한다. CPU를 할당 받을 프로세스가 많을 경우 프로세스를 suspend 시킨 후 메모리에서 디스크로 swap out한다. 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라는 것을 조절하는 스케줄러이다.

프로세스의 상태를 ready => suspend

단기 스케줄러

CPU에 의해 실행될 프로세스를 결정한다.

• CPU와 메모리 사이의 스케줄링
• ready queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
• 프로세스의 상태를 ready => running => waiting => running

CPU 스케줄러

FCFS

• 비선점형
• 선입선출
• 짧은 프로세스에 효과적이다.
• convy effect: 소요시간이 긴 프로세스가 먼저 도착해 효율성을 낮추는 현상이 생길 수 있다.

SJF

• 비선점형
• CPU burst time이 가장 짧은 프로세스에게 먼저 할당
• Starvation: 짧은 프로세스가 계속 들어오면 긴 프로세스는 프로세서를 할당 받지 못하고 굶어 죽을 수도 있다.

SRT

• 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 burst time을 가진 프로세스가 도착하면 CPU를 뺏긴다.

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형 스케줄링

RR

timer를 기반으로 선점한다. 각 프로세스들은 동일한 길이의 할당 시간(time quantum)을 갖게 된다. 할당 시간이 지나면 프로세스는 선점 당하고 다시 ready queue 뒤에 들어가 줄을 선다. 사용 시간이 랜덤한 프로세스가 섞여 있을 경우 효과적이다. 프로세스의 context를 저장할 수 있기 때문에 가능하다.

• 응답 시간이 빨라진다.
• 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다.
• 할당 시간이 너무 커지면 FCFS와 같아지고 너무 작으면 context switch가 자주 일어나 오버헤드가 발생한다.

동기와 비동기의 차이

Race Condition

스레드에 의해서 공유 자원에 접근한 결과가 스케줄러에 의한 접근 타이밍에 의존해 결정되는 상태이다. 결과를 예측할 수 없고 싱글 프로세스이든 멀티 프로세스이든 발생 할 수 있다.

프로세스 동기화

멀티 스레드 프로그램에서 스레드들은 자원을 공유하며 협력한다. 이때 공유 자원 접근 시에 동기화가 보장되지 않으면 Race condition이 발생할 수 있고 부정확한 결과로 이어진다. 이를 방지하기 위한 방법을 동기화라고 한다.

공유 자원을 어떠한 프로세스가 사용하고 있을 경우 값이 반환되기 전까지 blocking 하는 것을 말한다. 즉 critical section에 대한 상호 배제를 제공해 race condition을 회피하는 방법이다.

임계 구역 문제 (Critical Section Problem)

동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역을 critical section이라고 한다. 만약 모든 스레드가 read만 할 경우에는 race condition이 발생하지 않는다. 임계 구역 문제는 프로세스들이 critical section을 함께 사용할 수 있는 프로토콜을 설계하는 것이다.

해결을 위한 3가지 조건

• 상호배제 : 한번에 하나의 쓰레드만 임계 구역에 접근할 수 있도록 보장하는 것이다.
• 진행 조건 : 임계구역에서 실행 중인 프로세스가 없을 때, 별도의 동작이 없는 프로세스들만 임계 구역의 진입 후보로서 참여될 수 있다.
• 한정 대기 : 모든 프로세스의 대기가 언젠가는 끝나야한다. starvation이 일어나서는 안된다.

해결방안

Spin Lock

busy waiting에 의해 lock되는 것을 spin lock이라고 한다. busy waiting은 대기를 하는 동안 실제 작업 없이 CPU를 계속 사용하여 대기하는 것이다. 자원이 낭비되며 fairness를 보장하지 않아 starvation이 일어날 수 있다. 또한 다중 쓰레드가 데이터를 공유하는 과정에서 명령어의 순서를 바꿔버리면 상호 배제 조건이 충족되지 않는다는 한계가 있다.

Disabling Interrupt

싱글 프로세서 시스템의 경우 어떤 프로세스가 임계 영역에 들어갔을 때 나머지 인터럽트를 disable하는 방법이다. interrupt가 lost 될 수 있고 멀티 프로세스에서는 사용할 수 없으며 비효율적이다. 고의적인 프로그램에 의해 privileged operation이 남용될 수 있다.

Mutex Lock

동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section에 진입하는 프로세스는 Lock을 획득하고 Critical Section을 빠져나올 때, Lock을 방출하므로써 동시에 접근되지 않도록 한다. Binary Semaphore라고도 불린다. 세마포어가 locked / unlocked로 0 또는 1의 정수 값만 가질 수 있기 때문이다.

다중 쓰레드 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.

Semaphore

세마포어는 프로그램 레벨에서 쉽게 상호 배제시키기 위해서 2개의 primitive operation과 하나의 공통으로 관리하는 값(세마포어)를 사용한 기법이다. 진입에 실패한 프로세스에 대해서 Lock 시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식으로 Busy waiting을 해결했다.

• 카운팅 세마포어: 가용한 개수을 가진 자원에 대한 접근 제어용으로, 세마포어는 그 가용한 자원의 개수로 초기화된다. 자원을 사용하면 세마포어가 감소, 방출하면 세마포어가 증가한다.
• 이진 세마포어

한계

• 데드락이 발생할 수 있다. (두 개 이상의 프로세스들이 실행 되지 못하는 상태로 서로의 점유하고 있는 자원을 기다리면서 실행 되지도 종료되지도 못하는 상태에 빠진 것을 말한다.)
• 프로그램에 흩어져 있어서 디버깅하기가 어렵다.

Monitor

세마포어의 단점을 보완한 고급 언어의 설계 구조물로서 개발자의 코드를 상호 배제하게끔 만든 추상화된 데이터 형이다. 직접 키 해제와 공유 자원 접근 처리가 필요한 세마포어와 달리 공유 자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다.

생산자, 소비자 문제

생산자가 데이터를 생산하면 소비자는 그것을 소비하는 형태에서 발생하는 문제를 말한다. 일반적으로 멀티 쓰레드 웹 서버를 예로 들 수 있다.

생산자와 소비자의 속도 차이를 보완하기 위해 버퍼라는 공간을 활용한다. 생산자는 데이터를 생산해 버퍼를 채운다. 버퍼가 가득 차면 생산자는 더 이상 생산을 할 수 없다. 소비자는 버퍼에서 데이터를 꺼내 소비한다. 버퍼가 비어 있으면 소비자는 소비를 할 수 없다.

해결 방안

• 생산자, 소비자는 공유 자원을 이용하고 관리를 위해 상호 배제여야한다.
• 공유 자원의 상태를 체크해야한다.

메모리 관리 전략

각각의 프로세스는 독립된 메모리 공간을 갖고, 운영체제 혹은 다른 프로세스의 메모리 공간에 접근할 수 없는 제한이 걸려있다. 단지, 운영체제만이 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 제약을 받지 않는다.

아래의 역할을 한다.

• allocation
• relocation
• protection
• sharing

swapping

메모리의 관리를 위해 사용되는 기법. 표준 swapping 방식으로는 rr과 같은 스케줄링의 다중 프로그래밍 환경에서 CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억장치로 내보내고 다른 프로세스의 메모리로 불러들일 수 있다. 이 과정을 swap이라고 하며 주기억 장치로 불러오는 과정을 swap-in, 보조 기억장치로 내보내는 과정을 swap-out이라고 한다. swap에는 큰 디스크 전송이 필요하기 때문에 현재에는 메모리 공간이 부족할 때 swapping이 시작된다.

메인 메모리

메인 메모리는 CPU가 직접 접근할 수 있는 기억 장치이다. 프로세스가 실행되려면 프로그램이 메모리에 올라와야한다. CPU는 레지스터가 지시하는대로 메모리에 접근하여 다음에 수행할 명령어를 가져온다. 명령어 수행 시 메모리에 필요한 데이터가 없으면 해당 데이터를 우선 가져와야한다. 이때 MMU가 사용된다.

MMU (Memory Managment Unit)

mmu는 논리적 주소를 메인 메모리의 물리적 주소로 변환해주는 역할을 한다. 또한 메모리 보호나 캐시 관리 등 CPU가 메모리에 접근하는 것을 총 관리해주는 하드웨어이다.

• 논리적 주소 : 프로세스 또는 프로그램 안에 위치하며 어떤 논리적 주소의 상대적주소이다. 메모리 공간이 한정적이기 때문에 사용자에게 더 많은 메모리를 제공하기 위해 등장하였다.
• 물리적 주소 : 메인 메모리에 존재하는 실제 주소이다.

relocation

가상 주소를 통해서 실제 데이터가 담겨 있는 곳에 접근하기 위해서는 빠른 주소 변환이 필요한데 이를 MMU가 도와준다.

protection

메인 메모리의 크기는 한정되어 있기 때문에 해당 크기를 넘어가면 잘못된 주소를 참조하게 된다. 또한 만약 멀티 프로세싱 시스템일 경우 메모리에 여러 프로세스들이 들어 있기 때문에 서로 독립된 공간을 가지며 자신을 제외한 공간을 침범해서는 안된다. 이를 위해 MMU는 limit register를 두어 주소의 영역을 제한하고 잘못된 접근이 오면 Trap을 발생시키며 메모리를 보호한다. 이를 memory protection이라고 한다.

주기억장치 할당 방식

단편화 (Fragmentation)

프로세스들이 메모리에 적재되고 제거되는 일이 반복되다보면, 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할 만큼의 작은 자유 공간들이 늘어나게되는데, 이것이 단편화이다.

• 외부 단편화 : 메모리 공간 중 사용하지 못하게 되는 일부분
• 내부 단편화 : 프로세스가 사용하는 메모리 공간에 포함된 남는 부분

외부 단편화를 해결하기 위해서 프로세스가 사용하는 공간들을 한 쪽으로 몰아, 자유 공간을 확보하는 방법으로 압축(memory compaction)이 있지만 CPU 시간 낭비 문제가 발생하기 때문에 비효율적이다.

불연속 할당 기법

메모리를 불연속으로 분할하여 할당해주는 기법으로 페이징 기법과 세그먼트 기법이 있다.

Paging

하나의 프로세스가 사용하는 메모리 공간이 연속적이어야한다는 제약을 없애는 메모리 관리 방법이다. 외부 단편화와 압축 작업의 문제점을 해소하기 위해 생긴 방법이다.

물리 메모리는 Frame이라는 고정 크기로 분리되어 있고, 논리 메모리는 페이지라 불리는 고정 크기의 블록으로 분리된다.

프로그램을 고정 길이로 나눈 단위를 페이지라고 하고, 페이지 크기로 일정하게 나누어진 메인 메모리의 단위를 페이지 프레임이라고 한다.

페이징 기법을 사용함으로써 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 프레임에 적절히 배치됨으로 외부 단편화를 해결할 수 있는 큰 장점이 있다.

하나의 프로세스가 사용하는 공간은 논리 메모리에서 여러 개의 페이지로 나뉘어서 관리되고 개별 페이지는 순서에 상관 없이 물리 메모리에 있는 프레임에 mapping되어 저장된다. 이 때 매핑 정보를 알기 위해 page table을 사용하며 인덱스는 페이지 번호이고 각각 frame 번호 정보를 가지고 있다.

단점은 내부 단편화의 비중이 늘어나게 된다는 것이다.

Segmentation

가상 메모리에 보관되어 있는 프로그램을 가변 길이의 논리적인 단위로 나눈 후 메인 메모리에 적재시켜 실행시키는 기법이다. 논리 메모리와 물리 메모리를 서로 다른 크기의 논리적 단위인 세그먼트로 분할한다.

세그먼트는 논리적 영역으로 분할되기 때문에 코드 영역에는 코드 영역만 들어가고, 중요한 프로세스와 중요하지 않는 프로세스로 구분되기 때문에 보호와 공유의 기능을 수행하기도 쉬워져 오버헤드를 줄일 수 있다.

만약 같은 프로그램을 사용하는 프로세스 여러개가 서로 다른 기능을 수행하기 위해 존재한다면 모두 메모리에 적재하는 것은 낭비일 것이다. 따라서 하나만 메모리에 모두 적재한 후 다른 프로세스들은 해당 프로세스의 코드 영역을 공유한다.

가상 메모리

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야한다. 가상 메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.

배경

프로그램의 일부분만 메모리에 올릴 수 있다면

• CPU의 용량보다 큰 프로세스를 실행할 수 있다.
• 더 많은 프로그램을 동시에 실행할 수 있게 된다. 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다.
• swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.

가상 메모리가 하는 일

가상 메모리는 실제 물리 메모리 개념과 논리 메모리 개념을 분리한 것이다. 용량이 작은 메인 메모리를 마치 큰 용량을 가진 것처럼 사용할 수 있다. 프로그램을 여러 개의 작은 블록 단위로 나누어서 가상 메모리에 보관해놓고 실행 시 요구되는 블록만 메인 메모리에 불연속적으로 할당하여 처리한다.

Demand Paging (요구 페이징)

프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리로 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라고 하며, 가상 메모리 시스템에서 많이 사용된다. 가상 메모리는 대개 페이지로 관리되는데, 요구 페이징을 사용하는 가상 메모리에서는 실행 과정에서 필요해질 때 페이지들이 적재된다. 한번도 접근되지 않는 페이지는 물리 메모리에 적재되지 않는다.

프로세스 내의 개별 페이지들은 페이저에 의해 관리된다. 페이저는 프로세스 실행에 필요한 페이지들만 메모리로 읽어 사용되지 않을 페이지를 가져오는 시간 낭비와 메모리 낭비를 줄일 수 있다.

페이지 교체 알고리즘

프로그램 실행 시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 페이지 부재가 발생하게 되면, 원하는 페이지를 보조 저장 장치에서 가져오게된다. 하지만 만약, 물리 메모리가 모두 사용 중인 상황이라면 페이지 교체가 이뤄져야한다. 이때 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법이 페이지 교체 알고리즘이다.

페이지 교체가 발생해도 프로세스를 계속 수행시켜주면서 사용자가 알지 못하도록 해야한다. 이를 위해서는 페이지 교체시에 오버헤드를 최대한 줄여야한다.

오버헤드가 발생하는 이유?

어떤 프레임을 선택해서 비울 때, 해당 프레임에 페이지를 올릴 때, 이렇게 두 번의 디스크 접근이 이루어지기 때문에 페이지 교체가 많아지면 입출력 연산이 많이 발생하게 되면서 오버 헤드 문제가 발생하게 된다.

흐름

1. 디스크에서 필요한 페이지의 위치를 찾는다.
2. 빈 페이지 프레임을 찾는다.
   1. 페이지 교체 알고리즘을 통해 희생될 페이지를 고른다.
   2. 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정한다.
3. 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다.
4. 사용자 프로세스 재 시작

종류

• OPT : 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법, 구현 어려움
• FIFO : 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다.
• LRU : 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.
• LFU : 사용 빈도가 가장 적은 페이지를 교체하는 기법이다.
• NUR : 최근에 사용하지 않은 페이지를 교체하는 기법이다.

캐시의 지역성

캐시 메모리는 속도가 빠른 장치와 느린 장치 간의 속도 차에 따른 병목 현상을 줄이기 위한 범용 메모리이다. 이렇나 역할을 수행하기 위해서는 CPU에 어떤 데이터를 원할 것인가를 어느 정도 예측할 수 있어야한다. 캐시의 성능은 작은 용량의 캐시 메모리가 CPU가 이후에 참조할, 쓸모 있는 데이터가 얼마나 들어 있느냐에 따라 좌우된다.

CPU와 주기억 장치의 속도 차이로 성능 저하를 방지하기 위해 주기억 장치에 저장된 내용의 일부를 임시로 저장해둔다.

Locality

지역성이란 기억 장치 내의 정보를 균일하게 Access하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 성질이 있다는 이론이다.

• 시간 지역성 (Temporal Locality): 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성
• 공간 지역성 (Spatial Locality): 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

Caching line

캐시는 프로세서 가까이에 위치하면서 빈번하게 사용되는 데이터를 놔두는 장소이다. 하지만 찾고자 하는 데이터를 찾기 위해 모든 데이터를 순회해야한다면 시간이 오래 걸리게 된다. 즉 캐시에 목적 데이터가 저장된다면 바로 접근하여 출력할 수 있어야 캐시가 의미 있어진다.

따라서 캐시에 데이터를 저장할 때 특정 자료구조를 사용하여 묶음으로 저장하게 되는데 이를 캐싱라인이라고 한다. 프로세스는 다양한 주소에 있는 데이터를 사용하므로 빈번하게 사용하는 데이터의 주소도 흩어져있다. 따라서 캐시에 저장하는 데이터에는 데이터의 메모리 주소 등을 기록해둔 태그를 달아 놓을 필요가 있다. 이러한 태그들의 묶음을 캐싱 라인이라고 하고 메모리로부터 가져올 때도 캐싱 라인을 기준으로 가져온다. 3가지 방식이 존재한다.

• Direct Map
• Full Associative
• Set Associative

PCB와 Context Switching, System Call

Context

CPU가 해당 프로세스를 실행하기 위해 필요한 정보들을 컨텍스트라고 한다.

Sytem-level Context

OS가 프로세스를 관리하기 위해 필요한 정보를 포함한다.

• PCB
  • 프로세스 식별
  • 프로세스 상태 정보
  • 프로세스 제어 정보

User-level Context

프로세스가 실행되는 동안 CPU는 스택을 사용하여 사용자 프로그램의 기본 요소 text와 data영역을 포함한다.

• User text
• User data
• User stack

HW Context

• 레지스터들

Process Context

PCB

PCB는 특정 프로세스에 대한 중요한 정보를 저장하고 있는 운영체제의 자료구조이다. 운영체제는 프로세스를 관리하기 위해 생성과 동시에 고유한 PCB를 생성한다.

프로세스는 CPU를 할당 받아 작업을 처리하다가도 프로세스 전환이 발생하면 진행하던 작업을 저장하고 CPU를 반환해야한다. 이러한 작업의 진행 상황을 모두 PCB에 저장하게 된다. 그리고 다시 CPU를 할당 받게 되면 PCB에 저장되어 있던 정보를 불러와 이전에 종료되었던 시점부터 다시 작업을 수행한다.

PCB는 Process Image에 포함되어 있는데 Process Image란 CPU가 프로세스를 컨트롤 하기 위해 각 프로세스에 대한 정보를 저장해놓은 것이다. User level의 context와 System level의 context가 합쳐진 것으로 User data, User Program, Stack, PCB를 포함한다.

Kernel

메모리에 항상 상주해 있는 OS 영역

프로세스 관리, 동기화, CPU 스케줄링, 메모리 관리, 디바이스 관리, 인터럽트 처리 등의 함수들(커널 서비스)들을 시스템 콜을 통해 제공한다.

Utility (User Program)

명령, OS 디스크 영역에 상주 (요청 시에 적재됨)

시스템 콜

운영체제는 Dual Mode로 구성 되어 있다. kernel 모드와 user 모드이다.

이 두가지로 모드를 나누는 이유는 시스템을 보호하기 위해서이다. kernel 모드만이 I/O와 같은 privileged op-code를 사용할 수 있다.

이슈를 만들어 커널모드로 진입할 수 있는 방법은 3가지이다.

• Interrupt
• Trapp
• System call
  • 시스템 자원을 보호하기 위해 사용한다.
  • 신뢰성을 위해 사용한다. : 유저 프로그램의 버그 발생 방지
  • 보안을 위해 사용한다. : 악의적인 유저 프로그램이 OS나 다른 자원을 허가 없이 읽지 못하도록 한다.

이 중 시스템 콜은 커널 서비스를 유저 프로그램이 요청하고 받을 수 있게 하는 것이다. 유저 모드에서 커널 모드 서비스를 사용하고 싶을 때 시스템콜을 호출한다. 이렇게 유저 모드에서 커널 모드로 프로세스를 변경하는 것을 모드 스위칭이라고 한다.

컨텍스트 스위칭 = 프로세스 스위칭 (Context Switching = Process Switching)

프로세서를 하나의 프로세스에서 다른 프로세스로 스위칭하는 것을 말하며 Mode switching을 전제로 한다. (커널 모드인 상태)

• 현재 프로세스의 프로세서 정보를 저장한다. (작업 어디까지 했는지)
• PCB에 프로세스의 상태를 변경한다. (Ready, Block 등)
• 현재 프로세스의 PCB를 적절한 큐로 이동한다.
• 실행할 다른 프로세스를 선택한다.
• 선택한 프로세스의 PCB에 프로세스 상태를 Running으로 변경한다.
• 메모리 관리를 위해 TLB(최근에 일어난 가상 메모리 주소와 물리 주소의 변환 테이블) 를 업데이트한다.
• 선택한 프로세스의 프로세서 정보를 복구한다.

컨텍스트 스위칭은 언제 일어날까?

• Timer Interrupt
• System Call
• Exception

즉 커널이 컨트롤을 가질 때 발생한다.

데드락(DeadLock)

2개 이상의 프로세스들이 서로의 자원을 얻지 못해서 진행할 수 없는 상황을 말한다.

프로세스에게 한정된 자원이 할당되었을 때 프로세스들의 자원 부족으로 더 이상 실행할 수도 없으며, 종료 후에 다른 작업을 시작하는 것도 불가능한 상태를 말한다.

block된 프로세스들은 각각의 자원을 가지고 다른 프로세스가 점유한 자원을 얻기를 기다리고 있는 상태이다.

데드락 발생 조건

• 비선점 : 어떤 자원은 그 자원을 점유한 프로세스에 의해 자발적으로만 방출된다. 중간에 다른 프로세스가 강제로 뺏을 수 없다.
• 점유 대기 : 프로세스는 적어도 하나의 자원을 점유한 채로 다른 프로세스에 의해 점유된 다른 자원을 추가적으로 얻기를 기다리고 있어야한다.
• 순환 대기 : 스레드와 자원이 순환적으로 꼬리를 물고 기다리는 구조이다.
• 상호 배제 : 하나의 자원에는 한 번에 하나의 프로세스만 점유할 수 있다.

해결 방법

예방 기법

데드락 발생 조건 중 하나라도 만족하지 않도록 하여 데드락을 해결하는 방식이다.

자원 낭비가 심하다.

회피 기법

시스템의 요청에 의해 어떤 자원을 할당하기 전에 데드락이 발생할 수 있는 상태인지 확인하고 발생하지 않을 경우만 승인하여 데드락을 해결하는 것을 데드락 회피라고 한다. 은행원 알고리즘이 대표적이다.

탐지 & 회복 기법

데드락을 주기적으로 체크한 후 데드락된 프로세스를 죽이고 리소스를 방출하는 것으로 회복하여 데드락을 해결 한다.

탐지

자원 할당 그래프를 통해 교착 상태를 탐진한다. 자원 요청시, 탐지 알고리즘을 실행시키기 때문에 그에 대한 오버헤드가 발생한다.

회복

교착 상태를 일으킨 프로세스를 종료하거나, 할당한 자원을 해제시켜 회복한다.

• 프로세스 종료
• 자원 선점 방법

 

 

파일시스템

파일

컴퓨터에서 의미가 있는 정보를 담은 논리적인 단위

블록이란 하드디스크와 데이터를 주고 받을 때 사용되는 논리적 단위이다.

파일을 하나 생성할 때 디스크에는 메타데이터와 데이터가 저장되어야 한다.

• 메타데이터 : 파일의 길이, 마지막으로 수정한 시각, 접근 권한 ...
  • inode로 저장되며 inode는 inode 블록에 저장된다.
• 데이터 : 실제로 가지고 있는 내용
  • 데이터 블록에 저장된다.

파일시스템이 필요한 이유

파일들을 효율적으로 관리하고 쉽게 사용할 수 있도록 하기 위해서

파일 시스템의 기능

• 파일의 할당
• 파일의 접근
• 파일의 보호
• 파일의 일관성

접근 방식

순차 접근

파일 정보가 레코드 순서대로 처리된다.

현재 위치에서 읽거나 쓰면 offset이 자동으로 증가하고, 뒤로 돌아가기 위해서는 되감기가 필요하다.

직접 접근

파일의 레코드를 임의의 순서로 접근할 수 있다.

색인 접근

파일에서 레코드를 찾기 위해 색인을 먼저 찾고 대응되는 포인터를 얻는다. 이를 통해 파일에 직접 접근하여 원하는 데이터를 얻을 수 있다. 크기가 큰 파일에서 유용하다.

디렉토리

디렉토리는 파일의 메타 데이터 중 일부를 보관하고 있는 일종의 특별한 파일이다. 해당 디렉토리에 속한 파일 이름과 속성들을 포함하고 있고, 다음과 같은 기능들을 제공한다.

• 파일 찾기
• 파일 생성
• 파일 삭제
• 디렉토리 나열
• 파일 재명명
• 파일 시스템 순회

디렉토리 구성

1단계 디렉토리

모든 파일들이 디렉토리 밑에 존재하는 형태

파일들은 서로 유일한 이름을 가지고 서로 다른 사용자라도 같은 이름을 사용할 수 없다.

파일이 많아질 경우 비효율적이다.

2단계 디렉토리

각 사용자 별로 별도의 디렉토리를 갖는 형태이다.

• UFD : 자신만의 사용자 파일 디렉토리
• MFD : 사용자의 이름과 계정 번호로 색인되어 있는 디렉토리. 각 엔트리는 사용자의 UFD를 가리킨다.

서로 다른 사용자가 같은 이름의 파일을 가질 수 있고 효율적인 탐색이 가능하다. 하지만 그룹화가 불가능하고, 다른 사용자의 파일에 접근해야하는 경우에는 단점이 된다.

트리 구조 디렉토리

사용자들이 자신의 서브 디렉토리를 만들어서 파일을 구성할 수 있다. 하나의 루트 디렉토리를 가지며 모든 파일은 고유한 경로를 가진다. 이를 통해 효율적인 탐색이 가능하고, 그룹화가 가능하다.

디렉토리는 일종의 파일이므로 일반 파일인지 디렉토리인지 구분할 필요가 있다. 이를 bit를 이용하여 0이면 일반 파일, 1이면 디렉토리로 구분한다.

비순환 그래프 디렉토리

디렉토리들이 서브 디렉토리들과 파일을 공유할 수 있도록 한다.

일반 그래프 디렉토리

순환을 허용하는 그래프 구조이다. 순환이 허용되면 무한 루프에 빠질 수 있다.

따라서, 하위 디렉토리가 아닌 파일에 대한 링크만 허용하거나 garbage collection을 통해 전체 파일 시스템을 순회하고 접근 가능한 모든 것을 표시한다.

디스크에 할당 방법

파일 데이터를 디스크에 할당하는 방법은 3가지이다.

• 연속 할당
  • 파일을 디스크에 연속되게 저장한다.
  • 외부 단편화가 발생한다.
• 연결 할당
  • 연속적으로 할당하지 않고 빈 위치면 자유롭게 할당할 수 있다.
  • 외부 단편화는 발생하지 않지만 포인터 배정을 위한 공간이 할당되어야한다.
• 색인 할당
  • 한 블록에 하나의 파일에 대한 데이터의 index들을 모두 저장하는 방식이다.
  • 외부 단편화가 발생하지 않으며 random access가 가능하다.
  • 작은 파일인 경우 블록 공간 낭비, 큰 파일일 경우 하나의 블록으로 파일 index를 모두 저장하기 부족한 문제가 있다.

https://rebro.kr/181