Preemptible I/O scheduling of garbage collection for solid state drives

Junghee Lee, Youngjae Kim, Galen M. Shipman, Sarp Oral, Jongman Kim

Research output: Contribution to journalArticlepeer-review

59 Citations (Scopus)


Unlike hard disks, flash devices use out-of-place updates operations and require a garbage collection (GC) process to reclaim invalid pages to create free blocks. This GC process is a major cause of performance degradation when running concurrently with other I/O operations as internal bandwidth is consumed to reclaim these invalid pages. The invocation of the GC process is generally governed by a low watermark on free blocks and other internal device metrics that different workloads meet at different intervals. This results in an I/O performance that is highly dependent on workload characteristics. In this paper, we examine the GC process and propose a semipreemptible GC (PGC) scheme that allows GC processing to be preempted while pending I/O requests in the queue are serviced. Moreover, we further enhance flash performance by pipelining internal GC operations and merge them with pending I/O requests whenever possible. Our experimental evaluation of this semi-PGC scheme with realistic workloads demonstrates both improved performance and reduced performance variability. Write-dominant workloads show up to a 66.56% improvement in average response time with a 83.30% reduced variance in response time compared to the non-PGC scheme. In addition, we explore opportunities of a new NAND flash device that supports suspend/resume commands for read, write, and erase operations for fully PGC (F-PGC). Our experiments with an F-PGC enabled flash device show that request response time can be improved by up to 14.57% compared to semi-PGC.

Original languageEnglish
Article number6416101
Pages (from-to)247-260
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number2
Publication statusPublished - 2013
Externally publishedYes


  • Flash memory
  • I/O scheduling
  • garbage collection (GC)
  • preemptive I/O
  • solid-state drives (SSDs)
  • storage systems

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Preemptible I/O scheduling of garbage collection for solid state drives'. Together they form a unique fingerprint.

Cite this