Please enable JavaScript.

Coggle requires JavaScript to display documents.

Operating System (Shnchorization (Mechanism (Semephore (Alternative…

- - - - Signal(), V()
      - Wait(), P()
      - Has memory (i: int, l: list)
      - signal & wait needs sync for their impletation
      - Alternative
        
        Wait() -. check s ==0 block, else --
        
        Signal - check pros == 0, if ++, else unblock
      - Classic
        
        Wait(): --s, check if <0, if block,
        
        signal: ++s, check if process empty, if not, unblock one
    - - Peterson
      - Test & Set (locks the memory bus)
  - - - Process owns resource (r -> p)
      - Process wants resources (p -> r)
    - - Deadlock Prevention
        
        Remove one deadlock condition
      - Deadlock Avoidance
        
        Avoid situations that lead to deadlock
        
        Banker(safe and unsafe state)
        
        Safe State: certain order of process so that deadlock can be avoid
        
        Unsafe: deadlock possible but not certain
        
        Need maximum resource req
      - Deadlock Dection
    - - Mutual Exclusion
        
        counter: relax when sharing is possible
      - Hold-and-wait
        
        Get all resource simutaneously
      - No Preemption
        
        allow preemption
      - Circular Wait
  - - - At most one process in a CS
      - CANNOT Prevent Entry if no others in CSD
      - Should eventually get into CS
      - No assumption about CPU spped
- - - - Size is determined by RAM
        
        Has offset same as physical memory
    - - Virtual Table Entry(VTE)
      - Size is determined by ISA
        
        Has offset same as virtual memory
    - - Page Table Entry
        
        Physical address of physical frame
        
        other bits
        
        dirty
        
        valid
        
        access control
        
        control caching
- - - - Run a program
        
        Provide Machine Abstraction
        
        Desired illution
        
        Manage Resource
        
        Mechansim
        
        How to create illution
        
        Policy
        
        how to use mechanism for different goal
    - - Def: A running program with memory
      - Resource
        
        CPU
        
        Memory
        
        State: Context(stored in kernel)
        
        CPU Context
        
        PC
        
        SP
        
        Top of the stack
        
        Memory Context
        
        Stack record
        
        Return Address
        
        Link to previous record
        
        Automatic Var
        
        Others
        
        Text
        
        Data
      - Multi-Programming
        
        Cause: A running prod could not proceed due to lack of resource
        
        Yield() to other proc
        
        Context Switching
        
        Save current content
        
        Load the context of other process
        
        Make system call / interrupt
        
        change from user to kernel mode
        
        Issue trap instruction
      - User Level
        
        Use user space
        
        User "TRAP" to tap in kernel space
      - Kernel Level
        
        System Call()
        
        Fork()
        
        Yield()
        
        Read()
        
        Write()
        
        ForkedThread()
      - Characterized State
        
        Running
        
        Readt
        
        Block
    - - Reason: 1 Kernel Cannot fail
      - Reason2: number of process in kernel is limited
    - - path of execution w/o memory
        
        Part of process
      - Thread Management func is in Kernel
        
        Thread Context Switching
        
        Thread Scheduling
      - Needs USER and KERNEL stack
      - Kernel Schedule threads on different CPU
      - User level thread
        
        Management at user level and kernel does not know
        
        Context Switching happen in user-level
        
        Support by library regardless kernel
        
        No True parallelism
      - Kernel Level thread
        
        True Parallelism
        
        Context Switch requires kernel call ( overhead)
- - - - Caused by external events: I/O finished, timer expire
      - Asyn
      - Example
        
        software interrupt
        
        Async Trap
        
        Async or deferred procedual call
    - - Caused by from instruction
      - Sync
      - Example
        
        fault
        
        Handling
        
        fixed the exception condition, return to faulting context
        
        Insert Page
        
        notifying the process
        
        UNIX: signal
        
        Win: user mode Async Proc Call
        
        Kernel: unrecoverable faults
        
        If Kernel fails
        
        1 more item...
        
        syscall trap
  - - - Something went wrong
    - - scheduled by OS or App
- - - - Same Arrival Time
      - Different Arrival Time
        
        Round Robin
        
        No starvation
        
        Wait at most (n-1) quant
        
        SRT( Shortest Remain Time)
        
        Optimal for preemptive
        
        Allow Starvation
        
        Assuming Service Time is known
        
        Multi-level feedback Queues
        
        Each level, from 0 to high, for 2^k quant
        
        Used 2^k , move to lower level
        
        Used less than 2^k, remain the same level
        
        Possible Starvation
        
        ProrityScheduling
        
        Based on priotity
        
        Possible Starvation
        
        Fair Share
        
        Minimal actual / request go first
        
        util over long time, will be close to requested
        
        Inefficient,
        
        Strike Scheudling
        
        use passval
        
        use strike = 1/request
        
        optimized
        
        reduce float calculation
    - - Different Arrival Time
        
        FCFS(
        
        Simple. no starvation
        
        bad for short process
        
        SPN (Shortest Process Next)
        
        OPTIMAL for non-preemptive
        
        Allow starvation
        
        Assuming service time is known
      - Same Arrival Time
        
        Shortest-First(OPTIMAL Turnaround Time)
        
        Longest First
    - - Periodic
        
        C: CPU, T = period, U = C/T
        
        EDF(Earliest Deadline First)
        
        Preemptive
        
        100% util
        
        Inefficient (slow)
        
        RMS(Rate Monotonic Scheduling)
        
        Rate = 1/period
        
        Sum of util of all process is less than n (2^(1/n-1)
        
        Yes, then pass RMS test and vice versa
        
        Static based on rate(priority)
        
        OPTIMAL for static priority algo
        
        Gurantee upper bound of util
        
        If rms TEST PASS, Then deadline under util bound will be met