CPU와 메모리 심화

스케줄링

프로세스와 스레드

• 프로세스: 프로그램을 실행하는 주체
• 스레드: 작업을 처리해주는 주체

CPU는 한정된 자원으로 최대한 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야만 한다.
=> OS는 실행 대기중인 프로그램(프로세스)들에게 CPU 자원을 적절하게 배정하여 시스템의 성능을 끌어올릴 수 있다.

공통 배정 조건

• 오버헤드: 프로세스가 필요한 자원보다 더 많은 지원을 사용하는 것
• 사용률: 프로세스가 최대한 자원을 많이 받고 빨리 처리하는 것
• 기아현상: 프로세스가 자원할당을 받지 못해 대기하는 것

오버헤드↓, 사용률↑, 기아현상↓
1. 배치 시스템 : 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
2. 대화형 시스템 : 빠른 응답 시간. 적은 대기 시간이 중요
3. 실시간 시스템 : 실시간(time) 즉, 최소 응답시간(dead line) 이 중요!

스케줄링의 단위

프로세스 실행은 CPU실행 <-> 입/출력 대기의 반복이다.

스케줄링 알고리즘 평가기준

• CPU이용률 : 전체 시스템 시간 중, CPU가 작업을 처리하는 시간의 비율
• 처리량 : CPU가 단위 시간당 처리하는 프로세스의 개수
• 총 처리 시간 : 프로세스가 시작해서 끝날때 까지 걸린 시간
• 대기시간 : 프로세스가 준비완료 큐에서 대기하는 시간의 총 합
• 응답시간 : 대화식 시스템에서 요청 후 첫 응답이 오기까지 걸린 시간

스케줄링 종류

선점 스케줄링

OS가 CPU의 사용권을 선점할 수 있는 경우,강제 회수하는 경우(처리 시간 예측이 어려움)
=> OS가 나서서 CPU 사용권을 '선점'하고 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식이다.

• 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수할 수도 있습니다.
• 따라서 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어할 수 있다.

1.priority Scheduling(우선순위 스케줄링)

• 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 우선 순위가 낮은 프로세스가 무한정 기다리는 기아 현상 발생 가능
• Aging 방법으로 기아현상 문제 해결 가능

2.Round Robin(라운드로빈)
정해진 시간 할당량 만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐의 가장 마지막에 가서 재할당을 기다리는 방법(회전식)

3.Multilevel-Queue(다단계 큐)
준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케줄링 알고리즘을 가지는 방식
메모리 크기, 우선순위, 유형 등 프로세스의 특성에 따라 하나의 큐에 영구적으로 할당되기에 큐와 큐 사이에도 스케줄링이 필요하다.

비선점 스케줄링

프로세스 종료 또는 I/O 등 이벤트가 있을 때까지 실행 보장(처리시간 예측 용이)
어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나, 입출력 요구가 발생하여 자발적으로 중지될 때 까지 계속 실행되도록 보장하는 방법

• 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상할 수 있습니다.
• 선점방식보다 스케쥴러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적습니다.
• 일괄처리 시스템에 적합하며 자칫 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있습니다.

1.FCFS

• 큐에 도착한 순서대로 CPU 할당
• 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
  먼저 도착한 프로세스를 먼저 처리한다.
  비 선점형이며 FIFO큐를 이용하여 간단하게 구현
  다만, 긴 처리시간의 프로세스가 선점될 경우 나머지 프로세스들은 끝날때까지 대기해야하는 Convoy Effect(호위효과)가 발생한다.
  먼저 도착한 프로세스의 버스트 타임에 따라서 평균 대기시간의 편차가 크다.

2.SJF

• 수행시간이 가장 짧다고 판단되는 작업 먼저 수행
• FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
  CPU 버스트 타임이 가장 짫은,최단 작업을 우선 스케줄링 하는 알고리즘이다.
  가장 적은 평균 대기 시간을 달성 가능하다.
  CPU 버스트 시간이 동일한 경우, FCFS 방식을 따른다. (선점형인 경우)
  CPU 버스트 시간이 동일한 경우, 최소잔여시간우선법칙을 따른다. (비선점형인 경우)
  ==>최소 잔여 시간이 더 적은 프로세스를 할당하여 처리한다

3.HRN

• 우선순위를 계산하여 점유 불평등 보완(SJF 단점 보완)
• 우선순위 = (대기시간 + 실행시간) / (실행시간)

스케줄링 동작시점

프로세스의 상태변화와 스케줄링

1. 수행 -> 대기 (Running->Waiting) : I/O요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때
2. 수행 -> 종료 (Running -> Terminate) : 프로세스를 종료시켯을때
3. 수행 -> 준비 (Running-> Ready) : 인터럽트가 발생했을때
4. 대기 -> 준비 (Waiting -> Ready) : I/O가 완료되었을때

• 여기서 1,2은 프로세스가 스스로 CPU를 반환하기에 비선점 스케쥴링
  
• 3,4은 프로세스에서 CPU를 강제로 할당(회수)해야 하므로 선점 스케쥴링

캐시

캐시는 데이터를 미리 복사해 놓는 임시 저장소

• 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리
• 데이터 접근에 오래 걸리는 경우를 해결하고 다시 계산하는 시간을 절약
• 즉, 캐시는 계층과 계층 사이에서 속도차이를 해결하기 위한 임시 저장소입니다.
  • ex1) 레지스터 : 메모리와 CPU 사이의 속도 차이를 해결하기 위한 캐시
  • ex2) 주기억장치 : 캐시 메모리와 보조기억장치 사이의 속도 차이를 해결하기 위한 캐시

지역성의 원리

지역성: 자주 사용되는 데이터의 특성
캐시를 직접 설정할 때는 자주 사용되는 데이터를 기반으로 설정해야 하므로 이러한 특성을 지역성이라고 한다.

