운영체제

[kangchanguk]

운영체제 스터디

[kangchanguk]

Process

• 프로세스: 실행 중인 프로그램
• 프로그램: 디스크 상에 존재하며 실행을 위한 명령어와 정적 데이터의 묶음

운영체제는 이 명령어와 데이터 묶음을 읽고 실행하여 프로그램에 생명을 불어 넣는것!!

시분할

• 원하는 수 만큼의 프로세스를 동시에 실행할 수 있게 함

• 하나의 프로세스를 실행하고 얼마 후 중단시키고 다른 프로세스를 실행하는 작업을 반복하면서 실제 하나 또는 소수의 CPU로 여러 개의 가상 CPU가 존재하는 듯 작업

• 많은 개체들이 자원을 공유하는 방식

프로세스의 개념

• 실행 중인 프로그램

• 프로세스를 간단하게 표현하기 위해서는 실행하는 동안 접근했거나 영향을 받은 자원의 목록을 작성

  • 메모리
  • 레지스터
  • 영구 저장 장치

프로세스 API

1) 생성

운영체제는 새로운 프로세스를 생성할 수 있는 방법을 제공

2) Destory

운영체제는 강제로 프로세스를 제거할 수 있는 인터페이스를 제공

3) Wait

때로는 어떤 프로세스의 실행 중지를 기다릴 필요가 있기 때문에 대기 인터페이스가 필요

4) 각종 제어

프로세스의 일시 정지 등 각종 제어 기능 제공

5) 상태

프로세스 상태 정보를 제공하는 인터페이스 제공

프로세스 생성

어떻게 프로그램이 프로세스로 변형이 되는가??

1) 프로그램 코드와 정적 데이터를 메모리, 프로세스 주소 공간에 탑재

• 프로그램은 디스크 또는 ssd에 실행파일 형식으로 존재, 코드와 데이터는 메모리에 저장

• 현대에는 코드나 데이터가 필요할 때 필요한 부분만 메모리에 탑재

2) 스택과 힙을 할당

• 스택: 지역변수, 함수 인자, 리턴 주소를 저장하기 위해 스택을 사용
• 힙: 동적으로 할당된 데이터를 저장하기 위해 사용

3) 입출력과 관계된 초기화 작업을 진행

4) main()에서부터 프로그램 실행을 시작

프로세스 상태

• running, ready, block

자료구조

• 다양한 정보를 유지하기 위한 자료구조를 가지고 있음

[kangchanguk]

process API

unix 시스템의 프로세스 생성에 관해 논의 프로세스 생성을 위해 fork()와 exec() 시스템 콜을 사용

fork ()

• 프로세스 생성을 위해 해당 시스템 콜을 제공

  • 생성한 프로세스는 호출한 프로세스의 복사본(자신의 주소공간, 레지스터, pc 값을 가짐)
  • 부모 프로세스는 생성된 자식 프로세스의 pid 값을 반환, 자식 프로세스는 0을 반환
  • CPU 스케줄러가 실행할 프로세스를 선택할 때 두개의 프로세스 사이에서 어느 프로세스를 먼저 실행 할지 선택이 되어 있지 않기 때문(비 결정성)에 멀티 스레드 적용 시 다양한 문제가 발생

• pid: 프로세스 실행이나 중단과 같이 특정 프로세스를 대상으로 작업을 해야할 경우 프로세스를 지칭하기 위해 사용

wait()

• 부모 프로세스가 자식 프로세스의 종료를 대기해야하는 경우 사용되는 call

exec()

• 자기자신이 아닌 다른 프로그램을 실행해야 할 때 사용

실행 순서

• 1) 실행파일의 이름과 약간의 인자가 주어지면 해당 실행 파일의 코드와 정적 데이터를 읽어 들여 현재 실행 중인 프로세스 코드 세그멘트와 정적 데이터 부분을 덮어 씀

• 2) 힙과 스택 등 다른 주소 공간들도 새로운 프로그램 실행을 위해 초기화 됨

• 3) argv 같은 인자를 전달하여 프로그램을 실행 ( 현재 실행 중인 프로그램을 다른 실행 중인 프로그램으로 대체)

왜 이렇게 인터페이스 분리해둠??

• fork(), exec() 조합을 통해서 다양한 일들을 수행할 수 있음

여타 api

kill ()

• 프로세스에 signal을 보내는데 사용
• 프로세스를 block, 삭제 하는데 사용
• signal은 외부사건을 프로세스에 전달하는 토대

[kangchanguk]

CPU scheduling

• cpu 가상화를 하기 위해서는 운영체제는 여러 작업들이 동시에 진행되는 것처럼 보이도록 물리적인 CPU를 공유

• 한 프로세스를 잠시동안 실행하고 다른 프로세스를 잠깐 실행하는 등 cpu 시간을 나눠 씀

고려사항

• 성능저하: 과중한 오버헤드는 주지 않으면서 가상화 구현이 가능한가??
• 제어문제: CPU에 대한 통제를 유지하면서 프로세스를 효율적으로 실행시킬 수 있는 방법은 무엇인가??

제한적 직접 실행이라는 방법이 나옴!!

기본 원리

• 프로그램을 CPU 상에서 직접 실행시킴

운영체제)

• 프로세스 목록의 항목을 생성
• 프로세스 메모리 할당
• 메모리에 프로그램 탑재
• argc/argv를 위한 스택 셋업
• 레지스터 내용 삭제
• call main() 실행
• 프로세스 메모리 반환
• 프로세스 목록에서 항목 제거

해당 방식을 사용할 경우 하기와 같은 문제를 일으킴

