• Process Scheduling Simulator 사용법

Screen-Recording-2023年05月12日-at-11 49 29-PM

• Process 스케줄링은 multi-tasking system에서 여러 프로세스들에 프로세서 할당(dispatch) 순서를 결정하는 작업입니다.
• 목적은 성능 향상에 있습니다.
• 성능 지표는 굉장히 많은 종류가 있으며, 대표적인 지표는 다음과 같습니다.
  • mean response time (평균 응답 시간)
  • throughput (단위 시간당 처리량)
  • resource utilization (단위 시간당 자원 활용도)

• 도착한 순서대로 프로세스를 dispatch
• Non-preemptive 알고리즘

• Batch system에 적합
  • 빠른 응답시간보다는 작업 처리에 대한 성능이 더 중요하기 때문
• time-sharing(interactive) system에 부적합
• 장점
  • resource utilization이 높음
    • 불필요한 스케줄링(context switching)이 이루어지지 않아 프로세서가 지속적으로 작업을 수행할 수 있기 때문
• 단점
  • convoy effect가 발생
    • burst time이 긴 프로세스에 의해 다른 프로세스들의 대기시간이 길어지는 현상
  • 평균 respone time이 김
    • convoy effect가 원인

• 도착한 순서대로 프로세스를 dispatch 하되, 프로세서 사용 제한 시간(time quantum) 이 존재
• Preemptive 알고리즘

• running 상태의 프로세스중 time quantum이 만료된 프로세스가 있고, ready 상태의 프로세스가 있다면 선점
• 장점
  • time-sharing(interavtive) system에 적합
  • 특정 프로세스들의 자원 독점을 방지
• 단점
  • 잦은 context switching으로 인해 overhead가 큼
• time quantum이 시스템 성능을 결정 짓는 핵심 요소
  • very large(infinite) time quantum -> FCFS
  • very small time quantum -> processor sharing
    • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느끼게 됨
    • (프로세서의 작업 수행 체감 속도) = (프로세서의 실제 작업 속도 * 프로세서의 개수)

• burst time이 가장 작은 프로세스를 dispatch
• Non-preemptive 알고리즘

• 장점
  • 프로세스들의 평균 waiting time과 response time이 짧음
  • 시스템 내 프로세스들의 수를 최소화
    • 스케줄링 overhead가 감소하고, 메모리 절약을 할 수 있어 시스템의 효율을 향상시킴
• 단점
  • burst time이 상대적으로 긴 프로세스는 starvation 현상이 발생할 수 있음
  • burst time을 예측하기 어려움
    • 예측하기 위한 기법이 필요

• SPN을 preemptive 방식으로 변형한 알고리즘
• 잔여 burst time이 running 프로세스보다 더 적은 ready 상태의 프로세스가 있다면 선점

• 장점
  • SPN의 장점을 극대화
• 단점
  • 잔여 burst time을 계속해서 추적해야 하는 overhead
  • 잦은 context switching으로 인한 overhead
• 위 단점으로 인해 구현 및 사용이 비현실적

• SPN + Aging concept을 적용한 알고리즘
• Non-preemptive 알고리즘
• Aging concept
  • 프로세스의 waiting time을 고려하여 우선순위 설정
  • response ratio가 가장 높은 프로세스가 가장 우선순위가 높음
    • response ratio: (WT + BT) / BT

• 장점
  • SPN의 장점을 취하면서도 starvation을 방지함
• 단점
  • ready 상태 프로세스들의 우선순위를 지속적으로 업데이트 필요
  • burst time 예측 기법 필요

image

image

image

image

image

image

• 1 <= processes.size() <= 99
• 프로세스별 property
  • name
  • arrivalTime
  • workload

• 1 <= processors.size() <= 15
• 프로세서별 property
  • name
  • core

• 다음 중 택 1
  • FCFS
  • RR
  • SPN
  • SRTN
  • HRRN
  • MN

