운영체제

바인하·2022년 4월 20일
0

프로세스와 스레드의 차이

프로세스

: 실행 중인 프로그램으로, 디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 것
= 프로세스 스택 + 전역 변수들을 갖는 데이터 섹션 + 동적 메모리 힙

  • PCB (Process Control Block) : 특정 프로세스에 대한 중요 정보를 저장하고 있는 운영체제의 자료구조

    	- OS는 프로세스 관리를 위해 프로세스 생성과 동시에 고유한 PCB 생성
	- 컨텍스트 스위칭이 일어날 때 작업의 진행 상황을 PCB에 저장하고, 다시 CPU 할당받게 되면 저장된 내용을 불러와서 작업 수행

스레드

  • 프로세스의 실행 단위
  • 한 프로세스 내에서 동작하는 여러 실행흐름으로, 프로세스 내의 주소공간이나 자원 공유 가능
  • Code(Text), Data 섹션, 열린 파일이나 신호와 같은 OS 자원들을 공유
  • 멀티스레딩 : 하나의 프로세스를 다수의 실행 단위로 구분하여 자원 공유하고, 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것
    - 이 때, 각각의 스레드는 독립적인 작업을 수행해야 하므로 각자의 스택과 PC 값을 가짐
1. 스택을 스레드마다 독립적으로 할당하는 이유
- 스택 : 함수 호출 시 전달되는 인자, 되돌아갈 주소값, 함수 내에서 선언하는 변수 등을 저장하기 위해 사용되는 메모리 공간
- 스택 메모리 공간이 독립적 = 독립적인 함수 호출이 가능 = 독립적인 실행 흐름이 추가되는 것!
→ 스레드의 정의에 따라 독립적 실행흐름을 추가하기 위한 최소 조건으로 독립된 스택 할당

2. PC를 스레드마다 독립적으로 할당하는 이유
- PC : 스레드가 명령어를 어디까지 수행했는지 나타냄
- 스레드는 CPU를 할당받아도 스케줄러에 의해 선점당할 수 있으므로, 명령어가 연속적으로 수행되지 못하므로 위치를 기억할 필요가 있음

멀티스레드

멀티스레딩의 장점

  • 프로세스로 처리하던 것을 스레드로 구현하면, 메모리 공간과 시스템 자원 소모 줄어듦
  • 스레드 간 통신 필요 시, 별도의 자원이 아니라 전역 변수 공간이나 동적으로 할당된 공간인 Heap 영역을 이용할 수 있음
  • 스레드의 context switch는 프로세스 context switch 와는 달리 캐시 메모리를 비울 필요가 없어 더 빠름
    → 시스템의 throughput 이 향상되고 자원 소모가 줄어들며, 자연스럽게 프로그램 응답 시간이 단축됨
캐쉬는 CPU와 메인메모리 사이에 위치하며 
CPU에서 한번 이상 읽어들인 메모리 데이터를 저장하고 있다가, 
CPU가 다시 해당 데이터를 요구할 때, 
메인메모리를 통하지 않고 데이터를 전달해주는 용도

프로세스 Context Switching이 일어났을 때, 
공유하는 데이터가 없으므로 캐쉬가 쌓아둔 데이터들이 무너지고 새로 캐쉬정보를 쌓아야 한다.

멀티스레딩의 문제점

  • 서로 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 동일한 자원에 동시 접근하여 문제가 발생할 수 있다.
    → 멀티스레딩 환경에서는 동기화 작업이 필요!
    - 즉, 동기화로 작업 순서와 공유 자원에 대한 접근을 컨트롤하는 것
    - 하지만 이로 인해, 병목현상이 발생하여 성능이 저하될 가능성이 높으므로, 과도한 락은 줄여야 함

** 병목현상 : 어떤 시스템 내 데이터의 처리 속도가 지연 됨에 의해서 다음에 오는 데이터 처리가 지연되는 현상

멀티스레드 vs 멀티프로세스

  • 멀티 스레드
    • 멀티 프로세스보다 적은 메모리 공간을 차지하며 문맥 전환이 빠름
    • 오류로 인해 하나의 스레드가 종료되면 전체 스레드가 종료될 수 있음
    • 동기화 문제 고려

  • 멀티 프로세스
    - 하나의 프로세스가 죽어도 다른 프로세스에는 영향이 없고 정상 수행
    • 멀티 스레드보다 많은 메모리 공간과 CPU 시간을 차지

