Disk Scheduling

1. First-in, First-out (FIFO)

큐에 먼저 들어온 request 부터 처리한다.

2. Shortest Service Time First

실행시간이 짧은 request 부터 처리한다.

3. SCAN

굉장히 공정한 방법이다. Starvation 발생 가능성이 거의 없다. (완벽하게 없진 않다. 특정 트랙에 계속해서 request 가 쏟아지면 진행을 못할 수도 있기 때문이다.) → 완벽하게 fair 하냐? X, 어떤 상황에서 완벽하게 fair 하지 않나?

디스크 안에 여러 트랙이 있는데 중간 트랙에 있는 request가 있고 안쪽끝과 바깥쪽 끝에 있는 request가 있다.

request가 딱 도착을 했을 때 헤더가 그 트랙에 대한 서비스를 끝마치고 트랙을 막 떠난 상황이다. 끝까지 갔다가 다시 돌아올때까지 기다려야 한다.

얼만큼 기다리는가?
↳ 자기를 막 스치고 지나갔다고 했을 때 끝까지 갔다가 다시 돌아오는데 걸리는 시간 (내가 기다려야 하는 maximum 시간) = 바깥쪽 지점 > 중간 지점
⇒ 완벽하게 fair 하지 않다.

4. N-step-SCAN

Starvation 가능성이 완전히 없다.
↳ 추가로 도착하는 request 들을 나중에 처리하기 때문이다. 그러나 N 값이 1인 경우 FCFS 가 된다. 따라서 결국 N 값을 어떻게 정하느냐에 따라 성능이 SCAN 에 가까울 수도 있지만, FCFS 에 가까운 성능을 가지게 될 수도 있다.

5. FSCAN

• 큐 두개를 사용한다.
• 한 방향으로 끝까지 갔다가 다시 돌아오며 새로운 요청들을 처리한다.

Starvation 가능성이 완전히 없다.

C-SCAN

모든 request 들을 완벽하게 fair 하게 처리하겠다!

한쪽 방향으로만 서비스를 한다. 바깥쪽 끝까지 갔다가 방향을 바꿔 돌아올때는 서비스를 하지 않는다.

나를 스치고 지나갔을 때 기다려야 하는 시간 = 중간 지점 < 양쪽 끝 지점
⇒ not fair ⇒ fair 를 위해 C-SCAN은 한쪽 방향으로만 서비스한다.
↳ 반대 방향으로 갈때는 서비스하지 않는다.

어느 트랙에 있든 기다려야 하는 시간도 같아지게 된다.
⇒ 예측가능성 이 중요한 시스템에서 무척 좋다. 어떤 경우에도 어떤 request 든지 얘가 언제쯤 처리될지를 정확하게 예측해야 하는 real time system 같은 경우에 사용할 수 있는 기법이다.
⇒ CSCAN은 완벽하게 fair 한 기법이다.

단, SCAN 보다 성능은 낮다.

그 밖의 Disk Scheduling Policies

위의 Disk Scheduling 기법들은 head 의 움직임을 최소화하려고 했다.

Priority scheduling

• Short batch jobs and interactive jobs are given higher priority than jobs that require longer computation
• Not intended to optimize disk utilization, but to meet other objectives within the OS

Disk 의 Performance 를 생각하지 않고 request 를 보낸 프로세스의 종류 에 따라서
interactive 한 job이나 batch job 중에 실행시간이 짧은, 빨리 끝내야하는 프로세스들의 request를 먼저 처리하고,
일반 batch job 들, 실행시간이 느려도 되는 애는 나중에 처리한다.
⇒ 프로세스에 따라 다르게 우선순위를 맞추어 처리 준다.

Last-In-First-Out 🌟

• A policy of always taking the most recent request has
  some merit
• Taking advantage of the locality improves throughput and reduces queue lengths
• Possibility of starvation

Queue 의 요청들이 있으면, 큐의 제일 끝에서부터 처리하겠다는 것이다.
앞이 아닌 뒤부터 처리한다. ⇒ 지금 실행하고 있는 프로세스의 request인, 가장 최신 요청부터 처리한다는 의미를 가지고 있다.

Locality

뒤에서부터 처리를 하게 되면 그 근처에 실행하고 있는 프로세스의 요청들이 모여 있을 것이므로 → 하드디스크 안에 같은 block, sector, track 위치에 원하는 데이터나 코드가 모여 있을 것이다.

문제점

한 번 밀리면 거의 starvation 이다.

RAID

Redundant Array of Independent Disks

• harddisk 1개 → data 들이 있을 때 1개에 저장한다. 내가 하나의 하드디스크를 쓸때는 큐의 길이가 100개이다.(큐에 요청을 100개하는 것)
• harddisk 10개 → data 를 나눠서 저장한다. 한 디스크당 큐의 길이는 10개가 되어 하드디스크가 1개일때보다 길이가 1/10으로 줄어들고 읽는 속도는 증가한다.

여러개의 디스크를 구입해서 하나의 디스크처럼 사용하는 것으로 실제로는 10개의 디스크를 구입해서 10개의 디스크의 데이터를 분산을 시켰고 user 입장에서는 어느 디스크에 어느 데이터가 있는지 알아야할 필요가 없다.

여러 디스크들을 하나의 디스크처럼 logical 하게 사용하는 시스템을 RAID System 이라고 한다.

• Set of physical disk drives viewed by the operating
  system as a single logical drive
• Data are distributed across the physical drives of an array
• Redundant disk capacity is used to store parity information which provides recoverability from disk failure

RAID 0 (non-redundant)

Disk 4개 ⇒ 돈 4배

내 파일들을 strip 단위로 나누어서 4개의 디스크에 분산 저장하는 것

⇒ 속도가 4배 빨라진다.

하지만 디스크 중 한개가 고장날 수도 있다.
위의 그림을 보면 보라색 네모가 하나의 파일이라고 할 때 strip2 가 사라지면 파일의 일부가 사라져서 아무것도 할 수 없게 된다.

RAID 1 (mirrored)

문제점

하드디스크가 1개일때보다 돈이 8배가 더 들어간다. 하지만 속도는 4배만 빨라진다.

파란색 하드디스크

• 데이터를 strip 단위로 나누어서 저장
• 데이터를 읽을 때 여기서 읽으면 된다.
• 데이터를 쓸 때 여기도 써야하고 회색에도 써야한다.

회색 하드디스크

• 미러링한 하드디스크(copy 해놓은 것)
• 데이터를 써야 한다.

RAID 2 (redundancy through Hamming code)

복사본을 만들 때 code 를 사용하자!

스트립 단위가 아니라 bit 단위로 나누자!

• 제일 먼저 1, 2, 3, ..., 7 까지 쓰기
• 이진수 위치에 code bit 가 놓인다.
• 나머지 수에는 data bit 가 놓인다.
• code bit 계산 방법:
  • c0 → data bit 가 이진 수 제일 오른쪽 애가 1인 애들 exclusive or 하기 (같으면 0, 다르면 1)
  • c1 → data bit 가 이진 수 제일 오른쪽에서 두번째인 애가 1인 애들 exclusive or 하기
• d1 이 안되어도 나머지를 가지고 계산이 가능하다.
• disk 가 두개 고장나도 해결이 가능하다. ⇒ 복구가능성이 높다.

data disk 가 14개 존재한다. → code disk 가 몇개가 필요한가?
code disk 는 2진수에 위치한다.

code 는 2^n 에만 필요하다. ⇒ 간격이 점점 커진다.

data disk 의 개수가 많아질수록 code disk 의 개수는 적게 필요하게 된다.

계산해보기
data disk 의 위치부터 결정해야 한다. 이 예제에서는 코드디스크가 5개가 필요하다. 이진수로 3~20까지 만들면, 5비트의 이진수가 만들어진다.

• C0: 제일 마지막 비트가 1인 애들을 모아서 exclusive or
• C1
• C2
• C3
• C4

RAID 3 (bit-interleaved parity)

parity 는 bit 를 사용한다.

Parity bit 는 data disk 개수에 상관 없이 딱 하나의 하드디스크만 더 있으면 된다.
⇒ 최소한의 비용으로 문제를 해결할 수 있다.

b0b1b2b3  P(b)
1 0 0 1 → Parity bit = 1 (홀수)
1 1 1 0 → Parity bit = 0

RAID 4 (block-level parity)

필요한 모든 file 들 을 block 단위로 나누고 parity block 을 만들어서 block 단위로 parity 를 계산한다.

data disk 에는 내가 수정한게 여기저기 분산되어 있어서 read 가 아니라 write 를 request 하는 경우 한번의 업데이트가 아니라 4개의 request 가 몰리게 된다. 여러번 업데이트를 해주어야 한다.

write request 가 parity disk 에 data disk 의 네배정도가 몰릴 수 있다.

RAID 5 (block-level distributed parity)

Parity 를 다섯개의 disk 에 골고루 분산해서 나누었다. Disk Queue 의 길이가 길어지지 않고 전체적으로 속도 향상이 이루어지게 된다.

Disk Cache

file 에서 정수 하나 읽어오라고 했을 때 정수 하나를 읽으려고 하더라도 하나의 block 을 가져온다.
↳ 하드디스크와 메모리 사이에서 데이터가 움직이는 단위는 block 이다.

아까 가져온 block 에 내가 다음에 필요한게 block 에 이미 있으면 하드디스크로 가서 다시 block 을 가져오는 시간을 save 할 수 있다.

Disk Cache: Disk 에서 가져온 block 들을 메인 메모리 buffer 에 저장
→ block 이 필요할 때 이 buffer 에 있는지 확인
→ 확인해서 없으면 disk 로 가서 가져오기

• Buffer in main memory for disk sectors
• Contains a copy of some of the sectors on the disk
• When an I/O request is made for a particular sector,
  • a check is made to determine if the sector is in the disk
    cache.
• A number of ways exist to populate the cache

main memory 크기에 한계가 있으므로 제한된 크기의 disk cache 를 이용할 수 있다. 이 disk cache 에 들어 있는 block 하나를 버릴 때 굉장히 주의해서 버려야 한다.
(다시는 사용하지 않을 것 같은 block 은 버리고 사용할 것 같은 건 버리면 안된다.)
↳ page replacement 와 비슷하다.

page replacement 중 성능이 LRU 가 가장 좋았지만 DISK Cache 에서는 LRU 방법이 제일 좋진 않다.

Least Recently Used (LRU)

최근에 사용하지 않고 오래전에 가져온 것을 버린다. ⇒ stack 을 사용한다.

• top: 가장 최근에 사용한 block
• bottom: 가장 오랫동안 사용되지 않은 block

어떠한 block 이 다시 사용이 되면 stack 의 top 으로 올린다.

공간이 모자라서 block 을 버릴 때는 가장 밑에 애를 버린다. (Disk Cache 에서는 좋은 성능 X)

• A stack of blocks are cached
• Recently used block is on the top
• The block on the bottom of the stack is removed when a new block is brought in

Least Frequently Used

최근 사용 X

• O
• X

몇번 사용 O

• O
• X

각각의 block 마다 counter 를 만들어서 몇번 access 가 되었는지 몇번 사용되었는지 체크한다. 사용될 때마다 count 값을 하나씩 늘려준다.

block 을 버릴때는 count 값이 가장 적은 block 을 버린다.

LFU 가 LRU 보다 성능이 좋다.

Disk Cache의 경우에는 지금 당장 사용되어야 하는 block 이 중요한게 아니라 굉장히 오랜시간동안 계속해서 지속적으로 사용되는 block 을 disk cache 에 남겨 놓는 게 더 중요하다.

LFU의 문제점

방금 하드디스크에서 메모리로 올라온 애는 counte 값이 1이라 앞으로 사용될 수 있는데도 버려질 수 있다.

Frequency-based Replacement

stack 사용

두가지 section 으로 나누기

1. New Section

최근에 메인 메모리로 올라온 block 들, 최근에 사용된 block 들이 모인 곳

2. Old Section

오랫동안 덜 사용된 block emf

• 가장 왼쪽이 top → 가장 최근에 들어오거나 쓰인 애들
• 가장 오른쪽이 bottom → 가장 오랫동안 사용하지 않은 애들

count 관리

