02. CPU의 스케쥴링 및 메모리 심화

1. 스케쥴링

2. 캐시 메모리와 메모리 할당

 

 

 

스압주의....

---

 

0. 용어 정리

 - 프로세스: 프로그램을 실행해주는 주체

 - 쓰레드: 작업을 처리해주는 주체(프로세스 안에서 이런 저런 쓰레드를 사용)

 

1. 스케쥴링: CPU를 잘 사용하기 위해 프로세스를 잘 배정하는 것

 1-1 스케쥴링 목적

• CPU를 통해 한정된 자원으로 최대한 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야 함.
• 쉽게 표현하면, OS는 실행 대기중인 프로그램(프로세스)들에게 CPU 자원 배정을 적절히 하여 시스템의 성능을 끌어올릴 수 있음
• 공통 배정조건 : 오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓
  • 오버헤드 : 프로세스가 필요한 자원보다 더 많이 사용하지 않도록
  • 사용률 : 프로세스가 최대한 자원을 많이받고 빨리 처리하도록
  • 기아 현상 : 프로세스가 자원할당을 못받아 대기하지 않도록
• 목표에 따른 배정조건 :
  1. 배치 시스템 : 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
  2. 대화형 시스템 : 빠른 응답 시간. 적은 대기 시간이 중요
  3. 실시간 시스템 : 실시간(time) 즉, 최소 응답시간(dead line) 이 중요

 1-2 스케쥴링 단위

  CPU , I/O Burst Cycle

• 프로세스 실행은 “CPU실행 ↔ 입/출력 대기” 의 반복을 의미
• CPU Burst
  • 프로세스의 사용중에 연속적으로 CPU를 사용하는 구간
  • 즉, 실제 CPU 를 사용하는 스케쥴링의 단위
• I/O Burst
  • 프로세스의 실행 중에 I/O작업이 끝날때까지 Block되는 구간

 1-3 스케쥴링 알고리즘 평가기준

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

 1-4 스케쥴링 종류: 선점과 비선점

• 선점 스케쥴링: OS가 나서서 CPU사용권을 '선점'하고, 특정 요건에 따라 각 프로세스의 요청이 있을 때 프로세스에게 분배하는 방식
  • 가장 자원이 필요한 프로세스에게 CPU를 분배하며 상황에 따라 강제로 회수 가능
  • 따라서 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세스를 제어 가능
  선점1.Priority Scheduling(우선순위 스케쥴링): 우선순위에 따라 스케쥴링. (우선순위가 낮은 프로세스는 할당되지 않기도 함)
  선점2.Round Robin(라운드로빈): 정해진 시간 만큼 프로세스를 할당한 뒤, 작업이 끝난 프로세스는 준비완료 큐(순환 큐)의 가장 마지막에 가서 재할당을 기다리는 방법
  선점3.Multilevel-Queue(다단계 큐): 큐를 분리해서 FCFS과 라운드로빈을 섞어서 씀
  
  
• 비선점 스케쥴링: 프로세스 종료 or I/O 등 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이)
  • 순서대로 처리되는 공정성이 있고, 다음에 처리해야할 프로세스와 상관없이 응답시간을 예상 가능
  • 선점방식보다 스케쥴러 호출 빈도가 낮고, 문맥교환에 의한 오버헤드가 적음
  • 일괄처리 시스템에 적합하며 자칫 CPU사용시간이 긴 프로세스가 다른 프로세스들을 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점

• 비선점1. FCFS (First Come , First Serve): 큐에 도착한 순서대로 CPU 할당. FIFO큐. 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
  비선점2. SJF(Shorted Job First): 수행시간이 가장 짧다고 판단되는 작업 먼저 수행
  비선점3. HRN (Highest Response-ratio Next): 우선순위를 계산하여 점유 불평등 보완(SJF 단점 보완)
  • 우선순위 = (대기시간 + 실행시간) / (실행시간)

 1-5. 스케쥴링 동작시점

 - 프로세스의 상태변화와 스케쥴링: 스케쥴링 알고리즘에 따라 프로세스들은 상태변화가 일어나며 준비/수행 상태일때 CPU를 사용하게 됩니다.

아래 그림에서

• 🟠은 프로세스들의 상태
• 🔜 은 스케쥴링에 따라 상태가 변화되는 동작

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

• 여기서 1,2은 프로세스가 스스로 CPU를 반환하기에 비선점 스케쥴링이 발생되고

 

