[전공 복습] 1-2. 운영체제

1-2. 운영체제

스케줄링

 

장기 스케줄링

준비 큐에 어떤 프로세스를 넣을지 결정하여 메모리에 올라가는 프로세스를 조절한다.

 

중기 스케줄링

메모리에 올라온 프로세스의 수를 동적으로 조절한다.

스왑 아웃으로 프로세스를 디스크에 저장하거나 스왑 인으로 저장했던 프로세스를 메모리로 다시 올린다.

스왑 아웃된 프로세스는 중단 상태가 된다.

 

단기 스케줄링

준비 큐에 있는 프로세스 중에 실행할 프로세스를 결정한다.

 

위 그림에는 장기, 중기, 단기 스케줄링을 나타내고 있다.

 

위 그림은 스케줄러 관점에서 스케줄링을 표현하고 있다.

실행 상태에서 준비 큐나 대기 큐로 전환됨을 확인할 수 있다.

 

비선점형 스케줄링

 

실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없다.

다음의 종류가 있다.

• FCFS: 준비 큐에 들어온 순서대로 처리한다.
• SJF: 실행 시간이 짧은 프로세스가 우선권을 갖는다. 실행 시간이 긴 프로세스는 영원히 밀려날 수 있다.

 

선점형 스케줄링

 

스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있다.

 

Round Robin

정해진 time slice만큼 실행하고 다음 프로세스로 넘어간다. 우선순위가 없다.

컨텍스트 스위칭이 빈번하게 일어나지만 모든 프로세스가 반복 수행되어 응답속도가 빠르다.

 

SRTF, Shortest Remaining Time First

준비 큐에서 남은 시간이 가장 짧은 프로세스를 우선 수행하는 알고리즘이다.

평균 대기 시간이 짧아지지만, 남은 시간이 길다면 영원히 실행되지 않을 수 있다.

이처럼 영원히 실행되지 않는 것을 기아 상태(starvation)이라고 한다.

 

멀티 레벨 스케줄링

준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다.

각 큐는 우선순위를 가지고 있고 각자 다른 알고리즘을 적용할 수 있다.

 

메모리 관리 전략

 

cpu가 바라보는 메모리 주소 값과 실제 메모리의 주소 값은 다르다.

전자를 논리 주소이라고 하고 후자를 물리 주소이라고 한다.

 

그리고 실제 데이터에 접근하기 위해서 논리 주소를 물리 주소로 전환해야 하는데,

이러한 동작을 메모리 관리 장치(MMU, Memory Management Unit)이라고 한다.

메모리 관리 장치는 cpu에 위치한다.

 

비연속 메모리 할당

 

프로세스의 메모리 영역을 나누어 메모리 공간에 저장하는 방법이다.

페이징과 세그멘테이션이 있다.

 

페이징, paging

 

프로세스의 논리 메모리 영역과 물리 메모리 영역을 각각 일정한 크기의 페이지와 프레임으로 나눈다.

이 때, 페이지와 프레임의 크기는 동일하다.

 

페이지와 프레임을 매핑하기 위해서 페이지 테이블을 사용한다.

페이지 테이블은 프로세스의 페이지 정보와 대응되는 프레임의 주소 값을 저장한다.

페이지 테이블은 pcb에 저장된다.

또한, 페이지 순서대로 대응되는 프레임 주소 값만 가지면 되므로 하나의 배열로 표현할 수 있다.

 

페이징 기법의 특징은 고정된 크기로, 비연속적으로 배치하기 때문에 외부 단편화가 발생하지 않는다.

다만, 프로세스의 마지막 페이지가 페이지 크기보다 작을 수 있어 공간이 남는 내부 단편화가 발생할 수 있다.

 

세그멘테이션, segmentation

 

프로세스의 메모리 영역을 논리적 단위인 세그먼트로 분할한다.

이 때 논리적 단위란, 함수나 스택, 힙과 같은 영역을 의미하기도 한다.

 

세그멘테이션도 마찬가지로 세그멘테이션 테이블을 가지고 있다.

세그먼트 번호를 인덱스로 가지며 세그먼트 시작주소 base와 세그먼트 길이인 limit을 가진다.

 

세그멘테이션은 프로세스마다 세그먼트의 크기가 균등하지 않기 때문에 외부 단편화 문제가 생길 수 있다.

반대로 논리적 단위인 세그먼트로 분할하기 때문에 내부 단편화는 생기지 않는다.

 

가상 메모리

 

프로세스의 일부만 메모리에 로드하고 나머지는 디스크에 둔 상태로 프로세스를 실행하는 방식

프로세스를 실행하기 위해서 모든 데이터가 올라올 필요가 없기 때문에 가능하다.

가상 메모리를 사용하면서 많은 프로그램을 실행할 수 있어 cpu 이용률을 높일 수 있고

