Modern storage devices are becoming more complex and smarter compared to the past. As a consequence the central role of IO scheduling is shifting from operating systems to storage devices. Many scheduling algorithms for magnetic disk drives have been proposed, but for NAND-flash-based solid state drives (SSD), dissimilar approaches are necessary due to different physical characteristics.
SSD has no moving parts and has multiple flash chips operating in parallel, where IO requests are processed in a unit of page. Its write latency is tens of times as great as the read latency, and SSD requires erase operation to overwrite in a memory cell. Considering the characteristics, scheduling algorithms, such as earliest finish time first (EFTF) algorithm and simple intuitive ones, are explored and their implementations are provided. By employing a simulation-based method using various parameters, the performance of the algorithms are analyzed.
The simulation result shows that utilizing the EFTF algorithm improves the response time of SSD by average 16.85\% and maximum 34.63\% depending on the workloads intensity compared to first-in-first-out policy. Throughout our work we also have verified that small cache hit rate, large scheduling queue size, and high intensity of IO contribute to the effectiveness of the scheduling algorithms. In addition, by employing time-out strategy to prevent starvation, we have shown that there is a tradeoff between maximum response time and average response time.
본 논문에서는 SSD 내부의 플래시 메모리 요청들을 스케줄링 하여 전체적인 평균 입출력 응답시간을 단축시키는 방법들을 연구하였다. SSD 내부의 플래시 메모리 요청을 스케줄링 하는 것은 프로세싱 자원을 스케줄링 하는 문제와 유사하다.
가장 빨리 완료될 것으로 예상되는 요청을 먼저 스케줄링 하는 기법과 다른 직관적인 스케줄링 방법들의 구현을 제시하고 이들을 시뮬레이션 기법을 사용하여 분석하였다. 실험 결과 완료 시간을 기준으로 스케줄링 하는 기법의 성능이 가장 좋음을 확인하였고 여러 결과들을 바탕으로 스케줄링 기법에 영향을 미치는 요소들을 발견하였다. 입출력 요청의 빈도가 시간당 많을수록 스케줄링의 효과가 큰 것으로 나타났고 SSD의 입출력 큐와 플래시 메모리 요청을 스케줄링 하는 큐가 클수록 스케줄링이 효과적이고 유연성을 갖는 것으로 나타났다. 스케줄링은 여러 요청들을 동시에 처리할 때 효과적이기에 페이지 캐시에서의 Miss 비율이 높을수록 스케줄링 효과가 좋다. 스케줄링을 할 때 우선순위가 떨어지는 요청들은 오랫동안 처리가 되지 않을 수 있는데 이런 문제는 Time-out 기법으로 간단하게 해결될 수 있음을 실험을 통해 보였고 같은 실험을 통해 평균 응답 시간과 최장 응답 시간 간에 Tradeoff 관계가 있는 것을 보였다.
SSD는 하드디스크와 다른 특성을 갖기에 운영체제에서 입출력 요청을 스케줄링 하는 문제보다 SSD 내부에서의 요청을 스케줄링 하는 문제가 더욱 중요해질 것으로 예측된다. 본 논문은 SSD 내부에서의 입출력 요청을 스케줄링하는 문제를 다루는데 필요한 기초를 제공하며 동시에 스케줄링의 효과를 증진시키기 위한 기본적인 매개변수들을 이해할 수 있는 기반을 제시한다.