• 3,4은 프로세스에서 CPU를 강제로 할당(회수)해야 하므로 선점 스케쥴링 이 발생됩니다.

 

📌 예를들어 이해해봅시다.

카카오톡 메세지를 보내기 위해 메세지 창을 켜면 카카오톡 프로세스는 신규 > 준비 상태가 됩니다.

1. 준비 (Ready) 상태: 
    1. 카카오톡을 띄워서 메시지를 입력하고 있을 때, 해당 프로세스는 준비 상태가 됩니다. 
    2. CPU 스케줄링 알고리즘은 준비 상태의 프로세스 중에서 CPU를 할당할 프로세스를 선택합니다. 
    3. 이때, 선택하는 선점 알고리즘에 따라 우선순위, 라운드 로빈 등 다양한 방식이 있을 수 있습니다.
2. 대기 (Waiting) 상태: 
    1. 카카오톡이 비활성화 되어있거나, 가만히 상대방의 답장을 기다릴때 대기 상태가 됩니다.
    2. 해당 프로세스는 대기 상태로 변경되면서 수행중 이었다면 CPU를 반납합니다.
    3. CPU 스케줄링 알고리즘은 다른 준비 상태의 프로그램(프로세스)를 선택하여 CPU를 할당할 수 있습니다.
3. 수행 (Running) 상태
    1. 사용자가 메시지를 발송하거나 상대방의 메시지를 수신할때 수행 상태가 됩니다.
    2. CPU 가 준비 상태의 프로세스에 명령을 보내면, 해당 프로세스는 수행 상태로 변경됩니다. 
    3. CPU 스케줄링 알고리즘은 실행 시간을 제어하며, 일정 시간이 지나면 해당 프로세스를 중단하고 실행 대기 상태의 다른 프로세스를 선택할 수 있습니다.
4. 종료 (Terminated) 상태: 
    1. 카카오톡 프로그램을 종료하면 해당 프로세스는 중지 상태로 변경됩니다. 
    2. 이때, CPU 스케줄링 알고리즘은 다른 실행 대기 상태의 프로세스를 선택하여 CPU를 할당할 수 있습니다.

 

2. 캐시와 메모리 할당

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

- 화면에 출력되는 데이터는 결국 메인 메모리에 저장된 데이터

1. 프로그램이 실행되면 디스크를 읽어서 메인 메모리에 복사
2. CPU(MMU)가 메인 메모리에서 데이터를 읽어오며 작업을 처리
3. 이때 캐시가 중간에서 한번더 메인메모리의 데이터를 복사해두는 것

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

 

 2-2 지역성의 원리: 자주 사용되는 데이터의 특성. 캐시를 직접 설정할때는 자주 사용되는 데이터를 기반으로 설정해야 함

• 시간 지역성
  
  • 최근 사용한 데이터에 다시 접근하려는 특성
    ex) for문 안에 선언된 i는 반복문 안에서 계속해서 접근이 이루어지는 변수이다.최근에 사용했기 때문에 계속 접근해서 +1 이 이루어지는 것이다. (i 변수에 대한 시간 지역성)
    

    for i in range(5):
    	print(i)

    
    
    
• 공간 지역성
  • 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성
  ex) 배열 arr이라는 공간에 i가 연속적으로 할당되어 접근하는 방식 (arr 배열 원소에 대한 공간 지역성)

a = []
for i in range(5):
	a.append(i)

 

 

 2-3 캐시히트와 캐시미스

• 캐시히트: 캐시에 원하는 데이터를 찾은 것
  • 위치도 가깝고 CPU 내부버스를 기반으로 작동하여 빠르다
  • 👉 캐시히트를 하게 되면 해당 데이터를 제어장치를 거쳐 가져오게 된다.
• 캐시미스: 해당 데이터가 캐시에 없다면 주메모리로 가서 데이터를 찾아오는 것
  
  • 메모리를 가져올때 시스템 버스를 기반으로 작동하기 때문에 느림

 2-4 캐시 매핑: 캐시가 히트되기 위해 매핑되는 방법

• CPU의 레지스터 와 주 메모리(RAM) 간에 데이터를 주고 받을 때를 기반
• 주 메모리에 비해 굉장히 작은 레즈시터가 캐시 계층으로써 역할 -> 매핑이 중요

 - 직접 매핑

• 메모리가 1~100이 있고 캐시가 1~10이 있다면 1:1~10, 2:1~20... 와 같이 매핑
• 처리가 빠르지만 충돌 발생이 잦음

 - 연관 매핑

