Operating Systems 2026F Lecture 12

Video

Video from the lectures given on November 3rd and 4th, 2026 are now available:

• Lecture 12A
• Lecture 12B

Notes

Lecture 12A

Lecture 12A
-----------
A1 is graded
A2 is being graded, almost done
Midterm is to be graded


Remember that people made computers work before the Internet (search engines, AI, etc)
 - how did they do it?

Filesystems
 - files
 - and how they are stored


CPU  <--->  Memory
       |
      I/O devices

I/O device directly talks to memory: DMA
 - direct memory access


I/O devices
 - screen
 - keyboard, mouse, touchscreen
 - network
 - storage  <--- our focus

When we talk about storage, we distinguish between
volatile and non-volatile memory
 - does it save its contents when power is lost?

volatile storage is pretty simple in structure
 - RAM, basically
 - put in an address, get back one or more bytes

How much data do you get from RAM at a time?
 - at least a "word", i.e., the size of a register
   - today, generally 64 bits
 - but generally you load a cache line worth from main memory
   - some multiple of the word size


memory hierarchy
 - computers have many ways to store information
 - each method of storage involves a trade-off between
   durability, speed, & cost
   - speed involving latency and bandwidth
 - so to make things fast but use lots of storage,
   you have to play a balancing game
 
What storage do we have? (from fastest to slowest)
 - registers
 - TLB <-- for virtual memory, later discussion
 - cache (L1, L2, L3, ?)
 - RAM (DRAM)
 - SSD
 - hard drives
 - tapes

Tapes -
 - cheap: just tape!
 - big: just add more tape!
 - slow: sequential can be okay, but random access is SLOW

hard drives -
 - not so cheap: magnetic platters
 - big because of high density recording (also for tapes)
 - but also kinda slow (for random access)


Why do we care about the technology of hard drives?
 - because it informs the design of filesystems

How do we store data in a way that makes the best use of the performance characteristics of the device?

For RAM, we just have address spaces
 - not much difference between sequential and random access
   (in theory), so maps well
    - but actually random access of RAM is slow,
      but we deal with that in other ways

Virtual memory
 - make volatile storage fast
 - and account for not having enough of it
  
filesystems
 - make persistent storage useful and fast
 - so need to encourage sequential data access and
   discourage random data access
 - and when random data access happens, want to limit
   the randomness

Files and directories work well for this
 - mostly programs read only a small fraction of files on a system
 - and for those files, they are mostly accessed sequentially

This abstraction isn't essential
 - disk storage is an array of blocks
   (as an abstraction)
 - a block is a fixed unit of storage
   - 512 bytes or a multiple (4K, 8K)

caching

what is a cache?
 - faster storage that stores copies of data

cache is never authoritative, it is just a fast copy
 - higher in the memory hierarchy

a cached copy is normally disposable
 - can throw it away if you need the space

On Linux, filesystems are abstractions over block storage
 - provide extensive caching infrastructure


So what layers are we talking about with filesystems?
 - storage <- the device that actually stores the data
 - volume management <- reorganize storage
 - interface <- block device, way we get the data
 - filesystem <- abstraction over block device,
                 turns it into files

From a user's perspective, a filesystem is a hierarchical key value store
 - /path/to/something => data

But what if I want to use multiple filesystems at the same time?
 - how do I name the filesystems?

On MS-DOS and older windows -
  filesystems would have letter names

In UNIX, we mount filesystems
 - associate a directory with a filesystem
   - so all files and directories in the filesystem are under that directory
   - the mountpoint directory is where the filesystem's files are integrated as part of the mount
     - if the mountpoint directory has any files...
       they get hidden

Lecture 12B

Lecture 12B
-----------
A1 is graded (uploading today)
A2 is being graded, should be done soon
Then we'll be grading the midterm

Remember you need to be able to solve problems without a search engine or AI
 - figure out the right questions to ask: answers are easy, questions are hard


Filesystems

CPU  <--->  RAM
       |
   I/O devices

Real picture is much more complicated
 - I/O devices can be entire computers
 - really, everything but the simplest embedded system
   is a network of computers, but pretending to act
   like the above

Recall I/O devices are
 - keyboard, mouse, touchscreen
 - screen/GPU
 - disks <--- filesystems
 - network

Memory hierarchy
 - many different kinds of storage technologies
 - different trade-offs between speed, durability, and cost
 - speed is relevant in sequential vs random access to data

Data on tape is stored as magnetic fluxes
 - very little magnets
A read/write head allows us to access the bits stored in these magnetic regions

Reading a tape sequentially is very fast
Reading a tape randomly is very slow
 - lots of fast forwarding & rewinding

To use this sort of medium, you have to use the right abstractions to make it efficient

Key technologies in the memory hierarchy
(fastest to slowest, also smallest to biggest)

registers (on the CPU), 64 bits each
TLB <--- for virtual memory, 64-256K?
cache (L1, L2, L3) <--- few megabytes
RAM <--- gigabytes
SSDs <--- many gigabytes to terabytes
hard drives <--- terabytes
tapes <--- as much as you want

Speed is really about latency versus bandwidth
 - you can always increase bandwidth by duplication
   (more hard drives, more tapes, etc)

bandwidth: bytes per second
latency: time for first byte (request to response)
(seek time)


We have two basic abstractions for accessing stored data
 - address space <--- assumes random access is fast
 - file <--- assumes random access is slow

In an address space, there is no assumed pattern to which addresses will be access in which order
 - but in practice, sequential reads are faster!
   (not part of the abstraction)

But with files, assumption is that any application will only access a small fraction of the files on a system
 - and, it will want most of the data in those files it accesses


address space: address -> byte (or a word)
filesystem: /path/to/a/file -> stream of bytes

file systems are implemented on block devices:
 - block number -> block contents (multiple of 512 bytes, typically 4K or 8K)

UNIX abstracts I/O devices into character and block devices
 - character devices are not cached
   - not necessarily accessed character by character
 - block devices are cached

What is cache?
 - a cache in CS is faster storage that is used to
   store copies of data from slower storage

Operating systems cache files in RAM to make access to them faster

So what's a filesystem?
 - data structure for mapping pathnames to data
   - typically designed to be persistent and stored in sets of blocks stored on SSDs or hard drives
   - but could be anything that can map pathnames to data

When you make a filesystem on a block device, you are "formatting" it, i.e., you're initializing a data structure for storing files
 - if there was an existing data structure (filesystem), it isn't there anymore even if most of its data is still technically present - you can't access it anymore!

But what if you don't want to use the whole block device for one filesystem?
 - or, what if you want multiple devices to be combined into one filesystem?

We can split block devices up using partitions

We can join block devices together using logical volume management

What is mounting?
 - associating a filesystem with a directory
   - so files and directories in the filesystem
     now appear under the mountpoint directory