# 即時系統報告(50min)

---

## 可能的報告主題

1. 影像辨識、聲音辨識
2. 比起以前，NN如何增進辨識效能或是減少server負載
3. 有什麼新應用是在系統效能提高、延遲降低後出現的
4. 網際網路、www、http、5G
5. 電梯排程
6. 硬碟排程 ✓

---
## 報告大綱

### Disk Scheduling Algorithms：(與電梯排程方法重疊)

1. FCFS
2. SSTF
3. SCAN(C-SCAN)
4. LOOK(C-LOOK)
5. Sinewave Algorithm
6. 磁碟排程演算法選擇(適用情境)？

### Linux I/O Scheduler

1. noop
2. deadline
3. Anticipatory
4. CFQ
5. BFQ
6. 適用情境？

#### Noop
The NOOP scheduler inserts all incoming I/O requests into a simple FIFO queue and implements request merging.
This scheduler is useful when it has been determined that the host should not attempt to re-order requests based on the sector numbers

#### Deadline
written in 2002 by Jens Axboe.
The main goal of the Deadline scheduler is to guarantee a start service time for a request. It does so by imposing a deadline on all I/O operations to prevent starvation of requests.

有兩個 queue ，分別為 deadline queue 與 sorted queue ，分別代表每個 requests 的 deadline 排序，以及 sector 的排序。當要處理下一個 request 時，會先檢查 deadline queue 的第一個是不是超過 deadline ，則直接處理他，否則就是從 sorted queue 處理一個 request 。在兩種情況中，處理 request 時都會順便從 sorted queue 找後續的幾個 request 形成一個 batch 一起處理。

By default, read requests have an expiration time of 500 ms, write requests expire in 5 seconds.

#### Anticipatory
Base on deadline
"Deceptive idleness" 現象是指一個process發出read request後，他不會立刻進行下一次讀取，因為他可能在進行一些資料處理，這時候的io scheduler就可能會改成進行其他process的io request，這時候原始process又發出一次read request，這個過程就是"Deceptive idleness"，並且會造成seeking 過於頻繁。

因此Anticipatory會在每個read request後等待一小段時間，這段時間只能接收原本process的read request，並且對於寫入會等待寫入request變多後一次進行寫入。

#### CFQ
CFQ maintains the per process queue for the processes which request I/O
operation(synchronous requests). In case of asynchronous requests, all the
requests from all the processes are batched together according to their
process's I/O priority.
Higher priority process gets bigger time slice and lower priority process gets smaller time
slice.

#### BFQ
Base on CFQ
In its default configuration, BFQ privileges latency over
throughput.
Each process doing I/O on a device is associated with a weight and a `(bfq_)queue`.
每個 process queue 在被執行到的時候都有一個budget，並且在執行request時會根據request size不斷減少budget。
當 process queue 空了、budget用完了、process 執行太多random io時，就會切換到下一個queue執行
BFQ可能會在每個request中idle，給process機會讓他做下一次io，而且也可以讓傳統硬碟的效能增加，不過在process大量產生的時候(例如開機階段)，則會自動停止idle
如果多個process競爭io，則會保證每個process被分配一樣的資源。

#### 比較
https://algo.ing.unimo.it/people/paolo/disk_sched/comparison.php