스케줄러

  • 프로세스를 스케줄링하기 위한 Queue 3가지
    1) Job Queue : 시스템 내의 모든 프로세스 집합
    2) Ready Queue : 메모리 내에 있으면서 CPU를 잡아서 실행되길 기다리는 프로그램
    3) Device Queue : Device I/O 작업을 대기하고 있는 프로세스 집합

  • 장기 스케줄러 : 어떤 프로세스를 ready queue에 넣을 것인가?
    - 많은 프로세스가 한번에 메모리에 올라올 경우, 대용량 메모리 (일반적으로 디스크) 에 임시저장됨
    • 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당해 ready queue로 보낼지 결정하는 역할을 함
    • 수십 초~수 분 단위로 가끔 호출되므로 상대적으로 속도 느린 것이 허용됨

→ 현재 시분할 시스템에서 사용되는 OS에는 일반적으로 장기 스케줄러 두지 않는 경우가 대부분
- 프로세스가 시작되면 장기 스케줄러 없이 바로 그 프로세스에 메모리를 할당해 ready queue에 넣어준다.

  1. 메모리와 디스크 사이의 스케줄링 담당
    _ 디스크에서 하나의 프로그램을 가져와 커널에 등록하면 프로세스가 됨 -> 이 프로세스를 메모리에 할당하는 것
  2. 프로세스에 memory 및 각종 리소스 할당 (admit)
  3. 실행중인 프로세스 수 제어 = degree of Multiprogramming
  4. 프로세스의 상태
    new -> ready (admitted)
  • 단기 스케줄러 : 어떤 프로세스에게 CPU를 할당해줄 것인가?
  • ms 이하 시간 단위로 매우 빈번하게 호출되므로 수행속도가 빨라야 함
  1. CPU와 메모리 사이의 스케줄링 담당
    _ CPU 스케줄러라고도 함
  2. Ready Queue 의 프로세스 중 어떤 프로세스를 running 시킬 지 결정
    _ 시분할 시스템에서 timer interrupt 발생 시 단기 스케줄러 호출됨
  3. 프로세스에 CPU 할당 (scheduler dispatch)
  4. 프로세스의 상태
    ready -> running -> waiting -> ready
  • 중기 스케줄러 : 메모리에 적재된 프로세스 수 관리
  1. 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러
  2. 여유 공간 마련을 위해 프로세스 통째로 메모리에서 디스크로 쫓아냄 (swapping)
    _ 메모리에 올라와 있는 프로세스 중 일부로부터 메모리를 통째로 빼앗아 그 내용을 디스크의 swap 영역에 저장해둠 (= Swap out)
  3. 프로세스에서 memory deallocate
  4. degree of Multiprogramming 제어
  5. 프로세스의 상태
    ready -> suspended

중기 스케줄러의 등장으로 프로세스의 상태에 중지(Suspended or Stopped) 상태가 추가 되었으며 중지 상태의 프로세스는 메모리를 통째로 빼앗기고 디스크로 스왑 아웃된다. 중지 상태는 Suspended Blocked 와 Suspended Ready 상태로 나뉜다.

  • 중지 준비 (Suspended Ready) : ready 상태의 프로세스가 중기 스케줄러에 의해 디스크로 swap out
  • 봉쇄 중지 (Suspended Blocked) : blocked 상태의 프로세스가 중기 스케줄러에 의해 디스크로 swap out

Suspended Blocked 상태이던 프로세스가 blocked 조건을 만족하게 되면 이 프로세스의 상태는 Suspended Ready 상태로 바뀌게 된다.
 Suspended 에 있는 프로세스들은 Suspended Blocked이든 Suspended Ready이든 관계없이 메모리를 조금도 보유하지 않고 디스크에 통째로 스왑 아웃된 상태로 존재하게 된다.

** suspended (Stopped)

  • 외부적인 이유로 프로세스 수행이 정지된 상태로, 메모리에서 내려간 상태를 의미한다.
  • 프로세스 전부 디스크로 swap out
  • blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 ready state 로 돌아갈 수 있지만, 이 상태는 외부적인 이유로 suspending 되었기 때문에 스스로 돌아갈 수 없음

CPU 스케줄러

  • 스케줄링 대상: Ready Queue에 있는 프로세스

