Computer Science 1, 2강

CPU

구성

• 산술논리 연산장치(ALU): 비교, 판단, 연산 담당
• 제어부(CU)와 내부 버스: 명령어의 해석과 실행을 위해 CPU를 내부적으로 제어
• 메모리 유닛
  • 레지스터: 처리할 명령어 저장
  • 캐시 메모리(L1): 처리속도를 높여주는 역할

CPU가 명령어를 읽고 수행하는 동작

1. 명령어 인출
   • CU가 수행할 명령어 정보를 가지고 온다.
2. 명령어 해독
   • 보통 opcode라는 명령어 코드를 인출한다.
   • opcode의 성격에 맞게 레지스터들을 준비시킨다.
3. 실행
   • 해독된 명령어 수행한다.
   • Ex) 산술/논리 관련된 연산 -> ALU가 주체
4. 반영

CPU의 성능

• 클럭
  • CPU 내부에서 일정한 주파수를 가지는 신호
  • 1Hz(헤르츠)면 1초에 한 번의 주기(명령어)를 처리할 수 있다.
• 코어
  • 중앙처리 장치 역할을 하는 블록
  • 멀티 코어들은 싱글 코어에 비해 마치 여러 개의 CPU가 작동하듯 많은 연산을 빠르게 병렬 처리할 수 있다.

메모리

• 레지스터 = CPU
• 캐시 메모리(SRAM) (L2, L3)
• 메인 메모리(DRAM) = 주 기억장치 (주로)
• 하드 디스크(HDD) = 보조 기억장치 (비휘발성)

CPU와 메모리의 동작

1. 주기억장치가 입력장치에서 입력받은 데이터 또는 보조기억장치에 저장된 프로그램을 읽어온다.
2. CPU는 프로그램을 실행하기 위해 주기억장치에 저장된 프로그램 명령어와 데이터를 읽어와 처리하고 결과를 다시 주기억 장치에 저장한다.
3. 주기억장치는 처리 결과를 보조기억장치에 저장하거나 출력장치로 보내서 출력시킨다.
4. CPU 내의 제어장치(CU)가 1~3번 과정에서 명령어가 순서대로 실행되도록 각 장치들을 제어한다.

스케쥴링

목표

• CPU를 한정된 자원으로 최대한 성능을 이끌어내기 위해서 프로세스를 적절하고 효율적으로 배정해야 한다.

배정조건

1. 오버헤드 최소화
   • 프로세스가 필요한 자원보다 더 많이 사용하지 않도록 한다.
2. 사용률 최대화
   • 프로세스가 최대한 자원을 많이 받고 빨리 처리하도록 한다.
3. 기아 현상 최소화
   • 프로세스가 자원할당을 못받아서 배고픈 상태로 대기하지 않도록 한다.

스케쥴링 종류

선점 스케쥴링

• Priority Scheduling(우선순위 스케쥴링)

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

• Round Robin(라운드 로빈)

  • FCFS(First Come, First Serve)에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum만큼 CPU 할당
  • 작업이 끝난 프로세스는 준비완료 큐(순환큐)의 가장 마지막에 가서 재할당을 기다리는 방법 (회전식)
  • 시간 할당량이 중요
    • 너무 작으면 빈번한 문맥 전환(Context Switching) 발생
    • 너무 길면 FCFS(First Come, First Serve)와 다를 바 없음
  • 예시
    

• Multilevel-Queue(다단계 큐)

  • 준비완료 큐를 여러개의 큐로 분류하여 각 큐가 각각 다른 스케쥴링 알고리즘을 가지는 방법
  • 큐와 큐 사이에도 스케쥴링이 필요

비선점 스케쥴링

• FCFS(First COme, First Serve)

  • 큐에 도착한 순서대로 CPU 할당
  • 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
  • Convoy Effect(호위 효과): 긴 처리 시간의 프로세스가 선점되어버리면 나머지 프로세스들은 끝날때 까지 대기해야 하는 현상
  • 예시
    

