Please enable JavaScript.

Coggle requires JavaScript to display documents.

OPERATING SYSTEMS OS3 (Multithreading (Challenges of Multicore (Dividing…

- - - - A system can perform more than one task simultaneously
      - Types
        
        Data parallelism
        
        Distributing subsets of a data set across multiple cores, same operation on each
        
        Think map/reduce
        
        Task parallelism
        
        Distributing threads across cores, each thread performing a unique operation
    - - more than one task making progress
      - This is what having multiple processes on a single core is
  - - - POSIX Pthreads
        
        can be user level or kernel level
        
        It is a specification, not an implementation
        
        Common in UNIX OSes
      - Win32 threads
      - Java threads
      - management done by user-level libraries
        
        Can be achieved by
        
        Library entirely in user space
        
        Kernel-level library supported by the OS
    - - Supported by the kernel
    - - Many to One
        
        many user threads, single kernel thread
        
        One thread blocking causes all to block
        
        Multiple threads may not run in parallel, because only one may be in the kernel at a time
      - One to One
        
        Each user thread gets a kernel thread
        
        No. of threads per process may be restricted
        
        Approach currently taken by Linux / Windows XP
      - Many to Many
        
        Allows the OS to create a sufficient number of kernel threads for the user threads
      - Two-level
        
        Essentially a Many to Many that allows a thread to be bound to a kernel thread (i.e. taking on a 1:1 like characteristic)
  - - - When you fork a process do you fork all threads or just the calling one?
        
        Linux: just the calling thread
      - exec just replaces the running process, including all threads
    - - Signals are used to notify a process that an event has occured
      - kill() system call
      - signal handlers can be default or user-defined (signal() system call)
      - Where should the signal be delivered to for multi-threaded applications?
        
        Deliver to the tread it applies to
        
        Deliver to all threads in the process
        
        Deliver to certain threads in the process (random in Linux)
        
        Assign a specific thread to receive all signals for the process
    - - Asynchronous cancellation
        
        terminate immediately
      - Deferred cancellation
        
        have the target check periodically if it should be cancelled
      - thread to be cancelled is the target thread
    - - Allows each thread to have its own copy of data
      - Useful if you don't have control of the thread creation process, like when using Thread Pools
      - Not local variables, TLS are visible across function executions
    - - Many to Many and Two Level require communication to maintain an appropriate number of kernel threads
      - LWP - Lightweight Process
        
        Intermediate data structure between user and kernel threads
        
        Appears as a virtual processor that a process can schedule a user thread to run on
      - upcalls
        
        a communication mechanism from kernel to the upcall handler
        
        allows the application to maintain the correct number of kernel threads
  - - - PCS - Process Contention Scope
        
        scheduling competition is within the process
    - - SCS - System Contention Scope
        
        competition among all system threads
- - - - Provide access to internal systems
    - - Thin clients
      - like web terminals
  - - - LAN - Local Area Network
      - WAN - Wide Area Network
      - MAN - Metropolitan Area Network
      - PAN - Personal Area Network
    - - Provide basic features between systems across networks
      - Communication scheme to exchange messages
      - Give the illusion of a single system
  - - - Central lookup service
      - Broadcast / discovery protocols
  - - - Source CPU is different from target type
      - Slow
      - Example of when computer language cannot be turned into native code, it is interpreted
    - - OS natively compiled for the CPU, running as a guest OS
      - VMM - Virtual Machine Manager
        
        Can run as an application or as the OS itself - think VirtualBox vs ESX
  - - - Public Cloud - aka AWS
      - Private cloud - run by the company for it's own use
      - Hybrid cloud - includes both public and private cloud
    - - applications available via internet
    - - software stack ready for application to use via internet
      - example: a database server pre-made
    - - servers or storage available over the internet
      - Think S3
    - - Firewalls - internet security
      - Load balancers spread traffic across multiple applications
  - - - Types
        
        Hard
        
        Task must be serviced by its deadline
        
        Soft
        
        No guarantees as to when critical processes will be scheduled
      - Considerations
        
        Performance
        
        Interrupt latency
        
        Time from arrival of interrupt to start of routine that services interrupt
        
        Dispatch latency
        
        Time for schedule to take current process off CPU and switch to another
        
        Conflict phase
        
        Preemption of any processes that are running in kernel mode
        
        low priority processes release resources required by high priority ones
        
        Turnaround time
        
        Response time
        
        time from job released to job completion
        
        Deadline
        
        Relative
        
        absolute deadline - release time
        
        Absolute Deadline
        
        release time + relative deadline
        
        Priority
        
        Release time
        
        time taken from job submitted to being started
        
        sometimes there is "jitter" due to other factors
      - Algorithms
        
        Prioirty-based
        
        Only guarantees soft real-time
        
        Each process has a priority
        
        Rate Monotonic
        
        Priority assigned as inverse of the period between each execution of a process
        
        Short periods = higher priority
        
        EDF - Earliest Deadline First
        
        Priority assigned based on deadlines
        
        Earlier deadlines get higher priority
        
        Proportional Share Scheduling
        
        T shares are allocated among system processes
        
        application receives N shares
        
        application gets N / T of total processor time
      - Implementations
        
        POSIX
        
        SCHED_RR - time slicing occurs for threads of equal priority
        
        "scheduling policy"
        
        SCHED_FIFO - first come first serve
        
        Linux
        
        CFS - Completely Fair Scheduler
        
        Pick the process with lowest vruntime
        
        Per-task vruntime
        
        decay factor based on priority of task. Low priority, higher decay rate
      - "When a process starts or ends is part of its correctness"
        
        not finishing by deadline could cause incorrect / dangerous consequences
    - - Purely cyclic
        
        task executes periodically, demands do not vary from period to period
        
        digital controllers / real-time monitors
      - Mostly cyclic
        
        most tasks execute periodically, with some external tasks
        
        Avionics / process control systems
      - Asynchronous + predictable
        
        most tasks not periodic
        
        bounded ranges or known statistics
      - Asynchronous + unpredictable
        
        react to asynchronous events
        
        tasks with high run-time complexity
        
        intelligent, real time control systems
- - - - A program in execution
      - Requires resources - CPU, memory
      - Components
        
        Program Counter
        
        Represents the thread of execution
        
        One Program Counter per thread
        
        the address of the current instruction
        
        text section
        
        the program code itself
        
        Stack
        
        contains temporary data
        
        function parameters
        
        return addresses
        
        local variables
        
        Heap
        
        contains memory dynamically allocated at runtime
        
        Data section
        
        Contains global variables
        
        Process Control Block
        
        Information associated with each process
        
        Aka Task Control Block
        
        Contains
        
        Process State
        
        Program Counter
        
        CPU registers
        
        CPU scheduling information
        
        Memory management information
        
        Accounting information
        
        I/O status information
        
        Can store multiple thread information in same PCB
      - OS responsibilities
        
        Suspending / Resuming
        
        Synchronization
        
        Communication
        
        Processes are
        
        independent
        
        cannot be affected by the execution of other processes
        
        cooperating
        
        Information sharing
        
        Computation speedup
        
        Modularity
        
        Convenience
        
        can be affected by the execution of other processes
        
        IPC
        
        inter-process communication
        
        Two models
        
        Shared memory
        
        Producer-Consumer Problem
        
        2 more items...
        
        Message passing
        
        send(message)
        
        receive(message)
        
        must establish a communication link between processes
        
        2 more items...
        
        Client-Server
        
        Sockets
        
        "an endpoint for communication"
        
        Concatenation of IP address and port
        
        Communication between a pair of sockets
        
        loopback - 127.0.0.1 - refers to current running system
        
        Remote Procedure Calls
        
        Abstracts procedure calls between processes on networked systems
        
        Stubs
        
        client-side proxy for the actual procedure on the server
        
        locate the server
        
        marshall the parameters
        
        Examples
        
        MIDL - Microsoft Interface Definition Language
        
        XDL - External Data Representation
        
        OS provides a rendezvous or matchmaker service to connect client and server
        
        Pipes
        
        Acts as a "conduit" for processes communicating
        
        Issues with pipes
        
        Unidirectional or Bidirectional?
        
        if bidirectional: half or full duplex?
        
        Must there exist a parent/child relationship between processes?
        
        Can pipes be used over a network?
        
        Ordinary Pipes
        
        Standard producer/consumer style
        
        Producer writes to one end - write-end
        
        Consumer reads from the other - read-end
        
        Unidirectional
        
        Require parent-child relationships
        
        Named Pipes
        
        More powerful than ordinary pipes
        
        Bidirectional
        
        No parent-child relationship required
        
        Several processes can use named pipe for communication
        
        Available on UNIX and Windows
        
        Deadlock Handling
        
        Process Creation
        
        Processes are hierarchical - parent processes create child processes
        
        Each process has a process identifier (pid)
        
        Resource Sharing
        
        Parent and Child share all resources
        
        Children share a subset of parents' resources
        
        Parent and child share no resources
        
        Execution
        
        Parent and child execute concurrently
        
        Parent waits until children terminate
        
        UNIX
        
        fork() creates a new process
        
        exec() used after a fork() to replace the process' memory space with a new program
        
        Process Termination
        
        exit()
        
        Process finishes and asks the OS to delete it
        
        abort()
        
        Parent terminates execution of child
        
        cascading termination
        
        if a process is exiting, its child processes must be terminated also
        
        Zombie
        
        No parent waiting for process termination
        
        Orphan
        
        Child of a terminated parent
      - Also known as Jobs
      - States
        
        New
        
        Running
        
        Waiting
        
        Ready
        
        Terminated
      - SCHEDULING
        
        Maximise CPU use, switch processes onto CPU for time sharing
        
        Process scheduler
        
        Scheduling Queues
        
        Job queue
        
        All processes in the system
        
        Ready queue
        
        All processes in main memory waiting to execute
        
        Device queues
        
        set of processes waiting for an IO device
        
        Long vs Short term schedulers
        
        Long Term / job scheduler
        
        Selects which processes should be brought into the ready queue
        
        Invoked infrequently (seconds/minutes)
        
        Controls the "degree of multiprogramming"
        
        the maximum number of processes that a CPU can accommodate efficiently
        
        main limiting factor is the amount of memory available - more processes take up more memory, regardless of if they are executing or not
        
        Strive for a good process mix
        
        IO-bound - short bursts of CPU time
        
        CPU-bound - long bursts of CPU time
        
        Short-term / CPU scheduler
        
        selects which process should be executed next and sets it up on the CPU
        
        Sometimes the only scheduler on a system
        
        Invoked very frequently
        
        Must be fast
        
        Dispatcher
        
        Gives control of the CPU to the process
        
        switches context
        
        switches to user mode
        
        jump to proper location in program to resume execution
        
        Dispatch Latency
        
        1 more item...
        
        Criteria for Scheduling
        
        CPU utilization
        
        Throughput
        
        1 more item...
        
        Turnaround time
        
        1 more item...
        
        Waiting time
        
        1 more item...
        
        Response time
        
        1 more item...
        
        Scheduling Algorithms
        
        First come, First serve
        
        2 more items...
        
        SJF - Shortest Job First
        
        2 more items...
        
        Priority Scheduling
        
        2 more items...
        
        Round Robin
        
        5 more items...
        
        Multilevel Queue
        
        5 more items...
        
        Medium term scheduling
        
        used if the degree of multiprogramming must decrease
        
        Remove a process from memory, store on disk, bring back from disk, continue executing
        
        roll out, roll in
        
        priority based
        
        low priority processes swapped to disk in favor of high priority in memory
        
        Mobile Multitasking
        
        Mobile OSes allow more than one process
        
        iOS allows a singleforeground process and multople background processes to be running, but not on the display
        
        A lot of times there are limitations to this
        
        Context switching
        
        Must save the state of the old process and load the saved state for a new process
        
        Context is represented by the PCB
        
        Context-switch time is useless, the system does nothing useful, therefore it it critical that this is optimised
        
        The more complex the OS / PCB, the longer the context-switch time
        
        Linux Scheduling
        
        Priority ranges
        
        Real-time 0-99
        
        Normal 100-140
        
        CFS - Completely Fair Scheduler
        
        Based on proportion of CPU time, not time quantums
        
        Pick highest priority task in highest scheduling class
        
        Uses the "nice" value to calculate the time quantum for a given task
        
        ranges from -20 to +19
        
        -20 maps to global priority 100, +10 maps to global priority 139
        
        each task has virtual run time vruntime
        
        default priority = actual run time
        
        associated with the decay factor based on the priority of the task
        
        scheduler picks the task with lowest vruntime
  - - - User-mode
      - Kernel-mode
        
        Used to run privileged instructions
        
        Entered by means of a System Call
  - - - Base and Limit Registers
        
        Base - the first address
        
        The no. of addresses sequentially that are allocated to this process
        
        Allows the OS to protect another process from reading a process' memory
    - - Compiled code addresses "bind" to relocatable addresses
      - Can happen at different stages
        
        Compile Time
        
        ABSOLUTE CODE
        
        Must recompile if starting location changes
        
        Load time
        
        RELOCATABLE CODE
        
        Execution time
        
        Bind is delayed until runtime if the process can be moved in memory during execution
      - Linking
        
        Static Linking
        
        System libraries and program code combined into one binary program
        
        Dynamic Linking
        
        Linking postponed until execution time
        
        STUB
        
        used to locate the appropriate library routine
        
        Replaces itself with the address of the routine
        
        If the routine is not in the process' memory address range, if it's not, add it
        
        Versioning is a concern
    - - Logical Address
        
        Generated by CPU
        
        Aka virtual address
      - Physical address
        
        The actual address seen by the MMU
      - Are equivalent for Compile or Load time binding
      - Are different for execution-time binding
      - MMU - Memory Management Unit
        
        Maps Virtual to Physical addresses
        
        Methods
        
        Relocaiton / Base register
        
        Register provides offset from zero in physical memory that the virtual addresses have
        
        Dynamic Loading
        
        Routine is not loaded until called
        
        Routines kept on disk in relocatable format
        
        Useful for infrequently occurring cases
        
        No special OS support required
      - Contiguous Allocation
        
        Multiple-partitions
        
        Operating System memory
        
        User processes
        
        Held in high memory addresses
        
        Single contiguous block per process
        
        Degree of Multiprogramming limited by no. of partitions
        
        Variable partition sizes
        
        Provide efficiency
        
        Hole
        
        Block of available memory
        
        Scattered throughout memory
        
        Process allocated to a hole large enough to house it
        
        Dynamic Storage-Allocation Problem
        
        First-fit
        
        Find the first hole that is big enough
        
        Best-fit
        
        Allocate the smallest hole that is big enough
        
        Worst-fit
        
        Allocate the largest hole
        
        Fragmentation
        
        External
        
        the total memory space exists to satisfy a request, but is not contiguous
        
        Reduced by Compaction
        
        3 more items...
        
        Internal
        
        Allocated memory may be larger than requested memory, so there is some free capacity that is not being used within the partition
        
        Up to 50% of blocks may be unusable due to fragmentation
        
        Backing store also has Fragmentation problems
        
        Segmentation
        
        A program is a collection of segments
        
        Segment table
        
        Base - starting physical address
        
        Limit - length of the segment
        
        STBR
        
        Segment Table Base Register
        
        Points to the Segment Table in memory
        
        STLR
        
        Segment Table Length Register
        
        No. of segments used by a program
        
        Segment no n is valid if s < STLR
        
        Protection bits
        
        code sharing occurs at segment level
        
        valid-invalid bit
        
        1 more item...
        
        Paging
        
        Physical address space of a process can be non-contiguous
        
        Avoids external fragmentation
        
        avoids varying sized memory chunks problems
        
        Frames
        
        Divisions of PHYSICAL memory
        
        Fixed size
        
        Pages
        
        Divisions of LOGICAL memory
        
        Fixed size
        
        To run a program of N pages, need N free frames
        
        Page Tables
        
        Index - Page Number (p)
        
        Page offset (d)
        
        1 more item...
        
        Worst case fragmentation = 1 frame - 1 byte
        
        Average fragmentation = 1/2 frame size
        
        IMPLEMENTATION
        
        5 more items...
        
        Still have internal fragmentation
        
        Virtual Address Space
        
        Demand Paging
        
        10 more items...
        
        Memory-Mapped files
        
        6 more items...
        
        Relocation registers
        
        allows kernel code to be transient, changing location
  - - - Directories
      - Access control
      - Creating/deleting files
      - Backup files onto non-volatile memory
      - Free space management
      - Storage acllocation
      - Disk scheduling
    - - Making sure that all CPUs have the latest value in their cache
  - - - Memory
        
        Memory management of IO
        
        spoolling - output of one job | input of another aka piping
        
        caching
        
        buffering
        
        devices have registers where driver can place commands, addresses, data etc
        
        Devices have addresses
        
        Direct I/O instructions
        
        Memory-mapped I/O
        
        Direct Memory Access
        
        Programmed I/O
        
        one byte at a time being transferred
        
        useful for large amounts of data
        
        Bypass the CPU to transfer data directly between device and memory
        
        Done by DMA controller, which reads instructions from the DMA command block in memory
        
        "grabs" the bus from the CPU, interrupts when done
      - Port
        
        connection point for device
      - Bus
        
        daisy chain
        
        shared direct access
      - Controller / host-adapter
        
        electronics that operate port, bus, device
        
        integrated or separate circuit board
    - - Polling
        
        Busy-wait cycle to wait for I/O from the device
        
        good if device fast
        
        what if CPU switches context, misses a cycle and data is overwritten / lost?
      - Interrupts
        
        Interrupt-request line
        
        a wire/connection that the I/O device can trigger an interrupt with
        
        received by interrupt handler - can be masked to ignore/delay interrupts
        
        Use interrupt vector to dispatch interrupt to the correct handler
        
        Must context switch at start and end of the handler
        
        Based on priority
        
        Some nonmaskable - you must actually do the interrupt
        
        interrupt CHAINING if there's more than one device at the same interrupt number
    - - Block I/O
        
        e.g. Disk Drives
        
        Raw I/O
        
        direct I/O
        
        file-system access
        
        capable of memory-mapped file access
        
        DMA
      - Character I/O (stream)
        
        keyboards, mice, serial ports
        
        get(), put()
        
        Libraries allow line editing
      - Memory-mapped file access
      - Network sockets
        
        Separate network protocol from operation
        
        Approaches vary widely
    - - Blocking
        
        process suspended until I/O complete
        
        Easy to use
        
        Inefficient
      - Nonblocking
        
        I/O call returns as much as available
        
        Implemented by multi-threading
        
        select() to find if data is ready
      - Asynchronous
        
        Process runs while I/O executes
        
        Difficult to use
        
        I/O subsystem signals process when I/O is done
    - - Scheduling
        
        I/O request ordering via per-device request queue
        
        Quality of Service
        
        Fairness
      - Buffering
        
        store data in memory while transferring between devices
        
        cope with device speed difference
        
        cope with transfer size mismatch
        
        maintain copy semantics
        
        Double Buffering
        
        buffering done at user and kernel level
        
        full - being processed
        
        not-full - being used
        
        copy on write can be used in some cases
      - Caching
        
        faster device holding a copy of data
        
        sometimes combined with buffering
      - Spooling
        
        hold output for a device if it can only service one thing at a time
        
        think: a printer
      - Device reservation
        
        exclusive access to a device for one process
        
        done by system calls
        
        be careful of deadlock
      - Protection
        
        all I/O instructions must be considered privileged
        
        I/O must be performed by system calls
        
        most I/O devices return an error when I/O request fails
      - Data structures
        
        keep state for i/o components
        
        open file tables
        
        network connections
        
        character device state
        
        to track buffers, memory allocation, dirty blocks
        
        object oriented methods / message passing to implement I/O
    - - full-duplex communication channel
      - Components
        
        stream head
        
        interfaces with the user process
        
        driver end
        
        interfaces with the device
        
        Modules
        
        zero or more
        
        modules to facilitate communication
        
        each have a read queue and write queue
        
        message passing used to communicate between queues
        
        flow control option to indicate available/busy
      - Are internally asynchronous, but user process interacting with stream head is synchronous
    - - Reduce number of context switches
      - Reduce data copying
      - Reduce interrupts
        
        large transfers
        
        smart controllers
        
        polling
      - Use DMA
      - Use smarter hardware
      - Move user-mode processes/daemons to kernel threads
  - - - Name
      - associated number
    - - allows a set of users to be defined
      - can be associated with each process/file
    - - Allowing user to change to an effective ID with more rights
- - - - Not difided into modules
      - Provide most functionality in least space
    - - Limited by hardware functionality
      - Limited structure
      - Systems programs
      - The kernel
    - - Bottom layer is hardware
      - Top layer is user interface
    - - Moves as much from the kernel into the user space
      - Example: Mach - Mac OSX is partly based on this
      - Communicaiton takes place using message passing between user modules
      - Benefits
        
        Easy to extend
        
        Easier to port to new architectures
        
        More reliable - less code is running in kernel mode
        
        Mores secure
      - Detriments
        
        Performance overhead of user space to kernel space communication
    - - loadable kernel modules
      - Object-oriented approach
      - Each core component is separate
      - Each talks to the other over known interfaces
      - Each is loadable as needed with kernel
      - Similar to layers, but more flexible
    - - Combine multiple methods to address performance, security, usability needs
  - - - Applicaiton failure
      - App memory
    - - OS Failure
      - Kernel memory
- - - - Data
      - Program
    - - Name
      - Identifier
      - Type
      - Location
      - Size
      - Protection
      - Time, date, user identification
      - Extended file attributes
    - - Create
      - Write
      - Read
      - Seek - reposition within file
      - Delete
      - Truncate
      - Open
      - Close
    - - Simple record structure
        
        Lines
        
        Fixed length
        
        Variable length
      - Complex structure
        
        Formatted document
        
        Relocatable load file
    - - Sequential
        
        read next
        
        write next
        
        reset
      - Direct Access
        
        read n
        
        write n
        
        position to n
        
        read next
        
        write next
        
        rewrite n
        
        Can simulate sequential access on a direct-access file
        
        reset: cp = 0
        
        read next: read cp: cp++
        
        write next: write cp: cp++
      - Other
        
        Usually require an index for the file
        
        Keep index in memory
  - - - No of times a file is open
      - Allows removal from open-file table when the last process closes it
    - - Similar to reader-writer locks
      - Shared lock
        
        several processes can acquire concurrently
      - Exclusive lock
        
        writer lock, only one process can acquire
      - Mandatory
        
        access denied depending on locks held and requested
      - Advisory
        
        Process can check lock status and decide what to do
  - - - Partitions
        
        Can be RAID - protected against failure
        
        Raw
        
        Unformatted
        
        Formatted
        
        With a file system
        
        Known as VOLUME
    - - Search
      - Create file
      - Delete file
      - List
      - Rename file
      - Traverse file system
    - - Efficiency
      - Naming convenient to users
      - Grouping
    - - Single-level
        
        a single index points to a file
        
        Naming problem - no two files can be called the same
        
        Grouping problem
      - Two-level
        
        Different directories for different users - solves naming problem
        
        No grouping capability
      - Tree-structured
        
        Efficient to search through - binary search tree
        
        Grouping capability - make a subdirectory
        
        concept of working directory
        
        absolute or relative paths
      - Acyclic Graph Directories
        
        Can have shared sub directories and files
        
        Two different names for the same file (aliasing)
        
        Problem of "dangling pointers" when a file gets deleted
        
        Backpointers, so delete all pointers
        
        Backpointers using a "daisy chain" organisation
        
        Entry-hold-count
        
        Link - pointer to file
        
        Resolve the link
      - General Graph Directory
        
        How to guarantee no cycles?
        
        Only allow links to files, not subdirectories
        
        Garbage collection
        
        Use a cycle detection algorithm every time a new link is added
    - - Linear list of file names with pointer to data blocks
        
        Simple to program
        
        Time consuming - $$O(n)$$
      - Hash Table
        
        linear list with hash data structure
        
        Search time $$O(1)$$
        
        Collisions
        
        two file names hash to same location
        
        Keep entries fixed-size
        
        Use chained-overflow method
  - - - File owner/creator should be able to control
        
        what can be done
        
        by whom
      - Access Lists and Groups
        
        Owner access
        
        Group access
        
        Public access
    - - NFS - Network File System
      - FTP - File Transfer Protocol
      - WWW
      - Client-server model
        
        Server can serve multiple clients
        
        Client and user-on-client identification is insecure/complicated
        
        NFS - Unix Standard
        
        CIFS - Windows Standard
        
        OS file calls are translated into remote calls
      - Distributed Naming Services
        
        LDAP
        
        DNS
        
        Active Directory
    - - All file systems have failure modes
        
        corruption of metadata
      - Network Failure
      - Server Failure
      - Combated by having Stateless protocols such as NFSv3
        
        Easy recovery
        
        Less security
    - - How to allow multiple users to access a shared file simultanously
  - - - manage I/O devices and I/O control layer
      - read drive 1, cylinder 72, track 2, sector 10 into mem location 11234
    - - retrieve block x
      - manages memory buffers and caches
    - - understands files, logical address, physical blocks
      - Logical block -> Physical block
      - Manages free space, disk allocation
    - - Translates file name into file number, handle, location
      - File control blocks - inodes in UNIX
      - Directory management
      - Protection
    - - Boot control block
        
        info needed by system to boot OS from that volume
        
        usually the first block of the volume
        
        required if you plan to boot OS from volume
      - Volume control block
        
        Superblock
        
        Master file table
        
        Contains volume details
        
        Total no of blocks, no of free blocks, block size, free block pointers etc
      - File Control Block
        
        One per file
        
        Inode number
        
        permissions
        
        size
        
        dates
        
        (NTFS stores this as part of master table)
      - In-memory
        
        Mount-table storing file system mounts
        
        Buffers to hold data blocks
        
        File handles
        
        Data eventually read will be stored in user process memory
      - Must have a root partition, others can be loaded automatically or manually
      - fsck - file system consistency check
        
        if not fix it and try again
        
        if yes, add to mount table
        
        compares data in directory structure with blocks on disk, tries to fix inconsistencies
        
        use system programs to back up data from a disk to something else
        
        Recover lost file by restoring data from backup
      - Virtual File System
        
        Object Oriented way of implementing file systems
        
        Allows same system call interface to be used for different types of file systems
        
        Separates FS generics from implementation details
        
        Linux
        
        inode
        
        file
        
        superblock
        
        dentry
        
        defines a set of operations that must be implemented
      - Allocation Methods
        
        Contiguous
        
        Each file occupies a set of contiguous blocks
        
        Performance
        
        Best performance in MOST cases
        
        Good for sequential and random
        
        Simple to implement
        
        starting location
        
        no. of blocks
        
        Problems
        
        finding space for a file
        
        external fragmentation
        
        compaction
        
        off-line (downtime)
        
        on-line
        
        Extent-Based
        
        Allocate disk blocks in "extents"
        
        Extent
        
        contiguous set of blocks
        
        extents allocated for file allocation
        
        file consists of one or more extents
        
        Linked
        
        Each file is a linked list of blocks
        
        File ends at nil pointer
        
        no external fragmentation or compaction required
        
        Reliability a problem
        
        Locating a block can take a lot of IO time and disk seeks
        
        FAT - File Allocation Table
        
        Beginning of volume has a table, indexed by block number, points to next block
        
        Faster on disk, cacheable
        
        New block allocation is simple
        
        Performance
        
        Good for sequential
        
        Not good for random
        
        Indexed
        
        Each file has its own index block of pointers to it's data blocks
        
        Need an index table
        
        Random access
        
        Dynamic access without external fragmentation, but overhead of index
        
        Mapping
        
        Linked
        
        Link blocks of index table
        
        Two level index
        
        have two levels of indexing
        
        Performance
        
        single access could require 2 index block reads then data block read
        
        Clustering can help improve throughput, reduce CPU overhead
      - Free Space Management
        
        free-space list
        
        tracks available blocks/clusters
        
        Bit vector / bit map
        
        requires extra space
        
        block size of 4KB, disk size 1 TB , n = 2^40 / 2^12 = 2^28 = 256MB. If clusters of 4 blocks -> 64mb taken up by bit map
        
        Linked list
        
        cannot get contiguous space easily
        
        no waste of space
        
        no need to traverse the entire list if # of free blocks is recorded
        
        Grouping
        
        Linked list to store address of next n-1 free blocks in first free block, plus a pointer to next block that contains free-block pointers
        
        Counting
        
        Keep address of first free block and count of following free blocks
        
        Free space list has entries containing addresses and counts
        
        Space Maps
        
        Used by ZFS
        
        Bit maps can't fit in memory for very large file systems
        
        Divide space into metaslab units
        
        each has an associated space map
        
        uses counting algorithm
        
        records to log file
        
        Efficiency and Performance
        
        Efficiency
        
        Dependent on
        
        Types of data kept in file's directory entry
        
        pre-allocation or as-needed allocation of metadata
        
        Fixed-size or varying-size data structures
        
        Disk allocaiton / directory algorithms
        
        Performance
        
        Dependent on
        
        Keeping data and metadata close
        
        Buffer cache
        
        separate section of memory for frequently used blocks
        
        Synchronous writes
        
        no buffering/caching
        
        Asynchronous writes are more common - bufferable, faster
        
        Free-behind and read-achead
        
        Reads slower than writes
        
        Page Cache
        
        Cache memory pages rather than disk blocks
        
        Memory-mapped I/O caching technique
        
        I/O through file system uses the buffer cache
        
        Unified Buffer Cache
        
        uses the same page cache to cache both memory mapped pages and ordinary file system I/O
        
        Avoids double-caching
        
        What caches get priority?
        
        What replacement algorithm to use?
      - Log Structured File Systems
        
        Journaling
        
        Record each metadata update as a transaction
        
        All transactions written to log
        
        Sometimes the log is a separate device, or different section of disk
        
        Transactions are asynchronously written to file system
        
        If file system crashes, all remaining transactions must be performed
        
        Faster recovery from crash, removes inconsistency of metadata
- - - - asdfasdfasd
- - - - Moves data to/from buffers and main memory
    - - Random-access
      - Volatile
    - - Device Controller
        
        INTERRUPTS
        
        TRAP or EXCEPTION are user-generated Interrupts
        
        Interrupt Vector
        
        Interrupts and addresses of the subroutine handlers
        
        Controls one type of device
        
        has a local buffer
  - - - Runs at startup to load the Kernel
      - Stored In...
        
        ROM (Read Only Memory)
        
        EPROM (Erasable Programmable Read Only Memory)
      - Example: GRUB
      - Once kernel loads, the system is running
    - - "the one program always running on a computer"
- - - - CLI
        
        Command Line Interpreter
        
        Sometimes in kernel, sometimes in system program
        
        multiple flavours, shells
      - GUI
        
        Desktop
        
        WIMP
        
        Windows Icons Menus Pointer
        
        Directories / Folders / Icons
  - - - Win32 API
      - POSIX API
      - Java API for JVM
    - - each call has a number
      - System-call interface maintains a table of these numbers
      - Invokes system call in kernel
      - The call must obey the API specification, otherwise the caller need not know anything about it
    - - Passs parameters in registers
        
        But what if there are more parameters than registers?
      - Parameters stored in block/table in memory, and address passed via a register
      - Parameters pushed onto the stack by program and popped by OS
  - - - Some systems have a registry used to fetch information
    - - Basic text editors
      - Commands to transform text
    - - compilers
      - assemblers
      - debuggers
      - interpreters
    - - Web browsers
      - Sending messages
      - email
    - - Services, subsystems, daemons
      - Launch at boot time
      - Run in a user context, not kernel context
- - - - access time is independent of location of the processor
    - - Processor can access its own memory faster than it can that of others
  - - - One active, others standby
    - - multiple active nodes
- - - - The critical section is when shared/common variables/objects are updated
      - Each process asks for permission in the entry section, leaves the critical section with the exit section and then continues with remainder section
      - Solution must have
        
        Mutual Exclusion
        
        No other process can be in its' critical section if one process is in it
        
        Progress
        
        If no process is executing its critical section, then you cannot postpone the entry to the critical section indefinitely
        
        Bounded Waiting
        
        A bound must exist on the no of times that other processes can enter critical section before the request is granted
      - Approaches
        
        Preemptive
        
        Non-preemptive
      - In a system of n processes, only one process may be in it's critical section at a time
    - - Protecting critical sections by locking
      - Uniprocessors
        
        Disable interrupts temporarily
        
        Inefficient on multiprocessor systems
      - Atomic hardware instructions
        
        Atomic = non-interruptible
        
        test and set memory value
        
        swap contents of two memory words
    - - Mutex Locks
        
        Busy waiting - spinlock
        
        acquire() and release()
      - Semaphores
        
        Do not require busy waiting
        
        wait() and signal()
        
        Counting semaphore
        
        Integer value over an unrestricted domain
        
        Binary semaphore
        
        Can only range between 0 and 1
        
        Is a mutex lock
        
        Must guarantee that no two processes can execute wait() and signal() on the same semaphore at the same time
        
        critical section problem
        
        busy waiting implementation
        
        code is short
        
        very rarely ever triggered
        
        waiting queue
        
        each entry has
        
        value
        
        pointer to next record
        
        block()
        
        1 more item...
        
        wakeup()
        
        1 more item...
        
        Problems
        
        Incorrect use of operations
        
        signal then wait
        
        wait then wait
        
        ommiting of either wait or signal or both
        
        Deadlock and starvation
      - Examples
        
        Linux
        
        semaphores
        
        spinlocks
        
        reader-writer semaphore
        
        reader-writer spinlocks
        
        PThreads
        
        mutex locks
        
        condition variables
        
        read-write locks - non-portable
        
        spinlocks (non-portable)
    - - Bounded-buffer
        
        ?
      - Readers and Writers
        
        Allow multiple readers to read at the same time, but only one writer to write at a time
        
        must have a read-write mutex as well as a read mutex
        
        All variations may still suffer from starvation
        
        Can be solved by providing kernel reader-writer locks
      - Dining-Philosophers
  - - - a process may never be removed from the semaphore queue in which it is suspended
    - - lower-priority process holds a lock needed by higher-prioirty process
    - - Traffic can only flow in one direction over the bridge
      - Cars are head to head
      - Deadlock only solved by one car (or one side of cars) backing up
    - - Resource types $$R_i$$
      - Instances of resource $$W_i$$
      - Utilise a resource by
        
        request
        
        use
        
        release
    - - Mutual exclusion
        
        only one process can use a resource at a time
      - Hold and wait
        
        a process holding one resource is waiting to acquire additional resources held by other processes
      - No preemption
        
        a resource can be released only voluntarily by the process holding it
      - Circular wait
        
        P0 is waiting for a resource held by P1, P1 waiting for P2 ... Pn waiting for resource held by P0
    - - Resource Allocation Graph
        
        Vertices partitioned into two types
        
        P = the set of all processes in the system
        
        R the set of all resource types in the system
        
        request edge
        
        directed edge
        
        assignment edge
        
        directed edge
        
        if it contains no cycles
        
        no deadlock - YAY
        
        if it contains a cycle
        
        if there's only one instance per resource type
        
        definite deadlock
        
        if there's multiple instances of a resource type
        
        not definite, but a chance of deadlock
      - Ensure the system will never enter a deadlock state
        
        Mutual Exclusion
        
        not required for shareable resources
        
        must have for non-shareable resources
        
        Hold and Wait
        
        Guarantee that when a process requests a resource, it doesn't hold any other resources
        
        Require the process to request and be allocated resources before execution
        
        Allow the process to request resources only when it has none
        
        Starvation possible, low utilization
        
        No preemption
        
        If a process requests an unavailable resource, all the resources it currently holds are released
        
        Preempted resources are added to a resource waiting list for the process
        
        Process restarted once it can have access to it's old resources as well as the requested one
        
        Circular Wait
        
        Impose a total ordering of all resource types, require that each process requests resources in an increasing number of enumeration
        
        This way Pn cannot refer back to P0
        
        Deadlock Avoidance Algorithm
        
        Must have some a priori information
        
        Requires process declare the maximum number of resources that it may need
        
        Dynamically examines the resource allocation state to ensure there cannot be a circular-wait
        
        Resource allocation state
        
        The max number of allocated resources
        
        The max demands of the processes
        
        Safe State
        
        exists when all the processes that request resources can still be satisfied by the currently available resource + resources held by processes with a smaller number
        
        If Pi resource needs are not met, then Pi can wait until all Pj processes have finished (j < i)
        
        No deadlocks if in Safe state
        
        Deadlock avoidance: ensure system never enters an unsafe state
        
        Algorithms
        
        Single instance of a resource type
        
        Resource-allocation graph
        
        (see before)
        
        The request can only be granted if converting the request edge to an assignment edge does not make a cycle in the graph
        
        Multiple instances of a resource
        
        Banker's Algorithm
        
        Each process must claim maximum use a priori
        
        when a process requests a resource, it may have to wait
        
        When a process gets all its resources it must return them in a finite amount of time
        
        Data Structures
        
        4 more items...
        
        Safety Algorithm
        
        4 more items...
      - Allow the system to enter deadlock and then recover
        
        Deadlock Detection Algorithm
        
        single instance of resources
        
        Wait-for graph
        
        Nodes are processes
        
        directed edges are processes waiting for another process
        
        Multiple instances of resources
        
        variation of Banker's
        
        Available
        
        Allocation
        
        Request
        
        Request[i, j] = k means Pi requests k more Rj
        
        For every process, if the allocation is not zero, mark the process as unfinished, else mark as finished
        
        Find an i that satisfied Pi is not finished and Request_i is <= Work
        
        1 more item...
        
        $$O(m n^2)$$
        
        Recovery
        
        Process Termination
        
        Abort all deadlocked processes
        
        Abort one process at a time until the deadlock cycle is eliminated
        
        What order? What processes can/should we abort?
        
        Preemption
        
        Pick a victim
        
        Starvation - the same process may always be picked as the victim
        
        Rollback to a safe state, restart the process at that state
      - Ignore the problem and pretend that deadlocks never occur in the system
        
        used by most OSes, including UNIX