File systems cont. #

Protection #

These permissions are implemented as an ACL (access control list). This keeps track of the capability of every object.

Other systems keep track of the capability of every subject.

Why do most OS choose ACL? (Associating permission with the object, compared to associating permission with the subjects).

Organization #

Note: The linear list implementation can be done using a B+ tree.

Allocation #

• Contiguous allocation works well with spinning disk memory (no giant leaps)
• but suffers greatly from external fragmentation

• this is the file system used by linux

• linked files is a non-contiguous allocation
• no more external fragmentation
• sequential access is easy
• random access is still a linear operation
• lots of physical movement for spinnning disks

• maintain head and tail (to add to end)

• File-Allocation Table = FAT, an example of the linked allocation.

• OS must maintains pointer arrays for each file

• block 19 doesn’t store any data from the file, just an array of pointers
• currently using 5 out of 8 sectors available
• sequential access is easy
• random access is easy

So how do we allow the file size to grow beyond maximum?

Notes on the final #

Make sure I know how to calculate:

• fork(), exec(), wait() system calls
• Scheduling algorithms as Gantt charts
  • FCFS SJF SRTF RR
  • Average wait time, turnaround time, response time
  • Start counting once the process arrives, not from \( t = 0 \)
• Semaphore order with wait() and signal()
  • look for race conditions
  • deadlock
• Semaphore based solutions like
  • bounded buffer
  • readers writers
  • dining philosophers
• Deadlock avoidance
  • Banker’s algorithm avoid version ensures system doesn’t enter unsafe state
  • Safety checks if we’re in a safe state
  • Resource-request checks if the process can receieve resource, and if so it checks the state using safety alg after “allocating”
• Deadlock detection
  • Safety algorithm detection version checks to see if system is in unsafe state
• Memory allocation
  • First fit, best fit, worst fit
• Translatoin look-aside buffer (TLB)
  • Usually given page size, if we know the page size then
    • we know the offset (binary log of page size)
    • Also know the VPN bits, (the difference)
    • The VPN bits gives us the number of virtual pages
  • If asking for page table size
    • Size depends on the size of a page table entry (for example 4B) multiplied by number of pages
  • Performance: effective access time
    • Probability of a TLB hit and TLB miss
    • probability of hit * time + probability of miss * time
• Page faults
  • Effective access similar to TLB
• Demand paging
  • FIFO Optimal LRU CLOCK
  • The numbers are addresses, they must be converted from addresses into page numbers first
  • Calc using address mod page size
  • Run the algorithms using those page numbers
• Access time for storage
  • Seek time + rotational latency + data transfer
• Disk scheduling
  • FCFS SSTF SCAN/C-SCAN with/without LOOK
• Multilevel indexed files
  • EXT2 filesystem, where do we find the data
  • How many steps to fetch the data? (How many indexed tables do we need to hop)
  • Check group exercise

Exam covers about 40% of midterm 1, 40% of midterm 2, 20% of rest