각각의 block 마다 count 를 관리한다.

하드디스크에서 방금 올라온 새로운 block 은 count 값을 1로 둔다. 다시 사용되면 다시 top 으로 올려준다. new section 에서의 stack 위치 이동은 count 를 증가시키지 않는다.
↳ 최근에 집중적으로 사용되는 block 이라고 보기 때문이다.

new section 에 있는데 count 값이 굉장히 높다면 굉장히 오랜시간에 거쳐서 사용되고 있는 block 이고 지금도 집중적으로 사용되는 block 이다.

old section 에 있는데 count 값이 높으면 오랜시간을 거쳐서 지속적으로 높게 사용되는 block 이라는 의미이므로 절대 버리면 안되고,
old section 중 count 값이 1이라고 한다면 집중적으로 사용된 적이 있을지는 모르지만 오랫동안 사용된 애는 아니므로 old section 에서 count 값이 가장 작은 경우를 버린다. count 값이 같은 경우에는 bottom 쪽에 있는 애를 버린다.
⇒ LRU와 LFU 모두를 만족시킨다.

• LRU 적용: new section 에 있는 block 은 버리지 않는다.
• LFU 적용: old section 에 있는 block 중 count 값이 제일 작은 걸 버린다.

문제점

NEW 에서 계속 사용되어서 Count 값이 계속 1인데 한칸 밀려서 old section 에 와서 바로 버려질 수도 있다.

세가지 section 으로 나누기

1. New
   • 처음 하드디스크에서 메모리로 올라오면 여기로 들어온다.
   • count = 1
   • 다시 사용시 count 값은 변경되지 않는다.
2. Middle
   • Middle 에서 다시 호출되면 count 값이 1증가한다.
   • Middle 에서는 block 을 버리지 않는다.
3. Old Section
   • 버려질 때는 old 중 count 값이 가장 작은 것을 버린다.
   • 다시 호출되면 count 값이 1증가한다.

Operating System Design Objectives

I/O

I/O cannot keep up with processor and main memory speed ==> Efficiency is an important issue

I/O 에서는 속도가 매우 중요하다.
하드디스크 성능이 나쁘게 되면 아무리 CPU 나 메모리가 좋아도 성능이 올라갈 수 없다.

Uniform

Desirable to handle all I/O devices in a uniform manner ==> Generality is an important issue

I/O device 들을 access 하는데 uniform 한 방법으로 access 하고 싶다.

monitor이든 file 이든 입출력시 동일한 명령을 사용해서 같은 방식으로 입출력을 하고 싶으므로 같은 방법을 사용한다.

실제 시스템에서는 디바이스에 상관 없이 다 같은 명령을 사용해서 입출력을 하고 있다.

입출력 명령

System call X, I/O library 함수 O
→ 실제 OS 에게 I/O 요청할 때의 명령은 고정 Uniform 을 사용한다.

• 읽기 → Read()
• 쓰기 → Write()

Disk Performance Parameters

1. Access Time

Access Time is the sum of:

Seek Time

The time it takes to position the head at the desired track

헤드가 내가 원하는 트랙 까지 오는데 걸리는 시간

Rotational delay or rotational latency

The time its takes for the beginning of the sector to reach the head

헤드가 내가 원하는 섹터 까지 도달하는 데 걸리는 시간

2. Transfer Time

Transfer Time is the time taken to transfer the data.

Transfer Time 을 줄일 수 없기 때문에 Access time 둘 중 하나를 줄여야 하는데, 판을 돌리는 데 걸리는 시간은 얼마되지 않으므로 원하는 트랙에 도달하는 시간인 Seek time 을 줄여야 한다.

원을 따라 데이터 들이 쫙 써져 있다.

헤더가 존재하는데 헤더는 트랙의 안쪽과 바깥쪽을 왔다갔다 하며 데이터를 읽을 수 있다.

Disk Scheduling Policies

To compare various schemes, consider a disk head is initially located at track 100.

assume a disk with 200 tracks and that the disk request queue has random requests in it.

200개의 트랙이 있는 하드디스크가 있고 disk request queue 에서 무작위로 트랙 요청을 한다.

The requested tracks, in the order received by the disk scheduler, are

request 도착 → 55, 58, 39, 18, 90, 160, 150, 38, 184.

track 번호에 request 도착

First-in, first-out (FIFO)

Queue 에 들어온 순서대로 처리한다. ⇒ 성능이 최악이다.

• Process request sequentially
• Fair to all processes (가장 큰 장점)
• Approaches random scheduling in performance if there are many processes

Shortest Service Time First

현재 head 위치에서 가장 가까운 거 부터 실행

• Select the disk I/O request that requires the least movement of the disk arm from its current position
• Always choose the minimum seek time

SSTF 는 성능적으로 가장 Optimal 하면 Starvation 발생가능성이 매우 높다 .

SCAN

일단 한쪽 방향으로 끝까지 돌고 그 뒤, 다른 방향으로 돈다.

FIFO 보다 처리시간이 짧고 SSTF 보다는 길다. 그러나 Starvation 가능성이 매우 적다. → 거의 없다고 봐도 된다.

SCAN 의 문제점

1. Starvation 이 완전히 없진 않다.
2. Request
   ↳ 이 트랙의 여러 섹터들은 request 가 매우 많다. 어떤 섹터에 트랙이 너무 몰려 있으면 다른 섹터에 있는 request 들은 처리가 늦어지게 된다.

C-SCAN

Hard-Disk 접근 시, Starvation 이 발생하면 안된다.

예측가능성

내가 하드디스크에 어떤 request 를 보냈는데 다시 작업을 시작할 때까지 얼마나 시간이 걸릴까?

얼마나 시간이 걸릴지도 중요하지만,
track 중 어느 트랙이건 공정하게 예측 가능성이 같아야 하는데 SCAN 기법은 예측가능성이 track 에 따라 다르다.

• 안쪽 → 빠름
• 바깥쪽 → 느림

편차가 싫어서 C-SCAN 을 사용하는건데 성능이 더 좋지는 않다.

• Restricts scanning to one direction only
• When the last track has been visited in one direction, the arm is returned to the opposite end of the disk and the scan begins again

N-step-SCAN

• Segments the disk request queue into subqueues of length N
• Subqueues are processed one at a time, using SCAN
• New requests added to other queue when queue is processed

큐를 크기 N 인 서브 큐로 만든다. N개의 큐가 아니라 크기가 N 인 서브 큐로!

크기가 3인 서브큐를 두면, 특정 트랙에 request 가 들어와도 새로운 큐로 밑에 들어가 처리 속도가 느려지지 않는다.
⇒ N개씩 나눈다.

⇒ Starvation 가능성이 존재한다. → 큐가 몇개인지 알 수가 없다.
⇒ 따라서 request 가 굉장히 많아지면 큐가 굉장히 많아지게 된다.

N = 1 → FIFO 를 사용한다.
⇒ N 값에 따라 이 방법이 잘 작동되게 해준다.
⇒ SCAN, FIFO, ...

FSCAN

• Two subqueues
• When a scan begins, all of the requests are in one of
  the queues, with the other empty.
• All new requests are put into the other queue.
  • Service of new requests is deferred until all of the old requests have been processed.

• 두개의 큐만 사용한다.
• Starvation 이 없다.
• SCAN 과 가깝다.

10시 이후에 도착하는 애들은 반대쪽에 쌓이게 된다. 나는 10시 이후에 도착하는 저 request 를 처리하며 지나갈 필요가 없다. 10시 전에 온 request 만 처리한다. 끝까지 다 가서 10시 30분이되면 방향을 바꿔서 올 때는 10시에서 10시 30분에 도착한 request 만 처리한다. 매번 내가 SCAN 으로 한쪽 방향으로 끝까지 갈때는 전 타임동안 도착한 requst 만 처리하면 된다. 새로운 request 가 와도 걔네들은 다른 큐에 쌓이는 것이기 때문에 어느 한 트랙에서 계속 해서 서비스를 하는 상황은 발생하지 않게 된다. Starvtaion 은 존재하지 않는다.

큐가 두개밖에 없지만, 큐의 길이가 다르다고 성능이 달라지진 않는다. 거의 SCAN 과 가까운 그러나 Starvation 은 없는 방식이다.

Windows System Scheduling

Real-time task

→ Round-Robin 방식 사용
↳ 언제나 우선순위 기반의 Preemptive Scheduling 기법이다 🌟
내가 어떤 task 를 실행하고 있다가도 이거보다 조금이라도 우선순위가 높은 프로세스가 갑자기 시스템에 새로 들어오면 하던 거 중단하고 새로 들어온 프로세스를 서비스한다.

Non-Real-time task

→ Feedback 방식 사용
↳ 계속 CPU 를 사용하면 우선순위가 내려가고 CPU 를 사용하면 우선순위가 올라간다.
프로세스들이 한 번 Ready Queue 에 들어가면 끝날 때까지 작업하는 것이 아니라 Ready Queue 에 갔다가 I/O 작업 했다가 Ready Queue 에 갔다가, ... 한 번 Ready Queue 에 갔을 때의 서비스 타임을 Burst time 이라고 부르는데,
Burst time 이 짧다는 뜻은 내가 처음에 0번 큐에서 시작해도 I/O 작업을 반복해서 하다 보니 Burst time 이 계속 짧아지게 되면 2, 3, 4, ... 계속 큐가 올라가게 될 것 이다. 결국 15번 큐에서 서비스가 되게 된다.
Burst time 이 짧은 프로세스는 초기 우선순위에 상관 없이 결국 가장 우선순위가 높은 큐에서 처리가 되게 될 것이다.
⇒ 간단히 말해, SRT 처럼 실행 시간이 짧은 프로세스를 우선으로 하는 Scheduling 방법이라고 생각할 수 있다.

아무리 처음에 15번에서 시작을 했어도 실행시간이 길어서 매번 time quantum 을 끝까지 다 쓰면 14, 13, ... 결국 0번까지 갈 수 있다. 그렇게 되면 CPU 를 잡을 확률이 굉장히 떨어지게 된다.

Windows 는 실행시간이 짧은 프로세스를 먼저 처리하고 실행시간이 긴 프로세스의 우선순위를 낮추어서 나중에 처리되는 방식과 비슷한 성능을 보인다.
즉, SRT 와 비슷한 성능을 보이는 것이므로 성능이 무척 좋다고 할 수 있다.

↔ 그러나 문제점은 Starvation 가능성이 높다는 것이다.

0번 큐는 위에 있는 31개의 큐가 다 비어야 CPU 를 잡을 수 있다.
0 번 큐에 들어 있는 프로세스나 task 들을 위한 어떠한 보호조치가 없다.

UNIX SVR4 Scheduling

160개의 큐로, 큐가 매우 많기 때문에 우선순위를 굉장히 세분화 했기 때문에 완전히 우선순위 기반 시스템이라고 할 수 있다.

Real-time processes (159-100)

• Highest preference to real-time processes (159-100)
• 60개

Kernel-mode processes (99-60)

• Next-highest to kernel-mode processes (99-60)
• 30개

Time-Shared process (59-0)

• Lowest preference to other user-mode processes (59-0)
• 일반적인 유저 프로세스

제일 우선순위가 높은 159번 큐부터 시작해서 0번째 있는 프로세스를 확인하기 위해서는 159번 확인해야 한다.

간단히 우선순위 큐를 살펴보기 위해서 Bit map 을 사용한다. 159번 큐에 누가 있나 없나 한 비트로 표현한 것이다. 각각의 큐에 대기하고 있는 프로세스가 있을 경우엔 1, 없을 경우는 0으로 표현된다. 이렇게 Bit map 을 사용해서 비어 있는 큐를 빠르게 Scan 할 수 있다.

159개를 훑어 보는 거랑 Bit map 을 하나하나 확인하는 것이랑 차이가 있을까? 160bit 는 정수 하나가 32 bit 이므로 5개의 정수로 표현된다. 5개의 정수를 비교하는데 정수가 하필 0이면 32개의 큐가 다 비었다는 의미이다. 그럼 이 32개의 큐는 비교해 볼 필요가 없는 것이다.

그 다음 정수가 또 0이면 여기 32 개의 큐도 다 비었다는 의미이므로 비교해볼 필요가 없다.