• 순서를 일치하지 않고 관련 있는 캐시와 메모리를 매핑
• 충돌이 적지만 모든 블록을 탐색하여 속도가 느

 - 집합 연관 매핑

• 직접 매핑과 연관 매핑을 합쳐 놓은 것
• 순서는 일치하지만 집합을 둬서 저장하며 블록화되어 있어 검색이 효율적

 2-5 메모리 할당: 메모리에 프로그램을 할당할 때는 시작 메모리 위치, 메모리의 할당 크기를 기반으로 할당

 

 - 연속 할당: 메모리에 '연속적으로' 공간을 할당하는 것. 고정 분할 방식과 가변 분할 방식으로 나뉨

 

  고정 분할 방식: 메모리를 미리 나누어 관리하는 방식. 내부 단편화 발생함

  가변 분할 방식:

• 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용하는 방식
• 종류
  1. 최초적합: 위에서부터 바로 보이는 공간에 바로 할당
  2. 최적적합: 가장 크기에 맞는 공간부터 채우고 나머지를 할당
  3. 최악적합: 가장 크기가 큰 공간에 부터 채우고 나머지 할당
• 한계: 내부 단편화 발생없이 외부 단편화 발생

 

내부 단편화

메모리를 나눈 크기보다 프로그램이 작아서 들어가지 못하는 공간이 많이 발생하는 현상
즉, 들어갈 수 있는 공간보다 프로그램이 작아서 공간이 남아버리는 것
ex) 나눈 크기는 10씩. 10이라는 메모리공간에 8크기의 프로그램이 할당 -> 2라는 메모리 공간이 남음.

외부 단편화

메모리를 나눈 크기보다 프로그램이 커서 들어가지 못하는 공간이 많이 발생하는 현상
즉, 들어갈 공간보다 들어갈 것이 더 커서 들어가지 못하고 남아버리는 것

 

 - 불연속 할당: 운영체제에서는 여러개의 작업을 효율적으로 수행해야하기 때문에 불연속 할당방법을 사용

  불연속 할당 방식의 단점

• 메모리 공간 할당과 해제 시의 오버헤드가 발생할 수 있음. (불필요 할당)
• 메모리 공간이 분산되어 있기 때문에, 프로세스가 불연속 공간에 할당될 경우 프로세스의 페이지 교체와 같은 작업이 더 복잡할수 있음. (교체 알고리즘 최적화 필요)

• 운영체제에서 불연속 할당을 사용하는 3가지 방법
  1. 링크드 리스트(Linked List) : 불연속 공간에 프로세스를 할당할 때, 할당된 공간의 주소를 연결리스트에 저장하는 방식. 이 방식은 메모리 할당과 해제가 빠르지만, 공간 낭비가 발생할 수 있음.
  2. 비트맵(Bitmap) : 메모리 공간의 각 블록을 0 또는 1로 표시하여 사용 가능한 블록과 사용 중인 블록을 구분하는 방식. 이 방식은 링크드 리스트보다 효율적인 공간 관리를 제공하지만, 메모리 크기가 큰 경우 비트맵이 매우 커짐.
  3. 페이지 테이블(Page Table) : 가상 메모리 시스템에서 사용되는 방식으로, 물리적인 주소 공간을 페이지라는 작은 블록으로 나누어 사용. 각 프로세스는 자신의 페이지 테이블을 가지며, 페이지 테이블은 물리적인 주소와 가상 주소를 매핑. 이 방식은 링크드 리스트와 비트맵보다 효율적이며, 가상 메모리를 구현하는 데 필요한 기술.
  • 메모리를 동일한 크기의 페이지로 나누고 프로그램마다 페이지 테이블을 두어 이를 통해 메모리에 프로그램을 할당
    1. 페이징, 2) 세그멘테이션, 3)페이지드 세그멘테이션1) 페이징
       • 동일한 크기의 페이지 단위 나누어 메모리의 서로 다른 위치에 프로세스를 할당
       • 빈데이터(홀)의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡
       2) 세그멘테이션
       • 의미 단위인 세그먼트로 나누는 방식
       • 코드와 데이터 등을 기반으로 나눌 수 있으며, 함수 단위로 나눌 수도 있음을 의미.
       • 공유와 보안 측면에서 좋습니다.
       • 빈데이터(홀) 크기가 균일하지 않는 문제 발생
       3) 페이지드 세그멘테이션
       • 공유나 보안은 세그먼트로 나누고
       • 물리적 메모리는 페이지로 나누는 방식
  • 페이지 교체 알고리즘