1. FCFS (First Come First Served)

  • 먼저 온 순서대로 처리
  • 비선점형 스케줄링
    - 일단 CPU를 잡으면 CPU Burst가 완료될 때까지 CPU 반환하지 않고, 할당된 CPU가 반환될 때만 스케줄링 이루어짐

<문제점>

  • convey effect : CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들이 오래 기다리는 현상, 효율성이 낮아짐

2. SJF (Shortest Job First)

  • 도착순서에 상관없이 CPU Burst time (CPU 점유시간) 이 짧은 프로세스에게 먼저 할당
  • 비선점형 스케줄링

<문제점>

  • starvation : 사용시간이 긴 프로세스는 거의 영원히 CPU를 할당받을 수 없음
    (starvation 상태를 해결하기 위한 방법은? : aging = HRN (Highest Repsonse ratio Next))

3. SRTF (Shortest Remaining Time First)

  • 새로운 프로세스가 도착할 때마다 새로운 스케줄링 이루어짐
  • 선점형 스케줄링
    - 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 갖는 새로운 프로세스가 도착하면 CPU를 뺏김

<문제점>

  • starvation : 새로운 프로세스가 도달할 때마다 스케줄링 다시하므로 CPU burst time을 측정할 수 없음
    _ 실행 시간이라는 임의의 값이라서 실제로 예측하기 어렵기 때문에 문제가 발생함

4. Priority Scheduling

  • 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링
  • 선점형 스케줄링 : 더 높은 우선순위 프로세스 도착 시 실행중인 프로세스 멈추고 CPU 선점
  • 비선점형 스케줄링 : 더 높은 우선순위 프로세스 도착 시 Ready Queue의 head에 넣음

<문제점>

  • starvation (Infinite blocking) : 실행준비는 되어있으나 CPU 사용못하는 프로세스를 CPU가 무기한 대기하는 상태

<해결책>

  • aging : 아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자

5. Round Robin

  • 현대적인 CPU 스케줄링
  • 각 프로세스는 동일크기의 할당시간 갖게 됨
  • 할당시간 지나면 프로세스 선점당하고, ready queue 제일 뒤로 다시 들어감.
  • RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있는 경우 효율적
    - 이것이 가능한 이유는 프로세스의 context를 save 할 수 있기 때문
    -> 응답시간이 짧은 경우에 좋음 (실시간 같은)

<장점>

  • Response time이 빨라짐
    -> n개의 프로세스가 ready queue에 있으며 / 할당시간이 q (time quantum) 인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 얻음
  • 프로세스가 기다리는 시간이 CPU 사용하는 만큼 증가 = 공정한 스케줄링

<유의점>

  • time quantum 이 너무 크면 FCFS 와 같음
  • 너무 작으면 스케줄링 알고리즘 목적에는 이상적이지만, 잦은 context switching 으로 overhead 발생
적당한 time quantum 이 무엇일까? 

- CPU Burst time의 80% 를 포함할 수 있도록

동기와 비동기의 차이

[참고]

Blocking : 호출된 함수가 할 일을 모두 마칠 때까지 제어권을 계속 갖고 호출한 함수에게 바로 돌려주지 않는 경우

Non-Blocking : 호출된 함수가 할 일을 마치지 않았더라도 바로 제어권을 건네주어 호출한 함수가 다른 일을 진행할 수 있도록 해주는 경우

Synchronous : 호출된 함수의 수행 결과 및 종료를 호출한 함수도 신경쓰는 경우

Asynchronous : 호출된 함수의 수행결과 및 종료를 호출된 함수 혼자 신경쓰고 처리하는 경우

시스템의 반환을 기다리는 동안

- 대기큐에 머무는 것이 필수라면 : blocking!!
- 대기큐에 머무는 것이 필수가 아니라면 : synchronous!! 그냥 신경만 쓰는 것.
  • 동기 : 메소드를 실행시킴과 동시에 반환 값이 기대되는 경우 <-> 비동기
    • 동시에 = 실행되었을 때 값이 반환되기 전까지는 blocking 되어 있는 상태!
    • 비동기의 경우, blocking 되지 않고 이벤트 큐에 넣거나 백그라운드 스레드에게 해당 task 위임하고 바로 다음 코드 실행

프로세스 동기화

  • Critical Section (임계 영역) : 동일한 자원을 동시에 접근하는 작업을 실행하는 코드 영역

