Winwoo's Story

CPU Scheduling

• Preemptible Resource
  - 한 Process가 점유한 상태에서 다른 Process에게 양보할 수 있는 자원
      (ex)CPU, Memory
  
  

• Non-Preemptible Resource
  - 한 Process가 점유하면 사용을 마칠때 까지 다른 Process에게 양보할 수 없는 자원
      (ex)Printer
  
  

• CPU Brust
  - 프로그램의 수행중에 연속적으로 CPU를 사용하는 단절구간
  

  
  

• I/O Brust
  - 프로그램의 수행중에 I/O의 완료를 기다리며 블록 되는 구간
  
  

• Scheduling Policies
  - 다음에 어떤 Process에게 CPU자원을 할당 할지
  - 얼마만큼에 시간동안 자원 할당 할지
  
  
• Scheduling Policies 설계 목표
  - Resource의 실질적인 작업시간 계산
  - 오버헤드의 최소화
  - Scheduling 최소화 ( Context Switching 최소화)
  - CPU Time을 여러 Process에게 골고루 할당
  
  
• Aging
  - Task가 CPU를 기다리는 시간에 비례하여 우선순위를 점차적으로 높이는 기법
  
  
• Process의 특징
  - CPU Bound Process : 대부분의 시간을 CPU연산에 사용
      성능적 요구 : 높은 CPU Utilization과 Throughput을 요구
  - I/O Bound Process : 대부분의 시간을 I/O를 보내고 wait에 사용하고 CPU연산을 짧게 한다.
     성능적 요구 : 짧은 Response Time을 요구한다.
  
  
• Scheduling의 종류
  1. First in First out ( FIFO )
      - 먼저 들어온 job을 먼저 처리한다.
      - CPU Brust기준으로 실행한다
      장점 : 단순하고 직관적
      단점 : 하나의 job이 무한Loop를 통해 CPU를 계속해서 점유하고 있을 수 있다. -> 이 경우 OS가 Timer를 통해 관리
      - CPU Brust가 짧은 순서대로 실행시키는게 효율적
          -> 문제점 : 운영체제가 Task의 남은 CPU Brust size를 예측할 수 없음
  
  2. Round Robin ( RR )
      - 기본적으로 FIFO 구조로 설계
      - Timeout 시간을 정해 일정시간 동안만 Job을 실행시키고 시간이 초과 하면 Ready Queue의 맨뒤로 간다.
      - 문제점
          (1) *<Timeout 시간>을 얼마나 잡을 것 인가?
              *Timeout 시간 : Time Slice 또는 TimeQuantum 
                  -> Task에게 CPU가 할당된 후 다음 스케쥴링을 위한 Timer Interrupt가 발생할 때 까지의 시간
          (2) 평균적으로 FIFO보다 좋은 성능을 보이지만 몇몇 상황에선 FIFO보다 안좋은 성능을 보인다.
          (3) CPU Brust의 차이가 미미하다면 FIFO가 효율적이다.
          (4) CPU Brust의 차이가 클수록 Round Robin이 효율적이다.
  
  3. Adeptive Scheduling
      - workload의 특성에 따라 Time Slice의 크기를 동적으로 바꿔주는 스케쥴링 기법
      - Multi Level Feedback Queue가 대표적 (MLFQ)
  
      
  
  4. Priority-based Scheduling
      - Process들에게 선호도를 매기고, 선호도가 높은 Process를 먼저 수행하는 스케쥴링 기법
      - 문제점 : Stavation -> 수행할 준비를 마치고 CPU를 할당 받기를 기다리는 Process가 선호도가 낮아 무기한 연기되는 현상 발생
  
  5. Fair Share Scheduling(Bandwidth Scheduling, Proportional Share Scheduling)
      - 대기중인 Process들에게 정해진 비율에 따라 CPU의 Bandwidth를 분배하는 스케쥴링 기법
  
  
• Evolution of Scheduling Policies
  
  

Computer HardWare

운영체제 ---(가장 먼저 Interection)---> HardWare 

1. Computer System

1.1 System Bus

1.1.1 System Bus란 : 

CPU, Memory, I/O -> 상호간 Data 전송 역할 

1.1.2 System Bus의 종류 : 

Data Bus, Address Bus

