Please enable JavaScript.

Coggle requires JavaScript to display documents.

COMP3231 - Coggle Diagram

- - - - We also have a series of blocked queues for each kind of event, so we know what process to release
    - - Goes into the ready queue, and is picked up by the scheduler.
- - - - Either flush the TLB
      - or mark each entry with an address space ID.
  - - - Illegal address
      - Page is not resident
  - - - Page frame number
      - present/absent: valid mapping to the page
      - Protection
      - Modified: dirty bit
      - Referenced: page has been accessed
      - Caching Disabled
    - - 10 bit first level table, referencing tables
      - 10 bit second level table, referencing PTEs
    - - Array of sorted page numbers by frame number. The index is the page number.
      - Algo: compute hash of page number, extract index, get frame.
      - IPTs grow with RAM, not address space.
      - Doesn't handle sharing very well.
    - - Hash to VPN to index, and entry has both VPN and PFN, also a next for collisions.
      - Based on physical memory size.
      - Each frame can have more than one PTE.
  - - - Temporal Locality: recently accessed items are likely to be used again.
      - Spatial locality: says items near recently uses are likely to be referenced soon.
    - - Recovery: suspend a few processes.
  - - - Demand: load when called.
      - Pre-paging: preload in the hopes its needed.
    - - Optimal: remove that which won't be used for the longest.
      - FIFO: toss oldest page
      - Least Recently Used (LRU)
      - Clock Page Replacement: loop around clock, find first one that hasn't been used. Once you replace, reset 'used' bit.
        'used/Reference' bit simulated with valid bit in software
    - - Fixed
      - Variable
        
        Global Scope: OS keeps list of free frames
        
        Local Scope: given an allocation of frames to process. Reevaluate (if too slow, gain frame, if too fast, lose frame).
    - - Demand cleaning: write page out once its been selected for replacement.
      - Precleaning: pages are written out in batches. (in background, pagedaemon)
- - - - Attributes
      - Location
      - Ownership
  - - - None
      - Knowledge
      - Execution
      - REading
      - Appending
      - Updating
      - Changing Protection of other users
      - Deletion
      - Owners
- - - - Efficiency: I/O tends to be slower than main memory
      - Generality/Uniformity
    - - User level
      - Device Independet OS Software
      - Device Drivers
      - Interrupt Handlers
      - Hardware
    - - Can execute at any time, causing concurrency issues.
      - Steps
        
        Save Registers
        
        Set up stack
        
        Ack/Mask interrupt controller
        
        Run interrupt service process
        
        Load new/original process registers
        
        Re-enable interrupts
      - Top and Bottom
        
        Top: handles interrupts
        
        Bottom: deals with what the interrupts mean. Can be run on in-kernel threads
- - - - Use test and set to perform both operations at once.
      - Causes busy waiting, a solution to this being to sleep and wake up
    - - If the resource is not available it goes to sleep and puts a resource in a queue.
        The check is decrementing a counter, and seeing if the counter is below zero.
      - When a process releases a resource, it signals via the semaphore.
        It checks first by incrementing a counter, and checking if the counter is <=0
      - Wait and signal can't be interupted.
    - - Mutual exclusion implemented in the compiler
      - An object that contains the shared resource, as well as procedures that interact with it.
      - Only one thread allowed into the monitor. The rest are queued.
      - Conditional Variables
        
        Contains the wait and sleep functions
        
        Contains its own queues
        
        Can act as specific conditions for wakeup
- - - - A pointer to an open file
    - - Mode
      - File Pointer
      - Vnode
    - - Provides an interface to many FSs to combine them.
      - Data Types
        
        VFS: represents all FS types. Contains FS functions
        
        Vnode: represents inode of the file system underneath.
    - - Buffer: so multiple block writes can happen contiguously.
      - Cache: so less writes to the HDD happen.
  - - - Linked list in blocks. Stored in hard drive. Bad random access.
      - File Allocation Table: keep the linked list part in memory. A bit faster. Finding free blocks is slow
      - inode: blocks stored per file. Only keep open files in memory. Fast Random access. Allocated dynamically.
    - - Linked list on disk, in free blocks.
        
        can be reordered in background.
        
        only one block of pointers in main memory
      - Bit maps
        
        Too big for main memory.
        
        good for ext frag tho.