• SJF(Shorted Job First)

  • 수행시간이 가장 짧다고 판단되는 작업 먼저 수행
  • FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
  • 만약 CPU버스트 시간이 동일하다면 FCFS방식을 따른다
  • 다만 선점형인 경우 위와 같이 진행, 비선점형의 경우 최소잔여시간우선 법칙을 따른다
  • 최소잔여시간우선 법칙: 현재 CPU에 할당된 프로세스의 남은 잔여시간과, 새로 들어온 프로세스의 CPU버스트 타임을 비교하여 더 적은 프로세스에게 할당
  • 최적이긴 하지만 다음 프로세스의 버스트시간을 계산하기 어렵다는 단점 존재해서 '비슷할 것이다'라고 추측을 통해 진행하기도 한다
  • 예시
    

• HRN(Highest Response-ratio Next)

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

스케쥴링 동작시점

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

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

비선점 스케쥴링

• 프로세스가 스스로 CPU를 반환

1. 수행 -> 대기 (Running -> Waiting): I/O 요청이 발생하거나, 자식 프로세스가 종료 대기를 할 때
2. 수행 -> 종료 (Running -> Terminate): 프로세스를 종료시켰을 때

선점 스켸줄링

• 프로세스에서 CPU를 강제로 할당(회수)

3. 수행 -> 준비 (Running -> Ready): 인터럽트가 발생했을 때
4. 대기 -> 준비 (Waiting -> Ready): I/O가 완료되었을 때

메모리 심화

캐시

• 계층과 계층 사이에서 속도 차이를 해결하기 위한 임시 저장소
  
• 근데 왜 SRAM(L1~3캐시)만 캐시라고 부를까?
  • 우리가 보는 화면에 출력되는 데이터는 메인 메모리에 저장된 데이터이다
  • CPU 연산을 위한 저장소인 레지스터와 메인 메모리 사이에서 임시 저장소 역할을 하는 것이 SRAM이기 때문

지역성의 원리

• 자주 사용되는 데이터의 특성

시간 지역성

• 최근 사용된 데이터에 다시 접근하려는 특성

• 예시

  for(let i=0; i<5; i++){
  		console.log(i) // 최근 사용된 i에 계속해서 접근
   }

공간 지역성

• 최근 접근한 데이터를 이루고 있는 공간이나 그 가까운 공간에 접근하는 특성

• 예시

  let arr = [];
  
   for(let i=0; i<5; i++){
  		arr.push(i) // 최근 접근한 arr에 계속해서 접근
   } 

캐시히트와 캐시미스

캐시히트

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

캐시히트

• 해당 데이터가 캐시에 없다면 주메모리로 가서 데이터를 찾아오는 것
• 메모리를 가져올때 시스템 버스를 기반으로 작동하기 때문에 느리다

메모리 할당

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

연속 할당

• 고정 분할 방식
  • 메모리를 미리 나누어 관리하는 방식
  • 한계
    • 내부 단편화 발생 ⭕
    • 들어갈 수 있는 공간보다 프로그램이 작아서 공간이 남는 현상
• 가변 분할 방식
  • 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용하는 방식
  • 종류
    1. 최초적합: 위에서부터 바로 보이는 공간에 바로 할당
    2. 최적적합: 가장 크기에 맞는 공간부터 채우고 나머지를 할당
    3. 최악적합: 가장 크기가 큰 공간에 부터 채우고 나머지 할당
  • 한계
    • 외부 단편화 발생 ⭕
    • 들어갈 공간보다 프로그램이 더 커서 들어가지 못하고 남아버리는 것

불연속 할당

• 장점
  • 여러개의 작업을 효율적으로 수행할 수 있다
• 단점
  • 메모리 공간 할당과 해제 시의 오버헤드가 발생할 수 있다 (불필요 할당)
  • 프로세스의 페이지 교체와 같은 작업이 더 복잡해질 수 있다 (교체 알고리즘 최적화 필요)
    
    
• 운영체제에서 불연속 할당을 사용하는 3가지 방법
  1. 링크드 리스트 (Linked List)
  2. 비트맵 (Bitmap)
  3. 페이지 테이블 (Page Table)
     a. 페이징
     b. 세크멘테이션
     c. 페이지드 세그멘테이션
     
     
• 페이지 교체 알고리즘
  1. 오프라인 알고리즘
  2. 시간기반 알고리즘
     • FIFO (First In First Out)
     • LRU (Least Recently Used)
     • NUR (NOt Used Recently)
  3. 빈도기반 알고리즘
     • LFU(Least Frequently Used)