그 다음 정수가 0이 아닌 어떤 숫자라면, 나는 거기에 task 가 있는 것이 확실하므로 32 bit 만 검사를 해보면 된다. 그렇게 되면 32개의 bit 만 보게 되므로 Windows 랑 비슷하게 된다.

UNIX SVR4 Scheduling 의 실제 Scheduling 방법

Windows System 과의 공통점

1. Priority-Driven Preemptive Scheduling
   (우선순위 기반의 Preemptive Scheduling, 내가 어떤 task 를 처리하다가 그것보다 우선순위가 하나라도 높은 task 가 오면 무조건 하던거 중단하고 새로운 프로세스를 처리한다.)
2. RR for the Jobs w/ the Same Priority (real-time class)
   ( real time class 에 있는 프로세스 중에 우선순위가 같은 것들이 있다. 이 경우, Round-Robin 으로 작업하게 된다.)
   • fixed priority and a fixed time quantum
     (real time class 에 있는 task 들은 fixed priority 를 가진다. 단, round-robin 을 할 때, time quantum 역시 fixed time quantum 을 가진다.)
3. Priority Feedback (time-sharing class)
   (일반 유저 클래스의 경우, CPU 를 많이 사용하면 우선순위를 낮추고 I/O 작업을 많이 하면 우선순위를 높여준다.)
   • Processor-bound threads down
   • I/O -bound threads up

Windows System 과의 차이점

The time quantum allocated to a timesharing process depends on its priority , ranging from 100 ms for priority 0 to 10 ms for priority 59.

Fairness 고려 ⇒ Starvation 줄이려고 노력

timesharing 프로세스인 경우에는 우선 순위에 따라 time quantum 을 다르게 설정한다.

• 0 → 우선순위가 가장 낮음: time quantum 길게 잡아주기
• 59 → 우선순위가 가장 높음: time quantum 짧게 잡아주기

Linux Scheduling

Scheduling classes

0-99 까지의 큐는 real-time class 들을 위한 큐이다.
그런데, 이 클래스를 RR 로 할지 FIFO 로 할지 결정할 수 있다.

1. SCHED_FIFO:

First-in-first-out real-time threads (0-99)

real-time task 들은 실행시간이 매우 짧은 task 들이다.

2. SCHED_RR:

Round-robin real-time threads (0-99)

FIFO 나 RR 둘 중 하나 선택할 수 있다.

3. SCHED_OTHER:

Other, non-real-time threads (100-139)

40개가 존재한다.

Within each class multiple priorities are used

Linux Scheduling for Real-time Classes

FIFO

The system will not interrupt an executing FIFO thread except in the following cases

• Another FIFO thread of higher priority becomes ready
• The executing FIFO threads becomes blocked
• The executing FIFO threads voluntarily gives up the processor following a system call
• If more than one thread has that highest priority, the thread that has been waiting the longest is chosen

CPU 를 잡으면 끝까지 실행한다 생각할 수 있지만,
우선 순위 기반의 Preemptive Scheduling 이므로 FIFO 스레드이기는 하지만,
하나를 실행을 하고 있다 했을 때, 우선 순위 높은 애가 나타나면 무조건 CPU 를 뺏기게 된다.

FIFO 이므로 Block 이 됐을 때, 시스템 콜 같은 것을 요청해서 내가 스스로 CPU 를 반납 했을 때, CPU 를 가져가게 된다.

FIFO 이므로 같은 우선순위인 스레드가 여러개인 경우에 어떤 순서대로 처리할까?
↳ 기다리는 시간이 오래된 프로세스를 먼저 선택한다.

RR

The scheduling policy for RR thread is similar, except for the addition of a time-slice associated with each thread

RR도 우선 순위 높은 스레드가 나타나면 무조건 CPU 를 뺏기게 된다.

Linux Scheduling Data Structures

Non-real time task → 40개의 큐가 존재한다. → 한세트 X, 두세트 O

Active Queue 가 100번 부터 139번 까지 존재하고, Expired Queue 가 100번 부터 139번까지 존재한다. 각각 두세트가 있는 상황이다.

1. 40개의 큐 중 현재 4개의 큐에만 프로세스가 들어 있는 상황이다.
2. P3는 timeout 전에 우선순위가 더 높은 프로세스가 등장해서 Preemptive 된다.
   → 이 경우 다시 active queue 로 돌아간다.
3. 어느 순간 active queue 가 모두 비게 되는데, Queue 를 Active 와 Expired 를 서로 바꾸어 준다.

우선순위 기반의 Preemptive Scheduling 이므로 실행을 하다가 우선순위가 더 높은 프로세스가 나타나면 CPU 를 뺏기고, Non-real time task 에서 CPU 를 많이 사용하는 프로세스들은 우선순위를 낮춰주고 우선순위가 낮은 큐로 들어갈 수 있고 일찍 CPU 를 놓고 I/O 작업을 하러간 프로세스들은 우선순위를 높여줘서 Blocked Queue 에 있다가 다시 Ready Queue 로 들어갈 때는 아까보다 우선순위를 더 높여줘서 들어간다.

⇒ Starvation 가능성이 매우 낮다. 굉장히 fair 하다. (기말고사 문제)
↳ WHY?

두 개의 Queue 가 하나의 Queue 보다 Starvation 가능성이 낮아지게 된다.

내 생각엔 우선순위가 높은 스레드들은 다른 우선순위가 높은 task 들에 의해 Preemptive 당할 가능성이 낮으므로 timeout 까지 CPU 를 모두 사용하고 Expired 로 들어가게 된다. 하지만 우선순위가 낮은 스레드들은 다른 다른 우선순위가 높은 task 들에 의해 Preemptive 당할 가능성이 높으므로 Preemptive 되어 active 에 계속 남아있게 된다. 그렇게 되면 결국 active 에 남게된 우선순위가 낮은 스레드들이 우선순위가 높지만 이미 expired 된 스레드들보다 우선적으로 실행을 마칠 수 있게 되므로 starvation 가능성이 낮아지게 된다.

Design Issues

1. 프로세스가 시스템 안에 들어왔을 때 이 프로세스를 어느 CPU 에게 할당해줄 것 인가?
   • CPU 마다 개별적인 Queue 를 줄 것인지?
   • Global Queue 를 줄 것인지? ✅
2. MultiProgramming?
   • Uni-Processor 에서는 MultiProgramming 은 당연한 것
   • Block 은 주로 I/O 작업에 의해서 발생하는데,
     하나의 application 안에서 여러개의 프로세스들 또는 스레드들이 만들어져서 굉장히 빈번하게 동기화를 한다고 했을 때의 Block 상태는 I/O 작업을 위한 Block 이 아니라 동기화를 위한 Block(Semaphore Wait) 또는 데이터를 주고 받기 위한 Block 과 같은 상황이 주이다.
     이 경우, Switching 을 하는 것보다 잠깐 기다리면 금방 해결되는 경우가 많기 때문에 MultiProgramming 을 하지 않고(Switching 을 하지 않고) 그냥 버티는게 더 나을 수도 있다.
3. 9장에서는 실행시간에 따라 프로세스를 실행시키는 순서가 매우 중요했으나,
   MultiProcessor System 의 경우에는 CPU 가 2개, 3개, ... 많아지면 많아질 수록 실행시간에 따라 프로세스 순서를 변경하는 것이 별로 의미가 없다.
   ↳ 다른 CPU 들이 있기 때문

4가지 Scheduling 방법

1. Load Sharing
2. Gang Scheduling
3. Dedicated Processor assignment
4. Dynamic Scheduling

Load Sharing

↳ Global Queue 사용 각각의 CPU 는 스레드나 프로세스를 실행하다가 스레드가 프로세스가 실행을 끝마치게 되면 OS 의 Scheduler 를 실행 시켜서 다음에 실행할 프로세스나 스레드를 선택한다.
⇒ Idle-While-Busy 상황은 발생하지 않는다.

Load Sharing 의 문제점

Global Queue 자체가 Critical Section 이다.

즉, 여러 CPU 에서 진행되고 있는 여러 Scheduler 가 동시에 Queue 를 보고 다들 Queue 앞에 있는 걸 선택해야지 하고 같은 프로세스를 동시에 선택하면 안되기 때문에 한 번에 한 사람만 Critical Section 에 진입해서 Scheduling 을 할 수 있다.

⇒ Performance Bottleneck 이 될 수 있다.

그럼에도 불구하고 가장 많이 사용되는 기법이다..!
↳ 이유: 적은 개수의 CPU 를 갖고 있는 시스템에서도 굉장히 잘 작동하기 때문이다.

CPU 의 개수가 수십개에서 수백개인 MultiProcessor System 을 다루는 Scheduling 들에 대해서 알아보자!
↳ Parallel Computer 에 가까운 시스템들에서 사용되는 Scheduling 들

Gang Scheduling

Application 이 여러개의 Thread 들로 구성되어 있다.
↳ 여기서의 Application은 independent 한 프로세스나 Very Coarse 정도가 아니라, 적어도 Medium 이나 fine 정도의 application 을 가르킨다.

이러한 시스템에서는 여러개의 스레드들로 이루어져 있을 뿐만아니라 굉장히 자주 밀접하게 동기화를 한다. 일정하게 자주 동기화하기 때문에 잠깐 Block 이 되어도 Switching 하지 않고 기다리는 게 나은 경우가 많다.

한 프로세스의 스레드를 동시에 실행한다!

Ready Queue 에 스레드 단위가 아닌 프로세스 단위로 줄을 선다.

어떤 프로세스가 Scheduling 이 되면, 이 프로세스가 몇개의 스레드를 포함하는지 확인하고 만약 5개의 스레드가 필요하면 5개의 스레드를 나누어 준다.
⇒ 필요하다고 하는 CPU 만큼 해당하는 application 에 할당해 스레드들을 동시에 실행시킨다.

가정

동시에 실행을 하지 않으면, Performance에 심각한 Damage 가 있다.
⇒ Parallel application

시스템 안에 N 개의 프로세서가 있다고 가정했을 때, 스레드의 개수는 N보다 작거나 같아야 한다.

CPU 개수 >= Application 의 thread 의 수

문제점

CPU 개수 < Application 의 thread 의 수 라면, Scheduling 이 불가능하다.

A set of related threads is scheduled to run on a set of processors at the same time

• Threads often need to synchronize with each other
• Simultaneous scheduling of threads that make up a single
  process
• Useful for medium-grained to fine-grained parallel applications whose performance severely degrades when any part of the application is not running

Processor allocation must be considered

• N processors
• for M applications
• w/ N or less thread

Time sharing

• 1/M of the available time on the N processors, for each
  application
• Scheduling weighted by the number of threads

CPU 를 1/M 씩 나누어 실행하면 밑의 예시의 Group1 의 그림과 같이 놀고 있는 CPU 의 수가 증가하게 되며, CPU 의 Utilization 이 굉장히 나빠진다.

Utilization 은 같은 time quantum 을 사용할 때 좋지 않다.

⇒ 스레드의 개수 에 따라 time quantum 을 다르게 주어야 한다.
⇒ idle time 을 줄일 수 있다.

Thread Example

Application 이 여러개 있을 수 있다. → Gang Scheduling 은 기본적으로 Round Robin , Time Sharing 을 한다.

내가 A → B → A → B → ... Application 을 번갈아 가며 실행한다. A 라는 Application 의 스레드를 동시에 실행하고, B 라는 Application 의 스레드를 동시에 실행한다.

Time quantum 을 어떻게 결정할 것인가?

그림에서 PE 는 CPU 를 나타낸다. 즉, CPU 가 4개 존재하는 시스템이다. Group 라는 2개의 application 이 실행을 하고 있다.

• Group1 은 4개의 스레드를 가지고 있다.
• Group2 는 1개의 스레드를 가지고 있다.
  ↳ Group2 가 실행될 때는 CPU 2, 3, 4 는 놀게 된다.

그럼 놀고 있는 CPU 2, 3, 4 를 Group1 에게 주어도 되지 않을까? 싶지만,
여기서의 가정은, Group1 의 네개의 스레드는 굉장히 밀접하게 동기화 하기 때문에
⇒ Group 1의 2, 3, 4 만 실행해도 1을 못해서 block 될 수 있기 때문에 Group2 를 실행할 때 CPU 2, 3, 4 를 Group1에게 주지 않는다.