→ 프로세스들이 Critical Section을 함께 사용할 수 있는 프로토콜을 설계하려면?

  1. 해결을 위한 기본조건
  • Mutual Exclusion (상호 배제) : 프로세스 P1이 임계 영역에서 실행중이면, 다른 프로세스들은 그들이 가진 임계영역에서 실행될 수 없음
  • Progress (진행) : 임계영역에서 실행중인 프로세스가 없고 / 별도의 동작이 없는 프로세스들만 임계영역 진입 후보로서 참여될 수 있음
  • Bounded Waiting (한정 대기) : P1이 임계영역에 진입신청 후부터 받아들여질 때까지, 다른 프로세스들이 임계영역에 진입하는 횟수는 제한이 있어야 함
  1. 해결책

  • Mutex Lock
    - 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section 으로 진입하는 프로세스는 lock 획득, CS 를 빠져나올 때 lock을 방출함으로써 동시 접근 불가능하도록!
    - 한계 : 멀티프로세스 환경에서는 시간적 효율성 측면에서 적용할 수 없음 (멀티스레딩을 하려면 Mutex Lock 을 걸어주면 동기화하는 의미가 없어지므로 시간적 효율성이 떨어짐)

  • Semaphore
    - 소프트웨어상에서 CS 문제를 해결하기 위한 동기화 도구
    - Counting Semaphore : 이용 가능한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 이용 가능한 자원의 개수로 초기화됨.
    - Binary Semaphore : Mutex 라고도 부르며, 다중 프로세스들의 CS 문제를 해결하기 위해 사용됨.

    [단점]

    • Busy Waiting : Semaphore 초기버전에서 CS 에 진입해야 하는 프로세스는 진입 코드를 계속 반복실행해야 해서, CPU 시간을 낭비했는데, 이를 Busy Waiting 이라고 불렀음.

      Semaphore에서 CS에 진입을 시도했지만 실패한 프로세스에 대해 block 시킨 뒤, CS에 자리가 날때 다시 깨우는 방식을 사용함으로써 Busy Waiting으로 인한 시간 낭비 문제가 해결됨

    • Deadlock : 둘 이상의 프로세스가 CS 진입을 무한정 기다리고 있고, CS에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되어야만 빠져나올 수 있는 상황을 지칭

  • 모니터
    - 개발자의 코드를 상호배제하게끔 만든 추상화된 데이터 형태
    - 공유자원에 접근하기 위한 키 획득, 자원 사용 후 해제를 모두 처리

→ 언어 차원에서 제공하는 프레임워크 / 개발자 입장에서는 mutex, semaphore 보다 수월하게 다룰 수 있는 것

메모리 관리 전략

1. 메모리 관리 배경

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

  • Swapping : 표준 Swapping 방식으로는 RR과 같은 스케줄링의 멀티프로세스 환경에서, CPU 할당시간이 끝난 프로세스의 메모리를 보조 기억장치 (HDD) 로 내보내고 다른 프로세스 메모리 불러들임
    • Swap-In : 주기억장치 (RAM) 으로 불러오는 과정
    • Swap-Out : 보조기억장치로 내보내는 과정
  • 큰 디스크 전송시간이 필요하기 때문에 (하드디스크에 있던 것을 다시 메모리에 로딩시켜야 하니까) , 현재는 메모리 공간이 부족할 때만 Swapping이 시작됨

  • 단편화 (Fragmentation) : 프로세스들이 메모리에 적재/제거되는 일이 반복되면, 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할만큼의 작은 자유공간이 늘어나게 되는데, 이것이 단편화
    • 외부 단편화 : 메모리 공간 중 사용하지 못하게 되는 일부분으로, 물리메모리(RAM) 에서 사이사이 남는 공간을 모두 합쳐 충분한 공간이 되는 부분들이 분산되어 있을 때 발생

      압축 : 외부 단편화를 해소하기 위해 프로세스가 사용하는 공간들을 한쪽으로 몰아 자유공간을 확보하는 방법론 / 하지만 작업효율이 좋지 않음 -> 애초에 그냥 방법론일 뿐이고 현실적으로 불가능
    • 내부 단편화 : 프로세스가 사용하는 메모리공간에 포함된 남는 부분
      100MB 메모리에 80MB 크기의 프로세스를 올리면 20MB의 내부 단편화가 발생