:+1: [BFQ 好處](https://www.hecticgeek.com/bfq-loads-programs-extremely-fast-under-heavy-disk-io-workloads-ubuntu/)

### Design method

設計一種NN scheduler，並且可以自動學習程式行為，並且針對不同行為來決定要使用 low latency 或是 high throughput 模式，藉此可以避免必須手動設定 BFQ configuration

首先準備數種應用(包含資料庫、 web server 、大數據訓練等等)，並且比較在單一應用以及多種應用下，預設的 scheduler 與我們的 scheduler 的效能如何(分別從 latency 與 throughput 比較)

---

## 報告資料：

### 網頁資料：

電梯排程課程

http://www.columbia.edu/~cs2035/courses/ieor4405.S13/p14.pdf
http://wayne.cif.takming.edu.tw/os/os_15.pdf

排程演算法(參考「什麼是排程演算法」那段有電梯舉例，前6個演算法講「電梯」舉例時，可以照這樣講)
https://www.mdeditor.tw/pl/2Szt/zh-tw

這是現在電梯的排程方法(一直上樓直到沒人要更上去，一直下樓直到沒人要更下去)
https://en.wikipedia.org/wiki/LOOK_algorithm

Introduction是從這裡複製貼上的
https://en.wikipedia.org/wiki/I/O_scheduling

OS架構圖
https://upload.wikimedia.org/wikipedia/commons/f/fb/The_Linux_Storage_Stack_Diagram.svg

https://en.wikipedia.org/wiki/Elevator_algorithm

http://blog.pulipuli.info/2006/06/942_15.html

磁碟排程筆記
https://hackmd.io/@Pl-eQT9CQaS0jhExKqL8_w/HJgYL_u7G?type=view

https://video.openedu.tw/MobileMOOCs/2015/b02/%E8%AC%9B%E7%BE%A9/12.9%E7%A3%81%E7%A2%9F%E5%AD%98%E5%8F%96.pdf

http://blog.pulipuli.info/2006/06/942_15.html

wiki介紹
https://en.wikipedia.org/wiki/Noop_scheduler

https://en.wikipedia.org/wiki/Anticipatory_scheduling

https://en.wikipedia.org/wiki/Deadline_scheduler

https://en.wikipedia.org/wiki/Native_Command_Queuing

BFQ
https://nan01ab.github.io/2018/09/BFQ-IO-Scheduler-of-Linux.html

BFQ commit log
https://github.com/torvalds/linux/commit/aee69d78dec0ffdf82e35d57c626e80dddc314d5#diff-d8f3703541125964cf981b43bf83ac389beb3bd65c4e8e7246792a70bc93adee

Wf2Q+
http://www.cs.cmu.edu/~cheeko/wf2q+/

### YT影片(片長)：

介紹電梯排程的方法們：
[Elevator System Design | Object-Oriented System Design Interview Question (42:49)
](https://www.youtube.com/watch?v=siqiJAJWUVg)
用例子解釋每個方法：
[6.06 - Disk Arm Scheduling Algorithms (11:27)
](https://www.youtube.com/watch?v=2nESY2GG0LA)
每個方法分一個影片講：
[SCAN disk scheduling algorithm | Example | OS | Lec-74 | Bhanu Priya (11:14)
](https://www.youtube.com/watch?v=uF8EjXtmRE4)

這個動畫豪可愛噢QVQ：
[The Science Behind Elevators (4:30)
](https://www.youtube.com/watch?v=xOayymoIl8U)

---
## Reference

### 聲音跟影像一起辨識(忽略)
[~~Active Object Discovery and Localization using Sound-Induced Attention~~
](https://ieeexplore.ieee.org/document/9109674/)

[~~YOLOv4~~
](https://research.sinica.edu.tw/yolov4-hong-yuan-mark-liao/)

### 硬碟/電梯排程
[Disk scheduling sinewave algorithm for minimizing the average jump rate of a hard drive over its lifetime
](https://ieeexplore.ieee.org/document/8089118)

[I/O issues in a multimedia system
](https://ieeexplore.ieee.org/document/268888)

[Modification over C-Look Disk scheduling
](https://ieeexplore.ieee.org/document/7100225)

->[這裡](https://www.geeksforgeeks.org/fcfs-disk-scheduling-algorithms/)

### 這也許有搞頭？(結果並沒有@@)(忽略)

[~~Self-Learning Disk Scheduling~~
](https://ieeexplore.ieee.org/document/4547426)

[~~Research on Traffic Mode of Elevator Applied Fuzzy C-Mean Clustering Algorithm Based on PSO~~
](https://ieeexplore.ieee.org/document/5203501)

[~~Modeling and optimizing of elevator group control system with destination floor guidance~~
](https://ieeexplore.ieee.org/document/4675586/)

### Linux I/O Schedulers
[IOSchedulers](https://wiki.ubuntu.com/Kernel/Reference/IOSchedulers)

---
## 工作分配
zZZ

---
## 目前的研究(忽略)

yolov3
**i7-9700F+16GB**

| Model | 416x416 | 512x512 | 608x608 |
| ----------- | ------- | ------- | ------- |
| YOLOv3 | 219 ms | 320 ms | 429 ms |
| YOLOv3-tiny | 49 ms | 63 ms | 78 ms |
| YOLOv4 | 344 ms | 490 ms | 682 ms |
| YOLOv4-tiny | 51 ms | 66 ms | 83 ms |
| Unofficial-YOLOv4-tiny | 64 ms | 86 ms | 110 ms |
| YOLOX | 67 ms | 83 ms | 104 ms |


## 書面報告

### 大標

1. Abstract
2. Introduction
3. Related work
4. Design method
5. Conclusion and future work

### 標題

***A Novel I/O Scheduling Method With Reinforcement Learning Approach***

### Abstract
*In this research, we discussed history of disk scheduling and approaches of related scheduling algorithm, then purpose a novel I/O scheduling method based on reinforcement learning approach .*

***Keywords—I/O scheduling, reinforcement learning, disk(key words)***

### Introduction

- Input/output (I/O) scheduling is the method that computer operating systems use to decide in which order the block I/O operations will be submitted to storage volumes.The layer of I/O sceduler is between the file system and I/O device driver, and the job of I/O scheduler is sorting and merging requests submitted by operation system.
- I/O sheduling methods mainly focus on how to minimize time wasted by hard disk seeks、prioritize a certain processes' I/O requests、give a share of the disk bandwidth to each running process, and guarantee certain requests will be issued before a particular deadline.

### Related work

#### *Disk Scheduling Algorithms* (ㄗㄧ先寫這)
Various types of disk arm scheduling algorithms are available to decrease mean seek time.

1. **FCFS (First come first serve)**
The driver only accepts one request at a time and serves it in the order of the request, that is, the first come first served algorithm.
It's like: Whoever presses the elevator button first gets the elevator first.
**Advantages of FCFS:**
The concept is simple, and every request has a fair chance.
There is no indefinite delay (no starvation).
**Disadvantages of FCFS:**
The search time is not optimized.
Usually cannot provide optimized services.

2. **SSTF (Shortest seek time first)**
The magnetic column closest to the current head position is read first to reduce the search time.
SSTF schedule will complete the work that takes less time first.
It's like: Whoever is closest to the floor where the elevator is located will get on the elevator first.
**Advantages of SSTF:**
The efficiency is better than FCFS.
Reduce the average response time and waiting time.
Provide greater bandwidth.
Used in batch processing system.
**Disadvantages of SSTF:**
May cause starvation.
Because the response time varies greatly, it lacks predictability.

3. **SCAN (Elevator algorithm)**
The SCAN scheduling algorithm is to move the disk arm from one end of the disk to the other, and serve the I/O requirements of each cylinder in sequence during the movement.
When it reaches the edge of the disk, it reverses to move forward to the other end, accessing the disk back and forth.
Also known as the Elevator Algorithm. It is like: first serve the upward passengers, and then serve the downward passengers in the reverse direction after reaching the top floor.
**Advantages of SCAN:**
The efficiency is better than FCFS.
It's easy to understand and there is no hunger.
**Disadvantages of SCAN:**
Priority such as deadline cannot be taken into consideration.
It is unfair, because it will cause longer waiting time for magnetic cylinders that are near the opposite direction or have just been searched.
When the read-write head turns, because the end has just been served, the density of requests must be much lower than the other end, and it will cause the other end to wait for a long time.

4. **C-SCAN**
C-SCAN is a modification of SCAN scheduling algorithm.
Think of the magnetic column as a circular series. From the original two-way service of the disk head to and from the disk, the service is changed from the starting position of the disk head to the end of the disk. After the end, it will be pulled back to the beginning of the disk and the one-way service will be performed again to the end.
Also known as Circular-Elevator Algorithm.
**Advantages of C-SCAN:**
Compared with SCAN, it provides more uniform waiting time.
There are less moving costs if the disks are connected end to end.
**Disadvantages of C-SCAN:**
Priority such as deadline cannot be taken into consideration.
It is unfair, because it will cause longer waiting time for magnetic cylinders that are near the opposite direction or have just been searched.
There are more moving costs (if the disks are not connected to the end).
It is not suitable for the actual elevator situation because the size of Buffer (Waiting Queue), that is, passenger capacity should be considered.

5. **LOOK**
SCAN and C-SCAN scheduling algorithms, the head will move to both ends of the disk, so the longest moving length is the width of the disk.
The LOOK scheduling is similar to the SCAN scheduling. The difference is that the LOOK scheduling will only move to the outermost and innermost magnetic cylinders with read and write requirements.
It Looks ahead to see if there are any requests pending in the direction of head movement.
**Advantages of LOOK:**
There is no hunger.
Compared with SCAN, it reduces the moving cost and delay time.
**Disadvantages of LOOK:**
Same as the disadvantages of SCAN scheduling.

6. **C-LOOK**
C-LOOK is a modification of LOOK scheduling algorithm.
The concept is similar to C-SCAN scheduling.
**Advantages of LOOK:**
Compared with LOOK, it provides more uniform waiting time.
**Disadvantages of LOOK:**
Same as the disadvantages of C-SCAN scheduling.

7. **Sinewave Algorithm**
**Problem Statement：**
The read-write sequence produced by any algorithm is aimed to minimize the travel rate of the hard drive in use.
There is a trade-off between shorter seek lengths and consistency.
If the sequence produced is an erratic pattern, then the hard drive actuator stress increases.
This hardware stress is what needs to be minimized in order to prolong the lifespan of the device in consideration.
**The Proposed Algorithm：**
The first step is to sort the input request queue in the ascending order. Then find the index which divides the queue in two parts, one containing all those request numbers below the central cylinder and the other, past the central cylinder.
The second step is to run a loop which alters the pattern of the sorted sequence into a sinewave i.e. the request queue follows a pattern of two alternate crests (One increasing and one decreasing).
This normalizes the process as the disk drive reads-writes continuously in very consistent time intervals.
**Limitations：**
The smaller the size of the request queue, lesser is the performance of the given algorithm.
**Conclusion：**
Thus, the new real-time disk scheduling algorithm that is aimed at improving read-write consistency, which works by normalizing the request queue to make the seek jump distance or the time spent in seeking uniform.
The consistency achieved here can be used to lengthen the life of traditional disk drives, by reducing the overall mechanical stress on the read-write head.
8. **Usage Scenarios**(不放了啦～或移動後兩段到conclusion)
SSTF is the most common method because it has better performance than FCFS.
SCAN, C-SCAN and Sinewave are suitable for systems that use a large number of disks, because the moving time is relatively reduced and there is less starvation.
For a series of disk I/O requirements, an optimized service sequence can be defined first, but additional computing time and hardware design are required, so it is not necessarily more efficient than the above method.
Disk service is also affected by the way of file configuration. For example, when reading links or index files, there may be more head movement, but it can be solved by caching.
(磁碟服務也受到檔案配置的方式影響，例如讀取鏈結或索引檔時，可能產生較多的磁頭移動，但可藉由快取解決。)
In addition, the execution efficiency will vary with the order and number of disk requirements, so it is difficult to evaluate the pros and cons of the disk scheduling algorithm, and you can only choose the scheduling algorithm most suitable for the situation.
(此外，執行效率會隨磁碟要求的先後順序和數量而改變，所以很難評估磁碟排程演算法的優劣，只能選擇最適合該情境的排程演算法。)

#### *Linux I/O Schedulers* (芒果)

##### noop

The NOOP scheduler inserts all incoming I/O requests into a simple FIFO queue and implements request merging. This scheduler is useful when it has been determined that the host should not attempt to re-order requests based on the sector numbers contained therein.

There are two basic situations where this situation is desirable. First, if I/O scheduling will be handled at a lower layer of the I/O stack. since I/O requests are potentially rescheduled at the lower level, resequencing IOPs at the host level uses host CPU time on operations that will just be undone at the lower level, increasing latency/decreasing throughput for no productive reason. Second, if system hold non-rotational media such as flash drives or solid-state drives (SSDs). The read/write head movement doesn't impact application performance enough to justify the reordering overhead.

##### deadline

The main goal of the Deadline scheduler is to guarantee a start service time for a request. It does so by imposing a deadline on all I/O operations to prevent starvation of requests. It also maintains two deadline queues, in addition to the sorted queues (both read and write). Deadline queues are basically sorted by their deadline (the expiration time), while the sorted queues are sorted by the sector number.

Before serving the next request, the deadline scheduler decides which queue to use. Read queues are given a higher priority, because processes usually block on read operations. Next, the deadline scheduler checks if the first request in the deadline queue has expired. Otherwise, the scheduler serves a batch of requests from the sorted queue. In both cases, the scheduler also serves a batch of requests following the chosen request in the sorted queue.

##### Anticipatory

"Deceptive idleness" is a situation where a process appears to be finished reading from the disk when it is actually processing data in preparation of the next read operation. This will cause a normal work-conserving I/O scheduler to switch to servicing I/O from an unrelated process. This situation is detrimental to the throughput of synchronous reads, as it degenerates into a seeking workload. Anticipatory scheduling overcomes deceptive idleness by pausing for a short time (a few milliseconds) after a read operation in anticipation of another close-by read requests.

Anticipatory scheduling yields significant improvements in disk utilization for some workloads. In some situations the Apache web server may achieve up to 71% more throughput from using anticipatory scheduling.

##### CFQ

CFQ places synchronous requests submitted by processes into a number of per-process queues and then allocates timeslices for each of the queues to access the disk. The length of the time slice and the number of requests a queue is allowed to submit depends on the I/O priority of the given process. Asynchronous requests for all processes are batched together in fewer queues, one per priority. While CFQ does not do explicit anticipatory I/O scheduling, it achieves the same effect of having good aggregate throughput for the system as a whole, by allowing a process queue to idle at the end of synchronous I/O thereby "anticipating" further close I/O from that process. It can be considered a natural extension of granting I/O time slices to a process.

##### BFQ

BFQ is a proportional-share storage-I/O scheduler that also supports cgroups. Available in Linux since 4.12, BFQ features the following performance (benchmark results here), on any type of storage medium (embedded flash storage, HDDs, SATA or NVMe SSDs, ...) and on systems ranging from minimal embedded systems to high-end servers:

Under load, BFQ loads applications up to 20X times as fast as any other I/O scheduler. In absolute terms, the system is virtually as responsive as if it was idle, regardless of the background I/O workload. According to soft real-time applications, such as audio and video players, enjoy smooth playback or streaming, regardless of the background I/O workload. Besides, high throughput also play as key feature.BFQ reaches an I/O throughput equal to or higher than that reached by the other I/O schedulers. In multi-client applications---i.e., when multiple clients, groups, containers, virtual machines or any other kind of entities compete for a shared medium---BFQ provides each entity with strong bandwidth and latency guarantees.Finally, BFQ provides higher speed for code-development tasks, if some additional workload happens to be executed in parallel, then BFQ executes the I/O-related components of typical code-development tasks much more quickly than the other I/O schedulers.

### Design method

In Linux kernel, the default configuration of the system cannot be adequately adapted to different usage conditions.
Under the situation, an reinforcement learning method is suitable here. By collecting the historical usage of the system,the system will learn a configuration policy based on experience that earned more rewards. In this way, the system can dynamically adjust the current scheduler configuration according to different hardware configurations and software usage conditions to achieve the best expected effectiveness.


### Conclusion and future work

There are many scheduling algorithms, but various algorithms are suitable for different situations.

In general systems, usually only a single algorithm is used, which is not flexible in complex tasks.

For example, Linux provides flexibility on configuration, but most people only use the default configuration.

Through the above methods, we hope to learn strategies and dynamically adjust the configuration to obtain the best expected performance.