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

우선순위: 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을 사용하는 것이 편할 수 있다.

Translation Lookaside Buffer

Relocation 을 위해서 Page Table 을 이용한다. Page Table 에는 두가지 종류가 있다.

• hierarchical page table
• inverted page table

hierarchical page table 을 사용할 때는 Page Table 자체가 크기 때문에 이게 2, 3, 4, ... 단계 page table 이 될 수 있다.

2단계 페이지 테이블의 경우
데이터 읽기 → Root Page Table → 2nd Page Table → 정확한 Physical Address 주소 획득 → memory
⇒ 데이터를 읽을 때, memory 에 3번 access

ex) 보통 프로그램을 실행할 때 
코드 → 데이터 → 코드 → 데이터 → ... 을 반복하는데 
각각 3번씩 접근하므로 프로그램의 속도가 3배가 느려진다.

3단계 페이지 테이블까지 존재하는 경우에는 4번 메모리에 접근해야 한다.

⇒ TLB (Translation Lookaside Buffer) : Cache 이용

페이지 크기 2^10, 2^12 → 너무 큰 숫자
⇒ 만약, 명령 1000개라고 치면, 한 페이지 안에 명령 1000개가 들어있다는 뜻인데 이건 매우 많은 양이다.

처음에 코드를 읽어올 때 이 코드가 몇번 프레임에 있는지 페이지 테이블을 통해 찾고, Locality 덕분에 그 뒤 같은 테이블을 계속 읽는다.
어떤 페이지를 한 번 읽었을 때 몇 번 프레임에 있었다는 정보를 TLB에다 최근에 내가 읽은 페이지에 대한 정보를 적어 놓게 되면 다시 페이지 테이블을 찾으러 갈 필요가 없다.
⇒ Cache 역할을 한다.

TLB 에서 access 하면 된다. 최근에 내가 access 한 페이지의 정보 O
⇒ 속도 저하 방지 가능

Each virtual memory reference can cause two physical memory accesses

• one to fetch the page table
• one to fetch the data

To overcome this problem a high-speed cache is set up for page table entries

• called the TLB - Translation Lookaside Buffer
• Contains page table entries that have been most recently
  used
• Functions same way as a memory cache

주소를 변환하는 과정

1. 페이지 번호를 TLB 에 주고 프레임 번호를 얻어온다.
2. 만약 데이터가 있다면, 이걸 TLB hit 라고 한다.
   = TLB 에 내가 원하는 페이지에 대한 정보가 있는 경우
3. 만약 데이터가 없다면, TLB miss 라고 한다.
   = TLB 에 내가 원하는 페이지에 대한 정보가 없는 경우
   → 페이지 테이블로 접근
   ↳ 페이지 테이블을 2단계, 3단계 거쳐서 내가 원하는 프레임 정보를 얻어내면 이걸 다시 TLB 에 쓴다 .
   → 그 후 , 주소 변환
4. 페이지가 메모리에 없는 경우 (= 페이지 테이블에 페이지가 없는 경우) 는 Page fault 라고 한다.
   → 하드디스크에 가서 페이지를 메모리에 올려 놓는다.
   당연히 올려 놓는 과정에서 페이지 테이블을 업데이트 하고, TLB 도 업데이트 한다.

이렇게 한 번 작업하고 나면, 나중에 TLB에서 내가 원하는 정보를 얻을 수 있기 때문에 주소 변환이 즉시 즉시 이루어지게 된다.

왼편은 일반적인 메모리에 TLB 가 저장되어 있는 것
어떤 프로세스의 연속된 정보가 들어 있는 것이 아니라 최근 정보가 들어 있는 것이기 때문에 sequential 하게 5번 페이지가 37 번 프레임에 있다 하면, 5번 페이지를 꼭 찾아야 한다.

른편은 페이지 번호가 원소의 일부로 사용되는 association 타입을 이용한다. 하나의 엔트리 안에 페이지 번호와 프레임 번호가 들어 있어있다.
⇒ 한번에 내가 원하는 프레임 번호를 찾아낼 수 있다.

associative 메모리를 사용하기 때문에 TLB 는 한번에 access 하면 프레임 번호가 딱 튀어 나온다.

거의 모든 시스템이 Virtual Memory 와 TLB 를 사용한다.