1) 프로그램을 직접 실행시키면 프로그램이, 운영체제가 원하지 않을 일을 하지 않는다는 것을 어떻게 보장할 것인가? 2) 프로세스 실행 시, 운영체제는 어떻게 프로그램의 실행을 중단하고 다른 프로세스로 전환시킬 수 있는가??

이러한 문제점들을 개선하는 과정에서 제한적이라는 개념이 도입됨

문제점 1) 제한된 연산

프로세스는 입출력 연산을 비론한 다른 제한된 연산을 수행해야 함

• 프로세스는 시스템에 대한 권한이 없기 때문에 제한된 연산을 수행할 수 없음

하드웨어는 두가지 실행모드를 제공하여 운영체제를 도움

• 사용자 모드: 응용프로그램은 하드웨어 자원에 대한 접근 권한이 제한되어 잇음

• 커널 모드: 운영체제가 컴퓨터 모든 자원에 대한 접근 권한을 가짐

• 사용자 프로세스에게 제한 작업 실행을 허용하기위해서 하드웨어는 사용자에게 시스템 콜을 제공

• 시스템 콜 수행을 위해서 trap, return-from-trap 명령어를 통해 사용자 모드를 변경함

• 커널은 부팅 시에 트랩 테이블(trap table) 만들어 시스템을 통제한다.

• 컴퓨터가 부트될 때 커널 모드에서 동작하여 특정 명령어로 하드웨어에게 트랩 핸들러(trap handler) 의 위치를 알려준다. 하드웨어는 이 위치를 저장하고 있다가 시스템 콜의 고유 번호를 통해 처리가 가능하다.

6.3 문제점 2: 프로세스 간 전환

직접 실행의 두 번째 문제는 프로제스의 전환이다.

• 협조 방식: 시스템 콜 호출시 까지 대기

• 협조(cooperative) 방식은 각 사용자 프로세스가 비정상적인 행동은 하지 않을 것으로 가정

• CPU를 장기간 사용하는 프로세스들이 다른 프로세스가 사용할 수 있도록 주기적으로 CPU 를 반납할 것이라 믿음

• 협조 방식을 사용하는 운영체제는 yield 시스템 콜로 다른 프로세스에세 CPU 를 할당할 수 있는 기회 제공

• 응용 프로그램이 비정상적인 행동을 하면 트랩이 일어나 CPU 획득하여 해당 프로세스 종료

• 협조 방식의 스케줄링 시스템은 근본적으로 수동

• 시스템 콜 호출을 기다리거나 불법적인 연산을 대기

• 프로세스가 무한 루프에 빠져서 시스템 콜을 호출할 수 없으면 문제 발생

• 비협조 방식: 운영체제가 제어권 확보

• 비협조 방식은 타이머 인터럽트(timer interrupt) 로 프로세스를 중단하고 인터럽트 핸들러(interrupt handler) 를 실행

• 인터럽트 핸들러는 운영체제의 일부로

• 인터럽트를 처리하는 과정에서 실행중인 프로세스를 중단하고 운영체제에게 CPU 제어권을 넘겨 필요한 작업을 수행

문맥의 저장과 복원

• 운영체제의 스케줄러(scheduler) 는 실행중인 프로세스를 계속 실행할 지, 전환할 지를 결정한다. 프로세스 전환을 결정하면 운영체제는 문맥 교환(context switch) 코드를 실행한다.

• 문맥 교환은 실행 중인 프로세스의 레지스터 값들을 커널 스택 같은 곳에 저장하고 실행될 프로세스의 레지스터 값을 복원하는 것이다.

6.4 병행실행으로 인한 문제

• 인터럽트나 트랩을 처리하는 도중에 다른 인터럽트가 발생할 때 주의가 필요하다.

• 간단한 해결책으로 인터럽트를 처리하는 동안에는 인터럽트를 불능화 하는 것이다.

• 하지만 이러한 기법은 인터럽트를 장기화 불능화하는 경우 손실되는 인터럽트가 발생될 수 있어서 신중하게 사용해야 한다.

• 운영체제는 커널 내부의 자료 구조들이 락(lock) 으로 보호되기 때문에 내부에서 다수의 작업들이 동시에 진행되는 것이 가능하다.

• 하지만 구성과 작동이 매우 복잡해지고 이 때문에 문제점과 버그들이 발생한다.

[kangchanguk]

cpu 스케줄링

스케줄링 정책 개발을 위해서는 하기의 의문점들을 정의해야한다.

• 스케줄링 정책을 생각하기 위한 기본적인 프레임워크를 어떻게 만들어야 하는가?
• 핵심 가정은 무엇인가?
• 어떤 평가 기준이 중요한가?
• 컴퓨터 시스템의 초창기에 사용되었던 기본 접근법은 무엇인가?

워크로드

• 워크로드: 일련의 프로세스들이 실행하는 상황

1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 각 작업은 시작되면 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다 (즉, 입출력을 수행하지 않는다).

평가 기준

• 반환 시간: 작업이 완료된 시각 - 작업이 시스템에 도착한 시각
• 공정성

1) 선입선출

• 먼저 온 순서대로 처리
• 가장 먼저 온 작업이 소모시간이 긴 경우에는 비효율적인 스케줄링
• convoy effect 야기(짧은 시간동안 자원을 사용하는 프로세스가 오랜시간동안 자원을 사용하는 프로세스를 기다리는 효과)

2) 최단 작업 우선(SJF)

• 가장 짧은 작업부터 처리하자
• 모든 작업이 동시에 도착한다면 최적의 알고리즘!!
• 여전히 convoy effect를 야기할 수 있음

3) 최소 잔여시간 우선(STCF)