Time Quantum 을 group1에 더 많이 주게 되면 IDLE 이 15% 정도 줄게 된다.

Dedicated Processor Assignment

Gang Scheduling 보다 한 단계 앞선 Scheduling 기법이라고 볼 수 있다.

Gang Scheduling 과 공통점

• Global Queue 에 Process 들이 줄 서 있다.
• 어떤 프로세스가 Scheduling 되면 그 프로세스가 가지고 있는 스레드 개수만큼 CPU 를 할당한다.
• CPU 에서 스레드은 동시에 실행된다.

Gang Scheduling 과 차이점

CPU 에서 스레드은 동시에 실행되는데, Time swapping X, Round robin X, Switching X

한번할당 → 계속 실행
⇒ 이유? application 안의 애들이 밀접하게 동기화 한다.

Round Robin 이나 Time Sharing 은 time out 이 되면 Switching 을 하게 되는데 그 시간도 아깝다는 것이다. 그 시간을 아껴서 계속 실행을 하겠다는 의미이다.

가정

이 application 들은 Parallel Program 이다.
↳ User 와 interaction X, 굉장히 많은 양의 file에서 Data 를 많이 읽고 많은 computation 을 한 후, 결과값을 file 에 적는다.

⇒ I/O 에 의한 Block 이 거의 없다.

최대한 빠르게 작업을 시키기 위해서 사용되는 Scheduling 기법이다.
어떤 경우에도 멈추지 않는다.

When application is scheduled, its threads are assigned to a set of processors

• Threads are assigned to a specific processor
• # of threads = # of processors

Some processors may be idle if some threads of an application are blocked for I/O or synchronization

Avoids process switching

Dedicated Processor Assignment 의 문제점

Processor fragmentation problem

16개의 CPU와 스레드 5개를 가지는 3개의 application 3개를 동시에 실행 → 5 5 5 개씩 CPU 를 나누어 준다.
⇒ CPU 가 1개 남는다. → 너무 작기 때문에 다른 스레드를 실행시킬 수 없다.

Scheduling 의 목적

프로그램을 실행하는 순서가 아니라, CPU 를 어떻게 application에게 어떻게 (몇개씩 한번에) 할당을 할까?

application 이 Ready Queue 에 굉장히 많다고 했을 때, Processor fragmentation problem 이 없게 하려면, 5 5 5 보다 5 3 3 4 과 같이 16개를 딱 맞추는 게 훨씬 효과적이라고 생각할 수 있다.

1개의 application 에 여러개의 CPU 를 할당하고도 CPU가 남는상황에서 Gang Scheduling 이나 Dedicated Processor Assignment 를 사용하는 것이다.

Dynamic Scheduling

줄 수 있는 최대한의 CPU 를 나누어 준다.

Global Sharing ↔ Gang Scheduling , Dedicated Processor Assignment 기법의 중간 정도의 CPU 개수를 보유한 시스템에서 사용하는 기법이다.

Gang Scheduling , Dedicated Processor Assignment 기법의 Scheduling 은 많은 CPU 를 어떤 application 에게 할당할지 OS 가 관리한다.

OS is responsible for partitioning the processors among the jobs

Multi-Processor System 에서 Scheduling 은 내가 가지고 있는 굉장히 많은 CPU 를 언제 누구한테 몇개 나누어줄것인지를 결정하는 것인데, 이 작업을 OS 가 한다.

OS 는 CPU 를 잘 나눠서 각각의 application 에게 나누어 주는 역할을 한다.

각각의 application 은 CPU 를 할당을 받는데, 자기가 원하는 개수보다 부족할 수 있다. 나는 5개의 CPU 가 있으면 동시에 5개의 스레드를 실행시킬 수 있는데, application 은 5개가 필요하지만 CPU 는 3개만 줄 수 있다. 이렇게 되면 5개의 스레드를 3개의 CPU 에서 실행을 시켜야 한다. 그러면 5개의 스레드를 3개의 CPU에서 어떠한 순서대로 어떻게 실행시킬까 하는 것은 application level 에서 결정하는 것이다.

• OS 의 역할 = CPU 를 나누어 주는 것
• 실제 나누어 받은 CPU 안에서의 Scheduling 은 user level application 에서 실행된다.

Each job uses the processors currently in its partition to execute some subset of its runnable tasks

1. 일단 어떠한 job 이 필요한 CPU 의 개수를 이야기한다. → 5개가 필요하다.
2. 만약 5개의 idle 한 CPU 가 있으면, 당연히 5개를 나누어준다.
3. 만약 남아있는 CPU 가 3개라면 3개를 나누어준다.

⇒ 일단, 달라고 하면 존재하는 놀고 있는 CPU 들을 있는만큼 준다.
↔ 만약, 아예 줄게 없으면 다른 application 이 사용중인 CPU 뺏어서 준다.
↳ 다 뺏진 않고, 각각의 application 이 필요한 최저치보다 많이 가지고 있는 CPU 를 뺏게 된다. 경우에 따라서는 각각 다 최저치 만큼만 갖게 될 수 있는데, 이 경우 해당하는 application 은 Ready Queue 에서 기다려야 한다.

Ready Queue 에서 기다려야 하는 application 이 생길 수 있는데, 어떠한 프로세스가 실행을 끝마치면, CPU 가 많이 반납되게 되어 Ready Queue 에 5명이 기다리고 있는데 CPU 가 5개 있으면 5명에게 1개씩 나누어 준다. 즉, 최소 1개씩은 갖게되어 실행을 시작할 수 있게 된다. 그 다음에 남아있는 것은 Frist Come First Basis ( FCFS )로 가장 오래 기다린 프로세스에게 CPU 를 주게 된다.

An appropriate decision about which subset to run is left to the individual application

OS 의 역할은 실제 스케쥴링 → application level 에서 결정한다. → 가능한 만큼 준다.

⇒ 실제 CPU 개수 < application 스레드 필요 개수 여도 실행 가능하다는 장점이 있다.

When a job requests one or more processors;

• Assign idle processors
• New arrivals may be assigned to a processor that is used by a job currently using more than one processor
• Hold request until processor is available

Upon release of one or more processors;

• Assign a single processor to each job in the queue that currently has no processors
• Allocate the rest of the processors on an FCFS basis

Real-Time Scheduling

Real-Time task 는 정확도 는 기본적으로 중요하고, 거기에 Deadline 을 맞춰야 한다.
→ Deadline 을 지나치면 필요없는 결과값이 된다.

• 정확한 실행
• Deadline 맞추기

Real-time computing

type of computing in which the correctness of the system depends not only not the logical results of the computation, but also the time at which the results are produced

1. Hard real-time task

one that must meet its deadline; otherwise it will cause unacceptable damage or a fatal error to the system

deadline 을 못 맞추면 시스템에 데미지가 가해지기 때문에 반드시 deadline 을 맞춰주어야 한다.

2. Soft real-time task

associated deadline is desirable but not mandatory

deadline 을 맞추면 좋은데, deadline 을 못 맞추더라도 시스템에 데미지가 가해지진 않는다.

시스템 관점 에서 중요한것: Througput ⇒ deadline 을 못맞추면 Throughput 에 포함되지 않기 때문에 Throughput 을 높이기 위해 deadline 을 맞춰야 한다.

periodic task & aperiodic task

1. periodic task

주기가 있는 task 이다.

2. aperiodic task

주기가 없는 task 이다.

주기가 없어 예측이 불가능하기 때문에 미리 Scheduling 이 불가능하다.

주로 Soft real-time task 인데 periodic 하게 도착하는 task 에 대해서 어떻게 Scheduling 하면, deadline 을 최대로 맞추고 Througput 을 최대로 만들 수 있을까? 가 Real-time Scheduling 에서 얘기가 된다.

Real-time Scheduling
1. Earliest-deadline Scheduling

Deadline 이 빠른 task 를 먼저 Scheduling 한다.

realtime task 는 우선순위가 정해져 있다.

• deadline
• 도착 주기

우선순위를 무조건 맞춰야 한다.
⇒ Real-time Scheduling 은 우선순위에 의한 Preemptive 가 존재한다.

각 task 는 본인의 다음 task 가 올 떄까지 (deadline) 이 오기 전까지 작업을 마쳐야 한다.

• A task 는 20분 주기로 1번씩 도착 / 10분간 작업한다.
• B task 는 50분 주기로 1번씩 도착 / 20분간 작업한다.

↑ Scheduling 의 결과

B1과 A3 를 비교할 때는 B1의 deadline 이 먼저 끝나므로 B1 을 먼저 실행한다.

B2 와 A5 를 비교할 때, 둘 다 deadline 은 같지만 이 경우 먼저 도착한 애가 먼저 실행되기 때문에 B2 를 먼저 실행한다.

⇒ 매번 새로운 job 이 도착할 때마다 실행하고 있던 task가 끝날 때마다 다음에 누구를 실행을 시켜야 할지를 결정한다.
↳ 여기서는 Deadline 이 빠른것을 먼저 선택한다.

Real-time Scheduling
2. Rate Monotonic Scheduling

우선순위가 deadline 이 아니라 주기인 Scheduling 이다.

주기가 짧은 걸 먼저 실행한다. ⇒ 주기가 짧다는 것은 deadline 이 금방 다가온다는 뜻이므로, deadline 이 금방 끝나는 것과 일맥상통한다.

Rate Monotonic Scheduling 은 Earliest-deadline Scheduling 보다 더 많이 사용되는 방식이다.

• ↓ : deadline 시간
• ↑ : 도착 시간

3개의 task T1, T2, T3 가 존재한다.

• T1 - 주기: 4시간 / 실행: 1시간
• T2 - 주기: 5시간 / 실행: 2시간
• T3 - 주기: 7시간 / 실행: 2시간

따라서 우선순위는 T1 > T2 > T3 이다.

1. 0시에 동시 도착하고 우선순위가 제일 높은 T1 부터 실행한다.
2. T3는 한시간 작업하고 T1의 다음번 Task 가 와서 중지하고 T1 을 서비스 한다.
3. T3 는 deadline 이 지나버렸다..!

Real-time Scheduling → Priority Inversion

Priority Inversion : 모종의 이유로 우선순위가 더 높은 task 가 우선순위가 더 낮은 task 를 기다리는 상황

여기서 우리가 어떻게 해결할 수 있는 상황이 아니다.

• Scheduling 은 Scheduler 가 한다.
• OS 가 application 안의 code 를 실행하는데 Critical Section(semWait) 에서 우선순위를 따지지 않는다.
  → 먼저 통과한 애가 먼저 실행된다.

⇒ Scheduling과 Critical Section 은 완전히 별개의 작업이다.

Priority Inversion 은 발생할 수 밖에 없지만, Unbounded priority inversion 은 막아야 한다.

Unbounded priority inversion

Unbounded priority inversion : 계속해서 Priority Inversion 이 발생하는 상황

우선순위 T1 > T2 > T3

1. T3 가 critical section 인 s 를 lock 시킨다.
2. t3에 우선순위가 높은 T1 에게 CPU 를 빼앗기지만 s 는 이미 T3 가 이용 중이므로 T1 은 s 를 이용할 수 없다.
3. T3 는 잠깐 동안 진행하다 t5에 온 T2 에게 CPU 를 빼앗긴다.
4. CPU 를 빼앗은 T2 는 s 와 상관이 없어 계속 진행한다.
5. t6에 다시 CPU 를 잡은 T3 는 작업을 마치고 s 를 unlocked 한다.
6. T1 이 CPU 를 잡고 다시 s 를 lock 시키고 작업을 한다.

Unbounded priority inversion 해결 방법
⇒ Priority inheritance

해결방법: T3 의 우선순위를 일시적으로 높여준다.

a lower-priority task inherits the priority of any higher-priority task pending on a resource they share

T3 가 작업하다 T1 에게 CPU 를 걸고 T1 이 s 에 lock 을 걸려고 할 때, T3 의 우선순위를 T1 만큼 높여준다.
⇒ T2 보다도 우선순위가 높아져서 T3 가 먼저 실행된다.

Window Scheduling

Multi-level Priority Queue