1.1.3 System Bus의 행동 : 

Read & Write

- CPU <- Memory : Read

- CPU -> Memory : Write

1.2 Bus Master / Bus Arbiter / Bus Slave

1.2.1 Bus Master : 

-Bus Transaction을 시작하는 요소 

-System에는 여러개의 Bus Master가 존재함

* 대표적인 Bus Master : CPU, I/O Controller, DMA Controller 등

1.2.2 Bus Arbiter : 

여러Bus Master중 특정 Bus Master에게  Bus를 제공해주는 조정자

1.2.3 Bus Slave : 

데이터를 담고 있는 장치(Memory)

(*Transaction : CPU의 작업단위)

1.3 I/O Controller

1.3.1 Interrupt-Driven I/O :

I/O 동작이 완료되면 I/O Controller가 CPU에게 '비동기'적으로 완료되었음을 알려주는 방식

1.3.2 Polling I/O : 

I/O 동작이 완료 될 때까지 CPU가 반복해서 I/O Controller의 Resgister 상태를 확인하는 방식

1.4 DMA Operation (Direct Memory Access)

1.4.1 DMA 이란 :

CPU의 개입 없이 I/O Controller가 메모리에 직접 접근하여 Data를 읽거나 쓸 수 있도록 하는 기능

1.4.2 CPU가 DMA에게 전달하는 요소 :

CPU -----------> DMA Controller

- 전송 될 Block의 시작

- Block의 Size

- Operation Command (Read & Write)

(*DMA는 Block 단위로 전달 됨)

1.4.3 DMA 사용 이유 :

Block Data를 옮길 때 CPU Intervention을 최소화하기 위해 사용

1.4.4 DMA가 Block Data를 전송하는 방식

1. Cycle Stealing : 

CPU 성능에 영향이 없지만 DMA시간이 증가함

->CPU가 BUS를 사용하고 있지 않을 때만 DMA Controller가 Bus를 사용

2. Block Transfer : 

CPU 성능에 영향이 있지만 DMA시간이 감소

->CPU와 DMA Controller가 대등하게 경쟁하여 Bus를 사용

2. Interrupt Mechanism

2.1 Interrupt Mechanism이란

1. 비동기적 Mechanism

2. Hardware Interrupt

- CPU 외부에서 CPU가 관심을 가져야 될 상황에 대에서 CPU에게 전달 (비동기)

3. Software Interrupt

- 현재 수행하는 Program의 문제를 알리기 위해 사용

ex) Exception funtion

-코드분석을 통해 문제를 알 수 있음

(동기적)

2.2 Interrupt의 구현

1. Interrupt Source 

- I/O Controller, DMA Controller 등

2. Interrupt의 처리과정

- 현재 Instruction을 완료하고 마이크로 프로세서의 프로그램 카운터(PC)값을 안전한 곳에 저장

- 현재 수행중인 프로그램 중단

- Interrupt Request Number(IRN)를 통해 Interrupt Source 확인

- Interrupt Vector Table을 검색해서 Interrupt Service Routine(ISR)의 주소를 확인하고 수행

3. PIC(Programmable Interrupt Controller)

- CPU의 Interrupt PIN의 유동적 확장을 위해 사용

- PIC 하나당 16개 Interrupt 처리 가능

3. Hardware Protection Mechanism

3.1 Hardware Protection Mechanism 이란

- Multi Programming을 할 때 Memory에 Active한 여러 Job들이 다른 영역에 접근하지 못하게 하는 기법

*Privileged Instruction

 -> Operation System만 수행할 수 있는 Instruction

3.2 Duel Mode Operation

- Kernel Mode : Privileged Instruction들을 수행 시킬 수 있는 Mode

- User Mode : Privileged Instruction들을 수행 시킬 수 없는 Mode

- Mode변환은 Kernel Mode만 가능

- User Mode에서 Kernel Mode로 변환하기 위해선 Interrupt를 이용

*본 자료는 서울대학교 홍성수 교수님의 '운영체제' 수업을 바탕으로 개인적으로 정리하여 올립니다. 관련 이미지 자료는 홍성수 교수님 수업 PPT자료가 출처임을 알립니다. 문제 시 말씀해주시면 삭제 조치 하겠습니다. 감사합니다.