• SJF + 선점 기능을 추가
• 새로운 작업이 들어오면 남아있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 가장 적은 잔여 실행 시간을 가진 작업을 스케줄링

새로운 평가기준: 응답 시간

• 사용자가 터미널에서 작업을 하게 되어 시스템에게 상호작용을 원할히 하기 위한 성능을 요구하기 시작
• 응답시간이 새로운 평가 기준으로 떠오름
• 응답시간: 작업이 도착할 때부터 처음 스케줄링 될 때까지의 시간을 의미

라운드 로빈

• 일정 시간 실행한 후 실행 큐의 다음 작업으로 전환하는 방법

• 타임 슬라이스 or 퀀텀이라고 부름

• 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야함(타이머가 10msec 마다 인터럽트를 발생시키면 타임 슬라이스는 10, 20 등의 배수가 되어야함)

• 타임 슬라이스 길이에 따라 라운드 로빈 성능이 결정됨(응답 시간 기준)

• 그러나 너무 짧으면 context 스위칭 비용때문에 전체 성능이 떨어짐

• context 스위칭 비용과 응답 시간 모두 고려해야함!!

• 반환시간을 기준으로 해서는 효율이 낮아짐.....

[kangchanguk]

multi level feedback queue

• 프로세스에 대한 정보가 없다면 스케줄링을 어떻게 하는것이 좋은가??

mifq

• 여러개의 큐로 구성되며 각각 다른 우선순위가 배정
• 높은 우선순위를 가진 작업이 높은 우선순위큐에 위치함
• 같은 큐에 속한 작업은 동일한 우선순위, RR로 스케줄링

규칙

• 규칙 1: Priority(A) > Priority(B) 이면, A가 실행된다 (B는 실행되지 않는다).
• 규칙 2: Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
• 규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.
• 규칙 4: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
• 규칙 5: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

mifq는 주어진 프로세스가 짧은 작업이라고 가정하여 높은 우선순위를 부여하고 짧은 작업이 아니라면 천천히 우선순위를 떨어뜨린다.

mifq의 문제점

1) 기아상태 발생: 시스템에 너무 많은 대화형 작업이 존재하면 모든 CPU 시간을 소모하게 될 것 이고 긴 실행 시간 작업은 CPU 시간을 할당 받지 못함

2) 자신에게 유리하도록 프로그램 작성이 가능: 타임슬라이스를 99%까지 사용하고 CPU를 양도한다면 우선순위 유지가 가능 3) CPU 위주 작업이 대화형 작업으로 바뀜

해결책

1) 일정 시간이 지나면 시스템의 모든 작업을 최상위 큐로 이동

2) 더 나은 시간 측정 (스케줄러를 자신에게 유리하도록 동작시키는 것 방지)

• CPU 총 사용시간을 측정(타임 슬라이스에 해당하는 시간을 모두 사용한다면 바로 강등)

[kangchanguk]

스케줄링 비례배분

• 비례배분, 공정 스케줄링 (반환시간이나 응답시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU 일정 비율을 보장하는 것)
• 추첨을 통해 다음 실행될 프로세스를 결정
• 자주 수행되어야할 프로세스는 당첨기회를 더 많이 줌

기본 개념

• 추첨권!!(프로세스가 소유한 티켓의 갯수와 전체 티켓에 대한 비율이 자신의 몫을 의미)
• 어떤 추첨권이 나오느냐에 따라 실행되는 프로세스가 달라짐
• 계속 수행하다보면 원하는 비율을 달성할 수 있다

추첨 기법

1) 추첨권 화폐

• 추첨권을 자신의 화폐 가치로 자유롭게 할당할 수 있도록 허용

2) 추첨권 양도

• 프로세스가 드른 프로세스에게 추첨권을 양도해서 특정 작업을 처리함

3) 추첨권 팽창

• 하나의 프로세스가 많은 양의 추첨권을 본인에게 할당
• 프로세스간 상호 신뢰가 있는 경우에 가능

추첨권 배분 방식

• 아직 미해결( 몇개 씩 줘야하지, 추첨권 할당 방식에 따라 시스템 동작이 달라짐)

장점

• 구현이 쉽다.

단점

• 무작위성은 원하는 비율을 보장하지 않음

보폭 스케줄링

• 보폭: 자신이 가지고 있는 추첨권 수에 반비례하는 값
• 프로세스가 실행될 때마다 pass라는 값을 보폭만큼 증가시켜서 얼마나 cpu를 사용했는지 추적한다.
• 스케줄러는 보폭과 pass를 활용하여 프로세스를 선택
• 가장 작은 pass 값을 가진 프로세스를 선택
• 프로세스를 실행시킬 때마다 pass 값을 보폭만큼씩 증가

단점: cpu 사용현황이나 pass 값을 유지하고 갱신해야한다.

[kangchanguk]

주소 공간의 개념

초기 시스템

• 운영체제(코드, 데이터)
• 현재 프로그램(코드, 데이터)

멀티프로그래밍과 시분할

• 운영체제가 프로세스들을 전환하면서 CPU 이용률을 증가시킴
• 대화식 이용의 개념이 부상함
• 시분할 시대가 시작함
  • 하나의 프로세스를 짧은 시간동안 실행시킴
  • 프로세스에게 모든 메모리에 접근할 권한이 주어짐
  • 해당 프로세스를 중단하고 중단 시점의 모든 상태를 디스크 종류의 장치에 저장하고 다른 프로세스 상태를 탑재하여 짧은 시간에 실행시킴

해당 방식은 느림, 메모리가 커지면 어케할겨.... 프로세스 전환 시 프로세스를 메모리에 그대로 유지하면서, 운영체제가 시분할 시스템을 효율적으로 구현할 수 있게 해주는 것이 중요!!