하지만, Page size 에는 의견이 다양하다.

Page Size (페이지 크기는 작아서는 안된다!)

• Smaller page size, more pages required per process
• More pages per process means larger page tables
• Larger page tables means large portion of page tables in virtual memory

페이지의 크기가 작다면, 같은 크기의 프로그램 내에 더 많은 페이지 수가 많아지게 되므로 페이지 테이블의 Entry 개수가 많아지게 된다.
⇒ Page Table 수가 증가한다.
↳ 메모리에 페이지 테이블이 없을 확률이 높아진다.
⇒ 시간 소요가 증가한다. ⇒ 페이지 크기는 작아서는 안된다!

Page Size2 (페이지 크기는 커서는 안된다!)

• Small page size, large number of pages will be found in main memory
• As time goes on during execution, the pages in memory will all contain portions of the process near recent references. Page faults low.
• Increased page size causes pages to contain locations further from any recent reference. Page faults rise.

Virtual Memory System 에서는 여러 프로그램들이 메모리에 들어와 있어야 한다. 대부분의 경우 프로세스 하나하나 마다 일정한 크기의 공간을 나누어 준다.

만약 내가 할당받은 공간이 이만할 때, 우연히 내 페이지 크기가 딱 그만큼이라서 이 공간에 딱 한페이지만 들어갈 수 있다고 하자.
↳ 즉, 페이지 크기가 상당히 큰 것이다.

프로그램을 실행하려고 하면, 코드와 데이터가 있어야 한다. 코드 한줄, 데이터 한줄 계속 실행하는데, 각각의 코드와 데이터가 들어 있는 페이지는 하드디스크로 계속 Swap-In, Swap-Out 하게 된다.

그럼 계속 코드가 들어 있는 페이지와 코드가 들어 있는 페이지가 왔다갔다 실행되며 Thrasing 이 발생할 것이다.

만약 페이지의 크기가 작아서 내 프로그램이 더 작은 단위로 나뉘어져 있다면, 코드 한쪽 데이터 한쪽 스택 한쪽, ... 필요한 애들을 한쪽씩 갖다 놓고 작업을 할 수 있기 때문에 Page fault 가 일어나지 않는다.

Thrasing이 발생할 것이다

data ↔ code 왔다갔다 많이할 것

페이지를 작게하면 필요한 애들을 적게 적게 갖다 놔서 Page Fault 가 적어질 것이다.
↔ 페이지 크기를 크게 하면 Page Fault 가 많아질 것이다.

⇒ 결론적으로는 페이지는 너무 커도 안되고, 너무 작아도 안된다.

Segmentation

Segmentation을 이용한 Virtual momory system 은 굉장히 비효율적이기 때문에 사용하지 않는다.

• May be unequal, dynamic size
• Lends itself to sharing data among processes
• Lends itself to protection

sharing 하는 단위가 분명하다.

의미 있는 단위로 나뉠 것이다. → 한 segment 안에 data 또는 code 만 존재할 것이다.

Protect 하는 단위가 분명하다.

• PCB → OS 가 사용
• Code → User 가 사용

Segment Table Entries

Segment 을 이용한 시스템에서는 Dynamic Partitioning 을 사용하기 때문에 Segment 의 정확한 시작 주소를 알아야 한다.

길이가 제각각이기 때문에 Offset > Length 인지 계속 확인해 주어야 한다.

Segment Tables

• Each entry contains the length of the segment
• A bit is needed to determine if segment is already in
  main memory
• Another bit is needed to determine if the segment has been modified since it was loaded in main memory

Address Translation in Segmentation

주소변환과정

Combined Paging and Segmentation

두 시스템의 장점을 결합하여 사용

• Paging System → External Fragmentation X
• Segmenation System → Protection, Sharing 👍

1. 페이지 크기로 나누기 전에 Segmentation 4가지 영역으로 먼저 나눔
2. 동일한 크기의 page frame 크기로 나눔 ⇒ page 크기로 나눔
   ⇒ 한 페이지 안에 code 와 data, pcb 등등 서로 섞인 페이지가 존재하지 않게 된다.
3. 각 Segment 로 나눈 단위마다 Internal Fragmentation 존재 가능 (공간 낭비 조금 존재, but Protection 과 Sharing 이 더 중요)