1. 시간 지역성

• 최근 사용한 데이터에 다시접근하려는 특성
  for문에서 i와 같이 반복문 안에서 지속적으로 접근이 이루어지는 변수

2. 공간 지역성

• 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하려는 특성
  for문에서 배열 arr과 같이 공간에 i가 연속적으로 할당되어 접근하는 방식

캐시히트와 캐시미스

1.캐시히트
캐시에서 원하는 데이터를 찾은 것

• 위치도 가깝고 CPU 내부버스를 기반으로 작동하여 빠르다
• 👉 캐시히트를 하게 되면 해당 데이터를 제어장치를 거쳐 가져오게 된다.

2.캐시미스
해당 데이터가 캐시에 없다면 주메모리로 가서 데이터를찾아오는 것

• 메모리를 가져올때 시스템 버스를 기반으로 작동하기 때문에 느리다
  

메모리 할당

메모리에 프로그램을 할당시 시작 메모리 위치,메모리의 할당 크기를 기반으로 할당

1. 연속 할당

• 메모리에 '연속적으로' 공간을 할당하는 것을 말합니다.
• 고정 분할 방식과 가변 분할 방식으로 나뉩니다.

1.고정 분할 방식

• 메모리를 미리 나누어 관리하는 방식 입니다.
• 한계
  • 내부 단편화 발생 ⭕

2.가변 분할 방식

• 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용하는 방식 입니다.
• 종류
  1. 최초적합: 위에서부터 바로 보이는 공간에 바로 할당
     • 메모리 내에서 빈 공간 중 가장 먼저 발견되는 첫 번째 공간에 블록을 할당합니다.
     • 블록 크기와 공간 크기가 일치하지 않을 경우, 남은 공간을 새로운 빈 공간으로 남깁니다.
     • 초기 메모리 관리를 위한 간단한 방법이지만, 외부 조각화가 발생할 수 있습니다.
  2. 최적적합: 가장 크기에 맞는 공간부터 채우고 나머지를 할당
     • 메모리 내에서 블록 크기와 가장 근접한 크기를 가진 가장 작은 빈 공간을 찾아 할당합니다.
     • 블록 크기와 공간 크기가 일치하지 않을 경우, 남은 공간을 새로운 빈 공간으로 남깁니다.
     • 내부 조각화는 줄일 수 있지만, 메모리를 탐색하는 데 시간이 걸리므로 성능 저하가 있을 수 있습니다.
  3. 최악적합: 가장 크기가 큰 공간에 부터 채우고 나머지 할당
     • 메모리 내에서 가장 큰 빈 공간을 찾아 블록을 할당합니다.
     • 할당된 블록 크기와 공간 크기가 일치하지 않을 경우, 외부 조각화가 발생합니다.
     • 내부 조각화가 적지만, 빈 공간을 찾는 데 시간이 걸리므로 성능 저하가 있을 수 있습니다.
• 한계
  • 내부 단편화 발생 ❌
  • 외부 단편화 발생 ⭕

내부단편화 & 외부단편화
내부단편화: 메모리를 나눈 크기보다 프로그램이 작아서 들어가지 못하는 공간이 많이 발생하는 현상

• 하나의 메모리 공간 > 프로그램
  외부단편화: 메모리를 나눈 크기보다 프로그램이 커서 들어가지 못하는 공간이 많이 발생하는 현상
• 하나의 메모리 공간 < 프로그램

3. 불연속 할당

• 메모리 공간 할당과 해제 시의 오버헤드가 발생할 수 있다.

• 메모리 공간이 분산되어 있기 때문에 프로세스가 불연속 공간에 할당될 경우 프로세스의 페이지 교체와 같은 작업이 더 복잡해질 수 있다.

• 불연속 할당의 3가지 방법

  • 1.링크드리스트: 불연속 공간에 프로세스를 할당시, 할당된 공간의 주소를 연결리스트에 저장하는 방식, 메모리의 할당과 해제가 빠르지만 공간낭비가 발생할 수 있음
  • 2. 비트맵: 메모리 공간의 각 블록을 0 또는 1로 표시하여 사용 가능한 블록과 사용 중인 블록을 구분하는 방식, 이 방식은 링크드 리스트보다 효율적인 공간 관리를 제공하나 메모리 크기가 큰 경우 비트맵이 매우 커지는 단점이 있다.
  • 3. 페이지 테이블: 가상 메모리 시스템에 사용되는 방식으로
       물리적인 주소 공간을 페이지라는 작은 블록으로 나누어 사용한다.
       각 프로세스는 자신의 페이지 테이블을 가지며, 페이지 테이블은 물리적인 주소와 가상 주소를 매핑하는 역할을 한다.

불연속 할당(가상메모리) 기법들

1. 페이징

• 동일한 크기의 페이지 단위 나누어 메모리의 서로 다른 위치에 프로세스를 할당
• 빈데이터(홀)의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡

2.세그멘테이션

• 의미 단위인 세그먼트로 나누는 방식
• 코드와 데이터 등을 기반으로 나눌 수 있으며, 함수 단위로 나눌 수도 있음을 의미합니다.
• 공유와 보안 측면에서 좋습니다.
• 빈데이터(홀) 크기가 균일하지 않는 문제 발생

3.페이지드 세그멘테이션

• 공유나 보안은 세그먼트로 나누고
• 물리적 메모리는 페이지로 나누는 방식

페이지 교체 알고리즘

한정적인 물리적인 메모리 공간에서 페이지 부재(page fault)가 발생하는 상황에 새로운 페이지를 적재하기 위해 기존 페이지 중 어떤 페이지를 제거할지 결정하는 역할을 한다.