주소공간

• 코드: 메모리에 존재
• 스택: 함수 호출 체인 상의 현재 위치, 지역변수, 함수 인자와 반환값 등을 저장하는데 사용
• heap: 동적으로 할당되는 메모리를 위해 사용

스택과 heap은 확장을 위해 주소공간 양 끝단에 위치

운영체제는 물리 메모리를 공유하는 다수의 프로세스에게 어떻게 프로세스 전용의 커다란 주소공간이라는 개념을 제공할 수 있는가??

가상화의 목표

• 고립
• 투명성
• 효율성
• 보호

[kangchanguk]

메모리 API

메모리 공간의 종류

void func() {
    int x;
}

스택

• 스택에 int 형을 선언
• func()이 호출될 때 마다 스택에 공간을 확보하고 함수에서 리턴하면 메모리를 반환(오래 유지 안됨

heap

• 오래 유지되어야 하는 변수를 위한 메모리
• 모든 할당과 반환이 프로그래머에 의해 명시적으로 처리됨

1) malloc

• 힙이 요청한 공간의 크기를 넘겨주면, 성공했을 경우 새로 할당된 공간에 대한 포인터를 사용자에게 반환하고 실패했을 겨우 Null을 반환

2) free

• 힙 메모리 해제

3) 흔한 오류

1) 메모리 할당 잊기 2) 메모리 부족하게 할당받기(버퍼 오버플로우) 발생

4) 할당받은 메모리 초기화 하지 않기

• 새로 할당받은 데이터 타입에 특정값을 넣는 것을 깜빡함
• 프로그램이 힙으로부터 데이터를 읽으려고 할 때 에러가 발생

5) 메모리 해제하지 않기

• 메모리 누수가 발생

프로세스 종료 시 메모리 누수가 일어나지 않는 이유

• 프로세스에서 malloc으로 메모리 할당 후 종료 직전에 free를 하지 않아도 메모리 누수는 일어나지 않음
• 메모리 관리는 두단계로 이루어짐
• 첫번째 단계(시스템)
  • 프로세스가 실핼할 때 메모리를 프로세스에게 건내주고 종료하거나 죽으면 메모리를 돌려받음
• 두번째 단계(프로세스)
  • 프로세스가 종료할 때 운영체제가 프로세스의 모든 메모리를 회수

6) 메모리 사용이 끝나기 전에 메모리 해제하기

• dangling pointer( 메모리 사용이 끝나기 전에 메모리 해제)
• free하고 malloc을 해버리면 잘못 해제된 메모리를 재사용

반복적으로 매모리 해제

• 메모리를 한번 이상 해제함(이중 해제)

잘못 free

• 잘못된 포인터의 메모리를 free

realloc

• 할당된 공간에 대해 추가 공간이 필요한 경우 용이

calloc

• 메모리 할당 영역을 0으로 채워서 반환(초기화 하는 것을 잃어 버린 경우를 방지)

[kangchanguk]

멀티프로세서 스케줄링(고급)

여러 CPU에 작업을 어떻게 스케줄 해야하는가??

멀티 프로세서 구조

• 단일 CPU 하드웨어와 멀티 CPU 하드웨어의 근본적인 차이

  • 다수의 프로세서 간의 데이터 공유, 하드웨어 캐시의 사용방식에서 근본적인 차이가 발생

• 단일 CPU 시스템에서는 하드웨어 캐시 계층이 존재

• 캐시는 지역성에 기반함

• 지역성

  • 시간 지역성: 데이터가 한번 접근되면 가까운 미래에 다시 접근되기 쉽다.
  • 공간 지역성: 프로그램이 주소 x의 데이터를 접근하면 x 주변의 데이터가 접근되기 쉽다는 것

• 하나의 시스템에서 여러 프로세서가 존재허고 하나의 공유 메인 메모리가 있는 경우

• 캐시 일관성 문제가 일어날 수 있음

캐시 일관성 문제 해결책

• 하드웨어에서 여러개의 프로세스들이 하나의 메모리에 갱신할 때 항상 공유되도록 시스템을 관리하도록 함

동기화를 잊지 마라

• CPU들이 동일한 데이터 또는 구조체에 접근할 때 올바른 연산결과를 보장하기 위해서는 상호배제를 보장하는 동기화 기법이 많이 사용

• 구조체를 원자적으로 갱신하기 위해서는 락이 필요

• mutex를 할당하고 루틴의 시작에 lock, unlock을 추가하면 문제를 해결할 수 있지만 CPU개수가 증가할수록 동기화된 자료 구조에 접근하는 연산은 매우 느려지게 됨

캐시친화성 문제 발생

• 프로세스가 다른 CPU에서 실행 될 때마다 필요한 정보를 캐시에 탑재해야만 하기 때문에 프로세스 성능이 개 나빠짐
• 스케줄링 시 해당 사항도 고려해야함

단일 큐 스케줄링

• 단일 프로세서 스케줄링의 기본 프레임 워크
• 다수의 프로세스가 단일 큐에 적재된 작업을 선택하는 구조

단점

1) 확장성 결여: 다수의 CPU에서 제대로 동작하기 위해 락을 삽입하지만 락이 성능 저하를 초래

2) 캐시 친화성 문제: 캐시 친화성 방지를 위해 되도록 하나의 CPU에서 프로세스가 실행되도록 함(구현과 기법이 복잡)

멀티 큐 스케줄링

• CPU마다 큐를 둠

장점

• 확장성이 좋음

단점

• workload의 불균형(하나의 CPU에 TASK가 몰림)
• 노는 CPU가 생길 수 있음

해결책