• Real-time Priority Queues (16 Levels)
• Variable Priority Queues (16 Levels)

총 32 개의 Ready Queue 가 있으며 각각 16개씩 나누어져 있다.

Real-time Priority Queues

→ Real-time task 를 위한 queue
↳ fixed priority 를 가진다.

Real-time task 는 우선순위가 deadline 이므로 우선순위가 변하지 않는다. 같은 우선순위를 갖는 task 는 존재할 수 있는데, 이때는 Round-Robin 으로 스케쥴링을 한다.

Variable Priority Queues

→ Non-real-time task 를 위한 queue
↳ 우선순위가 변한다.

내가 CPU 를 한번 잡고 실행을 하고 나면, 어떻게 실행을 했느냐에 따라 우선순위가 달라질 수 있다. 일종의 Feedback Queue 라고 생각할 수 있다. 우선순위가 높아질 수도 낮아질 수도 있다.

Jobs in Real-time Priority Queues

• Fixed Priority
  ↳ 우선순위: DeadLine 인 애들이 많다.
• RR within a Queue
  ↳ 같은 우선순위를 갖는 task 들

Jobs in Variable Priority Queues

• Feedback Queue
  ↳ 내가 지금 작업한 내용에 따라서 우선순위가 높아질 수도 작아질 수도 있다.

Windows Thread Dispatching Priorities

Starvation 에 대한 고려를 전혀 하지 않는다.

우선순위는 다음과 같다.

• 31: A
• 30: B
• 29: C, D
• 28: E

CPU 가 1개라면, A → B → C D C D (Round-Robin) ... → E

Priority-Driven Preemptive Scheduling

우선순위 기반 Preemptive Scheduling 이다.

Real Time Task

1. 위에 큐가 다 비어져야 밑의 큐 Scheduling 가능
2. 위의 큐에 task 가 오면 현재 작업 중단 하고 우선 순위가 높은 task 먼저 실행한다.
3. 우선순위가 같은 경우에만 round-robin 을 한다.

Jobs in Real-time Priority Queues

RR for the Jobs w/ the Same Priority

29하다가 30 드들어오면 무조건 멈추고 우선순위 높은 애를 먼저 실행한다. 같은 경우에만 round-robin 방식을 실행한다.

Non Readl Time Task
→ 9Priority Feedback for Jobs in Variable Priority Queues

Processor-bound threads down

OS 가 봤을 때, 내 실행 방식이 좋으면 우선순위가 높아지고, 내 실행방식이 좋지 않으면 우선순위가 낮아진다.

OS 가 좋아하는 실행 방식이란?
↳ CPU 를 안쓰고 I/O 작업이나 동기화를 많이 하는 것을 좋아한다.

만약 내가 10번 큐에서 나가서 CPU 를 잡았다면, 기본적으로 Variable Priority Queue 에 있는 task 들은 Timeout 을 둬서 작업을 할 것이다. Timeout 까지 작업을 할 수 있는데, Timeout 을 다 쓴 경우, OS 는 얘를 싫어하게 된다.

I/O-bound threads up

주어진 Timeout 을 다 쓴 스레드를 의미한다.

이 스레드들은 다음번에 우선순위를 낮추어서 9번, 8번, 7번 큐에 집어 넣게 된다. 반면, 내가 10번 큐에서 나가서 CPU 를 잡았는데 CPU 잡자마자 I/O 작업을 한다든지, 메시지 receive 를 한다든지, 동기화를 한다든지 block 상태가 된다.
⇒ blocked queue 로 온다.
→ 이후 작업을 마치고 다시 Ready Queue 로 올 때, 10번에서 나왔지만 11번, 12번, 13번 큐로 올려주게 된다.

Feedback Queue 에 있는 task 들의 우선순위

• CPU 를 많이 사용 → 우선순위 ↓
• CPU 를 적게 사용, I/O, 동기화, ... 많이 할 수록 → 우선순위 ↑

within a certain range

그러나 우선순위가 무조건 낮아지고 무조건 높아지는 것은 아니다. 범위가 존재한다.

프로세스의 우선순위, 스레드의 base 우선순위, 스레드의 dynamic 우선순위
→ 모든 프로세스는 프로세스의 base priority 를 가진다. 이것은 어떤 일을 하는 프로세스냐에 따라 달라진다.

• 일반적인 user process 인 경우에는, 우선순위가 낮다.
• 시스템 작업을 하는 process 의 경우에는 우선순위가 높다.

⇒ 프로세스의 종류에 따라서 base priority 가 결정된다.

base priority

현재는 base priority 가 5로 정해져 있다.
스레드의 base priority 는 프로세스 안에서 스레드를 만들어 낼 때 자체적으로 결정하는데, 여러 스레드를 만들 때 스레드들에게 다 똑같은 우선순위를 줄 수도 있지만, 이 스레드는 조금 더 중요한 일을 하므로 우선순위를 조금 더 주고 저 스레드는 조금 덜 중요한 일을 하니까 우선순위를 낮춰주고 할 수 있다.
이러한 스레드들의 base priority 는 프로세스의 base priority +- 2 만큼이다.
즉, 프로세스의 base priority 가 5인 경우의 최저 3, 최대 7까지 스레드의 base priority 를 application 안에서 조정할 수 있다.

3 ← 5(proces) → 7 (base)

프로세스의 base priority 나 스레드의 base priority 는 프로그램 성격에 따라 조정이 된다. 실제로 실행이 되며 조정되는 부분은 마지막 스레드의 dynamic priority 이다.

처음에는 굉장히 낮은 base priority 로 시작했지만 얘는 CPU 잡을 때마다 계속 I/O 작업을 하거나 동기화 작업을 해서 Timeout 을 다 못 쓰면, 점점 우선순위가 위로 올라간다.
→ 최대치로 15까지 우선순위가 올라갈 수 있다.
당연히 16부터는 real-time-task 이므로 거기까지는 올려주지 않는다.
↳ Variable Queue 에서 제일 높은데 까지만 올라갈 수 있다.

단, 내려갈 때는 막 내려가서 0까지 내려가진 않고 스레드의 base priority 의 최저값까지만 내려간다.
↳ 왜냐하면 application 자체가 어떤 특정한 역할을 하는 application 이기 때문에 스레드가 CPU 를 많이 쓴다고 해서 우선순위를 너무 낮추어서 (시스템 작업을 하는 application 인데,) 실행이 안되면 안되기 때문이다.

⇒ 이렇게 적절한 범위 안에서 스레드의 우선순위를 우리가 바꿔준다.

Multiprocessor Scheduling w/ N Processors

Windows 시스템은 당연히 Multiprocessor 를 가정하고 Scheduler 를 만든다. 실제 CPU 는 하나가 아니라 여러 개가 되는 것이다.

N 개의 CPU 를 가지는 시스템이라고 했을 때, Queue 그림을 보여주면 Queue 도 32개, CPU 도 32개라 0번 CPU 가 0번 Queue, 1번 CPU 가 1번 Queue, ... 와 같이 담당하나 착각할 수 있지만, 그게 아니라 언제나 우선순위가 높은 것 부터 작업을 해야한다.
실제 CPU가 몇개든 상관 없이 모든 N개의 CPU 는 내가 실행을 하다가 실행하던 작업이 끝나면(Timeout 등으로) Queue 에 가서 다음에 실행할 스레드를 가져오는데, 제일 우선순위가 높은 Queue 부터 다음에 실행할 스레드를 가져온다.
⇒ Idle-While-Busy 는 존재하지 않는다.
⇒ 32개의 Queue 가 하나의 Global Queue 이다.

우선순위가 낮은 스레드가 실행되고 있는데, 우선순위가 더 높은 스레드가 Queue 에서 기다리는 상황도 존재하지 않는다.
↳ 왜냐하면, 항상 우선순위가 높은 것 부터 스레드를 가져오기 때문이다.

언제나 N 개의 제일 우선순위가 높은 스레드가 동시에 N개의 프로세서에서 실행이 되는 방식이다.

제일 우선 순위가 높은 것부터 N 개를 가져다가 실행을 한다.

• Dispatcher assigns a ready thread to the next available processor - No processor is idle or executing a lower-priority thread when a higher-priority thread is ready
• Kernel tries to give the N processors to the N highest-priority threads that are ready to run

Soft affinity

dispatcher tries to assign a ready thread to the same processor it last ran on – processor’s cache reuse

어떤 스레드가 N개의 CPU 가 있다고 할 때 캐시는 무용지물이 된다. CPU 를 계속 바꾸는 것은 캐시의 입장에서는 좋지 않다.

Thread 의 Processor affinity : 이 스레드는 몇번몇번 CPU에서 실행을 하는 것이 좋다.
↳ 왜냐하면 거기에 내 캐시가 존재하기 때문이다.

Soft affinity : Scheduling 를 할 때, 우선순위가 높은 것 부터 꺼내가는 것은 맞지만, 가급적 내가 아까 실행한 적이 있는 Processor affinity 에 맞는 CPU 에 우선적으로 할당을 하는 것이다.

문제점

Traditional Unix System 에서는 CPU 사용 시간을 우선순위에 기준으로 잡아 공정성을 중요하게 여겨 Starvation 가능성을 0 이라고 봐도 좋다. 하지만, Windows System 은 Starvation 은 전혀 고려하지 않고 있다.

우선순위의 기준이 무엇이냐에 따라 좋은 스케쥴러가 달라진다.

우선순위: Queue 에 들어온 순서

• 공정성 ↑
• 예측가능성 ↑ : 내가 언제 실행을 끝낼 수 있는지 예측할 수 있음

SPN (Shortest Process Next), SRT (Shortest Remaining Time)

• Response Time 이 중요한 시스템에서 좋다.
• 그러나 시간예측과 Starvation 의 문제점이 있다.

Preempted ↔ Non-Preempted : 기준으로도 나눌 수 있다.

Use Of Exponential Averaging

• x축: Time
• y축: T 값
• 검정색 찬 네모 그래프: 실제 시간당 실행시간을 나타낸 그래프이다.
• 검정색의 빈 네모 그래프: 산술평균으로 예측한 그래프이다. → 예측도가 낮다.
• 파란색 찬 동그라미 그래프: 알파 값이 0.8인 그래프로 실제 값과 비슷하다.
• 파란색 빈 동그리미 그래프: 알파 값이 0.5인 그래프로 실제 값과 비슷하다.

각각의 시간에 몇시간씩 작업하는지를 보여준다.

실행시간이 증가하는 그래프에서는 괜찮았지만 감소하는 그래프에서 exponential 예측 그래프의 경우 exponential 의 첫번째 값을 모르기 때문에 기본값은 1로 시작한다.
⇒ 처음엔 조금 헤매는 형태를 보인다.
↔ 나중엔 예측을 잘하는 모습을 보인다.
⇒ SPN, SRT 등을 실제로 구현할 수 있다는 의미이다.

SRT(Shortest Remaining Time)

Preemted 기법이다.

내가 실행하다 나보다 늦게 큐에 도착했어도, 실행 시간이 나보다 짧은 애가 오면 CPU 를 뺏긴다.

남아 있는 시간과 비교하기 때문에 "Ramining" Time 기법이라고 한다.

Shortest Remaining Time

1. 2시에 B가 왔지만 A의 실행시간이 1시간 남은 상태이므로 A가 끝까지 실행하고 CPU 가 B에게 넘어간다.
2. B가 1시간 실행하다 4시에 C가 오는데 B의 실행시간은 5시간 남았지만 C의 실행시간은 4시간 남은 상태이므로 CPU 를 C에게 빼앗기게 된다.
3. D가 6시에 도착했지만, 실행시간이 5시간인 D는 C보다 실행시간이 길므로 CPU를 빼앗지 않고, C가 끝까지 실행을 하게 된다.
4. 8시에 E가 오게 되어 총 3개의 프로세스의 실행시간을 비교하게 된다.
   • E(2) Vs. B(5) Vs. D(5) ⇒ E가 실행시간이 제일 짧으므로 E가 CPU 를 잡고 실행하게 된다.
5. B Vs. D 인 상황인데, 실행시간이 같으면 먼저온 프로세스가 먼저 실행하게 되므로 B가 실행하게 된다.
6. D가 실행한다.