• Round-Robin 알고리즘에서의 프로세스 실행 제한 시간

{
 "processes": [
 {
 "name": "p1",
 "arrivalTime": 0,
 "workload": 9
 },
 {
 "name": "p2",
 "arrivalTime": 1,
 "workload": 8
 },
 {
 "name": "p3",
 "arrivalTime": 3,
 "workload": 11
 },
 {
 "name": "p4",
 "arrivalTime": 4,
 "workload": 7
 },
 {
 "name": "p5",
 "arrivalTime": 5,
 "workload": 12
 }
 ],
 "processors": [
 {
 "name": "Core1",
 "core": "E"
 }
 ],
 "algorithm": "RR",
 "timeQuantum": 2
}

• 시간 구간(n ~ n + 1초)별 상태

• start time (n)

• end time (n + 1)

• [프로세스, 프로세서] pair 리스트
  • 프로세서가 해당 프르세스에 할당되었다는 의미
• pair별 property
  • processorName
  • processName

• 프로세서별 누적 전력 소비량
• 프로세서 누적 전력 소비량별 property
  • processorName
  • totalPowerConsumption

• 모든 프로세서의 누적 전력 소비량 합

• 현재 ready queue 상태 (프로세스 리스트)
• 우선순위순 (앞에서부터)

• 해당 시간에 종료된 프로세스 리스트
• 프로세스별 property
  • name
  • arrivalTime
  • burstTime
  • waitingTime
  • turnaroundTime
  • normalizedTurnaroundTime

{
 "statuses": [
 {
 "from": 0,
 "to": 1,
 "pairs": [
 {
 "processorName": "Core1",
 "processName": "p1"
 }
 ],
 "processorPowerConsumptions": [
 {
 "processorName": "Core1",
 "totalPowerConsumption": 1.1
 }
 ],
 "totalPowerConsumption": 1.1,
 "readyQueue": [],
 "terminatedProcesses": []
 },
 
 ...
 skip
 ...
 
 {
 "from": 6,
 "to": 7,
 "pairs": [
 {
 "processorName": "Core1",
 "processName": "p3"
 }
 ],
 "processorPowerConsumptions": [
 {
 "processorName": "Core1",
 "totalPowerConsumption": 7.4
 }
 ],
 "totalPowerConsumption": 7.4,
 "readyQueue": [
 "p2",
 "p4",
 "p5"
 ],
 "terminatedProcesses": []
 },
 
 ...
 skip
 ...
 
 {
 "from": 19,
 "to": 20,
 "pairs": [
 {
 "processorName": "Core1",
 "processName": "p4"
 }
 ],
 "processorPowerConsumptions": [
 {
 "processorName": "Core1",
 "totalPowerConsumption": 21.2
 }
 ],
 "totalPowerConsumption": 21.2
 "readyQueue": [],
 "terminatedProcesses": [
 {
 "name": "p2",
 "arrivalTime": 1,
 "burstTime": 7,
 "waitingTime": 11,
 "turnaroundTime": 18,
 "normalizedTurnaroundTime": 2.57
 }
 ]
 },
 {
 "from": 20,
 "to": 21,
 "pairs": [
 {
 "processorName": "Core1",
 "processName": null
 }
 ],
 "processorPowerConsumptions": [
 {
 "processorName": "Core1",
 "totalPowerConsumption": 21.2
 }
 ],
 "totalPowerConsumption": 21.2,
 "readyQueue": [],
 "terminatedProcesses": [
 {
 "name": "p4",
 "arrivalTime": 5,
 "burstTime": 5,
 "waitingTime": 10,
 "turnaroundTime": 15,
 "normalizedTurnaroundTime": 3.0
 }
 ]
 }
 ]
}

image

domain diagram

• Language
  • Java 11
• Framework
  • Spring Boot 2.7.12
• Build tool
  • Maven
• Infra
  • AWS EC2
  • Nginx