• migration 도입
• 유휴상태의 CPU가 생기고 다른 프로세서의 큐에 작업이 적재되어있다면 유휴상태의 CPU가 해당 작업을 가져옴
• work stealing: 작업 개수가 낮은 큐가 다른 큐에 훨씬 많은 수의 작업이 있는지를 검사하고 대상 큐가 소스 큐보다 더 가득 차 있다면 워크로드의 균형을 위해 소스는 대상에서 하나이상의 작업을 가져옴
• 큐를 너무 자주 검사하면 높은 오버헤드로 확장성에 문제가 생김



[kangchanguk]

주소변환의 원리

• 하드웨어는 주소 변환을 통해 명령어 반입, 탑재, 저장 등의 가상 주소를 정보가 실제 존재하는 물리주소로 반환

• 운영체제가 주소변환시 추구하는 사항

  • 효율성 : 레지스터, TLB 등의 하드웨어의 도움을 받는다
  • 제어 : 하드웨어의 도움을 받아 응용프로그램이 자기 자신의 메모리 이외의 공간에 접근하지 못하도록 막는다.
  • 유연성 : 프로그래머가 원하는 대로 주소공간을 사용할 수 있어야 한다

• 프로그램의 모든 메모리 참조를 실제 메모리 위치로 재지정하기 위하여 하드웨어가 주소를 변환함

• 하드웨어 만으로는 메모리 가상화 구현이 힘듬(운영체제가 관여해야함)

  • 메모리의 빈공간과 사용중인 공간을 알고 메모리 사용을 제어하고 관리해야함

사례

void func()
    int x = 3000;
    x = x + 3;

컴파일러가 변환한 어셈블리 코드

128 : movl 0x0 (\%ebx), \%eax;
132 : addl \$0x03, \%eax;
136 : movl \%eax, 0x0(\%ebx);

• 프로그램의 관점에서 주소공간은 0에서 최대 16kb 까지이다.
• 프로그램이 생성하는 메모리 참조는 이 범위내에 있음
• 메모리 가상화를 위해 운영체제는 프로세스를 물리 메모리 주소가 0이 아닌 다른 곳에 위치

동적(하드웨어 기반) 재배치

• 베이스레지스터와 바운드 레지스터를 활용해 원하는 위치에 주소 공간을 배치할 수 있게 함

베이스 레지스터

• 프로그램이 물리 메모리에 탑재 될때, 운영체제는 어느 위치에 프로그램이 탑재 될지 결정하고 해당 위치를 베이스 레지스터 값으로 지정
• pysical address = virtual address + base
• 하드웨어는 가상주소에 베이스값을 더하여 실제 물리 주소로 변환을 한다.

바운드 레지스터

• 메모리 보호를 위해 존재하는 레지스터
• 가상 주소가 바운드 안에 존재 하는지 확인할 때 필요한 값. 가상주소의 최대 크기 저장되어 있음
• 프로세스가 바운드 보다 큰 가상주소나 음수인 가상 주소를 참조하려고 하면 CPU는 예외를 발생 시킨다.

한 쌍의 레지스터를 가지고 주소 변환에 도움을 주는 프로세서의 일부를 메모리 관리 장치(MMU)라고 함

운영체제 이슈

베이스 바운드 방식의 가상 메모리 구현을 위해서 운영체제가 반드시 개입되어야하는 중요한 세개의 시점이 존재

1) 프로세스가 생성될 때 운영체제는 주소 공간이 저장될 메모리 공간을 찾아 조치를 취해야 함

2) 프로세스가 종료할 때, 정상적으로 종료될 때 또는 잘못된 행동을 하여 강제적으로 죽게 될 때 프로세스가 사용하던 메모리를 회수하여 다른 프로세스나 운영체제가 사용할 수 있게 해야함

3) 운영체제는 프로세스 전환 시 베이스와 바운드 쌍을 저장하고 복원해야 한다.

• 프로세스 중단 시 메모리에 존재하는 프로세스 제어 블럭에 베이스와 바운드 레지스터 값을 저장해야 함

4) 예외 핸들러 또는 호출될 함수를 제공해야한다.

• 부팅시, 특권 명령어를 사용하여 예외 핸들러를 설치함
• CPU가 예외를 발생시킬 때(바운드 밖의 메모리를 접근하려는 경우), 예외에 따른 핸들러가 작동. 보통은 프로세스 종료

프로세스 가상메모리공간 전체를 연속적으로 물리 메모리에 탑재 하게 됨으로서 프로세스의 힙과 스택 사이의 공간이 낭비되는 현상이 발생한다. 이를 해결하기 위해 세그멘테이션(segmentation)이라는 일반화된 base-bound 기법이 등장하게 된다.

[kangchanguk]

페이징

세그멘테이션의 한계

• 논리적인 의미를 가지는 가변크기의 공간으로 메모리를 나눠서 물리 메모리에 올리게 되면 외부 단편화가 발생할 수 있는 태생적인 한계를 가지고 있음

• 동일 크기의 공간으로 분할하는 아이디어 => 페이징(paging)

• 페이징에서는 프로세스의 주소공간을 고정 크기의 단위로 나누게 되고 물리 메모리 또한 페이지 프레임(page frame)이라는 고정크기로 나눔

페이징의 간단한 예시

위의 그림과 같이 64바이트의 작은 주소 공간을 16바이트짜리 페이지 4개로 나눌수 있고 이를 물리 메모리의 페이지 프레임에 탑재 한것을 볼 수 있음.(물리 메모리의 페이지 프레임 또한 16바이트)

페이징 장점

1. 유연성

• 주소공간의 사용 방식(힙인지 스택인지 코드영역인지)에 상관 없이 효율적으로 주소 공간을 관리 할 수 있음
• 힙과 스택이 어느 방향으로 커지는지에 대한 고려가 필요 없어짐

