where is disk scheduling implemented

I'm recently learning the part of disk schedulingof operating system. And I could understand the various algorithms for this issue, like FCFS, LIFO, SSTF, SCAN and so on. But I was wondering where these algorithms are implemented?

I don't think operating system is the answer because OS can't know the details of the I/O devices. So are they implemented on the devices themselves? Could anyone clarify it for me? Any related literature or links will be appreciated.

2 answers

  • answered 2018-03-11 12:41 Basile Starynkevitch

    In practice, disk scheduling (in the sense of e.g. reordering the pending disk reads to minimize rotational delay) is less important today than it was in the XXth century.

    • hard disks are probably less used, in favor of SSDs, and they are even more slow w.r.t. fast RAM access time.

    • the disk sector as seen by the kernel have been reorganized by the disk controller itself, so the CHS addressing (as seen by the OS kernel) does not correspond to geometrical reality

    • the hard disk drive is smarter today and its internal controller has significant memory and computing capabilities. The SATA protocol has some "higher level" requests (e.g. TRIM). Read about SMART and hybrid drives.

    However, application code can give hints to the operating system about access patterns. Look for example into posix_fadvise(2).

    Read also Operating Systems: Three Easy Pieces

  • answered 2018-03-11 12:41 user3344003

    The simple answer is that these days, this all takes place in the drive controller.

    In ye olde days, operating systems usually implemented disk I/O in two layers. At the the top was a drive independent logical layer. This viewed the drive as an array of blocks. Below this was a physical layer that viewed disks as platters, tracks, and sectors. Because the physical details varied among drives, the physical layer was usually implemented in a disk-(or class of disks) specific device driver.

    In these dark times, you often had to wait for your drive vendor to create a new device driver before you could upgrade your operating system.

    In the mid-1980's it started to become common for disk drives to provide a logical I/O interface. The device driver no longer saw disks/platters/sectors. Instead, it just saw an array of logical blocks. The drive took care of physical locations and redirecting of bad blocks (tasks that the operating system used to handle). This allowed single device driver to manage multiple types of devices, sharing the same interface and differing only in the number of logical blocks.

    These days, you'd be hard pressed to find a disk drive that does not provide a logical interface.

    All the scheduling algorithms that involve physical locations have to take place within the disk drive.

    Unless you are doing disk drive engineering, such scheduling algorithms are quite meaningless. If you learning hard drive engineering, expect that occupation to disappear soon.