369 Notes

369 Lecture 1

369 Lecture 2

Basic Input Output System
Hardware stores small program in non-volatile memory.
When power is fist supplied, this program executes.
  • Checks that RAM, keyboard, and basic devices are installed and functioning correctly
  • Scans buses to detect attached devices and configures new ones
  • Determines boot device (tries list of devices in order)
  • Reads first sector from boot device and executes it (bootloader)
  • Bootloader reads partition table, finds active partition, reads secondary bootloader
  • Secondary bootloader reads OS into memory and executes it
OS Initn
  • Initz internal data structs.
    (Machine dependent oprtns are typically done first)
  • Create 1st process.
  • Switch mode to user & Start running 1st process.
  • Wait for sth to happen
    (OS is entirely driven by external events.)
From Program to Process
From Program To Process
  • Stop current process
  • Load program into process'address space
  • Initz hardware context & args for new program
  • Place PCB onto ready queue
  • Note: It does NOT create a new process
Boundary Crossings
  • User Mode -> Kernel Mode
    • Boot time
    • Explicit sys call (Req for service by app)
    • Hardware interrupt
    • Software trap/exception
    • Hardware has table of "Interupt service routines"
  • Kernel Mode -> User Mode
    • Jump to next app instruction
Sys Calls for Process Management
Call Description
fork() Create
waitpid() Wait
execve() Replace
exit() Terminate
Sys Calls for File Management
Example of System Calls (for read())

Note: Trap: User -> Kernel
Interleaved Schedules

Two concurrent threads manipulated a shared resource (account) w/o any sycn.

Need to ensure that only one thread at a time can manipulate shared resource. Thus sycn is needed.

Race Condition
Outcome depends on order in which accesses take place.
the process by which a running computer system is restarted, either intentionally or unintentionally.

Note: Permission required cuz it is a system call.

Note: OS itself is a process.

Critical Section (CS)
A segment of code which accessed the shared resource.

We want to ensure that:

  1. Only one thread at a time can execute in the critical section
  2. All other threads are forced to wait on entry
  3. When a thread leaves the CS, another can enter

Data shared:

  • Global vars
  • Static objs
  • Dynamic objs
  • Heap objs
  • Note: Local vars are not shared (private).


  1. Mutual Exclusion
    • If one thread is in the CS, then no other is.
  2. Progress
    • If no thread is in the CS, and some threads want to enter CS, it should be able to enter in definite time.
  3. Bounded Waiting (No starvation).
    • If some thread T is waiting on the CS, then there is a limit on the number of times other threads can enter CS before this thread is granted access
  4. Performance
    • The overhead of entering and exiting the CS is small with respect to the work being done within it.

Assumptions & Notation

  • Assume no special hardware instructions, no restrictions on the # of processors (for now).
  • Assume that basic machine language instructions (LOAD, STORE, etc.) are atomic:
    If two such instructions are executed concurrently, the result is equivalent to their sequential execution in some unknown order
  • If only two threads, we number them T0 and T1
    Use Ti to refer to one thread, Tj for the other (j=1-i) when the exact numbering doesn’t matter
Peterson's Solution
Higher-Level Abstractions for Critical Sections
  • Lock
  • Semaphore
  • Monitor
  • Message
Test-&-Set Lock (TSL)
Atomic Instruction


369 Lecture 3

Swap (Exchange) Instruction
Operate on 2 words atomically.
Can also be used to solve critical section problem.
Higher-Level Abstractions for critical sections
Primitive, minimal semantics
Operations: Acquire (Lock), Release (Lock)
Easy to understand
Hard to program w/
High-level, ideally has language support (Java)
Simple model for communication & syncn
Direct application to distributed systems
Producer & Consumer Model
2 processes share a bounded buffer
Producer puts info in buffer
Consumer takes info out
Sleep: Cause caller to block
Wakeup: Awaken a process
Problem: What if consumer wakes up producer before it sleeps
An operation that appears to the rest of the system to occur instantaneously.
Usually just 1 line of code.
ADT that provides syncn.
1 int var, accessed only thru 2 atomic operations
Atomic operation wait (or P or decrement): Decrement variable & block until semaphore is free.
Atomic operation signal (or V or increment): increment var, unblock a waiting thread if there are any.
A queue of waiting threads.
Mutex (Binary) Semaphore
Represent single access to a resource.
Guarantee mutual exclusion to a critical section
Has count = 1
Counting Semaphore
Represent a resource w/ many units available, or a resource that allows certain kinds of unsynced concurrent access (e.g. reading)
Multiple threads can pass semaphore
Max # threads is determined by semaphore's init value, count
Had count = N
Reader & Writer Problem
// # readers
int readcount = 0;
// Mutex to readcount
Semaphore mutex = 1;
// Mutex to writer/reader
Semaphore w_or_r = 1;