2. 빈공간 관리의 단순화

• 빈공간 리스트에서 각 청크가 같은 크기를 가지고 있기 때문에 단순히 사용자가 원하는 수의 페이지 만큼 반환

주소 공간의 각 가상 페이지에 대한 물리 메모리의 위치를 기록하기 위해서 운영체제는 각 프로세스마다 페이지 테이블이라는 자료구조를 가지고 있다. 페이지 테이블의 주요 역할은 주소 변환이다.

페이징 기법의 주소 변환 방법

• 주소 변환을 위해 먼저 가상 주소를 가상페이지 번호(virtual page number, VPN)와 페이지내에서의 오프셋(OFFSET)으로 나눔

예시

64바이트의 가상주소로 가정 하였으므로 6비트가 필요하고 각 페이지의 크기를 16바이트로하고 총 4개로 나눴기 때문에 2개의 비트로 VPN을 나타낼 수 있다.

가상 주소 21을 변환해 보면 아래와 같다.

• 21의 이진수 형식 : 010101
• vpn : 01 -> 1
• offset : 0101 -> 5
• 의미 : 1번 가상페이지에서 5만큼 떨어진 곳

페이지 테이블을 가지고 가상 페이지가 어떤 물리 페이지 프레임에 저장되어 있는지 찾아 낼수 있고 offset을 통해 해당 물리 페이지 프레임에서 얼만큼 떨어져 있는지도 알아낼 수 있기 때문에 주소 변환이 가능해 진다.

페이지 테이블은 어디에 저장될까?

실제 32비트 주소 공간에서 4KB의 페이지를 사용한다고 하였을 때의 경우에 대해서 가상 주소 공간을 아래와 같이 나눔

• VPN : 20비트 사용

• OFFSET : 12 비트 사용 (10비트 = 1KB 이기 때문에 2비트만 추가 하면 4KB를 나타낼 수 있음)

• 페이지 테이블은 총 2^20(거의 백만) 개의 정보를 저장 하고 있어야 되고 페이지 테이블 항목(page table entry, PTE)마다 4바이트가 필요하다고 한다면 각페이지 테이블을 저장하기 위해 4MB의 메모리가 필요

• 프로세스 100개만 실행 시켜도 400MB의 메모리가 필요하게 되므로 이는 꽤 큰 공간이고 현대의 64비트 주소 공간을 가정하게 된다면 아주 커지게 된다.

-페이지 테이블의 크기가 크기 때문에 이를 MMU안에 유지할 수 없고 운영체제의 가상메모리에 저장된다.

페이지 테이블 안에는 실제 무엇이 있을까?

우선 페이지 테이블이 VPN을 인덱스로 하는 단순한 배열 자료 구조(선형 페이지 테이블)라고 가정하고 생각을 할 수 있다. 이는 이후에 페이징의 문제를 해결하기 위해 고급 자료 구조로 변환된다. VPN 인덱스에 접근하면 PTE에 저장된 정보를 확인 할 수 있음

• valid bit : 할당되지 않은 주소 공간을 표현
  • 주소 공간에서 힙과 스택 사이의 미사용 공간과 같은 미사용 공간을 표시 함으로서 이러한 페이지에 물리 프레임을 할당할 필요를 없애 대량의 메모리를 절약할 수 있음
• protection bit : 페이지의 읽기 / 쓰기 / 실행 권한을 나타냄
• present bit : 페이지가 물리 메모리에 있는지 디스크에 있는지 (스왑 아웃 되었는지 판단)
• dirty bit : 메모리에 반입된 이후 페이지가 변경되었는지 여부를 나타냄
• reference bit : 페이지가 접근되었는지 추적하기 위해 사용
  • 물리 메모리가 모자랄 떄 페이지 교체를 판단하는데 필요한 정보( 어떤 페이지가 인기가 많을 까를 판단) 이외 여러 다양한 비트들이 있음

페이징은 느리다?

• 하드웨어에 페이지 테이블 베이스 레지스터(page table base register)는 페이지 테이블의 시작 위치를 저장하고 있다.

• 모든 메모리 참조에 대해 먼저 페이지 테이블에서 변환 정보를 반입 해야하기 때문에 한번의 추가적인 메모리 참조가 필요하게 된다.

• 메모리 참조는 비용이 비싸기 때문에 프로세스가 느려지게 됨

페이징 단점

• 페이지 테이블 자체가 큰 메모리를 차지 한다.

• 주소 변환을 위한 추가적인 메모리 참조로 인해 느려진다.

[kangchanguk]

세그멘테이션

동적 재배치의 한계

• 내부 단편화: Partition의 크기가 프로세스의 크기보다 커서 메모리가 남지만, 다른 프로세스가 사용할 수 없는 상태
• 힙과 스택사이의 빈 공간
• 프로그램 전체를 물리 메모리에 올려야 함

베이스 바운드의 일반화

• 주소공간의 논리적인 단위인 세그멘트의 갯수만큼 베이스/바운드 레지스터를 가짐
• 대표적인 세그먼트: 코드, 스택, 힙
• 물리 메모리의 각기 다른 위치에 세그멘테이션을 배치할 수 있게 됨으로서 내부 단편화를 막고자 함

세그멘트 종류 파악

• 하드웨어는 가상 주소를 보고 세그먼트의 종류가 무엇인지 알 수 있어야 하고 해당 세그먼트 안에서 오프셋이 얼마인지 알 수 있어야 함.

• 상위 2비트는 세그먼트의 종류
• 하위 2비트는 오프셋을 나타냄
• 오프셋이 바운드보단 작은지 검사하여 유효한 주소인지를 검사

