COMP 3000 2012 Week 11 Notes

CPU SCHEDULING

• Kernel operations:
  • switch to supervisor-> caused by interrupt
  • when we switch back into user, we need to figure out what process to run next. THIS IS SCHEDULING

• CPU state
  • ready
  • running
  • loading (loading into memory)
  • blocked (waiting for I/O)
  • Scheduling takes processes and changes its state
  • see diagram

Which process does the scheduler run next?

• To avoid starvation, uses round robin algorithm
• preemption: max time a process can use the CPU
• prioritize unblocked processes: those using limited resources are prioritized
• priorities set by nice values and other jigging

• Scheduling is HARD. Figuring out fine grained scheduling is still an open problem. Everything we have is a bit "hacky"

CFS (completely fair scheduler) is the linux scheduler

I/O scheduling

• Disk scheduling.
  • Elevator algorithm
    • "Get on elevator when it passes by, get off when it gets to your floor, but you're not controlling the elevator
    • there are exceptions though. Some processes "can control the elevator"
    • To avoid long "queues", we batch I/O requests together (I/O reordering)
    • We employ HD caches to help deal with batching and I/O reordering

Filesystems -- Journaled (revisted)

FSCK walks the FS checking for errors. Takes long time. Bad idea. Journaled FSes fixes this.

Journaled FSes

• Transactions do not happen directly to disk.
• We first write to a journal.
• Later, the journal will be read and the transactions will write to disk
• These transactions happen in a stream (sequentially), which will be much faster than random writes
• We're actually writing twice as much (time, transactions, not data) to the disk
• we actually write to the rest of the disk in the background, when nothing is relying on I/O

• If you're writing a lot to your FS, though, this'll be slow. We're writing twice to disk.
  • To solve this issues, the entire file system becomes the FS.
  • Could someone expand on this?

Log structured FS Could someone expand on this

SSDs use wear leveling. Each memory cell has a dedicated lifespan. We try to lengthen their life by spreading the wear across the SSD.