2. Paging (페이징)

[참고]

  • 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없앤 메모리 관리 방법
    → 외부 단편화+압축 작업 해소하기 위한 방법론
    (외부단편화+압축 하려는 게 메모리 공간 연속적으로 사용하게 하려는 것이기 때문)

    물리메모리는 Frame 이라는 고정 크기로 분리
    논리메모리 (가상메모리) 는 Page 라는 고정 크기의 블록으로 분리

  • 각각의 페이지는 물리 메모리의 프레임과 맵핑
  • 페이지를 가리키는 논리주소에서, 프레임을 가리키는 물리주소로 변환

Page Fault (페이지 부재) : 프로세스의 페이지가 물리메모리에 없는 경우

_ 페이지 부재 발생시, 요청된 페이지를 디스크에서 메모리로 읽어와야 함
→ 이 때, 물리메모리에 빈 프레임이 존재하지 않는다면, 메모리에 이미 있는 페이지 중 하나를 디스크로 쫓아내어 공간 확보해야 함 = 페이지 교체해야 함
OS가 Page Fault를 해결하는 과정을 요구 페이징이라고 한다.

→ 페이징 기법을 통해 논리 메모리는 물리 메모리에 저장될 때 연속 저장일 필요가 없고, 물리메모리의 남는 프레임에 적절히 배치됨으로써 외부 단편화를 해결할 수 있음

하나의 프로세스가 사용하는 공간 = 여러 개의 Page로 나뉘어 관리됨 (논리 메모리에서)
개별 페이지는 순서에 상관없이 물리 메모리에 있는 프레임에 mapping 되어 저장됨

  • 단점 : 내부 단편화 문제의 비중이 늘어남.
    → 해결하려면 페이지 단위를 작게 한다. 완전히 해결할 수는 없고 단편화를 최소화할뿐!

3. Segmentation (세그멘테이션)

[참고]
https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-14.-%EC%84%B8%EA%B7%B8%EB%A9%98%ED%85%8C%EC%9D%B4%EC%85%98

  • 페이징 (일정 크기인 페이지 단위로 잘라서 적재) 에서처럼 논리/물리메모리를 같은 크기의 블록이 아닌, 서로 다른 크기의 논리적 단위인 세그먼트로 분할
치즈를 모두 같은 단위로 잘라서 보관 - paging
치즈를 다른 크기로 잘라서 보관 - segmentation
  • 세그멘테이션은 프로세스를 세그먼트 집합으로 생각
  • 세그먼테이션은 물리적인 크기의 단위가 아닌 논리적 내용의 단위(의미가 같은)로 자르기 때문에 세그먼트들의 크기는 일반적으로 같지 않다.
    • 프로세스 = Code + Data + Stack 으로 나누는 것 역시 세그멘테이션의 모습이다.
- 세그먼트 테이블 : 세그먼트 번호+시작주소(base)+세그먼트 크기(limit)
- CPU 에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트 발생시켜 해당 프로세스를 강제 종료시킴

논리주소 (s,d) -> 물리주소 (a,d) 로 변환
d = 세그먼트 크기
a = base[s]+d

[EX]
논리주소 (2,100) = 4300+100 = 4400번지 물리주소
논리주소 (1,500) = limit이 400인데 이를 넘었기 때문에 프로세스 강제 종료

  • 단점 : 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되면, 자유공간들이 많은 수의 작은 조각들로 나누어져 못쓰게 될 수도 있음 → 외부 단편화

가상메모리

  • 다중 프로그래밍 실현하려면, 많은 프로세스들을 동시에 메모리에 올려두어야 함.
  • 가상메모리는 프로세스 전체가 메모리 내에 올라오지 않아도 실행이 가능하도록 하는 기법
    = 최소한의 메모리를 할당받아 RAM에서 사용하고, 나머지는 HDD에 저장하는 것

1. 가상 메모리 개발 배경

- 실행되는 코드의 전부를 물리 메모리에 존재시켜야 하며,
- 메모리 용량보다 큰 프로그램은 실행시킬 수 없었음
- 여러 프로그램을 동시에 메모리에 올릴 때는 용량의 한계, 페이지 교체 등의 성능 이슈 발생
- 가끔만 사용되는 코드가 메모리를 차지할 수 있으므로 전체 프로그램이 메모리에 올라와 있는 것은 불필요