A, C, E 는 Waiting Time 이 존재하지 않는다. B, D 만 Waiting Time 이 존재한다.

• Preemptive version of SPN(Shortest Process Next) Policy
• Must estimate processing time

Shortest Remaining Time의 Response Time

Response Time = Waiting Time + Service Time

• Service Time: 고정값
• Waiting Time: 다른 프로세스의 서비스 타임
  ⇒ 프로세스의 실행시간이 짧은걸 먼저 실행하게 되면 전체적인 Response Time이 감소하게 된다.

↔ But, 모든 프로그램이 SRT 를 사용하는가? → No! → Starvation 발생 가능성이 있다!

Highest Response Ratio Next (HRRN)

실행시간 짧은걸 먼저 실행하지만, 공정성도 잡을 수 있다.
⇒ Waiting Time이 긴 것을 먼저 실행시키기 때문에 Starvation 을 없앤다.

Ratio

• HRRN에서의 우선순위 = Ratio
  ⇒ Ratio 값이 큰 값을 먼저 실행시킨다.
• Ratio = 1 + W/S = Waiting Time/Service Time + 1
  ⇒ Ratio 값은 Waiting Time 이 길수록, Service Time 이 작을 수록 높아진다.

1. A 는 혼자 있기 때문에 계산할 필요가 없다.
2. B 는 혼자 있기 때문에 계산할 필요가 없다.
3. B 가 끝나면 큐에는 C, D, E 가 존재한다.
   • 이 때 Ratio 를 계산하면 C 가 가장 크므로 C 를 실행한다.
   • C 가 실행하는 동안 D, E 의 Ratio 값이 달라진다.
4. D, E가 큐에 있는데 Ratio 가 E 가 더 크므로 E가 실행된다.

⇒ 모든 프로세스가 같은 시간을 기다리지만, 수식에 따라 Service Time 이 작을 수록, Service Waiting Time 을 크게 느끼게 설정된다!

• Fair 하며 성능 까지 고려하는 로직이다.
• Non-Preemptive
• Preemptive 의 경우 새로운 프로세스가 나타날때마다 계속 계산을 해주어야 한다.
  ⇒ 그렇기 때문에 Non-Preemptive 로 구현한 것이다.

Highest Response Ratio Next (HRRN) 의 Response Time

HRRN 은 두 그룹의 중간정도의 성능과 Fair 을 가진다.

실제 큐는 1개가 아니라 여러개이기 때문에 여기서 배운 기법들을 응용한 기법을 사용한다.

Feedback

스케줄링 기법으로 앞에 5가지 기법을 응용한다.

1. 실행시간 ↓ O
2. 시간 계산 하고 싶지 않음 O
   ↳ 시간 예측을 프로세스마다 해주는 것을 하고 싶지 않음
3. Starvation 안 일어나게 하기 O

위의 3가지를 모두 해결한 방식이다. → 대부분 feedback scheduling 을 응용한 방법을 사용한다.

• Feedback q = 1
  ↳ Starvation 가능성이 매우 높다.
• Feedback q = 2^i
  ↳ i는 Queue 의 번호이다. 1번 Queue 의 경우 2시간 실행, 2번 Queue 의 경우 4시간 실행, ... Queue 의 번호가 커질 수록 CPU 를 잡으면 오랫동안 작업할 수 있다. → 아래쪽 Queue 는 CPU 를 차지하기 어렵다.
  ↔ 하지만, 한 번 CPU 를 잡으면 오랫동안 작업을 하기 때문에 할당량을 끝마칠 수 있도록 한다.

• Penalize jobs that have been running longer
• Don’t know remaining time process needs to execute

Multi-level Feedback Queue

• CPU 가 1개인 시스템이다.
• 3개의 Queue 가 존재한다.
• 모든 프로세스들은 0번 Queue 에서 실행을 시작한다.
  

  

1. 0번 Queue 에 있는 모든 프로세스들이 CPU 를 잡고 Timeout(Preemptive) 되어 다시 Queue로 돌아갈 때는 Queue1로 들어가게 된다.
2. 1번 Queue 는 0번 Queue 가 비었을 때만 실행시킨다. 0번 Queue 때와 마찬가지로 1번 Queue 의 모든 프로세스들이 CPU 를 잡고 실행하다가 Timout 되어 다시 Queue 로 돌아갈때는 Queue2로 들어간다.
3. 0번, 1번 Queue가 빌 경우에만 스케쥴링된다. 이제 갈 Queue가 없기 때문에 Round Robin 방식으로 작업된다.

Multi-level Feedback Queue (2)

Round Robin 방식은 Queue 를 그려가면서 진행 방식을 확인하자!

Fair-Share Scheduling

3가지 중에 Burst Time 계산 X But, 실행시간 짧은 애한테 우선권을 줬다고 직접적으로 말하지는 못하지만, 짧으면 0번 Queue 나 1번 Queue 에서 실행을 끝냈을 것이다.

실행시간이 짧을 수록, 0번 Queue 나 1번 Queue 에서 실행을 끝냈을 것이다.

• 0번 Queue, 1번 Queue : Queue 에 들어있는 프로세스의 실행시간이 길수도 짧을 수도 있다.
• 후반대의 Queue: 무조건 프로세스의 실행시간이 긴 프로세스들이 존재한다.
  ⇒ 즉, 후반대의 Queue에 들어있는 프로세스일 수록 우선순위가 낮다.
  ⇒ 실행시간이 길수록 실행될 확률이 낮다. ← 일종의 Penalty 라고 볼 수 있다.
  ↔ 실행시간이 낮을 수록 실행될 확률이 높아진다.

⇒ 따라서, 실행시간이 짧은 프로세스에게 우선권을 준다고 말할 수 있다!

프로그램 작성
→ 여러개의 프로세스로 작업
⇒ 프로그램의 여러개의 Process 나 Thread 를 동시에 실행하게 되면, Ready Queue 에 동시에 5명이 기다린다고 하면 6개의 프로세스 10개의 Thread 가 있다고 할 때, 5개의 Thread 를 갖고 있는 Process 가 전체의 50% 를 이용하게 된다.
⇒ Fair-Share Scheduling → User 의 Process 나 Thread 가 많은 CPU 들에 어느 애플리케이션에 속해있는지

• User’s application runs as a collection of processes (threads)
• User is concerned about the performance of the application
• Need to make scheduling decisions based on process sets

• Process A: t 하나의 App 에서 나온 하나의 Process
• Process B, C: 같은 App 에서 나온 두개의 Processes

A → B → C 순 X
A → B or A → C
⇒ Fairness 를 최대한 살린 프로그램이라고 할 수 있다.

Traditional UNIX Scheduling

9장에서는 CPU가 1개인 상황만을 다룬다. → CPU 가 1개인 시스템: Traditional UNIX

UNIX 는 Fairness 를 성능보다 중요하게 생각한다. (성능 < 공정성)
↳ 모든 프로세스가 CPU 를 공평하게 사용할 수 있도록 한다.

Preempted 방식인 TIMEOUT 을 사용하는데, TIMEOUT 이 되어 Queue1 로 가는 것이 아니라 다시 Queue0 으로 돌아온다.

Queue 1의 P3 이 실행되기 위해선 P1, P2 가 실행이 완전히 종료되거나 I/O 작업을 하기 위해 사라져 Queue0이 빌 경우에만 가능하다.

↑ 1초뒤, 우선순위가 바뀐다.

• P3가 Queue 0에 혼자 있는 상황
• P3 가 1초 동안 계속 실행하다가 P3 가 종료되거나 I/O 작업으로 Block 되면 1번 Queue에 P5, P4 가 실행된다.
• 결국 전부 실행 가능하게 되므로 굉장히 공정하다는 것을 알 수 있다.
  ↳ 우선순위가 낮아지는 경우는 없다.

• Multilevel feedback using round robin within each of the priority queues
  • Multilevel feedback 은 Round Robin 을 사용한다.
    ⇒ 아래의 Queue 로 내려가지 않고, 자기 Queue 로 다시 돌아온다.
  • 여러개의 Queue 가 있으므로 제일 높은 순위의 큐에 있는 애들은 Round Robin 으로 실행된다.
• Priorities are recomputed once per second
  • 우선순위는 1초마다 다시 계산된다.
  • 최근에 CPU 를 많이 사용했을 수록 우선순위가 낮아진다.
  • 최근데 CPU 를 적게 사용했다면 우선순위가 높아진다.
• Priority is based on process type and execution history
  • Process type 과 실행 기록 에 따라 우선순위를 계산한다.

Scheduling Formula

한시의 CPU 값 = 한시간 전 12시의 CPU 값 / 2
⇒ recursive 하게 정의한다.
⇒ 1/4, 1/8, ...

P 값이 작을수록 우선순위가 높다. P 값이 제일 작은 걸 제일 먼저 선택한다. 1초마다 한번씩 P 값을 계산한다.
→ 같은 Queue 에 우선순위가 같은 프로세스들을 순서대로 집어넣는다.
⇒ 굉장히 공정
⇒ Starvation X

• CPU 사용 ↑ → CPU 사용 못하게
• CPU 사용 ↓ → CPU 사용 하게

CPU 값이 0인 프로세스가 존재하면 확실하게 실행한다.
→ 방금 시스템 안에 들어온 Process ⇒ Queue 의 제일 앞에 들어간다.
→ 실행시간이 길지 짧을지 모른다.
⇒ 최근에 들어온 애가 먼저 실행된다.
⇒ 성능이 나쁘지 않다.

CPUj(i)

Execute History

i 초에 j Process 의 우선순위

Pj(i)

Basej

프로세스 j base priority → 무슨 작업을 하는 프로세스?

• user process 일 수록 우선순위가 낮다.
• system 작업을 하는 process 일수록 우선 순위가 높다.

다음의 순서로 우선순위가 낮아진다.
1. Swapping
2. Block
3. File
4. 문자 단위

1, 2, 3, 4, ... X

굉장히 차이가 크다. ⇒ 같은 작업하는 프로세스 사이에 우선순위가 역전하는 일이 없도록 한다.

nicej

user 가 주는 값이다. → System call 로 nice 값을 조절할 수 있다.

기본 값보다 낮출 수는 있지만, 높일 수는 있다. 이를 통해 상대적 우선순위를 높일 수 있다.

Traditional UNIX Scheduling(2)

Base priority divides all processes into fixed bands of priority levels

• Swapper (highest)
• Block I/O device control
• File manipulation
• Character I/O device control
• User processes (lowest)

Nice adjustment factor used to keep process in its assigned band

Traditional UNIX Scheduling 의 Response Time

U = Utilization → 1초마다 한번씩 시간 계산을 할 수 있다.

나 혼자 CPU 다 쓰면 U = 1 이다.

T1

• T1 = 1 → 1시간 사용 X, 비율 O
• T1 = 1/2 → 전체 1초 중 Queue 에 2명이 같이 들어 있어서 반 사용한 것
• T1 = 1/4 → 전체 1초 중 Queue 에 4명이 같이 들어 있어서 번갈아가면서 작업한 것

T2

T2: 전시간의 U의 반 값을 사용한다.

• T2 = 0 + 1/2
• T2 = 0 + 1/4
• T2 = 0 + 1/8

내가 매번 CPU 를 얼만큼 썼는지를 계산한다.
↳ 한타임 지날 수록 1/2 씩 곱해진다.
⇒ 내가 CPU 사용한 것에 가중치를 주어 더한다.
⇒ CPU 를 많이 사용하면 CPU 하게 된다.
↔ CPU 를 많이 사용하지 앟을 수록 0에 가까운 값이 된다.

9장에서의 CPU 는 1개만 존재한다.

Replacement 의 성능 → Page Fault 수가 증가하면 성능이 낮아진다.

Aim of Scheduling

1. Response time
2. Throughput
3. Processor efficiency
4. Fairness

위의 네가지가 스케쥴링의 목표이지만, 애매하고, 동시 만족이 불가능하다.

1. Response time

Input ↔ Output 사이의 걸리는 시간

응답 시간이 짧으면 짧을 수록 좋다.

2. Throughput

User 의 관점이 아니라 시스템의 관점에서 단위 시간 동안 몇 개의 request 를 완료했는지를 말한다.