스택

• 스택의 경우 세그멘트와 다르게 주소가 감소하는 방향으로 늘어남
• 세그먼트는 주소공간 내에서 확장하는 방향도 알아야하기 때문에 하나의 비트를 써서 방향을 표시

공유지원

• 주소 공간들 간에 특정 메모리 세그멘트를 공유하는 것이 유용
• protection bit를 추가하여 읽기/쓰기/실행과 같은 권한을 설정 할 수 있음
• 권한을 설정할 수 있게 되면 코드 세그먼트를 읽기 권한으로 설정하면 주소 공간의 독립성을 유지하면서도 여러 프로세스가 주소 공간의 일부를 안전하게 공유 가능

한계

• 외부 단편화 초래
• 압축을 쓰면 어느정도 문제 해결이 가능하지만 세그먼트를 복사하여 새로운 곳으로 이동 시키는 것은 메모리 부하가 큰 연산이고 상당량의 프로세서 시간을 사용하기 때문에 비용이 많이 듬.

[kangchanguk]

TLB

페이징의 한계

• 페이징을 잘못 구현하면 큰 성능 저하가 올 수 있는데 이유는 아래와 같다
• 가상 주소 변환을 위해 주소 변환에 필요한 정보를 담고 있는 페이지 테이블을 접근(메모리 읽기 작업 느림)해야 되기 때문에 성능저하 발생

TLB 란?

• 변환 색인 버퍼(translation-lookaside buffer, TLB)는 MMU의 일부로서 자주 참조되는 가상 주소의 변환 정보를 저장하는 하드웨어 캐시 주소 변환 캐시(address-translation cache)

• 가상 메모리 참조시, 하드웨어는 먼저 TLB를 확인

TLB 기본 알고리즘

1. 가상 주소로 부터 가상 페이지 번호를 추출한다.
2. 해당 가상 페이지 번호가 TLB에 들어있는지 확인한다.
3. 만약 TLB에 들어있다면 TLB에 들어있는 정보 기반으로 물리 주소 계산해서 접근
4. 만약 TLB에 들어있지 않다면 페이지 테이블에 접근하여 주소변환에 필요한 정보를 TLB에 갱신하고 해당 명령어를 재실행

TLB 미스 처리의 주체

하드웨어

• CISC(complex instruction set computers): 복잡한 하드웨어 명령어들로 구성된 컴퓨터 시스템

• TLB 미스 처리를 하드웨어에서 처리한다. 하드웨어는 페이지 테이블에 대한 정보를 가지기 위해 page table base register를 가짐

소프트웨어

• RISC(reduced intruction set computing):
  • TLB 미스를 소프트웨어에서 처리한다
  • TLB 미스가 발생하면 하드웨어는 예외 시그널을 발생 시키고 운영체제의 커널 모드에서 트랩 핸들러가 실행된다.
  • 핸들러에서는 특권명령어를 사용하여 TLB에 접근하여 TLB정보를 갱신한다.
  • 구현 시 중요 사항
    • 시스템 콜과 달리 핸들러가 실행 된 이후 다음 명령어를 실행 하는 것이 아니라 현재 명령어를 재실행 하여야 하기 때문에 운영체제는 트랩의 발생 원인을 알고 있어야 하고 해당 원인에 따라 PC값을 어떻게 변경할지 정해야 한다.
    • TLB 미스 핸들러를 실행 할때, TLB 미스가 무한 반복되지 않도록 주의 해야 한다. 만약TLB 미스 핸들러를 접근하는 과정에서 TLB 미스가 일어나게 된다면 무한 루프에 빠지게 된다. 이를 해결하기 위한 두가지 방법은 아래와 같다.
      • TLB 핸들러의 주소를 물리 주소로 표시한다. (주소 변환 없이 핸들러를 실행 시킬 수 있음)
      • 핸들러 코드 주소를 저장하는데 TLB의 일부를 영구히 할당한다.

TLB 구성

• TLB는 완전 연관(fully associative) 방식으로 설계
• 해당 방식에서 원하는 변환 정보의 검색은 병렬적으로 수행된다.

TLB의 추가적인 정보들

• Valid Bit 특정 항목이 유효한 변환 정보를 가지고 있는지 표현

• Protection Bit 페이지가 어떻게 접근될 수 있는지 표현(읽기, 쓰기, 실행)

문맥 교환 시 TLB 교체

• TLB내에 저장되어 있는 주소 변환 정보는 해당 정보를 탑재 시킨 프로세스에서만 유효하다. 따라서 문맥교환이 일어날 때 현재 TLB에 저장되어 있는 정보는 의미가 사라지게 된다. 해당 문제를 해결하기 위한 방법은 아래와 같다

Valid Bit을 0으로 만들어 TLB를 비우기

• 문맥 교환이 자주 일어 난다면 코드페이지에 접근을 할때 마다 TLB 미스가 발생하므로 성능에 부담을 줌

주소 공간 식별자(address space identifier, ASID)를 추가

• 프로세스 마다 TLB 변환 정보를 구분할 수 있게됨
• 하드웨어는 현재 어떤 프로세스가 실행 중인지 알기 위해 별도의 레지스터가 필요함

TLB 교체 정책

• TLB 캐시가 가득 찻을 때 어떤 부분을 교체해야 할지 정하는 정책이 필요하고 이는 디스크와 메모리 간의 페이지 스와핑 부분과 유사하다.

• 가장 대표적인 정책으로는 최저 사용 빈도(least-recently-used, LRU) 방식이 있다. 사용되지 않은 오래된 항목일수록 다음에 사용될 확률이 적다는 가정에 근거한다.