필요한 영역만 메모리에 로드하기 때문에 스와핑 횟수를 줄일 수 있다.

또한, 메모리에 접근하기 전에 가상 메모리라는 추상 계층을 추가하여 관리와 보안의 측면에서 강점이 있다.

 

요구 페이징

 

프로세스에서 필요한 페이지만 메모리에 로드하고 다른 페이지는 디스크에 저장한다.

따라서 페이지 테이블을 통해 페이지에 대응되는 프레임을 찾는 과정에서 물리 메모리에 페이지가 있을 수도 있고 없을 수도 있다.

필요한 페이지가 없을 때를 페이지 폴트(page fault)라고 한다. 페이지 폴트가 발생하면 스왑 인으로 디스크에 있는 페이지를 로드한다.

한편, 페이지 테이블은 대응되는 프레임이 존재하면 v(valid)값을 반환하고 없거나 유효하지 않으면 i(invalid)를 반환한다.

만약 스왑 인으로 페이지를 적재하는 과정에서 메모리가 꽉차 있다면 메모리 교체 알고리즘을 통해 기존의 페이지를 스왑 아웃한다.

 

The page table lookup may fail, triggering a page fault, for two reasons

The lookup may fail if there is no translation available for the virtual address, meaning that virtual address is invalid. This will typically occur because of a programming error, and the operating system must take some action to deal with the problem. On modern operating systems, it will cause a segmentation fault signal being sent to the offending program.
The lookup may also fail if the page is currently not resident in physical memory. This will occur if the requested page has been moved out of physical memory to make room for another page. In this case the page is paged out to a secondary store located on a medium such as a hard disk drive (this secondary store, or "backing store", is often called a swap partition if it is a disk partition, or a swap file, swapfile or page file if it is a file). When this happens the page needs to be taken from disk and put back into physical memory. A similar mechanism is used for memory-mapped files, which are mapped to virtual memory and loaded to physical memory on demand. - wiki

위키에 page fault의 원인에 관한 글이다.

위 내용을 요약하면, 페이지 폴트가 발생하는 원인은 하나는 가상 주소가 유효하지 않거나 물리 메모리에 적재되지 않았기 때문이라고 한다.

 

스레싱, thrashing

 

동시에 일정 수 이상의 프로그램을 실행했을 때, 오히려 cpu 이용률이 떨어지는 상황을 의미한다.

일반적으로 가상 메모리를 통해 여러 프로세스를 실행하면 cpu 이용률이 올라간다 했다.

하지만 다중 프로그래밍 정도가 어떤 한계를 넘어가면 페이지 폴트가 급격하게 늘어나서 cpu 이용률이 떨어지게 된다.

스레싱을 해결하기 위해서 워킹 세트를 설정하는데, 지역성을 바탕으로 페이지를 메모리에 올려두어 페이지 폴트를 방지하는 방법이 있다.

 

캐시 메모리

 

cpu와 메인 메모리 간에 데이터 접근 시 속도 차이를 줄이기 위해 사용된다.

 

캐시 메모리는 메인 메모리보다 적은 용량만 저장할 수 있기 때문에

지역성에 근거하여 효율적으로 데이터를 관리한다.

지역성은 cpu가 자주 참조하는 데이터가 고르게 분포한 것이 아니라 특정 부분에 몰려 있는 것을 말한다.

 

There are several different types of locality of reference: 

Temporal locality: If at one point a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future. There is temporal proximity between adjacent references to the same memory location. In this case it is common to make efforts to store a copy of the referenced data in faster memory storage, to reduce the latency of subsequent references. Temporal locality is a special case of spatial locality (see below), namely when the prospective location is identical to the present location. Spatial locality: If a particular storage location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future. In this case it is common to attempt to guess the size and shape of the area around the current reference for which it is worthwhile to prepare faster access for subsequent reference. - wiki

위 글은 지역성에 관한 글이다.

시간적 지역성은 특정 메모리 위치가 한 번 참조된 경우, 가까운 미래에 동일한 위치가 다시 참조될 가능성이 높은 현상.

이는 주로 빠른 메모리 저장소에 참조된 데이터의 사본을 저장하여 이후 참조의 지연 시간을 줄이는 데 사용된다.

이는 공간적 지역성의 특수한 경우로, 현재 위치와 미래 위치가 동일한 경우이다.

공간적 지역성은 특정 저장 위치가 특정 시간에 참조된 경우, 근처의 메모리 위치가 가까운 미래에 참조될 가능성이 높은 현상.

이 경우 주변 참조를 빠른 액세스를 위해 준비하는 것이 일반적이다.

 

 

 

출처

 

기술 면접 대비 cs전공 핵심 요약집 - 길벗

https://youtu.be/-jlzaslp-w4?si=2g1v_XzcuWSgmXD7

https://en.wikipedia.org/wiki/Page_table 

https://en.wikipedia.org/wiki/Locality_of_reference