프로그램의 일부분만 메모리에 올릴 수 있다면?
1. 물리 메모리 크기에 제약받지 않음
2. 더 많은 프로그램을 동시에 실행할 수 있음
(응답시간 유지, CPU 이용률과 처리율 높아짐)
3. 프로그램에서 사용하지 않는 부분은 올리지 않음으로써, 공간을 확보하여 Swap 에 필요한 입출력 줄어들기 때문에 프로그램 빠르게 실행가능

2. 가상 메모리가 하는 일

  • 실제 물리메모리와 사용자의 논리 메모리를 분리한 것
  • 따라서, 작은 메모리를 갖고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공 가능

  • 가상 주소 공간
    • 한 프로세스가 메모리에 저장되는 논리적 모습을 가상 메모리에 구현한 공간
    • 프로세스가 요구하는 메모리 공간을 가상메모리에서 제공함으로써, 현재 직접적으로 필요하지 않은 메모리 공간은 실제 물리 메모리에 올리지 않는 것으로 물리 메모리 절약 가능

  • 프로세스간의 페이지 공유
    가상메모리는..!
    • 시스템 라이브러리 (프로세스가 OS에게 요청해서 쓸 수 있는 함수들)가 여러 프로세스들 사이에 공유될 수 있도록 함
      → 각 프로세스들은 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것으로 인식하지만, 라이브러리가 올라가있는 물리메모리 페이지들은 모든 프로세스에 공유되고 있음

      < 가상메모리에서는 여러 프로세스들이 하나의 물리메모리를 참조할 수 있으니까, 프로세스 A, B가 같은 부분을 참조하면 되므로 물리 메모리 공간을 절약할 수 있고, 디스크에서 RAM으로 중복해서 올릴 필요가 없음 >

    • 프로세스들이 메모리 공유하는 것을 가능하게 함
      → 공유 메모리를 통해 프로세스간 통신 가능
      → 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있음
    • fork() 를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 함

3. Demand Paging (요구페이징)

  • 운영체제는 Page Table 로 가상메모리 관리
    Page Table 에는 각 페이지가 저장되어 있는 주소값이 있음. +) Valid Bit 를 이용해 해당 페이지가 어느 메모리에 있는지 표시가능 

<요구 페이징을 수행하는 과정>
1. 페이지 테이블 참조하여 메모리에 해당 페이지가 올라와 있는지 여부 확인
2. 페이지가 메모리에 없는 경우(Page Fault) MMU가 인터럽트 발생시킴
3/4. OS는 해당 프로세스를 wait 상태로 만들고, 요구된 페이지를 HDD에서 찾아 메모리에 적재
→ 비어있는 프레임이 없으면 페이지 교체 알고리즘이 등장할 타이밍!
5. 페이지 테이블 갱신
6. 해당 프로세스를 다시 ready->running하여 작업 진행
  • 프로그램 실행 시작시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 것이 아니라! 초기에 필요한 것들만 적재하는 전략
    → 가상메모리 시스템에서 많이 사용됨
    - 실행과정에서 필요해질 때 페이지들이 적재되며, 한번도 접근되지 않은 페이지는 물리메모리에 적재X
  • 프로세스 내의 개별 페이지들은 Pager 에 의해 관리됨 → 페이저는 프로세스 실행에 실제 필요한 페이지들만 메모리로 읽어와서, 사용되지 않을 페이지를 가져오는 시간낭비와 메모리 낭비를 줄일 수 있음
  • Page Fault Trap: 페이지가 메모리에 없는 경우 발생되는 것