Writer {
    wait(w_or_r); // Lock out others
    signal(w_or_r); // Up for grabs

Reader {
    wait(mutex); // lock readcount
    // one more reader
    readcount += 1;
    // is this the first reader?
    if (readcount == 1) {
        // sync w/ writers
    // unlock readcount
    wait(mutex); // lock readcount
    readcount -= 1;
    if (readcount == 0)
First reader arrives while writer is active
Then first reader is blocked at wait(w_or_r)
All other readers are blocked on mutex
Second reader arrives while writer is active
Then second reader is blocked at wait(mutex)
Once writer exits, which reader gets to go first?
The one at wait(w_or_r) goes first
If both readers & writers are waiting, once writer exits, who goes first?
It depends on the scheduler.
ADT w/ restriction that only one process at a time can be active within monitor.
A process in monitor may need to wait for sth to happen.
Monitor Semantics for signal
Hoare Monitor
Signal() immediately switches from caller to a waiting thread
Brinch Hansen
Signaler must exit monitor immediately
i.e. Signal() is always last statement in monitor procedure
Mesa Monitor
Signal() places a waiter on ready queue, but signaler continues inside monitor

369 Lecture 4

Dining Philosophers Problem
Page 4-6
How does OS keep tract of processes?
OS maintains a collection of queues that represent state of all processes in sys.
Typically, OS has one queue for each state. (Ready, waiting, etc.)
Each PCB is queued on a state queue according to its current state.
As a process changes state, its PCB is unlinked from one queue and linked into another.
OS manages processes by keeping track of their state
Different events cause changes to a process state, which OS mush record/implement.
What happens on dispatch/context switch?
Switch CPU to another process.
Save current running process state.
Unless current process is exiting.
Select next process from ready queue.
Restore state of next process.
Restore registers
Switch to user mode
Set PC to next instruction in this process
What is Process Life Cycle?
Processes repeatedly alternate between computation and I/O.
Called CPU bursts and I/O bursts.
Last CPU burst ends with a call to terminate process(_exit() or equivalent).
CPU-bound: Very long CPU burst, infrequent I/O bursts.
I/O-bound: Short CPU bursts, frequent (long) I/O bursts.
During I/O bursts, CPU is not needed. Opportunity to execute another process.
What is processor scheduling?
Allocation of processors to processes over time.
Key to Multiprogramming.
We want to increase CPU utilization and job thruout by overlapping I/O and computation.
Mechanisms: Process states, Process queues.
Policies: ...
Scheduling Goals:
All systems
Fairness: Each process receives fair share of CPU.
Avoid starvation
Policy enforcement: Usage policies should be met.
Balance: All parts of sys should be busy.
Batch Systems:
Thruout: Maxize jobs completed per hour.
Turnaround Time: Minize time btw submission and completion.
CPU Utilization: Keep CPU busy all time.
What are types of scheduling?
Non-Preemptive Scheduling
Once CPU has been allocated to a process, it keeps CPU until it terminates.
Suitable for batch scheduling.
Preemptive Scheduling
CPU can be taken from a running process and allocated to another.
Needed in interactive or real-time syses.
What is Scheduling Algo: FCFS?
"First Come, First Serve"
Choose process at head of FIFO queue of ready processes.
What are problems w/ FCFS?
Avg waittime often quite long.
Convoy Effect: All other processes wait for 1 big process to release CPU.
What is Scheduling Algo: SJF?
"Shortest Job First"
Choose process (among all processes that are waiting) w/ shortest processing time.
What are problems w/ SJF?
Need to know processing time in advance.
Programmer estimate
History stats
Starvation + Fairness??
Difference btw FCFS and SJF?
SJF has short wait times, but unfair
FCFS is faire, but can lead to long wait times. (Short jobs can get stuck behind long jobs)
What is Scheduling Algo: RR?
"Round Robin"
Compromise btw FCFS and SJF.
Designed for time-sharing syses.
Ready queue is circular.
Each process is allowed to run for time quantum q before being preempted and put back on queue.
Choice of quantum (aka time slice) is critical.
As q -> ∞, RR -> FCFS;
As q -> 0, RR -> process sharing (PS).
We want q to be large wrt context switch time.
What is Priority Scheduling?
A priority, p, is associated w/ each process.
Highest priority job is selected from ready queue.
Can be pre-emptive or non-pre-emptive
Starvation: A low priority task may never get to run.
Priority Inversion: A low priority task may prevent a high priority task from making process by holding a resource.
What do real syses do?
Combination of:
Multi-level queue scheduling (Typically w/ RR and priorities)
Feedback scheduling
What is MLQ Scheduling?
"Multi-Level Queue"
Have 2 scheduling policies:
1st decides which queue to serve (e.g. Based on queue priorities)
2dn decides which job within a queue to choose (e.g. FCFS or RR)
What is Multiple Queues w/ Priority Scheduling?
Highest priority gets 1 quantum, second highest gets 2, etc. If highest cannot be finished, bump it to 2nd highest, and so on.
Consequently, shortest (high priority) jobs get out first.
What is Feedback Scheduling?
Adjust criteria for choosing a particular process based on past history.
Combine w/ MLQ.
Can prefer processes that do not use full quantum.
Can change priority of processes based on age.
Can change priority of processes based on CPU consumed so far.
Can boost priority following a user-input event.
Move processes btw queues.
How does Linux 2.6 CPU deal w/ scheduling?
Always run task in active array w/ highest priority.
If there are processes w/ same priority, RR btw them.
Swtich after Granularity time units
If Timeslice expires, move to expired array
How to determine priority of process?
Some processes are more important than others.
Assign Static Priorities [-20, 19].
Done thru nice syscall.
Interactive and I/O bound processes should be favored.
Give bonus/penalty on top of static priority.
Priority = StaticPriority + Bonus
How to identify interactive and I/O bound processes
Maintain sleep_avg (time process is sleeping v.s. CPU time)
How to set timeslice and granularity?
Timeslice depends on static priority (btw 5ms and 800ms).
Granularity depends on dynamic priority.

369 Lecture 5

What is Memory Management?
Every active process needs memory.
CPU scheduling allows processes to share (multiplex) the processor.
Must figure out how to share main memory as well.
What are the goals of memory management?
Support enough active processes to keep CPU busy.
Use memory efficiently (minize wasted memory).
Keep memory management overhead small while satisfying vasic requirements.
What are requirements for memory management?
Programmers don't know what physical memory will be available when their programs run.
Scheduler may swap processes in/out of memory, need to be able to bring it back in to a diff region of memory.
This implies we will need some type of address translation.
Logical Organization
Machine accesses memory addresses as a one-dimensional array of bytes.
Programmers organize code in modules.
Need to map btw these views.
A process's memory should be protected from unwanted access by other processes, both intentional and accidental.
Requires hardware support.
In some instances, processes need to be able to access same memory.
Need ways to specify and control what sharing is allowed.
Physical Organization
Memory and Disk form a 2-level hierarchy, flow of info btw levels must be managed.
CPU can only access data in registers or memory, not disk.
How to meet the requirements?
Modern systems use Virtual Memory虛擬內存: Complicated technique requiring hardware and software support.
What are some simpler schemes?
Fixed partitioning
Dynamic partitioning
What is Address Binding?
Programs must be in memory to execute.
Program binary is loaded in to a process
Needs memory for code (instructions) and data
Addresses in program must be translated to read addresses
Programmers use symbolic addresses (i.e. var names) to refer to memory locations.
CPU fetches from, and stores to, real memory addresses.
What is absolute code?
Addresses bound during compile time.
Disadvantages of addresses bound in compile time?
Must know waht memory process will use during compilation.
No relocation is possible.
What if bound in load time?
Compilers traslates (binds) symbolic addresses to logical, relocatable addresses w/in compilation unit (source file).
Linker takes collection of obj files and translates addresses to logical, absolute addresses w/in executable. It resolves refs to symbols defined in other files/modules.
Loader translates logical absolute addresses to physical addresses when program is loaded into memory.
Disadvantage: Programs can be loaded to diff address when they start, but cannot be relocated later.
What if bound in execution time?
Exe obj file, a.out, contains logical addresses for entire program.
Translated to a real, physical address during execution.
Flexible, but requires special hardware.
What is Fixed Partitioning?
Divide memory into regions w/ fixed boundaries.
Can be equal-size or unequal-size
A single process can be loaded into each remaining partition.
Disadvantages of fixed partitioning?
Internal fragmentation
What is Internal Fragmentation?
Memory is wasted if process is smaller than partition
What is Overlay?
Programs that are larger than partition
Placement w/ Fixed Partitions
Equal-sized partitions: Process can be loaded into any available partition.
Unequal-sized partitions: Queue-per-partition, assign process to smallest partition in which it will fit. A process always runs in the same size of partition. Single queue, assign process to smallest available partition.
What is Dynamic Partitioning?
Partitions vary in length and number over time.
When a process is brought in to memory, a partition of exactly the right size is created to hold it.
What is disadvantage of Dynamic Partitioning?
As processes come and go, holes are created, which needs compaction and requires processes to be relocatable.
What is External Fragmentation?
Some blocks may be too small for any process.
What is Compaction?
OS may move processes around to create larger chunks of free space.
How are malloc() and free() implemented?
Manage contiguous range of logical addresses.
malloc(size) returns a ptr to a block of memory of at least "size" bytes, or NULL.
free(ptr) releases previously-allocated block pointed to by "ptr".
Dynamic partitioning system.
Ways of tracking memory allocation?
Free List
Implicit List
Explicit List
What is Bitmap?
One way of tracking memory allocation.
1 bit per allocation unit.
0 == free, 1 == allocated
It allocates a N-unit chunk requires scanning bitmap for sequence of N 0's.
But it is slow.
What is Free List?
It maintains linked list of allocated and free segments.
List needs memory too. Where do we store it.
What is Implicit List?
Each block has header that records size and status (allocated or free)
Searching for free block is linear in total number of blocks.
What is Explicit List?
Store ptrs in free blocks to create doubly-linked list.
Freeing Blocks
Adjacent free blocks can be coalesced.
What are Placement Algos?
What is First-Fit?
Choose first block that is large enuf; search can be start at beginning, or where prev search ended (called next-fit).
Simplest, and often fastest and most efficient.
May leave many small fragments near start of memory that must be searched repeatedly.
What is Best-Fit?
Choose block that is closest in size to request.
Left-over fragments tend to be small (unusable)
In practice, similar storage utilization to first-fit.
What is Worst-Fit?
Choose largest block.
Not as good as best-fit or first-fit in practice.
What is Quick-Fit?
Keep multiple free lists for common block sizes.
Great for fast allocation, generally harder to coalesce.
What are problems w/ partitioning?
W/ fixed partitioning, internal fragmentation and need for overlays are big problems. Scheme is too inflexible.
W/ dynamic partitioning, external fragmentation and gestion of space are major problems.
Basic problem is that processes must be allocated to contiguous blocks of physical memory.
Hard to figure out how to size these blocks given that processes are not all the same.
So need to use Paging.
What is Paging?
Partition memory into equal, fixed-size chunks. These are called page frames or simply frames.
Divide processes' memory into chunks of same size, which are called pages.
What is page table?
OS maintains a page table for each process.
Page table records which physical frame holds each page.
Virtual addr are now page # + page offset
Page # = vaddr / page_size
Page offset = vaddr % page_size
"Page Table Entry"
It controls mapping.
M(1), R(1), V(1), Prot(3), Page Frame #(26)
Modify Bit (M): whether or not page has been written. Set when a write to a page occurs.
Ref Bit (R): whether page has been accessed. Set when a read or write to page occurs.
Valid Bit (V): whether PTE can be used. It checks on each use of virtual address.
Protection bits specify what operations are allowed on page. RWX
PFN (Page Frame Number) determines physical page.
Not all bits are provided by all architectures.
What is TLB?
"Translation Lookaside Buffer"
It translates virtual page #s into PTEs (not physical addrs).
Can be done in a single machine cycle.
TLBs are implemented in hardware.
It is a fully associative cache(All entries looked up in parallel).
Cache tags are virtual page numbers
How much space does a page table take up?
Need one PTE per page
4MB/Page Table
Too large!
Hierarchical (Multi-level) page tables
Hashed page tables
Inverted page tables
2-Level Paging
32-bit virtual addr space.
Master = 10 bits
Secondary = 10 bits
Offset = 10 bits

369 Lecture 6

What is Inverted Page Table?
Keep one table w/ an entry for each physical page frame.
Entries record which virtual page # is stored in that frame. Need to record process id as well.
Less space, but lookups are slower. Refs use virtual addrs, table in indexed by physical addrs. Use hashing to reduce search time.
What is Page Fault?
When a process accesses page, invalid PTE will cause a trap.
Trap will run OS page fault handler.
Handler uses invalid PTE to locate page in swap file.
Reads page into a physical frame, updates PTE to point to it.
Restarts process.
What is MMU?
"Memory Management Unit"
It is a computer hardware unit having all memory references passed through itself, primarily performing the translation of virtual memory addresses to physical addresses. It is usually implemented as part of the central processing unit (CPU), but it also can be in the form of a separate integrated circuit.
An MMU effectively performs virtual memory management, handling at the same time memory protection, cache control, bus arbitration and, in simpler computer architectures (especially 8-bit systems), bank switching.
Policy Decision
Page tables, MMU, TLB, etc. are mechanisms that make virtual memory psb.
Policies for virtual memory management:
Fetch Policy: When to fetch a page. Demand paging vs. Prepaging.
Placement Policy: Where to put page.
Replacement Policy: What page to evict to make room?
What is Prepaging?
== Prefetching
It predicts future page use at a time of current fault.
Placement Policy?
In paging syss, memory gestion hardware can translate any virtual-to physical mapping equally well.
What is NUMA multiprocessor?
"Non-Uniform Memory Access"
Any processor can access entire memory, but local memory is faster
What is Cache Performance?
Choose physical pages to minize cache conflicts
How to evict best page?
Goal of replacement algo is to reduce fault rate by selecting best victim page to remove
Replacement algos are evaluated on a reference string by counting
Best pg to evict is 1 never used again, which will never fault on it.
Never is a long time, so picking pg closest to never is next best thing.
Evicting pg that won't be used for longest period of time minizes # pg faults.
What is Cold Miss?
1st access to a pg (Unavoidable).
What is Capacity Miss?
Caused by replacement due to limited size of memory.
What is Belady's Algo?
It is known as optimal pg replacement algo cuz it has lowest fault rate for any pg ref stream (aka opt/min).
Idea: Replace pg that won't be used for longest period of time.
Problem: Have to know future perfectly.
It can compare implementations of pg replacement algos w/ optimal to gauge room for improvement.
If optimal is ! much better, then algo is pretty good.
If optimal is much better, then algo could use some work.
Rand replacement is often lower bound.
What are psb replacemnt algos?
Last 3 of these require book-keeping.
What is Belady's Anomaly?
A phenomenon in which increasing # pg frames results in an increase in # page faults for certain memory access patterns.
What is Second Chance Algorithm?
Don't evict oldest pg if it has been used.
Evict oldest page that has not been used.
Pgs that are used often inuf to keep ref bits set won't be replaced.
Arrange ol of physical pg frames in a big circle (clock).
A clock hand is used to select a good LRU candidate.
It sweeps thru pgs in circular order like a clock.
If ref bit (use bit) it hasn't been used recently (R = 0): Evict pg and set R = 1.
If ref bit is on (R = 1): Turn it off (Set R = 0) and go to next pg.
Arm moves quickly when pgs are needed.
Low overhead when plenty of memory.
What is LRU?
"Least Recently Used"
It uses ref info to make a more informed replacement decision.
Idea: We can't predict future, but we can make a guess based upon past exp.
On replacement, evict pg that has not been used for longest time in past (Belady's: Future).
How to implement exact LRU?
Option 1:
time stamp every ref.
Evict pg w/ oldest time stamp.
Need to make PTE large inuf to hold meaningful time stamp.
Need to examine every pg on eviction to find 1 w/ oldest time stamp.
Option 2:
Keep pgs in a stack. On ref, mv pg to top of stack. On eviction, replace pg at bottom.
Problem: Need costly software oprtn to manipulate stack on EVERY memory ref.
How to approx LRU?
Exact LRU is too costly to implement.
LRU approxs use PTE ref bit.
What is Additional Ref Bits Algo?
Keep a counter for each pg.
At regular intervals, for every pg do:
Shift R bit into high bit of counter reg.
Shift other bits to right.
Pgs w/ larger counters were used more recently.
What is Fixed space algo?
Each proc is given a limit of pgs it can use.
When it reaches limit, it replaces from its own pgs.
Local replacement: Some procs may do well while others suffer.
What is Var space algo?
Process' set of pgs grows and shrinks dynamically.
Global replacement: 1 proc can ruin it for rest.
Local replacement: Replacement and set size are separate
What is Working Set Model?
It is used to model dynamic locality of its memory usage.
WS(t, Δ) = {Pgs P s.t. P was refed in time interval (t, t-Δ)}
t = time
Δ = working set window (measured in pg refs).
A page is in working set (WS) only if it was refed in last Δ refs.
What is Working Set Size?
Working set size is # pgs in working set. # pgs refed in interval (t, t-Δ).
Working set size changes w/ program locality.
Don't run a proc unless working set is in memory.
What is PFF?
"Page Fault Frequency"
It is a var space algo that uses a more ad-hoc特別地 approach.
Monitor fault rate for each proc.
If fault rate is above a high threshold, give it more memory. So that is faults less, but not always (FIFO, Belady's Anomaly).
If fault rate is below a low threshold, take away memory. Should fault more, but not always.
Hard to use it to distinguish btw changes in locality and changes in size of working set.
What is Thrashing?
Page replacement algos avoid thrashing.
When more time is spent by OS in pging data back and forth from disk than exeing user programs.
No time spent doing useful work (making progress).
In this situation, sys is overcommitted.
What is Paging Policy for Win?
Local pg replacement.
Per-process FIFO.
pgs are stolen from processes using more than their min working set.
Processes start w/ a default of 50 pgs.
It monitors pg fault rate and adjusts working-set size accordingly.
On pg fault, cluster of pgs around missing pgs are brought into memory.
What is Paing Policy for Linux?
Global replacement.
Modified second-chance clock algo.
Pgs age w/ each pass of clock hand.
Pgs that are not used for a long time will eventually have a value of 0.

369 Lecture 7: Midterm

369 Lecture 8

What do file syses do?
They provide a nice abstraction of storage.
What is File Management System?
Implement an abstraction (files) for secondary storage.
Organize files logically (dirs)
Permit sharing of data btw processes, people, and machines.
Protect data from unwanted access (security).
What are File Access Methods?
General-purpose file syses support simple methods.
Seq access - Read bytes 1 at a time, in order: Read next/Write next.
Direct access: Rand access given block/byte #: Read n (byte at offset n)/Write n
What does Unix use?
Read, Write, Seek.
What is Metadata?
It is not data itself, but info that describes properties of data.
Oprtns on dirs?
Search: find a particular file w/in dir.
Create: Add a new entry to dir.
Delete: Remove an entry from dir.
List dir: Return file names and reqed attrs of entries.
Update dir: Record a change to some file's attrs.
Dir is file in OS perspective.
What is a Link?
A ptr to another file or subdir.
2 Types: Symbolic & Hard Links
What is Symbolic (Soft) Link?
Dir entry contains true path to file.
What is Hard Link?
2nd dir entry identical to 1st.
A dir can be deleted iff count = 0.
Path Name Translation
Root: /
Movement of head of hard disk is very slow and time-consuming.
If master block is lost, all files are lost, but OS keeps multiple copies of master block.
How to represent protection?
What is Subj and Obj?
Subj: User
Obj: File/Dir
What is ACL?
"Access Control List"
For each obj, maintain a list of subjs and their permitted actions.
What is Capability?
For each subj, maintain a list of objs and their permitted actions.
How to implement a file sys?
1. Linear List
Simple list of file names and ptrs to data blocks.
Requires linear search to find entries.
Easy to implement, slow to execute.
Dir oprtns are freq.
2. Hash Table
Add hash data structure to linear list.
Hash file name to get ptr to entry in linear list.
What are disk layout strategies?
Files span multiple disk blocks.
How to find all blocks for a file?
1. Contiguous allocation
Like memory
Fast, simplifies dir access
Inflexible, causes fragmentation, needs compaction.
2. Linked, or chained, structure.
Each block points to next, dir points to 1st.
Good for seq access, bad for all others.
Con: 1. Hard to read from mid, need to traverse from beginning, 2. if mid 1 is lost: lost all data after that.
Indexd Structure (indirection, hierarchy)
An "index block" contains ptrs to many other blocks
Handles rand better, stil good for seq.
May need multiple index blocks (linked together)
Con: Space, but not very large so we can afford it.
What is Unix Inode?
Unix inodes implement an indexed structure for files.
Each inode contains 15 block ptrs.
1st 12 are direct block ptrs (e.g. 4KB data blocks).
Then single, double, and triple indirect.
What is File Buffer Cache?
Cache file blocks in memory to capture locality.
File buffer cache competes with vm.
Like vm, it has limited size.
Need replacement algos again (LRU usually used).

369 Lecture 9

What is Secondary Storage?
Anything outside of primary memory.
Anything that does not permit direct instruction execution or data fetch via machine load/store instructions.
Is persistent: Data survives loss of power.
How to read disk?
Plater is used to keep data.
1. Seek
2. Rotate
3. Read
Seq access is a lot faster than rand access.
Why mixing workloads can be tricky?
Need a lot of time to seek and rotate.
What are components of disk access time?
Dis req performance depends on 3 steps:
Seek: Moving disk arm to correct cylinder. Depends on how fast disk arm can move (increasing very slowly).
Rotate: Waiting for sector to rotate under head. Depends on rotation rate of disk (increasing very slowly).
Transfer: Transferring dta from surface into disk controller electronics, sending it back to host. Depends on density (increasing quickly).
What are OS design principles?
Minize # disk accesses. e.g. By caching.
Minize access cost when using disk.
What are Disk Scheduling algos?
What is FCFS?
"First Come First Serve"
Do nothing
Reasonable when load is low
Long waiting times for long req queues
What is SSTF?
"Shortest Seek Time First"
Minize arm movement (Seek time), maxize req rate
Favor mid blocks
Shortest distance from current location
Con: Need time to find shortest, and next after next may not be optimal
What is SCAN?
Like elevator
Service reqs in 1 direction until done, then reverse
What is C-SCAN?
Like typewriter
Like SCAN, but only go in 1 direction
What is LOOK/C-LOOK?
Like SCAN/C-SCAN but only go as for as last req in each direction (not full width of disk)
What are disk layout strategies?
Contiguous allocation.
Linked, or chained, structure (Con: Lose 1, lose all that come after)
Indexed structure (indirection, hierarchy)
What is indexed allocation?
Unix Inodes
Theyre NOT dirs
Each inode contains 15 block ptrs
1 block for every 4KB, so 48KB at most.
0-11: Direct ptrs
12: Single indirect
13: Double indirect
14: Triple indirect
What is implementation of file sys?
Master Block (Partition Control Block, Superblock): Determines location of root dir.
Free Map: Determines which blocks are free, allocated.
Remaining disk blocks used to store files and dirs.
What is LBN?
"Logical Block Number"
What is FFS?
"Fast File System"
A redesign.
Improved disk utilization, decreased response time.
What is Cylinder Group?
aka Allocation Group
Disk partitioned into groups of cylinders
Data blocks in same file allocated in same cylinder group
Files in same dir allocated in same cylinder group.
Inodes for files allocated in same cylinder group as file data blocks.
It decreases seeking time and increase utilization.
It provides closeness.
It reduces # long seeks
Free space requirement
To be able to allocate according to cylinder groups, disk must have free space scattered across cylinders.
10% of disk is reserved just for this purpose.
If preferred cylinder group is full, allocate from a nearby group.
What is LSF?
"Log Structured File System"
Write all file sys data in a continuous log.
Uses inodes and dirs from FFS.
Needs an inode map to find inodes.
An inode # is no longer a simple idx.
Cleaner reclaims space from overwritten or deleted blocks.
Reading is still very slow.
What is Linux Ext3 File Sys?
Extends ext2 w/ journaling capabilities
Designed as a separate, generic journaling layer
Journaling: To recover from crash
What is NTFS?
"New Tech File Sys"
From microsoft replaced old FAT file sys