- - - - Consistency issues: when a cache saves data, the same references in other caches are invalidated.
      - Could also have a multilevel cache system, to lift cache to cache transfers off the bus.
  - - - OS runs on all processors
      - Load balanced between all CPU's
      - Issue: concurrency
        
        Make entire kernel a mutex (only one CPU at a time)
        
        Split kernel into smaller mutex's
  - - - Solution: store value in cache for all CPUs.
      - Spin on read of value. When the value is invalidated, race to main memory to perform TSL
    - - Spin if it will be spinning for less time than is the overhead for blocking.
      - Otherwise block
- - - - Goals:
        
        minimise response time
        
        Provide proportionality (short jobs short, long jobs long)
      - Round Robin Scheduling
        
        Given a timeslice to run in.
        
        Ready queue and regular timer interrupts
        
        Assumes equality
      - Priorities
        
        Like round robin, but with productivity levels.
        
        Multiple queues for each level
        
        UNIX Scheduler: priority = cpu usage + nice (given by user) + base (hardcoded in)
        High is bad, low is good.
    - - Goals:
        
        meet deadlines
        
        provide predictability
  - - - Multiple Queue SMP Scheduling
        
        Each CPU has a read queue.
        
        Processes asigned to CPUs.
        
        If empty ready queue, grabs from another CPUs.
- - - - T: transfer time for a block to device
      - C: computation time to process incoming blocks
      - M: copy kernel buffer to user buffer
- - - - Hold and Wait: Release if deadlock is caused and try again. Could cause livelock: constantly hitting deadlock, make no progress.
      - Circular Wait: Compute and detect deadlock and programatically prevent it. Commonly used for more critical systems.
    - - Detection: takes analysis through matrices for resources with capacity more than one.
      - Recovery
        
        Preemption: taking a resource away.
        
        Rollback: checkpoint preiodically and return to a previous checkpoint on deadlock.
        
        Kill the process: choose a process that can be rerun from beginning.
    - - Keep track of the state. The state be deemed safe or unsafe.
      - Safe: not deadlocked now, and there is a scheduling order that won't cause deadlock.
      - Bankers Algorithm: every time someone wants a resource, we check the state. If it will push us into an unsafe, we make them wait until its safe.
- - - - Equal sized partitions
        :red_cross: Internal fragmentation.
        :red_cross: Can't run if bigger than partition.
      - Variably sized at boot time
        Need to know the workload in advance
        
        Each partition has a queue
        :red_cross: Some partitions may be idle
        
        One queue, assign to whatever fits
        :red_cross: Increases internal fragmentation
    - - Free memory storage
        
        Linked list of available holes in address order:
        Holes are combined where possible
        
        Finding algorithms
        
        First-fit: find the best one that fits
        tends to allocate in one end of memory
        
        Next-fit: first-fit, but keep moving uniformly.
        Breaks up large free space
        
        Best-fit: choose smallest that fits
        Creates small unusable holes.
        
        Worst-fit: tries to fix best fit, doesn't.
        
        Compaction: removing external fragmentation.
        Generally requires hardware support.
      - Binding Addresses
        
        Where?
        
        Compile/link time: must know run location at compile time.
        
        Load time: compiler creates relocatable code, binds at load time.
        
        Run time: translated by hardware
        
        Base and Limit Registers
        
        restricts the processes memory to within the base and base + limit address space.
        
        Must be changed at load time, relocation and context switch.
        
        Pros: supports protected multi-processing.
        
        Cons:
        
        physical memory must remain contiguous.
        
        entire process in memory
        
        no partial sharing
- - - - DMA in device
      - Separate controller