⇒ 크면 클수록 성능이 높아진다.

3. Processor efficiency

CPU 가 의미 있는 일에 사용된 시간

CPU 는 OS 실행이 아니라 User Program 이 정확하고 신속하게 사용하려고 만들어진 애이다.

4. Fairness

얼마나 공정한가?

→ 수로 표현할 수 없다. 단위도 없다.
1, 2, 3은 단위도 붙일 수 있고 수적으로 나타낼 수도 있다.

메모리는 기준이 명확하지만, 스케쥴링은 기준이 명확하진 않다.

Types of Scheduling

3가지 Scheduling

Long-term Scheduling

어떤 프로세스가 만들어 졌을 때 Ready Queue 로 가냐, Ready/Suspend Queue 로 가냐를 결정하는 스케쥴링

↳ 시스템 바깥쪽에서 시스템 안쪽으로 들어올 수 있느냐 없느냐를 결정한다.

어떤 프로세스가 만들어 졌을 때, 스케쥴링이 만들어진다고 바로 메모리에 들어오지 못할 수도 있다.
Ready Queue 에 너무 많은 프로세스들이 있고 메모리에 너무 많은 프로세스들이 있으면 시작부터 Suspend 가 될 수도 있다.

• New → Ready
• New → Ready/Suspend

대부분의 프로세스들은 생성되면, Ready Queue 로 가지만 Batch Job 이라고 프로그램 실행
→ 입력과 출력 모두 파일에서 작업한다.
이 경우 User 가 실행을 시켜놓고 나중에 와서 결과만 확인한다. 이러한 프로세스 같은 경우 시스템 상황에 따라 Ready 상태로 보내기도 하고 Ready/Suspend 로 보내기도 한다.

performed when new process is created

Medium-term Scheduling

swapping 할 때, 언제 얼만큼 누구랑 바꿀지를 결정하는 스케쥴링이다.

swapping 과 관련이 있다.
시스템 안에 메모리가 한정적이기 때문에 어느 순간 Ready Queue 가 비고, Ready Queue 에 있었던 프로세스들이 전부 Blocked 상태가 되면 Blocked 상태의 메모리에 있는 프로세스와 하드디스크의 Swapping Area 에 있는 Ready/Suspend 상태의 프로세스들을 서로 자리를 바꾼다.

Short-term Scheduling

CPU 에서 실행할 프로세스를 선택하는 스케쥴링

Ready 상태에 있는 프로세스가 CPU 를 잡을 때, Ready Queue 에는 굉장히 많은 프로세스들이 존재한다.
CPU 안에 굉장히 많은 프로세스 존재 → CPU 가 하나인 시스템이므로 프로세스를 한번에 하나만 실행 → 누구를 선택할지? 하나를 고름

Ready → Running

which ready process to execute next

Block 상태 메모리

Types of Scheduling(2)

화살표 방향이 잘못되었다. 맨 밑 Blocked → Blocked/Suspend 방향으로 내려보내야 한다.

혹은 Ready/Suspend 상태 (Swapping Area) → Ready (Memory)

Types of Scheduling(3)

Short-Term Scheduling Criteria

Short-Term Scheduling 은 시스템 성능에 가장 큰 영향이 있다.

어떻게 해야 Scheduling 을 잘하는 건지 기준이 필요하다.

User-Oriented

• User System 의 관점에서 중요
• System 의 관점에서 상관 X

Response Time ↓

User 입장에서 Response Time은 짧은 게 좋다.

Elapsed time between the submission of a request until there is output.

Turnaround Time ↓

프로그램이 실행하고 끝날때까지 걸리는 시간

User 입장에서 Turnaround Time 은 짧은 게 좋다.

Elapsed time between the submission of a process and its completion

System-Oriented

• System 의 관점에서 중요
• 그나마 수치적으로 얘기가 가능하다.

utilization

System 입장에서는 Processor 를 얼마나 내가 효율적으로 사용하고 있는지가 중요하다.

Effective and efficient utilization of the processor

Throughput

단위 시간 동안 얼만큼 많은 작업을 끝낼 수 있는가?

Number of processes completed per unit of time

양적 성능 O , 질적 성능 → 예측 가능성, fairness(공정성)

예측 가능성

어떤 프로세스가 실행을 시작했을 때 언제쯤 끝날 지 예측을 할 수 있어야 한다.

우선 순위를 중요하게 생각하는 시스템에서는 예측 가능성이 떨어져서 최악의 경우에는 Starvation 이 발생하여 영영 실행되지 않을 수 있다.

fairness(공정성)

기회가 얼만큼 공정하게 주어지는가?

Performance-related

• Quantitative
• Measurable such as response time and throughput

Not performance related

• Qualitative
• Predictability and fairness

Priorities

우선순위를 결정해야한다.

시스템 스케쥴러는 어떤걸 기준으로 우선순위를 정할지 정해야한다.
→ fairness? 성능?

프로세스들을 우선순위가 높은 순서대로 줄을 쭉 세운다.

우선 순위가 동일할 경우 큐에 같이 넣는다.

Ready Queue 가 한 개있는 것 X → 여러개의 Multiple Ready Queue 로 나뉘어져 존재한다.

우선순위 Ready Queue 의 개수

• Windows → 32 개 (32개의 우선순위로 프로세스를 구분한다.)
• 다른 시스템 → 128 개 (128개의 우선순위로 프로세스를 구분한다.)

⇒ 우선순위에 따른 프로세스의 실행 순서가 시스템 성능에 어마어마하게 영향을 끼친다.

ex) 우선순위 Queue 가 300개일 때, 
300번째 Queue 에 들어있는 프로세스가 CPU 를 잡으려면,
위의 299개의 Queue 가 다 비워져야 300번째 프로세스를 실행할 수 있다. 
⇒ 시스템 마다 fairness 를 같이 고려

우선순위가 낮을 수록 Starvation 이 발생할 수 있다.

Starvation 발생 하지 않게 하기 위해 → 우선순위 고려 및 정의해야 한다.

• Scheduler will always choose a process of higher priority over one of lower priority
• Have multiple ready queues to represent each level of priority
• Lower-priority may suffer starvation
  allow a process to change its priority based on its age or execution history

Scheduing Algorithms

1. First-Come-First-Served
2. Round-Robin
3. Shortest Process Next
4. Shortest Remaining Time
5. Highest Response Ratio Next

First-Come-First-Served 과 Round-Robin 은 Fariness 가 높고 성능이 떨어진다.

Shortest Process Next 과 Shortest Remaining Time 은 성능은 높지만 Fairness 를 전혀 고려하지 않는다. ⇒ Starvation 발생 가능성이 있다.

Highest Response Ratio Next 은 성능과 Fairness 를 모두 고려한다.

An Example

• 0시 → 2시 → 4시 → 6시 → 8시 순으로 프로세스 도착
• Service Time = 실행시간

Response Time

Response Time = Waiting Time + Executing Time 의 평균

First-Come-First-Served (FCFS)

시스템 큐에 프로세스들이 도착한 순서대로 실행을 시킨다.

우선순위

우선순위 : 큐에 도착한 순서
↳ 프로세스가 Queue 에 먼저 도착할 수록 우선순위가 높아진다.

Non-Preemtion

한 번 실행을 시작하면 끝까지(service time 까지) 실행을 시킨다. 중간에 프로세스를 중단시키지 않는다. (중간에 CPU 를 빼앗지 않는다.)

A → B → C → D → E 순차적로 실행

• The oldest process in “ready queue” is selected
• Non-Preemption
• A short process may have to wait a very long time before it can execute

FCFS Response Time

Response Time = Waiting Time + Executing Time 의 평균

• B: 1시간 기다림
• C: 4시 도착, 5시간 기다림
• D: 6시 도착, 7시간 기다림
• E: 8시 도착, 10시간 기다림

B: 2시에 도착했지만 3시에 시작하므로 1시간 기다림

FCFS는 성능이 좋지 않다,,

몇시간을 기다린 수는 중요하지 않고, 실행시간 짧은게 뒤로 밀려서 오래 기다리는 상황이 발생할 수 있다. 이때 기다리는 시간이 길다는 생각을 하게 된다.
일찍 끝날줄 알았는데 오래걸리네..?

Round-Robin

Time-out 사용하는 방식이다. 프로세스가 일단 실행을 시작하면 타이머를 세팅하고 타임 아웃이 되면 프로세스를 Ready Queue 로 돌려보내고 다음 프로세스를 실행시킨다.

Queue 에 들어 있는 프로세스 입장에서 봤을 때, A → B → C → D → E → A → B → C → D → E 순으로 실행되어서 이름이 Round-Robin 방식이다.

Preemtion

Clock 에 기반한 Preemption 방식을 사용한다. 실행을 하다가 TIMEOUT 되며 CPU 를 뺏긴다.

우선순위

큐에 들어온 순서대로 차근차근 실행된다.

q = Time quanterm 한번 CPU 를 잡으면 얼만큼 작업을 할지를 나타낸다.

Time quanterm 에 따라 Response Time 이 바뀐다. ⇒ 성능이 달라진다.

• q = 1 → 프로세스마다 1시간씩 작업한다.
  q 를 2나 3, 4로 잡으면 실행되는 순서와 Response Time 이 바뀐다.
• q = 2 → Response Time 이 줄어든다. ⇒ 성능이 달라질 수 있다. ⇒ 적절한 TIMEOUT 시간을 잡아야 한다.

Time Slicing

Time Slicing 기법이라고도 불린다.

• Clock interrupt is generated at periodic intervals
• When an interrupt occurs, the currently running
  process is placed in the ready queue
• Known as time slicing

1. Queue 를 같이 그려야 한다.
2. 1시에 TIMEOUT 이 되어도 큐에 A 밖에 없기 때문에 중단되지 않는다.
3. 여러개의 프로세스가 동시에 Queue 에 들어오는 일은 없다.
   ↳ 인터럽트마다 우선순위가 존재한다. OS 가 순서대로 처리할 것이다.
   여기서는 외부에서 들어오는 프로세스가 Queue 의 앞쪽에 서 있다.

작업 순서: A → B → C → D → E 순서 X 언제 CPU 를 잡고 언제 Queue 에 들어가는지 등의 순서를 따져봐야 한다.

Round-Robin 의 Response Time

Waiting Time 은 중간중간 비어 있는 공간을 다 따져봐야 한다.

• A: 1시간 기다림
• B: 10시간 기다림

→ FCFS 보다 RR 의 Response Time 이 더 길어졌다.

시스템 입장에서 똑같은 시간만큼 일하면 좋은 것 같지만, User 입장에서는 CPU 가 얼만큼 일하는지는 중요하지 않다. → 입장에 따라 성능이 달라진다.

CPU 입장에서는 한번도 쉬지 않고 일함. CPU 가 얼만큼 일하는지 중요 X, 각각의 프로세스가 실행을 시작해서 언제 끝났는지(Response Time)가 중요하다.
↳ Response Time 은 작업 순서에 따라 달라진다.

FCFS 와 RR

공통점

우선순위
↳ FCFS 와 RR 모두 먼저 도착한 애가 우선순위를 갖는다.

차이점

Preemption Vs. Non-Preemption

Shortest Process Next (SPN)

우선순위

실행시간이 짧은 프로세스가 우선순위가 높아 먼저 실행한다.

Non-Preemption

⇒ 실행시간이 긴 프로세스가 큐에 이 프로세스밖에 없으면 먼저 실행한다. 하지만, 멈추지 않는다.

Queue: (A) A → Queue:(B) B → Queue: (CDE) E → C → D

E 때문에 C 와 D 는 우선순위에서 밀려 Waiting Time 이 각각 2시간 해서 총 4시간이 증가하게 되지만, E가 실행시간이 짧고 E의 Waiting Time 이 9시간이 줄어들어서 전체적인 Waiting Time 은 줄어들게 된다.

Process with shortest expected processing time is selected next

문제점 2개 존재

1. 실행시간 긴데 뒤로 밀려 실행시간이 짧은게 계속 오면 Starvation 이 발생할 수 있다. ⇒ Fairness X , 예측 가능성이 떨어진다.
   앞에 두 알고리즘은 굉장히 fair 하고 예측 가능성도 높았다.