4. 페이지 교체

  • 프로그램 실행 시 모든 항목이 물리 메모리에 올라오지 않으므로, 프로세스 동작에 필요한 페이지를 요청하는 과정에서 page fault (페이지 부재)가 발생하면 원하는 페이지를 보조저장장치에서 가져오게 됨

    • page fault 란?
      - 프로그램이 자신의 주소공간에는 존재하지만, 시스템의 RAM에는 현재 없는 데이터나 코드에 접근 시도했을 경우 발생하는 현상

  • 물리 메모리가 모두 사용중인 상황이라면?

  1. 디스크에서 필요한 페이지 위치 탐색
  2. 빈 프레임 탐색
    - 페이지 교체 알고리즘을 통해 희생될 페이지 선택 
    - 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블 수정
  3. 새롭게 비워진 프레임에 새 페이지 읽어와서, 프레임 테이블 수정
  4. 사용자 프로세스 재시작
  • 페이지 교체 알고리즘
  1. FIFO 페이지 교체
    물리 메모리에 들어온 페이지 순서대로 교체 시점에 먼저 나간다.
    <단점>
    • 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높일 수도 있다.
    • Belady의 모순 : 페이지 저장가능한 페이지 프레임 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순 존재
  2. 최적 페이지 교체
    앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체한다.
    <장점>
    • 가장 낮은 페이지 부재율을 보장
    <단점>
    • 모든 프로세스의 메모리 참조 계획을 미리 파악할 방법이 없어서 구현의 어려움이 있음
  3. LRU 페이지 교체
    Least Recently Used : 최적 알고리즘의 근사 알고리즘으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체
  4. LFU 페이지 교체
    Least Frequently Used : 참조 횟수가 가장 적은 페이지 교체
  5. MFU 페이지 교체
    Most Frequently Used : 참조 횟수가 가장 많은 페이지 교체 -> 참조 횟수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될거라는 가정에 기반함

캐시의 지역성

캐시의 지역성 원리

  • 캐시메모리 : 속도 빠른 장치와 느린 장치간의 속도차에 따른 병목현상을 줄이기 위한 범용 메모리 // 주기억장치와 CPU 사이에 위치하여 자주 사용하는 프로그램과 데이터를 기억함
  • 캐시의 성능은 작은 용량의 캐시 메모리에 CPU가 이후에 참조할 쓸모 있는 정보가 어느 정도 들어있느냐에 따라 좌우됨 → 따라서 CPU가 어떤 데이터를 원할 것인가를 어느정도 예측할 수 있어야 함

이 때, 적중률(Hit rate)을 극대화시키기 위해 데이터 지역성(Locality) 의 원리 사용!

Locality: 기억장치 내의 정보를 균일하게 접근하는 것이 아니라 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성

- 시간 지역성 : 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성
- 공간 지역성 : 대부분 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

Caching line

  • 캐시 : 프로세서 가까이 위치하면서 빈번하게 사용되는 데이터를 놔두는 장소
    → 캐시가 아무리 가까이 있어도, 찾고자 하는 데이터가 어디에 저장된지 몰라 데이터를 순회해야 하면 시간 오래 소요
    = 즉, 캐시에 목적 데이터가 저장되어 있다면 바로 접근하여 출력할 수 있어야 캐시가 의미 있는 것

  • 따라서 캐시에 데이터 저장시 특정 자료구조를 사용하여 묶음으로 저장하는데, 이를 캐싱라인 이라고 한다
  • 프로세스는 다양한 주소에 있는 데이터를 사용하므로 빈번하게 사용하는 데이터 주소 또한 흩어져 있기 때문에, 캐시에 저장하는 데이터는 데이터 메모리 주소 등을 기록해둔 태그를 달 필요가 있다
    → 이러한 태그들의 묶음을 캐싱라인이라고 함 / 메모리로부터 가져올 때도 캐싱라인을 기준으로~
  1. Full Associative
    • 태그와 관계없이 비어 있는 캐시 메모리를 탐색해서 집어 넣고, 데이터가 있는지 찾을 때도 순차적으로 탐색해서 가져오는 방식
    • 충돌 위험 적지만, 비교할 때마다 순차탐색 시간 발생해서 오래 걸림
  2. Set Associative
    • Full Associative와 Direct Map의 장점들을 고려하여 만들어진 방식
    • 테이블을 여러 개 만들면 같은 태그의 메모리여도 다른 테이블의 태그에 저장하면 되므로 테이블 개수에 따라 n-way set associative 라고 부름
      = n번만 탐색하면 돼서 direct map보단 시간이 걸리지만 충돌 위험이 줄어듦
  3. Direct Map
    • 테이블이 1개여서 같은 태그는 1개의 캐시 공간만 사용할 수 있음
    • 캐시 메모리에 데이터가 있는지 찾으려면 비교는 1번만 해도 돼서 빠르지만, 충돌이 자주 일어남
profile
바인하
되면 한다
이전 포스트

[CS] 네트워크

다음 포스트

4장: 처리율 제한 장치의 설계

0개의 댓글