Process-Scheduling-Simulator-API

• 한국기술교육대학교 컴퓨터공학부 23-1학기 운영체제(김덕수 교수님) 팀프로젝트 API

시연 영상

Details

Youtube

• Process Scheduling Simulator 사용법

GIF

'프로세스 스케줄링' 이란?

Details

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

기본 알고리즘

FCFS, RR, SPN, SRTN, HRRN

Details

FCFS (First-Come-First-Service)

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

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

RR (Round-Robin)

• 도착한 순서대로 프로세스를 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
    • 사용자는 모든 프로세스가 각각의 프로세서 위에서 실행되는 것처럼 느끼게 됨
    • (프로세서의 작업 수행 체감 속도) = (프로세서의 실제 작업 속도 * 프로세서의 개수)

SPN (Shortest-Process-Next)

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

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

SRTN (Shortest-Remaining-Time-Next)

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

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

HRRN (High-Response-Ratio-Next)

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

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

알고리즘 구현 Flow chart

FCFS

FCFS (First-Come-First-Service)

RR

RR (Round-Robin)

SPN

SPN (Shortest-Process-Next)

SRTN

SRTN (Shortest-Remaining-Time-Next)

HRRN

HRRN (High-Response-Ratio-Next)

말년병장

말년병장

API 명세

Request

POST /schedule

HTTP Body

Processes

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

Processors

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

Algorithm

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

Time quantum

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

Request JSON Example

{
    "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
}

Response

HTTP Body

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

from

• start time (n)

to

• end time (n + 1)

Pairs

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

ProcessorPowerConsumptions

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

TotalPowerConsumption

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

Ready queue

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

Terminated Processes

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

Response JSON Example

{
    "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
                }
            ]
        }
    ]
}

클래스 다이어그램

Details

사용 기술

Details

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