2. 두 번째 문제: 앞으로의 프로세스의 실행시간을 알 수 있는 방법이 없다.
   ⇒ 실행 안해보고 실행시간을 예측하기 힘들다.

• Predictability of longer processes is reduced
• If estimated time for process not correct, the
  operating system may abort it
• Possibility of starvation for longer processes

Shortest Process Next 의 Response Time

다른 사람의 실행시간이 내 waiting time 이 된다.

SPN 은 Response time 이 매우 줄어든다.

순서를 바꾼게 왜 Response time 을 줄어들게 할까?
→ Waiting Time + 실행시간 에서 실행시간 은 고정 되어 있기 때문에, Waiting Time 을 줄여야 Response time 이 줄어든다.

SNP의 실행시간을 정확히 예측하는 두가지 방법

1. CALCULATING PROGRAM ‘BURST’

대부분의 프로세스들은 실행을 하는데 실행을 시작해서 Ready Queue 에 있다가 CPU 를 잡아서 실행하고 끝인 프로그램은 별로 없고, 대부분의 프로그램들은 입출력이 있기 때문에 Ready Queue 에 있다가 CPU 를 잡아서 실행하고 그다음에 I/O 작업 때문에 Block 이 된다. 다시 Ready Queue 에 있다가 실행하고 또 I/O 작업 때문에 Block 이 된다.

프로세스의 실행 순서: 실행 → block → 실행 → block → ...

Burst Time

실행 시간

프로세스는 반복해서 Ready Queue 에 들어온다.

프로세스가 Ready Queue에 들어왔을 때 다음 실행시간은 어떻게 될지 모르지만, 옛날 Burst time 은 알기 때문에 이를 이용해 다음 걸 예측할 수 있다. → 산술 평균 이용

1. Ti = processor execution time for the i-th instance of this process
   i 번째 Time 의 작업 시간
2. Sn+1 = predicted value for the i-th instance
   예측값
3. S1 = predicted value for first instance; not calculated
   첫 번째 기본 값 필요 (초기값)
4. n = Ready Queue 의 개수

⇒ 전체 Ti 를 더해서 n 으로 나눈것이 다음의 예측 값이다.

( 1 + 2 + 3 ) / 3 = 2 ⇒ 네번째 실행시간은 2일 것

2. Exponential Averaging

가중 평균

A common technique for predicting a future value on the basis of a time series of past values is exponential averaging

1. Tn = Ti 는 i 번째 실제로 작업한 시간
2. a = 0~1 사이의 수, 0.5면 Ti 와 Sn 값의 평균이고 아니면 가중치가 붙는 것
3. Sn = 매번 예측한 값으로 n+1 번째 실행전 예측한 값

문제에 표가 주어지면 S 값을 구할 줄 알아야 한다.

https://github.com/ssunbear/database/

1. 프로젝트 개요

프로젝트 주제 및 설명

"StayHub: Real-time Accommodation Search and Sharing Platform"

국내 숙박업소를 검색해서 실시간으로 숙박업소에 대한 가격 및 여러 정보를 얻고, 숙박업소에 대한 정보를 사용자들이 직접 등록하여 공유할 수 있는 서비스

프로젝트 동기

최근 숙박업소의 예약 웹사이트가 증가하는 추세에도 불구하고, 각 사이트에서 제공되는 할인율에 따라 소비자는 같은 숙박업소임에도 더 비싼 가격으로 예약을 하는 상황들이 많아지고 있습니다. 특히 예약사이트의 종류도 다양하고, 객실마다 제시되는 가격도 다양하기 때문에 이에 대한 통합적인 정보를 제공하고자 해당 주제로 프로젝트를 진행하고자 합니다.

프로젝트 언어 및 환경

프로젝트 언어는 Python이고 DB는 postgresql에서 제공하는 엔진을 사용했습니다.

2. 프로젝트 목적, 기능

프로젝트 목적

각 웹사이트에서 제공하는 할인된 가격을 종합하여 보다 합리적인 가격으로 소비자가 이용할 수 있게 만드는 것 입니다. 숙박업소 DB를 구축하고, 검색 기능, 리뷰 및 선호도(별점) 등록하는 기능, 리뷰에 대한 댓글을 남길 수 있는 기능 등을 통해 사용자가 보다 다양한 선택지의 숙박업소를 비교하여 예약 할 수 있는 것을 목적으로 삼았습니다.

프로젝트 기능

‘StayHub’는 7가지의 핵심 기능을 담고 있습니다.

1. 숙박업소의 데이터 셋을 이용한 검색기능
2. 숙박업소의 정보를 등록 및 삭제하는 기능
3. 등록된 모든 숙박업소를 조회하는 기능
4. 숙박업소에 대한 리뷰와 선호도를 등록하는기능
5. 리뷰에 대한 답글을 남길 수 있는기능
6. 사용자가 원하는 숙박업소를 즐겨찾기에 추가하는 기능
7. 마이 페이지를 통해 자신이 즐겨찾기에 추가된 숙소 조회 및 삭제, 등록한 리뷰 조회하는 기능

3. 데이터베이스 설계

개체, 속성 추출 결과

관계 추출 결과

E-R 다이어그램

릴레이션 스키마

물리 ERD

테이블 명세서

4. 데이터 수집

데이터 수집 및 확보 방안

 아고다, 호텔스컴바인, 익스피디아 등 다양한 웹사이트의 통합 숙박업소 데이터베이스를 일일히 얻기 보다는 네이버 호텔(https://hotels.naver.com/) 페이지의 데이터베이스를 크롤링하여 데이터를 수집하였습니다.

 전국의 숙박업소의 데이터를 모두 수집하기는 어렵기에 주요도시 15개(서울, 제주, 부산, 인천, 강릉, 속초, 여수, 경주, 대구, 대전, 울산, 평창, 전주, 군산, 양양)의 숙박업소 데이터만 추출하여 데이터를 수집하였습니다

데이터 충분성 판단

선정한 15개 도시에서 인기순으로 100개의 숙소를 선정하여 DB를 구성하였습니다. 해당 지역의 숙소 순위가 100위가 넘는 숙박업소를 예약하지는 않는 것으로 생각하는 것이 합리적이기에 지역마다 100개의 숙박업소를 선정하였습니다. 이런 점에서 데이터의 양은 충분하다고 판단됩니다.

 크롤링으로 데이터를 수집하기에 숙박업소의 객실의 최소가격만 얻을 수 있다는 점과 객실 사이즈에 따른 가격을 수집하지 못한 것이 아쉽습니다.

5. 프로젝트 평가

프로젝트 기대효과

 ‘StayHub’를 통해 여러 웹사이트에서 제공하는 최저가 가격을 종합하여 합리적인 가격으로 사용자가 숙박업소를 예약할 수 있을 것입니다. 다음으로 리뷰 기능과 평점을 참조하여 사용자가 숙박업소를 예약하는데 도움이 될 것입니다. 

프로젝트 마무리

국내 주요 15개 도시의 통합 숙박업소 DB를 만들고  ‘StayHub’를 만들면서 아쉬운 점으로는 대용량의 데이터를 처음 다루다 보니 미숙한 점도 많았고, 기능 구현에 아쉬운 점도 많았습니다. 다만, 이 프로젝트를 발전시킨다면 15개의 도시를 넘어 전국의 통합 DB와 해외의 숙박업소 DB를 만들수 있다는 점에서 확장 가능성이 큰 좋은 프로젝트라고 생각합니다.  

6. 쿼리문/쿼리 결과물 예시 및 코드

CREATE TABLE member
(
	member_id varchar(20) PRIMARY KEY,
	member_pw varchar(45) NOT NULL,
	member_name varchar(45) NOT NULL,
	member_age int NOT NULL,
	member_phonenumber varchar(100) NOT NULL
);

COMMIT;

CREATE TABLE favorite
(
	favorite_num int PRIMARY KEY,
	member_id varchar(20) NOT NULL,
	accomodation_id varchar(45) NOT NULL,
	FOREIGN KEY (member_id) REFERENCES member(member_id),
	FOREIGN KEY (accomodation_id) REFERENCES accommodation(accommodation_id)
);

COMMIT;

CREATE TABLE accommodation
(
	accomodation_id varchar(45) PRIMARY KEY,
	accomodation_name varchar(45) NOT NULL,
	accomodation_address varchar(45) NOT NULL,
	accomodation_rate varchar(45) DEFAULT '0',
	accomodation_lowprice varchar(45) NOT NULL
);

COMMIT;

 
CREATE TABLE review
(
	review_num int PRIMARY KEY,
	review_title varchar(45) NOT NULL,
	review_detail varchar(400) NOT NULL,
	member_id varchar(20) NOT NULL,
	accomodation_id varchar(50) NOT NULL,
	accomodation_rate varchar(45) NOT NULL,
	FOREIGN KEY (member_id) REFERENCES member(member_id) ,
	FOREIGN KEY (accomodation_id) REFERENCES accommodation(accommodation_id)
);

COMMIT;

CREATE TABLE comment 
(
	comment_num int PRIMARY KEY,
	member_id varchar(20) NOT NULL,
	review_num int NOT NULL,
	comment_detail varchar(200) NOT NULL,
	FOREIGN KEY (member_id) REFERENCES member(member_id) ,
	FOREIGN KEY (review_num) REFERENCES review(review_num) 
);

COMMIT;

쿼리문 결과 - DB/Python 연동 

개인정보 입력

메뉴 출력 결과

7. 코드 및 파일 첨부 링크

https://github.com/ssunbear/database/

Python과 Postgresql과의 통신은 Psycopg2를 통해 이뤄지게 된다.

연동하면서 사용하는 방식

1) 기존에 Dbeaver 등을 통해 데이터베이스의 구조를 대략적으로 파악

2) Psycopg2를 통해 데이터베이스와 파이썬을 연결

3) 커서를 생성하고, 이를 통해 쿼리를 보냄

4) 결과를 받아서 활용

모듈에 대한 자세한 설명은 홈페이지를 통해 확인할 수 있다.

https://www.psycopg.org/docs/index.html

1. INSTALL

pip install psycopg2 를 통해서 패키지를 설치

2. CONNECTION AND CURSOR

connect 함수를 통해서 데이터베이스에 연결한 뒤(커넥션 생성), 커넥션에서 커서를 생성

(하나의 인자로 전달하여 연결하는 방식도 있음)

3. SELECT

execute를 통해 쿼리문을 수행하고, 결과는 fetchone, fetchmany, fetchall 을 통해 받는다

cur.execute('SELECT * FROM actor;')

fetchone, fetchmany, fetchall 중 어떤 것을 사용할 것인가?

→ 시스템 부하를 고려하면서 사용하는 것이 좋다

execute에서 수행한 query의 결과가 모두 return되기 전까지 커서는 뒤로 이동하면서 결과를 return 한다는 점에 유의할 것

✓ fetchone: 쿼리 결과물을 하나씩 받으며, 실행할 때 마다 다음 결과를 return 한다.

✓ fetchall: 쿼리 결과물을 모두 return 한다.

(결과를 모두 return 하기 때문에 이 이후에 fetch를 수행하게 되면 empty 결과가 return 됨)

일반적인 SELECT 문과 마찬가지로 WHERE를 통해 조건을 거는 것도 가능하다.

만약 쿼리문에 문제가 있다면 postgresql과 같이 에러메시지를 출력한다

(이렇게 에러가 발생했을 때는 rollback을 수행해줘야 함)

conn.rollback()

4. CREATE

execute를 통해 쿼리문을 수행한다

cur.execute('CREATE TABLE tttt (col1 SERIAL NOT NULL, col2 INT, col3 INT);')

commit하여 테이블을 생성한다(commit 하지 않으면 테이블 생성이 반영되지 않음).

conn.commit()

CREATE와 관련된 다른 기능들도 마찬가지로 수행할 수 있다

cur.execute('CREATE TABLE tttt2 (LIKE actor);')
conn.commit()

5. INSERT/DELETE/UPDATE

execute를 통해 INSERT/DELETE/UPDATE 쿼리문을 수행한다.

6. USE PLACEHOLDER

복잡한 쿼리문을 사용할 때는 FORMAT을 사용하는 것이 편할 수 있다.