[kangchanguk]

페이징( 더 작은 테이블 )

• 페이지 테이블을 어떻게 더 작게 만들 수 있을까??

1) 더 큰 페이지

• 페이지 크기가 커질수록 페이지 테이블의 크기는 줄어듬
• 내부단편화 초래

2) 하이브리드(페이징과 세그먼트)

• 기존의 방식대로 페이지 테이블 구성 시 쓰지 않는 공간도 페이지 테이블에 올려야함
• 페이지 테이블을 논리세그멘트로 나누고 세그멘트마다 페이지 테이블을 별도로 구성(코드, 힙, 스택 세그멘트에 대한 각각의 페이지테이블 생성)
• VPN을 Seg로 나눔

• 미사용 공간에 대해서 페이지 테이블을 생성하지 않고, 세그멘트의 size를 정의했기에 원하는 크기만큼의 페이지 테이블 사용이 가능

BUT!!! 세그멘테이션의 고질적인 문제점인 유연함 부족은 해결하지 못함

• 외부 단편화 유발

멀티레벨 페이지 테이블

• 페이지 테이블을 페이지로 구성해버림
• 페이지 디렉토리 -> 페이지 테이블들의 페이지 프레임 번호 위치가 존재 -> 페이지 테이블에서 페이지 테이블 항목 주소를 추출 -> 추출한 페이지 테이블 항목에서 페이지 프레임 번호를 추출 -> offset과 결합하여 실제 물리 주소를 얻어냄

1) Page Directory 에는 PDE가 존재한다. 이 PDE의 PFN의 값으로 접근하면 Page Table(페이지 테이블)이 나온다. 2)Page Table(페이지 테이블)에는 PTE가 존재한다. 이 PTE의 PFN 값으로 접근하면 찾고자 하는 주소의 PFN(Page frame number)이 나온다. 3) 얻어낸 PFN과 OFFSET을 결합시켜 최종 주소를 얻어낸다.

장점

1) 주소공간의 크기에 비례하여 페이지 테이블 공간이 할당 2) 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리에 용이

단점

• TLB 미스시 성능이 하락( 페이지 테이블에 접근하는 과정을 한번 더 수행해야함)

[kangchanguk]

swap mechanisms

• 다수의 프로세스들이 동시에 큰 주소공간을 사용하고 있을 때를 가정
• 큰 주소 공간 지원을 위해 주소공간 중에 현재는 크게 필요하지 않은 일부를 보관해 둘 공간이 필요
• 하드 디스크 드라이브가 해당 역할을 함

큰 주소 공간을 제공하면 좋은 점

• 운영체제에게 필요시 메모리 할당을 요청하기만 하면 됨
• 편리, 용이성

스왑 공간

• 스왑 공간이 추가되면 운영체제는 각 프로세스들에게 큰 가상 메모리가 있는 것 같은 환상을 줌
• 디스크에 페이지들을 저장할 수 있는 일정 공간을 확보(해당 용도의 공간을 스왑 공간이라고 함)
• 메모리 페이지를 읽어서 이곳에 쓰고(swap out), 여기서 페이지를 읽어 메모리에 탑재(swap in)
• 운영체제는 스왑 공간에 있는 모든 페이지들의 디스크 주소를 기억해야함
• 스왑 공간의 크기에 따라 시스템이 사용할 수 있는 페이지 수가 결정

페이지 스왑을 위한 기능

• 페이지가 디스크로 스왑되게 하려면 많은 기법들이 추가되어야 함

present bit

• 하드웨어는 present bit를 사용하여 각 페이지 테이블 항목에 어떤 페이지가 존재하는지를 표현
• 1: 물리 메모리에 해당 페이지가 존재
• 0: 메모리에 해당 페이지가 존재하지 않고 디스크 어딘가에 존재

page fault

• 정의: 페이지 폴트는 프로세스가 참조하려는 가상 메모리 페이지가 현재 물리적 메모리에 로드되어 있지 않을 때 발생

• 목적: 프로세스가 필요로 하는 페이지를 효율적으로 로드하고 관리하는데 필요

페이지 fault 작동 방식

1) 페이지 폴트 발생: 프로세스가 메모리에 접근하려 할 때, 해당 가상 주소에 대응하는 페이지가 물리적 메모리에 없으면 페이지 폴트가 발생

2) 인터럽트 처리: 페이지 폴트는 운영 체제에 의해 처리되는 인터럽트, 운영 체제는 이 인터럽트를 받고 현재 CPU의 상태를 저장한 후 페이지 폴트 처리 루틴을 실행

3) 페이지 로딩: 운영 체제는 필요한 페이지를 찾아 물리적 메모리로 로드, 이 페이지는 디스크의 스왑 영역이나 해당 파일 시스템에서 가져올 수 있습니다.

4) 페이지 테이블 업데이트: 페이지가 메모리에 로드된 후, 페이지 테이블이 업데이트되어 새로운 매핑 정보를 반영

5) 프로세스 재개: 페이지 로딩이 완료되면, CPU는 원래의 프로세스를 재개

메모리에 빈공간이 없을 경우

• 새로운 페이지들을 위한 공간 확보를 위해 하나 또는 그 이상의 페이지들을 먼저 페이지 아웃시킴

• 페이지 교체 정책: 교체 페이지를 선택하는 것

• 운영체제가 여유공간의 크기가 최솟값보다 작아지면 여유공간 확보를 담당하는 백그라운드 쓰레드가 실행

• 백그라운드 쓰레드는 일반적으로 스왑데몬, 페이지 데몬이라고 불리는데 여유공간의 크기가 최대값이 될 때 까지 페이지를 제거