This is a very sketchy notes of mine to review before the final exam of CS5348 - Operating System Concepts.

Previously: Midterm review

Concurrency

  • [[Threads]]:
    • Is a sequence of instructions that can be run independently of a parent process
    • Shared between threads: data, pid; not shared: registers, stack, thread id
    • [[pthread]]: declare, create (pass multiple arguments using struct), join
    • Sometimes more threads doesn’t mean better, like in [[multi-threaded merge sort]]. Need to put a limit on when to create new threads.
  • [[Lock (OS)]]:
    • To protect [[Critical Section]]
    • different implementation
      • Disable interrupts -> monopoly, false disables of other interrupts
      • software lock
      • spinning
      • hardware lock TestAndSet(&var, new) -> old
      • FetchAndAdd-> used for semaphores more?
  • [[Semaphores]]: sem_wait and sem_post are implemented using the atomic hardware-based testandset instruction. They are the generalization of Locks
  • Popular concurrency problems
    • [[Sleeping barber problem]]
    • [[Producer consumer problem]]
    • [[Readers-Writers problem]]
    • [[Roller Coaster Problem]]
  • Concurrency Bugs: order the locks

Files

Concepts:

  • File: sequence of persistent bytes, can be read/written
    • Virtually, a contiguous sequence of logical addresses
    • Everything is a file:
      • directories: contains a list of pointers to the children (either hard or soft links)
      • devices (including monitor, network interface, etc.): unified interface with Status, Command, and Data.
    • Each working instance of a file is maintained by a [[File descriptor]] (including inode pointer and offset within the file)
  • Inode: metadata for files
  • [[file links]]:
    • Hard link is reflected by the inode number in the data block.
    • Soft link: included in the file

File system structure:

  • Superblock
  • Inode bitmap
  • Data bitmap
  • Inodes
    • Always has at least 3 things: file type (f for regular, directory), data block address (a), reference count (r)
    • Reference count can help reflect the number of links to the file.
  • Data blocks
    • in a directory file, each child saves the inode number. Always contains entries for . and ...

[[RAID]]: Virtualize the disks

  • RAID-0: stripping -> no fault tolerance
  • RAID-1: mirroring -> wasting half of the space
  • RAID-4: [[parity bit]] in one disk -> bottle neck in random write
  • RAID-5: rotating parity

Example problem:

  • Block size = 4KB, Data region size = 4GB, Inode size = 256 bytes
  • Inode contains only direct pointers to 10 blocks. Maximum file size?
    • 10 x block size = 40KB
  • Inode contains 10 direct pointers and 1 indirect. Block numbers use 4 bytes each. Max file size?
    • block size x (10 + block size / 4) = 4K x (10 + 1K) = 4,235,264 bytes ~ 4MB
  • Size of data bitmap?
    • data region / block size = 4G / 4K = 2^(30-10) = 2^20 = 1M (bits)
  • num blocks for inode bitmaps
    • bit map size / block size = 2^20 / (2^12 * 8) = 2^5 = 32