Memoir Portal

운영체제(Operating System)

⌨️ 목차

세마포어와 뮤텍스

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.

이를 위해 나온 것이 바로 세마포어

세마포어 : 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

임계 구역(Critical Section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.

세마포어 P, V 연산

P : 임계 구역 들어가기 전에 수행 ( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

V : 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호 )

구현 방법

생략

이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다. P와 V를 사용하여 임계 구역에 대한 상호배제 구현이 가능하게 되었다.

예시

최초 S 값은 1이고, 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정하자

먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계구역에 들어감
그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
A가 임계구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행함

뮤텍스 : 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

상호 배제(Mutual Exclusion)의 약자임

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

lock : 현재 임계 구역에 들어갈 권한을 얻어옴 ( 만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기 )
unlock : 현재 임계 구역을 모두 사용했음을 알림. ( 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음 )

뮤텍스는 상태가 0, 1로 이진 세마포어로 부르기도 함

뮤텍스 알고리즘

데커(Dekker) 알고리즘
flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식
- flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수
- turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수
- 생략

피터슨(Peterson) 알고리즘
데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

제과점(Bakery) 알고리즘

여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

페이징과 세그멘테이션

기법을 쓰는 이유

다중 프로그래밍 시스템에 여러 프로세스를 수용하기 위해 주기억장치를 동적 분할하는 메모리 관리 작업이 필요하기 때문

메모리 관리 기법

연속 메모리 관리
프로그램 전체가 하나의 커다란 공간에 연속적으로 할당되야함

고정 분할 기법 : 주기억장치가 고정된 파티션으로 분할(내부 단편화 발생)
동적 분할 기법 : 파티션들이 동적생성되며 자신의 크기와 같은 파티션에 적재 (외부 단편화 발생)

여기서 내부, 외부 단편화란?

내부 단편화(Internal Fragmentation)
프로세스가 필요한 양보다 더 큰 메모리가 할당되어 메모리 공간 낭비 발생
프로세스는 실제로 사용하지 않는 메모리 영역을 가지고 있게 됨

외부 단편화(External Fragmentation)
남아있는 총 메모리 공간이 프로세스가 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적이지 않아 사용할 수 없는 경우
쪼개진 메모리 공간을 사용할 수 없어 메모리 낭비 발생
프로세스들이 메모리를 할당하고 반납하는 과정에서, 사용할 수 있는 메모리 공간이 쪼개져서 발생

불연속 메모리 관리
프로그램의 일부가 서로 다른 주소 공간에 할당될 수 있는 기법
페이지 : 고정 사이즈의 작은 프로세스 조각
프레임 : 페이지 크기와 같은 주기억장치 메모리 조각
단편화 : 기억 장치의 빈 공간 or 자료가 여러 조각으로 나뉘는 현상
세그먼트 : 서로 다른 크기를 가진 논리적 블록이 연속적 공간에 배치되는 것
고정 크기 : 페이징(Paging)
가변 크기 : 세그먼테이션(Segmentation)

단순 페이징
각 프로세스는 프레임들과 같은 길이를 가진 균등 페이지로 나뉨
외부 단편화 X
소량의 내부 단편화 존재

단순 세그먼테이션
각 프로세스는 여러 세그먼트들로 나뉨
내부 단편화 X, 메모리 사용 효율 개선, 동적 분할을 통한 오버헤드 감소
외부 단편화 존재

가상 메모리 페이징
단순 페이징과 비교해 프로세스 페이지 전부를 로드시킬 필요X
필요한 페이지가 있으면 나중에 자동으로 불러들어짐
외부 단편화 X
복잡한 메모리 관리로 오버헤드 발생

가상 메모리 세그먼테이션
필요하지 않은 세그먼트들은 로드되지 않음
필요한 세그먼트 있을때 나중에 자동으로 불러들어짐
내부 단편화X
복잡한 메모리 관리로 오버헤드 발생
페이지 교체 알고리즘
페이지 부재 발생 → 새로운 페이지를 할당해야 함 → 현재 할당된 페이지 중 어떤 것 교체할 지 결정하는 방법
좀 더 자세하게 생각해보면?
가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재하고 사용하지 않는 부분은 그대로 둔다.
하지만 필요한 페이지만 올려도 메모리는 결국 가득 차게 되고, 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다.
따라서 메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지는 out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 한다.
여기서 어떤 페이지를 out 시켜야할 지 정해야 한다. (이때 out 되는 페이지를 victim page라고 부름)
기왕이면 수정이 되지 않는 페이지를 선택해야 좋다.
(Why? : 만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 진행해야 하므로 시간이 오래 걸림)

이와 같은 상황에서 상황에 맞는 페이지 교체를 진행하기 위해 페이지 교체 알고리즘이 존재하는 것!

Page Reference String

CPU는 논리 주소를 통해 특정 주소를 요구함

메인 메모리에 올라와 있는 주소들은 페이지의 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함 발생 X

따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법이 바로 Page Reference String

FIFO 알고리즘
First-in First-out, 메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘
victim page : out 되는 페이지는, 가장 먼저 메모리에 올라온 페이지
가장 간단한 방법으로, 특히 초기화 코드에서 적절한 방법임
초기화 코드 : 처음 프로세스 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않으므로, 메인 메모리에서 빼도 괜찮음
처음 프로세스 실행시에는 무조건 필요한 코드이므로, FIFO 알고리즘을 사용하면 초기화를 시켜준 후 가장 먼저 내보내는 것이 가능함
OPT 알고리즘

Optimal 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄

FIFO에 비해 페이지 결함의 횟수를 많이 감소시킬 수 있음

하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘임

LRU 알고리즘

Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내려보내는 알고리즘

최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나옴

OPT의 경우 미래 예측이지만, LRU의 경우는 과고를 보고 판단하므로 실질적으로 사용이 가능한 알고리즘

(실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)

OPT보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법 중 하나임

교체 방식

Global 교체
메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
Local 교체
메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음

따라서, 다양한 프로세스의 페이지가 메모리에 존재함

페이지 교체 시, 다양한 페이지 교체 알고리즘을 활용해 victim page를 선정하는데, 선정 기준을 Global로 하느냐, Local로 하느냐에 대한 차이

→ 실제로는 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 함. 자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적

메모리

메인 메모리는 CPU가 직접 접근할 수 있는 기억 장치
프로세스가 실행되려면 프로그램이 메모리에 올라와야 함

주소가 할당된 일련의 바이트들로 구성되어 있음

CPU는 레지스터가 지시하는대로 메모리에 접근하여 다음에 수행할 명령어를 가져옴

명령어 수행 시 메모리에 필요한 데이터가 없으면 해당 데이터를 우선 가져와야 함

이 역할을 하는 것이 바로 MMU.

MMU (Memory Management Unit, 메모리 관리 장치)

논리 주소를 물리주소로 변환해 준다.
메모리 보호나 캐시 관리 등 CPU가 메모리에 접근하는 것을 총 관리해주는 하드웨어임
메모리의 공간이 한정적이기 때문에, 사용자에게 더 많은 메모리를 제공하기 위해 가상 주소라는 개념이 등장 (가상 주소는 프로그램 상에서 사용자가 보는 주소 공간이라고 보면 됨)
이 가상 주소에서 실제 데이터가 담겨 있는 곳에 접근하기 위해선 빠른 주소 변환이 필요한데, 이를 MMU가 도와주는 것

즉, MMU의 역할은 다음과 같다고 말할 수 있다.

MMU가 지원되지 않으면, physical address를 직접 접근해야 하기 때문에 부담이 있다.
MMU는 사용자가 기억장소를 일일이 할당해야 하는 불편을 없애준다.
프로세스의 크기가 실제 메모리의 용량을 초과해도 실행될 수 있게 해준다.

또한 메인 메모리의 직접 접근은 비효율적이므로, CPU와 메인 메모리 속도를 맞추기 위해 캐시가 존재함

MMU의 메모리 보호

프로세스는 독립적인 메모리 공간을 가져야 되고, 자신의 공간만 접근해야 함

따라서 한 프로세스에게 합법적인 주소 영역을 설정하고, 잘못된 접근이 오면 trap을 발생시키며 보호함

base와 limit 레지스터를 활용한 메모리 보호 기법

base 레지스터는 메모리상의 프로세스 시작주소를 물리 주소로 저장 limit 레지스터는 프로세스의 사이즈를 저장

이로써 프로세스의 접근 가능한 합법적인 메모리 영역(x)은

이 영역 밖에서 접근을 요구하면 trap을 발생시키는 것

안전성을 위해 base와 limit 레지스터는 커널 모드에서만 수정 가능하도록 설계 (사용자 모드에서는 직접 변경할 수 없도록)

메모리 과할당(over allocating)

실제 메모리의 사이즈보다 더 큰 사이즈의 메모리를 프로세스에 할당한 상황

페이지 기법과 같은 메모리 관리 기법은 사용자가 눈치 채지 못하도록 눈속임을 통해 메모리를 할당해줌 (가상 메모리를 이용해서)

과할당 상황에 대해서 사용자를 속인 것을 들킬만한 상황이 존재함

프로세스 실행 도중 페이지 폴트 발생
페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
메모리의 빈 프레임에 페이지를 올려야 하는데, 모든 메모리가 사용중이라 빈 프레임이 없음

이러한 과할당을 해결하기 위해선, 빈 프레임을 확보할 수 있어야 함

메모리에 올라와 있는 한 프로세스를 종료시켜 빈 프레임을 얻음
프로세스 하나를 swap out하고, 이 공간을 빈 프레임으로 활용

swapping 기법을 통해 공간을 바꿔치기하는 2번 방법과는 달리 1번은 사용자에게 페이징 시스템을 들킬 가능성이 매우 높아서 하면 안됨

(페이징 기법은 사용자 모르게 시스템 능률을 높이기 위해 선택한 일이므로 들키지 않게 처리해야한다)

따라서, 2번과 같은 해결책을 통해 페이지 교체가 이루어져야 함

페이지 교체

메모리 과할당이 발생했을 때, 프로세스 하나를 swap out해서 빈 프레임을 확보하는 것

프로세스 실행 도중 페이지 부재 발생
페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
메모리에 빈 프레임이 있는지 확인
빈 프레임이 있으면 해당 프레임을 사용
빈 프레임이 없으면, victim 프레임을 선정해 디스크에 기록하고 페이지 테이블을 업데이트함
빈 프레임에 페이지 폴트가 발생한 페이지를 올리고, 페이지 테이블 업데이트
페이지 교체가 이루어지면 아무일이 없던것 처럼 프로세스를 계속 수행시켜주면서 사용자가 알지 못하도록 해야 함
이때, 아무일도 일어나지 않은 것처럼 하려면, 페이지 교체 당시 오버헤드를 최대한 줄여야 함

오버헤드를 감소시키는 해결법

이처럼 빈 프레임이 없는 상황에서 victim 프레임을 비울 때와 원하는 페이지를 프레임으로 올릴 때 두 번의 디스크 접근이 이루어짐

페이지 교체가 많이 이루어지면, 이처럼 입출력 연산이 많이 발생하게 되면서 오버헤드 문제가 발생함

방법1

변경비트를 모든 페이지마다 둬서, victim 페이지가 정해지면 해당 페이지의 비트를 확인

해당 비트가 set 상태면? → 해당 페이지 내용이 디스크 상의 페이지 내용과 달라졌다는 뜻 (즉, 페이지가 메모리 올라온 이후 한번이라도 수정이 일어났던 것. 따라서 이건 디스크에 기록해야함)

bit가 clear 상태라면? → 디스크 상의 페이지 내용과 메모리 상의 페이지가 정확히 일치하는 상황 (즉, 디스크와 내용이 같아서 기록할 필요가 없음)

비트를 활용해 디스크에 기록하는 횟수를 줄이면서 오버헤드에 대한 수를 최대 절반으로 감소시키는 방법임

방법2

페이지 교체 알고리즘을 상황에 따라 잘 선택해야 함

현재 상황에서 페이지 폴트를 발생할 확률을 최대한 줄여줄 수 있는 교체 알고리즘을 사용

FIFO

OPT

LRU

캐시 메모리

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

CPU가 이미 봤던걸 다시 재접근할 때, 메모리 참조 및 인출 과정에 대한 비용을 줄이기 위해 캐시에 저장해둔 데이터를 활용한다

캐시는 플리플롭 소자로 구성되어 SRAM으로 되어있어서 DRAM보다 빠른 장점을 지님

CPU와 기억장치의 상호작용

CPU에서 주소를 전달 → 캐시 기억장치에 명령이 존재하는지 확인

(존재) Hit

해당 명령어를 CPU로 전송 → 완료

(비존재) Miss

명령어를 갖고 주기억장치로 접근 → 해당 명령어를 가진 데이터 인출 → 해당 명령어 데이터를 캐시에 저장 → 해당 명령어를 CPU로 전송 → 완료

이처럼 캐시를 잘 활용한다면 비용을 많이 줄일 수 있음

따라서 CPU가 어떤 데이터를 원할지 어느정도 예측할 수 있어야 함

(캐시에 많이 활용되는 쓸모 있는 정보가 들어있어야 성능이 높아짐)

적중률을 극대화시키기 위해 사용되는 것이 바로 지역성의 원리

지역성

기억 장치 내의 정보를 균일하게 액세스 하는 것이 아니라 한 순간에 특정부분을 집중적으로 참조하는 특성

지역성의 종류는 시간과 공간으로 나누어짐

시간 지역성 : 최근에 참조된 주소의 내용은 곧 다음에도 참조되는 특성

공간 지역성 : 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

캐싱 라인

빈번하게 사용되는 데이터들을 캐시에 저장했더라도, 내가 필요한 데이터를 캐시에서 찾을 때 모든 데이터를 순회하는 것은 시간 낭비다.

즉, 캐시에 목적 데이터가 저장되어있을 때 바로 접근하여 출력할 수 있어야 캐시 활용이 의미있어짐

따라서 캐시에 데이터를 저장할 시, 자료구조를 활용해 묶어서 저장하는데 이를 캐싱 라인이라고 부른다.

즉, 캐시에 저장하는 데이터에 데이터의 메모리 주소를 함께 저장하면서 빠르게 원하는 정보를 찾을 수 있음 (set이나 map 등을 활용)

운영체제 study복습3