Please enable JavaScript.

Coggle requires JavaScript to display documents.

OS (Operating System, Program Image, Spooling, CPU Registers, Interrupt),…

- - - - Types
        
        Medium-term scheduler
        
        Swapping may also be required to improve the process mix.
        
        After some time when main memory becomes available, medium-term scheduler swaps-in the swapped-out process to the main memory and its execution is resumed from where it left off.
        
        The primary objective of medium-term scheduler is to perform swapping.
        
        Medium-term scheduler swaps-out the processes from main memory to secondary memory to free up the main memory when required.
        
        Medium-term scheduler reduces the degree of multiprogramming
        
        Long-term scheduler
        
        The primary objective of long-term scheduler is to maintain a good degree of multiprogramming.
        
        it loads the selected processes into the main memory (ready state) for execution
        
        Long-term scheduler is also known as Job Scheduler
        
        It selects a balanced mix of I/O bound and CPU bound processes from the secondary memory (new state).
        
        Short-term scheduler
        
        After short-term scheduler decides the process, Dispatcher assigns the decided process to the CPU for execution
        
        The primary objective of short-term scheduler is to increase the system performance.
        
        It decides which process to execute next from the ready queue.
        
        Short-term scheduler is also known as CPU Scheduler.
      - Multiprogramming
        
        Optimal Degree of Multiprogramming
        
        An optimal degree of multiprogramming means average rate of process creation is equal to the average departure rate of processes from main memory.
        
        It is the responsibility of long-term scheduler to maintain a good degree of multiprogramming.
        
        Degree of Multiprogramming
        
        Multiple processes may be present in the ready state which are all ready for execution.
        
        Degree of multiprogramming is the maximum number of processes that can be present in the ready state.
        
        Medium-term scheduler reduces the degree of multiprogramming.
        
        Long-term scheduler controls the degree of multiprogramming.
      - Process Times
        
        Burst Time
        
        Burst time of a process can not be known in advance before executing the process
        
        Burst time is the amount of time required by a process for executing on CPU.
        
        It is also called as execution time or running time
        
        It can be known only after the process has executed
        
        Turn Around Time
        
        When present in the system, a process is either waiting in the ready queue for getting the CPU or it is executing on the CPU.
        
        Turn Around time is the total amount of time spent by a process in the system.
        
        Turn Around time = Completion time – Arrival time
        
        Turn Around time = Burst time + Waiting time
        
        Turnaround will be atleast the burst time
        
        Waiting Time
        
        Waiting time is the amount of time spent by a process waiting in the ready queue for getting the CPU
        
        Waiting time = Turn Around time – Burst time
        
        Waiting Time = Completion time(CT) − Arrival time(AT) − Burst Time(BT)
        
        For a set of process calculate AT, BT, CT for each process
        
        Average Waiting Time = (∑CT - ∑AT - ∑BT)/N
        
        Arrival Time
        
        Arrival time is the point of time at which a process enters the ready queue
        
        Response Time
        
        Response time is the amount of time after which a process gets the CPU for the first time after entering the ready queue.
        
        Response Time = Time at which process first gets the CPU – Arrival time
        
        Completion Time
        
        Completion time is the point of time at which a process completes its execution on the CPU and takes exit from the system
        
        Tips
        
        If the end time is x, it is till x and does not cross x(e.g. x + 1 is not included)
        
        If the start time is x, it is after x and does precede x(e.g. x - 1 is not included)
        
        So start and end time for two processes can be same time instant
        
        Technique
        
        0-3 P1 7
        3-7 P2 2
        7-8 P3 0
        8-10 P2 0
        10-13 P4 0
        13-20 P1 0
        20 - 0
        10 - 3
        1
        13 - 8
        
        Write the interval followed the process and the remaining time after the interval
      - Description
        
        They are mainly responsible for selecting the jobs to be submitted into the system and deciding which process to run.
        
        Schedulers in OS are special system software
        
        They help in scheduling the processes in various ways.
      - Algorithms
        
        FCFS
        
        Advantages
        
        It does not lead to starvation.
        
        It can be easily implemented using queue data structure.
        
        It is simple and easy to understand
        
        In case of a tie, process with smaller process id is executed first.
        
        Disadvantages
        
        Suffers from convoy effect
        
        Then, smaller processes have to wait for a long time for longer processes to release the CPU
        
        Consider processes with higher burst time arrived before the processes with smaller burst time
        
        It does not consider the priority or burst time of the processes
        
        It is always non-preemptive in nature.
        
        The process which arrives first in the ready queue is firstly assigned the CPU
        
        SJF
        
        Disadvantages
        
        Processes with larger burst time have poor response time
        
        Priorities can not be set for the processes
        
        It can not be implemented practically since burst time of the processes can not be known in advance
        
        It leads to starvation for processes with larger burst time
        
        Example: If a process P1 with burst time 100 is preempted by process with smaller burst time like 10, 20 etc. then the process P1 will be preempted and can get starved as long as new processes with smaller burst time keep coming up
        
        Techniques to Predict Burst Time
        
        Static Techniques
        
        Based on process type
        
        Assumed Burst Time
        
        2 more items...
        
        This technique predicts the burst time for a process based on its type.
        
        Based on process size
        
        This technique predicts the burst time for a process based on its size
        
        Burst time of the already executed process of similar size is taken as the burst time for the process to be executed.
        
        Dynamic Techniques
        
        Based on exponential averaging
        
        Given n processes P1, P2, … , Pn and burst time of each process Pi as ti. Then, predicted burst time for process Pn+1 is given as-
        
        Based on simple averaging
        
        Burst time for the process to be executed is taken as the average of all the processes that are executed till now
        
        Given n processes P1, P2, … , Pn and burst time of each process Pi as ti, then predicted burst time for process Pn+1 is given as
        
        Advantages
        
        It provides a standard for other algorithms since no other algorithm performs better than it
        
        SRTF is optimal and guarantees the minimum average waiting time
        
        Out of all the available processes, CPU is assigned to the process having smallest burst time.
        
        In case of a tie, it is broken by FCFS Scheduling
        
        SJF Scheduling can be used in both preemptive and non-preemptive mode
        
        Preemption
        
        Preemptive mode of Shortest Job First is called as Shortest Remaining Time First (SRTF).
        
        Every time a new job arrives, the remaining time of the currently executing process and the burst time of the other process are used to schedule the next process
        
        LJF
        
        Disadvantages
        
        The waiting time is high
        
        Processes with smaller burst time may starve for CPU
        
        Preemptive mode of Longest Job First is called as Longest Remaining Time First (LRTF).
        
        Advantages
        
        No process can complete until the longest job also reaches its completion
        
        All the processes approximately finishes at the same time
        
        Out of all the available processes, CPU is assigned to the process having largest burst time
        
        In case of a tie, it is broken by FCFS Scheduling
        
        LJF Scheduling can be used in both preemptive and non-preemptive mode
        
        Round Robin
        
        CPU is assigned to the process on the basis of FCFS for a fixed amount of time
        
        This fixed amount of time is called as time quantum or time slice
        
        Disadvantages
        
        It leads to starvation for processes with larger burst time as they have to repeat the cycle many times
        
        Priorities can not be set for the processes
        
        Its performance heavily depends on time quantum
        
        Round Robin Scheduling is FCFS Scheduling with preemptive mode.
        
        Advantages
        
        It gives the best performance in terms of average response time
        
        It is best suited for time sharing system, client server architecture and interactive system
        
        It is always preemptive in nature
        
        The value of time quantum should be such that it is neither too big nor too small.
        
        With decreasing value
        of time quantum
        
        Response time decreases
        
        Number of context switch increases
        
        Chances of starvation decreases
        
        With increasing value
        of time quantum
        
        Response time increases
        
        Number of context switch decreases
        
        When time quantum tends to infinity, Round Robin Scheduling becomes FCFS Scheduling
        
        Chances of starvation increases
        
        With increasing value of time quantum, Round Robin Scheduling tends to become FCFS Scheduling
        
        After the time quantum expires, the running process is preempted and sent to the ready queue
        
        The performance of Round Robin scheduling heavily depends on the value of time quantum
        
        Then, the processor is assigned to the next arrived process
        
        Turnaround Time Formula
        
        t = n*S + (n-1)*Q
        
        Calculation example
        
        Time taken to execute a process again after all others have executed
        
        Find burst time given average wait time
        
        Since the burst time will decide which process gets scheduled we cannot have a single formula
        
        Try different values of burst time starting from 1 to check if the average waiting time matches the given value
        
        New processes are added to the tail of the ready queue
        
        Waiting Time
        
        Last Start Time - Arrival Time - (Preemption X Time Quantum)
        
        Handling new processes
        
        New process is added while another one is executing
        
        Added to the ready queue before current process
        
        New process is added when current process ends
        
        Added to the ready queue before current process
        
        Note
        
        Keep a dot to keep track of top of stack
        
        If at the of a quantum a process has remaining burst time it is added to the back of the queue
        
        HRRN
        
        Disadvantages
        
        This is because burst time of the processes can not be known in advance
        
        It can not be implemented practically
        
        Response Ratio (RR)
        
        B = Burst time or Service time of the process
        
        W = Waiting time of the process so far
        
        It operates only in non-preemptive mode.
        
        Out of all the available processes, CPU is assigned to the process having highest response ratio
        
        In case of a tie, it is broken by FCFS Scheduling
        
        Advantages
        
        It performs better than SJF Scheduling
        
        It not only favors the shorter jobs but also limits the waiting time of longer jobs
        
        Priority Scheduling
        
        Disadvantages
        
        Processes with lesser priority may starve for CPU
        
        There is no idea of response time and waiting time
        
        Out of all the available processes, CPU is assigned to the process having the highest priority
        
        In case of a tie, it is broken by FCFS Scheduling
        
        The waiting time for the process having the highest priority will always be zero in preemptive mode
        
        The waiting time for the process having the highest priority may not be zero in non-preemptive mode
        
        Priority scheduling in preemptive and
        non-preemptive mode behaves exactly
        same under following conditions
        
        All the processes become available
        
        The arrival time of all the processes is same
        
        Advantages
        
        Priority scheduling in preemptive mode is best suited for real time operating system
        
        It considers the priority of the processes and allows the important processes to run first
        
        Priority Scheduling can be used in both preemptive and non-preemptive mode
        
        Priority Representation
        
        Low numbers represent high priority
        
        High numbers represent low priority
        
        Internal priority
        
        External Priority
        
        Aging
        
        A priority scheduling algorithm can leave some low priority processes waiting indefinitely
        
        Aging
        
        A solution to the problem of indefinite blockage of low-priority processes is aging
        
        Aging involves gradually increasing the priority of processes that wait in the system for a long time
        
        Multilevel Queue Scheduling
        
        Separate queues for each distinct priority, and priority scheduling simply schedules the process in the highest-priority queue
        
        If there are multiple processes in the highest-priority queue, they are executed in round-robin order
        
        In the most generalized form of this approach, a priority is assigned statically to each process, and a process remains in the same queue for the duration of its runtime
        
        Priority
        
        A multilevel queue scheduling algorithm can also be used to partition processes into several separate queues based on the process type
        
        Types
        
        Real-time processes
        
        System processes
        
        Interactive processes
        
        Batch processes
        
        Each queue has absolute priority over lower-priority queues
        
        Starvation
        
        Processes in lower priority queues can starve
        
        Solution
        
        Time-slice among the queues
        
        Each queue gets a certain portion of the CPU time, which it can then schedule among its various processes
        
        Multilevel Feedback Queue Scheduling
        
        Allows a process to move between queues
        
        The idea is to separate processes according to the characteristics of their CPU bursts
        
        If a process uses too much CPU time, it will be moved to a lower-priority queue
        
        This scheme leaves I/O-bound and interactive processes—which are typically characterized by short CPU bursts —in the higher-priority queues
        
        A process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation
        
        Parameters
        
        The number of queues
        
        The scheduling algorithm for each queue
        
        The method used to determine when to upgrade a process to a higher priority queue
        
        The method used to determine when to demote a process to a
        lower priority queue
        
        The method used to determine which queue a process will enter when that process needs service
        
        The definition of a multilevel feedback queue scheduler makes it the most general CPU-scheduling algorithm
        
        It can be configured to match a specific system under design
        
        it is also the most complex algorithm,
        since defining the best scheduler requires some means by which to select values for all the parameters
        
        Other Algorithms
        
        Gang Scheduling
        
        Gang scheduling is a scheduling algorithm for parallel systems that schedules related threads or processes to run simultaneously on different processors
        
        Usually these will be threads all belonging to the same process, but they may also be from different processes, where the processes could have a producer-consumer relationship or come from the same MPI program
        
        Gang scheduling is used to ensure that if two or more threads or processes communicate with each other, they will all be ready to communicate at the same time
        
        If they were not gang-scheduled, then one could wait to send or receive a message to another while it is sleeping, and vice versa
        
        Rate-Monotonic Scheduling
        
        Rate-monotonic scheduling (RMS) is a priority assignment algorithm used in real-time operating systems (RTOS) with a static-priority scheduling class
        
        The static priorities are assigned according to the cycle duration of the job, so a shorter cycle duration results in a higher job priority
        
        These operating systems are generally preemptive and have deterministic guarantees with regard to response times
        
        Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a particular application
        
        Fair Share Scheduling
        
        Fair-share scheduling is a scheduling algorithm for computer operating systems in which the CPU usage is equally distributed among system users or groups, as opposed to equal distribution among processes
        
        One common method of logically implementing the fair-share scheduling strategy is to recursively apply the round-robin scheduling strategy at each level of abstraction (processes, users, groups, etc.)
        
        Note
        
        Preemption Types
        
        At clock tick
        
        At process start/end
        
        Default is clock tick
        
        The solution will specify and if not specify use clock tick
        
        But in this question SRTF has default trigger as process start/end
      - Scheduling Queues
        
        Ready Queue
        
        This queue is generally stored as a linked list; a ready-queue header contains pointers to the first PCB in the list, and each PCB includes a pointer field that points to the next PCB in the ready queue
        
        As processes enter the system, they are put into a ready queue, where they are ready and waiting to execute on a CPU’s core
        
        Wait Queue
        
        When a process is allocated a CPU core, it executes for a while and eventually terminates, is interrupted, or waits for the occurrence of a particular event, such as the completion of an I/O
        request
        
        Processes that are waiting for a certain event to occur — such as completion of I/O — are placed in a wait queue
        
        Queueing Diagram
        
        A common representation of process scheduling is a queueing diagram
        
        Two types of queues are present: the ready queue and
        a set of wait queues
        
        A new process is initially put in the ready queue
        
        It waits there until it is selected for execution, or dispatched
        
        Once the process is allocated a CPU core and is executing, one of several events could occur:
        
        The process could issue an I/O request and then be placed in an I/O wait queue
        
        The process could create a new child process and then be placed in a wait queue while it awaits the child’s termination
        
        The process could be removed forcibly from the core, as a result of an interrupt or having its time slice expire, and be put back in the ready queue
        
        In the first two cases, the process eventually switches from the waiting state to the ready state and is then put back in the ready queue
        
        A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated
      - Context Switch
        
        Switching the CPU core to another process requires performing a state save of the current process and a state restore of a different process
        
        When a context switch occurs, the kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run
        
        Context switch time is pure overhead, because the system does no useful work while switching
        
        Switching speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied, and the existence of special instructions (such as a single instruction to load or store all registers)
        
        A typical speed is a several microseconds
        
        Context-switch times are highly
        dependent on hardware support
        
        Some processors provide multiple sets of registers. A context switch here simply requires changing the pointer to the current register set
        
        If there are more active processes than there are register sets, the system resorts to copying register data to and from memory, as before
        
        The more complex the operating system, the greater the amount of work that must be done during a context switch
        
        Advanced memory-management techniques may require that extra data be switched with each context
        
        The address space of the current process must be preserved as the space of the next task is prepared for use
        
        How the address space is preserved, and what amount of work is needed to preserve it, depend on the memory management method of the operating system
        
        User->User Vs Kernel ->User Context Switch
        
        User-To-User Switch Involves context save followed by context restore
        
        User to User Switch involves User->Kernel and Kernel->User Switch
        
        User To Kernel Switch has special instructions to reduce switch latency
        
        U->U > K->U/U->K
      - CPU–I/O Burst Cycle
        
        The success of CPU scheduling depends on an observed property of processes: process execution consists of a cycle of CPU execution and I/O wait
        
        Processes alternate between these two states
        
        Process execution begins with a CPU burst
        
        That is followed by an I/O burst, which is followed by another CPU burst, then another I/O burst, and so on
        
        Eventually, the final CPU burst ends with a system request to terminate execution
        
        The durations of CPU bursts have been measured extensively
        
        The curve is generally characterized as exponential or hyper exponential, with a large number of short CPU bursts and a small number of long CPU bursts
        
        An I/O-bound program typically has many short CPU bursts
        
        A CPU-bound program might have a few long CPU bursts
        
        This distribution can be important when implementing a CPU-scheduling algorithm
        
        Preemption
        
        Scheduling Circumstances
        
        When a process switches from the running state to the waiting state (for example, as the result of an I/O request or an invocation of wait() for the termination of a child process)
        
        When a process switches from the running state to the ready state (for example, when an interrupt occurs)
        
        When a process switches from the waiting state to the ready state (for example, at completion of I/O)
        
        When a process terminates
        
        For situations 1 and 4, there is no choice in terms of scheduling
        
        There is a choice, however, for situations 2 and 3
        
        When scheduling takes place only under circumstances 1 and 4,we say that the scheduling scheme is non-preemptive or cooperative
        
        Otherwise, it is preemptive
        
        Non-Preemptive
        
        Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases it either by terminating or by switching to the waiting state
        
        In Non-Preemptive scheduling a process can go from running state to ready state
        
        Preemptive
        
        Race conditions
        
        Unfortunately, preemptive scheduling can result in race conditions when data are shared among several processes
        
        Consider the case of two processes that share data
        
        While one process is updating the data, it is preempted so that the second process can run
        
        The second process then tries to read the data, which are in an inconsistent state
        
        Kernel
        
        Preemption also affects the design of the operating-system kernel
        
        During the processing of a system call, the kernel may be busy with an activity on behalf of a process
        
        Such activities may involve changing important kernel data (for instance, I/O queues)
        
        There will be issues if the process is preempted
        in the middle of these changes and the kernel (or the device driver) needs to read or modify the same structure
        
        A non-preemptive kernel will wait for a system call to complete
        or for a process to block while waiting for I/O to complete to take place before doing a context switch
        
        This scheme ensures that the kernel structure is simple,
        since the kernel will not preempt a process while the kernel data structures are in an inconsistent state
        
        This kernel-execution model is a poor one for supporting real-time computing, where tasks must complete execution within a given time frame
        
        A preemptive kernel requires mechanisms such as mutex
        locks to prevent race conditions when accessing shared kernel
        data structures
        
        Most modern operating systems are now fully preemptive when running in kernel mode
        
        In Preemptive scheduling a process cannot go from running state to ready state
        
        Dispatcher
        
        The dispatcher is the module that gives control of the CPU’s core to the process selected by the CPU scheduler
        
        Functions
        
        Switching context from one process to another
        
        Switching to user mode
        
        Jumping to the proper location in the user program to resume that program
        
        The dispatcher should be as fast as possible, since it is invoked during every context switch
        
        The time it takes for the dispatcher to stop one process and start
        another running is known as the dispatch latency
        
        Scheduling Criteria
        
        Different CPU-scheduling algorithms have different properties, and the choice of a particular algorithm may favor one class of processes over another
        
        In choosing which algorithm to use in a particular situation, we must consider the properties of the various algorithms
        
        Criteria
        
        CPU utilization
        
        Maximize
        
        Throughput
        
        Maximize
        
        The number of processes that are completed per time unit is called throughput
        
        Turnaround time
        
        Minimize
        
        The interval from the time of submission of a process to the time of completion is the turnaround time
        
        Waiting time
        
        Minimize
        
        Waiting time is the sum of the periods spent waiting in the ready queue
        
        Response time
        
        Minimize
        
        For interactive systems it is more important to minimize the variance in the response time than to minimize the average response time
        
        A system with reasonable and predictable response time may be considered more desirable than a system that is faster on the average but is highly variable
        
        The time from the submission of a request until the first response is produced
        
        In most cases, we optimize the average measure
        
        Under some circumstances, we prefer to optimize the minimum or maximum values rather than the average
        
        Gantt Chart
    - - NEW
        
        READY
        
        RUNNING
        
        WAIT/BLOCK
        
        READY
        
        SUSPEND/WAIT
        
        WAIT/BLOCK
        
        TERMINATED
    - - Process Creation
        
        During the course of execution, a process may create several new processes
        
        The creating process is called a parent process, and the new
        processes are called the children of that process
        
        The parent may have to partition its resources among
        its children, or it may be able to share some resources (such as memory or files) among several of its children
        
        Each of these new processes
        may in turn create other processes, forming a tree of processes
        
        A child process may be able to obtain its resources directly from
        the operating system, or it may be constrained to a subset of the resources of the parent process
        
        Most operating systems (including UNIX, Linux, and Windows) identify processes according to a unique process identifier (or pid), which is typically an integer number
        
        In general, when a process creates a child process, that child process will need certain resources (CPU time, memory, files, I/O devices) to accomplish its task
        
        The pid provides a unique value for each process in the
        system, and it can be used as an index to access various attributes of a process within the kernel
        
        Restricting a child process to a subset of the parent’s resources prevents any process from overloading the system by creating too many child processes
        
        Parent Behavior
        
        The parent continues to execute concurrently with its children
        
        The parent waits until some or all of its children have terminated
        
        In addition to supplying various physical and logical resources, the parent process may pass along initialization data (input) to the child process
        
        Address-space possibilities
        
        The child process is a duplicate of the parent process (it has the same program and data as the parent).
        
        The child process has a new program loaded into it
      - Process Termination
    - - User Level Threads
        
        The user-level threads are implemented by users and the kernel is not aware of the existence of these threads
        
        It handles them as if they were single-threaded processes
        
        User-level threads are small and much faster than kernel level threads
        
        They are represented by a program counter(PC), stack, registers and a small process control block
        
        Advantages
        
        User-level threads are easier and faster to create than kernel-level threads. They can also be more easily managed
        
        User-level threads can be run on any operating system
        
        There are no kernel mode privileges required for thread switching in user-level threads
        
        Disadvantages
        
        Multithreaded applications in user-level threads cannot use multiprocessing to their advantage
        
        The entire process is blocked if one user-level thread performs blocking operation
        
        Also called Light Weight Process(LWP)
      - Kernel Level Threads
        
        Kernel-level threads are handled by the operating system directly and the thread management is done by the kernel
        
        The context information for the process as well as the process threads is all managed by the kernel
        
        Because of this, kernel-level threads are slower than user-level threads
        
        Advantages
        
        Multiple threads of the same process can be scheduled on different processors in kernel-level threads
        
        The kernel routines can also be multithreaded
        
        If a kernel-level thread is blocked, another thread of the same process can be scheduled by the kernel
        
        Disadvantages
        
        A mode switch to kernel mode is required to transfer control from one thread to another in a process
        
        Kernel-level threads are slower to create as well as manage as compared to user-level threads
        
        Operating system maintains a separate program counter, stack and CPU register set for a thread
        
        Threads share various resources like virtual memory, file descriptors, heap etc.
      - Note: If question says X is transparent to Y that means Y does not know the details of X
  - - - Semaphore
        
        Binary Semaphore
        
        Can be incremented only one
        
        Note this while solving problems
        
        P and V with mutex named variable still means binary semaphore
        
        Tips
        
        Problem
        
        Check if operation is a loop or one time only
        
        If some thread continuously signals other threads will be unblocked
        
        Counting Semaphore
        
        Implement using binary semaphore
        
        Keep an integer with count
        
        Use two binary semaphores
      - Mutex
        
        Types
        
        Reentrant Mutex
        
        Reentrant mutex (recursive mutex, recursive lock) is a particular type of mutual exclusion (mutex) device that may be locked multiple times by the same process/thread, without causing a deadlock
        
        A recursive mutex tracks the number of times it has been locked, and requires equally many unlock operations to be performed before other threads may lock it
        
        Non-Reentrant
        
        Non-Reentrant mutex (non-recursive mutex, non-recursive lock) is a particular type of mutual exclusion (mutex) device that may be not locked multiple times by the same process/thread, without causing a deadlock
      - Condition
        
        Wait
        
        If a thread must wait for an event to occur, that thread waits on the corresponding condition variable
        
        Signal
        
        Ifanother thread causes an event to occur, that thread simply signals the corresponding condition variable
        
        A condition variable indicates an event and has no value
      - Test-and-set
        
        Test and Set Lock
        
        It uses a test and set instruction to provide the synchronization among the processes executing concurrently.
        
        It is an instruction that returns the old value of a memory location and sets the memory location value to 1 as a single atomic operation
        
        If one process is currently executing a test-and-set, no other process is allowed to begin another test-and-set until the first process test-and-set is finished
      - Fetch And Add
      - Barrier)
        
        Invocation
        
        Barrier invocation means one process entering the barrier twice.
        
        It does not mean another process blocking on the barrier
      - Monitor
        
        Abstract Data Type for handling/defining shared resources
        
        Comprises
        
        Shared Private Data
        
        Cannot be accessed from outside
        
        Procedures that operate on the data
        
        Gateway to the resource
        
        Can only act on data local to the monitor
        
        Synchronization primitives
        
        – Among threads that access the procedures
        
        Monitors guarantee mutual exclusion
        
        Only one thread can execute a monitor procedure at any time
        
        If second thread invokes a monitor procedure at that time
    - - Standard Problems
        
        Dining Philosopher Problem
        
        Solutions
        
        Swap the order of acquiring forks for the last philospher
        
        After taking the left chopstick, the program checks whether the right chopstick is available
        
        If it is not, the philosopher puts down the left one, waits for some time, and then repeats the whole process
        
        The dining philosophers problem states that there are 5 philosophers sharing a circular table and they eat and think alternatively
        
        There is a bowl of rice for each of the philosophers and 5 chopsticks
        
        A philosopher needs both their right and left chopstick to eat
        
        A hungry philosopher may only eat if there are both chopsticks available
        
        Implementation
        
        Each chop stick is a semaphore
        
        Each philosopher is a process
        
        Bounded Buffer/Producer Consumer Problem
        
        A bounded buffer lets multiple producers and multiple consumers share a single buffer
        
        Producers write data to the buffer and consumers read data from the buffer
        
        Producers must block if the buffer is full
        
        Consumers must block if the buffer is empty
        
        Solution
        
        Semaphores
        
        Mutex
        
        A binary semaphore can be used to protect access to the critical sections.
        
        Empty
        
        Use one semaphore named empty to count the empty slots in the buffer
        
        Initialise this semaphore to N
        
        A producer must wait on this semaphore before writing to the buffer
        
        A consumer will signal this semaphore after reading from the buffer
        
        Data
        
        Use one semaphore named data to count the number of data items in the buffer.
        
        Initialise this semaphore to 0
        
        A consumer must wait on this semaphore before reading from the buffer
        
        A producer will signal this semaphore after writing to the buffer
        
        Bankers Problem
        
        Deadlock avoidance problem
        
        Safe Sequence
        
        Algorithm
        
        Columns
        
        Process
        
        Allocation
        
        Given
        
        Max Need
        
        Given
        
        Available
        
        Total - Allocation
        
        Remaining Need
        
        Max Need - Allocation
        
        Select a process for which remaining need can be satisfied with available
        
        After the selected process completes it resources are added to the available resources
        
        Repeat until all process are executed
        
        Reader Writer Problem
        
        The readers-writers problem relates to an object such as a file that is shared between multiple processes
        
        Some of these processes are readers i.e. they only want to read the data from the object
        
        Some of the processes are writers i.e. they want to write into the object
      - Conditions
        
        Mutual Exclusion
        
        There must exist at least one resource in the system which can be used by only one process at a time
        
        If there exists no such resource, then deadlock will never occur
        
        Hold and Wait
        
        There must exist a process which holds some resource and waits for another resource held by some other process
        
        No preemption
        
        Once the resource has been allocated to the process, it can not be preempted
        
        It means resource can not be snatched forcefully from one process and given to the other process
        
        The process must release the resource voluntarily by itself
        
        Circular Wait
        
        All the processes must wait for the resource in a cyclic manner where the last process waits for the resource held by the first process
      - Deadlock Handling
        
        Deadlock Prevention
        
        This strategy involves designing a system that violates one of the four necessary conditions required for the occurrence of deadlock
        
        This ensures that the system remains free from the deadlock
        
        Conditions
        
        Mutual Exclusion
        
        To violate this condition, all the system resources must be such that they can be used in a shareable mode
        
        In a system, there are always some resources which are mutually exclusive by nature
        
        So, this condition can not be violated
        
        Hold and Wait
        
        Approach 1
        
        A process has to first request for all the resources it requires for execution
        
        Once it has acquired all the resources, only then it can start its execution
        
        This approach ensures that the process does not hold some resources and wait for other resources
        
        Drawbacks
        
        2 more items...
        
        Approach 2
        
        A process is allowed to acquire the resources it desires at the current moment
        
        After acquiring the resources, it start its execution
        
        Now before making any new request, it has to compulsorily release all the resources that it holds currently
        
        This approach is efficient and implementable
        
        Approach 3
        
        A timer is set after the process acquires any resource
        
        After the timer expires, a process has to compulsorily release the resource.
        
        No-Preemption
        
        This condition can be violated by forceful preemption
        
        Consider a process is holding some resources and request other resources that can not be immediately allocated to it
        
        Then, by forcefully preempting the currently held resources, the condition can be violated
        
        A process is allowed to forcefully preempt the resources possessed by some other process only if
        
        It is a high priority process or a system process
        
        The victim process is in the waiting state
        
        Circular Wait
        
        This condition can be violated by not allowing the processes to wait for resources in a cyclic manner
        
        Approach
        
        A natural number is assigned to every resource
        
        Each process is allowed to request for the resources either in only increasing or only decreasing order of the resource number
        
        In case increasing order is followed, if a process requires a lesser number resource, then it must release all the resources having larger number and vice versa
        
        This approach is the most practical approach and implementable
        
        However, this approach may cause starvation but will never lead to deadlock
        
        Deadlock Avoidance
        
        This strategy involves maintaining a set of data using which a decision is made whether to entertain the new request or not
        
        If entertaining the new request causes the system to move in an unsafe state, then it is discarded
        
        This strategy requires that every process declares its maximum requirement of each resource type in the beginning
        
        The main challenge with this approach is predicting the requirement of the processes before execution
        
        Resource Allocation State
        
        A resource allocation state is defined by the number of available and allocated resources, and the maximum requirements of all processes in the system
        
        Safe State
        
        A state is safe if the system can allocate all resources requested by all processes ( up to their stated maximums ) without entering a deadlock state
        
        A state is safe if there exists a safe sequence of processes { P0, P1, P2, ..., PN } such that all of the resource requests for Pi can be granted using the resources currently allocated to Pi and all processes Pj where j < i. ( I.e. if all the processes prior to Pi finish and free up their resources, then Pi will be able to finish also, using the resources that they have freed up. )
        
        If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock. ( All safe states are deadlock free, but not all unsafe states lead to deadlocks. )
        
        Resource-Allocation Graph Algorithm
        
        If resource categories have only single instances of their resources, then deadlock states can be detected by cycles in the resource-allocation graphs
        
        In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation graph with claim edges, noted by dashed lines, which point from a process to a resource that it may request in the future
        
        In order for this technique to work, all claim edges must be added to the graph for any particular process before that process is allowed to request any resources.
        
        Alternatively, processes may only make requests for resources for which they have already established claim edges, and claim edges cannot be added to any process that is currently holding resources
        
        When a process makes a request, the claim edge Pi->Rj is converted to a request edge. Similarly when a resource is released, the assignment reverts back to a claim edge
        
        This approach works by denying requests that would produce cycles in the resource-allocation graph, taking claim edges into effect
        
        Graph
        
        Vertex Types
        
        Process vertex
        
        1 more item...
        
        Resource vertex
        
        Every resource will be represented as a resource vertex
        
        Types
        
        2 more items...
        
        Edges
        
        Types
        
        2 more items...
        
        Deadlock
        
        Single Instance
        
        1 more item...
        
        Multi-Instance
        
        2 more items...
        
        Deadlock Detection and Recovery
        
        This strategy involves waiting until a deadlock occurs.
        
        After deadlock occurs, the system state is recovered
        
        The main challenge with this approach is detecting the deadlock
        
        Deadlock Ignorance
        
        This strategy involves ignoring the concept of deadlock and assuming as if it does not exist
        
        This strategy helps to avoid the extra overhead of handling deadlock.
      - Concepts
        
        Consider there are n processes in the system P1, P2, P3, ... Pn
        
        Process Pi requires xi units of resource R
        
        Maximum Resources for Deadlock
        
        The number of units that each process holds = One less than its maximum demand
        
        ∑xi – n
        
        Minimum Resources for no Deadlock
        
        Minimum number of units of resource R that ensures no deadlock
        = One more than maximum number of units of resource R that ensures deadlock
        
        (∑xi – n) + 1
      - Deadlock due to Locking Order
        
        Shared locks should be acquired by processes in the same order
        
        Example
        
        The unshared locks can be interspersed anywhere but the shared locks should be in the same order
    - - Consider a system consisting of n processes {P0, P1, ..., Pn−1}. Each process has a segment of code, called a critical section,
        in which the process may be accessing — and updating — data that is shared with at least one other process
      - The important feature of the system is that, when one process is executing in its critical section, no other process is allowed to execute in its critical section
      - The critical-section problem is to design a protocol that the processes can use to synchronize their activity so as to cooperatively share data
      - Other Sections
        
        Each process must request permission to enter its critical section. The section of code implementing this request is the entry section
        
        The critical section may be followed by an exit section
        
        The remaining code is the remainder section
      - Solution Requirements
        
        Mutual exclusion
        
        If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
        
        Progress
        
        If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely
        
        Bounded Waiting
        
        There exists a bound, or limit, on the number of times
        that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
      - Solutions
        
        Peterson’s Solution
        
        Peterson’s solution is restricted to two processes that alternate execution between their critical sections and remainder sections
        
        The processes are numbered P0 and P1
        
        For convenience, when presenting Pi, we use Pj to denote the
        other process; that is, j equals 1 − i
        
        Peterson’s solution requires the two processes to share two data
        items
        
        The variable turn indicates whose turn it is to enter its critical section
        
        If turn == i, then process Pi is allowed to execute in its critical section
        
        The flag array is used to indicate if a process is ready to enter its critical section
        
        Algorithm
        
        To enter the critical section, process Pi first sets flag[i] to be true and then sets turn to the value j, thereby asserting that if the other process wishes to enter the critical section, it can do so
        
        If both processes try to enter at the same time, turn will be set to both i and j at roughly the same time.
        
        Only one of these assignments will last; the other will occur but will be overwritten immediately
        
        The eventual value of turn determines which of the two processes is allowed to enter its critical section first
        
        Pseudocode
        
        int turn;
        
        boolean flag[2];
        
        while (true) {
        
        flag[i] = true;
        
        turn = j;
        
        while (flag[j] && turn == j)
        
        1 more item...
        
        /* critical section */
        
        flag[i] = false;
        
        /*remainder section */
        
        Software-based solution because the algorithm involves
        no special support from the operating system or specific hardware instructions to ensure mutual exclusion
        
        May not work on modern systems
    - - Software-based solutions are not guaranteed to work on modern computer architectures
      - Hardware instructions can provide support for solving the critical-section problem
      - These primitive operations can be used directly as synchronization tools, or they can be used to form the foundation of more abstract synchronization mechanisms
      - Solutions
        
        Memory Barriers
        
        A system may reorder instructions, a policy that can lead to unreliable data states
        
        How a computer architecture determines what memory guarantees it will provide to an application program is known as its memory model
        
        Categories:
        
        Strongly ordered
        
        Memory modification on one processor is immediately visible to all other processors
        
        Weakly ordered
        
        Modifications to memory on one processor may not be immediately visible to other processors
        
        Memory models vary by processor type, so kernel developers cannot make any assumptions regarding the visibility of modifications to memory on a shared-memory multiprocessor
        
        To address this issue, computer architectures provide instructions that can force any changes in memory to be propagated to all other processors, thereby ensuring that memory modifications are visible to threads running on other processors
        
        Such instructions are known as memory barriers or memory fences
        
        When a memory barrier instruction is performed, the system ensures that all loads and stores are completed before any subsequent load or store operations are performed
        
        Even if instructions were reordered, the memory barrier ensures that the store operations are completed in memory and visible to other processors before future load or store operations are performed.
        
        Compare and Swap(CAS)
        
        An atomic instruction used in multithreading to achieve synchronization
        
        It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of that memory location to a new given value
        
        This is done as a single atomic operation
        
        This operation is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms
        
        Atomic Variables
  - - - Information Maintenance
        
        set process, file, or device attributes
        
        get process, file, or device attributes
        
        get system data, set system data
        
        get time or date, set time or date
      - Protection
        
        get file permissions
        
        set file permissions
      - Device Management
        
        get device attributes, set device attributes
        
        logically attach or detach devices
        
        read, write, reposition
        
        request device, release device
      - File Management
        
        Types
        
        read, write, reposition
        
        create file, delete file
        
        get file attributes, set file attributes
        
        open, close
      - Process Control
        
        Types
        
        allocate and free memory
        
        create process, terminate process
        
        get process attributes, set process attributes
        
        load, execute
        
        wait event, signal event
        
        Examples
        
        fork
        
        Returns
        
        -1
        
        Failed/Parent
        
        0
        
        Success/Child
        
        1
        
        Success/Parent
        
        Number of processes created by fork
        
        For N fork calls the total number of process is the number of leaves in a complete binary tree to height N
        
        Total Processes = 2^N
        
        Total Children = 2^N - 1
        
        All processes except the first process are children
        
        On fork the virtual address of a variable will remain same even if the underlying page is changed due to copy-on-write Link
        
        exec
      - Communications
        
        attach or detach remote devices
        
        send, receive messages
        
        transfer status information
        
        create, delete communication connection
    - - Typically, a number is associated with each system call, and the system-call interface maintains a table indexed according to these numbers
      - The system-call interface then invokes the intended system call in the operating-system kernel and returns the status of the system call
      - The full suite of software needed to execute applications writ-
        ten in a given programming language, including its compilers or interpreters as well as other software, such as libraries and loaders
      - Provides a system-call interface that serves as the link to system calls made available by the operating system
      - The system-call interface intercepts function calls in
        the API and invokes the necessary system calls within the operating system
  - - - Shared-Memory model
        
        In the shared-memory model, a region of memory that is shared by the cooperating processes is established
        
        Processes can then exchange information by reading and writing data to the shared region
        
        In shared-memory systems, system calls are required only to establish shared memory regions. Once shared memory is established, all accesses are treated as routine memory accesses, and no assistance from the kernel is required
        
        Mechanism
        
        Interprocess communication using shared memory requires communicating processes to establish a region of shared memory
        
        A shared-memory region resides in the address space of the process creating the shared-memory segment
        
        Other processes that wish to communicate using this shared memory segment must attach it to their address space
        
        They can then exchange information by reading and writing data in the shared areas
        
        The form of the data and the location are determined by these processes and are not under the operating system’s control
        
        They can then exchange information by reading and writing data in the shared areas
        
        The processes are also responsible for ensuring that they are not writing to the same location simultaneously
        
        Buffer Types
        
        Unbounded Buffer
        
        The unbounded buffer places no practical limit on the size of the buffer
        
        The consumer may have to wait for new items, but the producer can always produce new items
        
        Bounded Buffer
        
        The bounded buffer assumes a fixed buffer size
        
        In this case, the consumer must wait if the buffer is empty, and the producer must wait if the buffer is full
        
        The scheme requires that these processes share a region of memory and that the code for accessing and manipulating the shared memory be written explicitly by the application programmer
      - Message-Passing model
        
        In the message-passing model, communication takes place by means of messages exchanged between the cooperating processes
        
        Message passing is useful for exchanging smaller amounts of data, because no conflicts need be avoided
        
        Message-passing systems are typically implemented using system calls and thus require the more time-consuming task of kernel intervention
        
        Message passing is also easier to implement in a distributed system than shared memory
        
        Operating system provides the means for cooperating processes to communicate with each other via a message-passing facility
        
        Message passing provides a mechanism to allow processes to communicate and to synchronize their actions without sharing the same address space
        
        It is particularly useful in a distributed environment, where the communicating processes may reside on different computers connected by a network
        
        Messages sent by a process can be either fixed or variable in size
        
        If only fixed-sized messages can be sent, the system-level implementation is straightforward
        
        This restriction, however, makes the task of programming more difficult
        
        Variable-sized messages require amore complex system-level
        implementation, but the programming task becomes simpler
        
        A communication link must exist between two processes that want to communicate
        
        Types
        
        Direct/indirect Communication
        
        Direct
        
        send(P, message)—Send a message to process P
        
        Under direct communication, each process that wants to communicate must explicitly name the recipient or sender of the communication
        
        receive(Q, message)—Receive a message from process Q.
        
        Communication Link Properties
        
        A link is established automatically between every pair of processes that want to communicate
        
        The processes need to know only each other’s identity to communicate
        
        A link is associated with exactly two processes
        
        Between each pair of processes, there exists exactly one link
        
        Addressing
        
        Symmetric
        
        1 more item...
        
        Asymmetric
        
        3 more items...
        
        Indirect
        
        With indirect communication, the messages are sent to and received from mailboxes, or ports
        
        A mailbox can be viewed abstractly as an object into which messages can be placed by processes and from which messages can be removed
        
        Each mailbox has a unique identification
        
        A process can communicate with another process via a number of different mailboxes, but two processes can communicate only if they have a shared mailbox
        
        send(A, message)—Send a message to mailbox A
        
        receive(A, message)—Receive a message from mailbox A
        
        Communication Link
        
        A link is established between a pair of processes only if both members of the pair have a shared mailbox
        
        A link may be associated with more than two processes
        
        Between each pair of communicating processes, a number of different links may exist, with each link corresponding to one mailbox
        
        Multiple Receiver
        Issue Resolution
        
        Allow a link to be associated with two processes at most
        
        Allow at most one process at a time to execute a receive() operation
        
        Arbitrarily
        
        3 more items...
        
        Ownership
        
        A mailbox may be owned either by a process or by the operating system
        
        Process
        
        4 more items...
        
        OS
        
        7 more items...
        
        Synchronous/Asynchronous Communication
        
        Blocking Send
        
        The sending process is blocked until the message is
        received by the receiving process or by the mailbox
        
        Non-Blocking Send
        
        The sending process sends the message and resumes
        operation
        
        Blocking Receive
        
        The receiver blocks until a message is available
        
        Non-Blocking Receive
        
        The receiver retrieves either a valid message or a
        null
        
        Automatic/explicit Buffering
        
        Zero capacity
        
        The queue has a maximum length of zero; thus, the link
        cannot have any messages waiting in it
        
        In this case, the sender must block until the recipient receives the message
        
        No-buffering
        
        Bounded capacity
        
        The queue has finite length n; thus, at most n messages
        can reside in it
        
        If the queue is not full when a new message is sent, the message is placed in the queue (either the message is copied or a pointer
        to the message is kept), and the sender can continue execution without waiting
        
        If the link is full, the sender must block until space is available in the queue
        
        Automatic buffering
        
        Unbounded capacity
        
        The queue’s length is potentially infinite; thus, any number of messages can wait in it.
        
        The sender never blocks
        
        Automatic buffering
    - - Independent Process
        
        A process is independent if it does not share data with any other processes executing in the system
      - Cooperating Process
        
        Any process that shares data with other processes is a cooperating process
        
        A process is cooperating if it can affect or be affected by the other processes executing in the system
        
        Reasons for process cooperation
        
        Information sharing
        
        Since several applications may be interested in the same piece of information (for instance, copying and pasting), we must provide an environment to allow concurrent access to such information
        
        Computation speedup
        
        If we want a particular task to run faster, we must break it into subtasks, each of which will be executing in parallel with the others
        
        Notice that such a speedup can be achieved only if the computer has multiple processing cores
        
        Modularity.
        
        We may want to construct the system in a modular fashion, dividing the system functions into separate processes or threads
    - - Sockets
      - RPC
        
        One of the most common forms of remote service is the RPC paradigm, which was designed as a way to abstract the procedure-call mechanism for use between systems with network connections
        
        Since we are dealing with an environment in which the processes are executing on separate systems, we must use a message-based communication scheme to provide remote service
        
        In contrast to IPC messages, the messages exchanged in RPC communication are well structured and are thus no longer just packets of data
        
        Each message is addressed to an RPC daemon listening to a port on the remote system, and each contains an identifier specifying the function to execute and the parameters to pass to that function
        
        The function is then executed as requested, and any output is sent back to the requester in a separate message
        
        A port in this context is simply a number included at the start of a message packet
        
        Whereas a system normally has one network address, it can have many ports within that address to differentiate the many network services it supports
        
        If a remote process needs a service, it addresses a message to the proper port
        
        If a remote process needs a service, it addresses a message to the proper port
        
        The semantics of RPCs allows a client to invoke a procedure on a remote host as it would invoke a procedure locally
        
        The RPC system hides the details that allow communication to take place by providing a stub on the client side
        
        A separate stub exists for each separate remote procedure
        
        When the client invokes a remote procedure, the RPC system calls the appropriate stub, passing it the parameters provided to the remote procedure
        
        This stub locates the port on the server and marshals the parameters
        
        The stub then transmits a message to the server using message passing
        
        A similar stub on the server side receives this message and invokes the procedure on the server
        
        Marshaling
        
        Parameter marshaling addresses the issue concerning differences in data representation on the client and server machines
        
        XDR
        
        Machine-independent representation of data
        
        On the client side, parameter marshaling involves converting the machine-dependent data into XDR before they are sent to the server
        
        On the server side, the XDR data are un-marshaled and converted to the machine-dependent representation for the
        server
  - - - Monolithic
        
        Tightly Coupled
      - Layered
        
        Loosely Coupled
      - Microkernels
    - - Multiprogrammed
        
        No-Preemption
        
        Reduce Idleness
        
        Multiple Programs in memory
        
        In systems using multiprogramming a program loaded to memory and ready to execute is called a job
      - Distributed
      - Realtime
        
        Hard
        
        Soft
      - Multitasking
        
        Increase responsiveness
        
        Preemptive
        
        Time Sharing
        
        Multitasking is a logical extension of multiprogramming where a timer is set to cause an interrupt at a regular time interval and the running process is replaced if the job requests I/O or if the job is interrupted by the timer
      - Clustered
      - Embedded
      - Batch
        
        The OS defines a job which has predefined sequence of commands, programs and data as a single unit
        
        The OS keeps a number a jobs in memory and executes them without any manual information
        
        Jobs are processed in the order of submission, i.e., first come first served fashion
        
        When a job completes its execution, its memory is released and the output for the job gets copied into an output spool for later printing or processing
      - Multiprocessing
        
        Using more than one CPU simultaneously
      - Multithreading
        
        Multithreading is an extension of multitasking
  - - - Types
    - - Memory Segmentation is defined as a system of segmenting processes and loading them into different non-contiguous addressed spaces in memory
      - The chunks that a program is divided into which are not necessarily all of the same sizes are called segments
      - Segmentation gives user’s view of the process which paging does not give
      - Segment Table
        
        It maps two-dimensional Logical address into one-dimensional Physical address
        
        Entries contain
        
        Base Address
        
        It contains the starting physical address where the segments reside in memory
        
        Limit
        
        It specifies the length of the segment
      - Segmentation + Paging
        
        Paged Segmentation
        
        The segments are paged
        
        The virtual address is represented as a pair (seg_number, offset), but the offset consists of a pair (page_number, page_offset), indicating which page number page_number of the segment seg_number the frame number frame_no is stored in, and the offset page_offset from the base of that page
        
        Self
        
        Segmented Paging
        
        The virtual address is represented as a pair (logical_page, offset), but the logical_page consists of a pair (seg_number, seg_offset) indicating which segment number seg_number of the page table the frame number frame_no is stored in, and the offset seg_offset from the base of that segment table
        
        The page tables are segmented
        
        Self
        
        Frame is in segment
        
        "The page tables are segmented" means the page table entry points to a segment and offset to the segment instead of a direct frame number
      - Disadvantages
        
        Can lead to external fragmentation
      - Advantages
        
        No internal fragmentation
        
        This allows for the loading of smaller segments of the process into memory, allowing the physical memory to be used more efficiently
        
        Once the process of segmentation occurs, the entire process can be loaded into different areas in memory instead of one contiguous space
      - The processes are first 'segmented' (or split) most commonly into three segments, one to house the data, another to house the code and a third to house the stack
    - - Multilevel Paging
    - - Main memory and the registers built into each processing core are the only general-purpose storage that the CPU can access directly
      - There are machine instructions that take memory addresses as arguments, but none that take disk addresses
      - Any instructions in execution, and any data being used by the instructions, must be in one of these direct-access storage devices
      - Register Access
        
        Registers that are built into each CPU core are generally accessible within one cycle of the CPU clock
        
        Some CPU cores can decode instructions and perform simple operations on register contents at the rate of one or more operations per clock tick
      - Memory Access
        
        Main memory, which is accessed via a transaction on the memory bus
        
        Completing a memory access may take many cycles of the CPU clock
        
        In such cases, the processor normally needs to stall, since it does not have the data required to complete the instruction that it is executing
        
        This situation is intolerable because of the frequency of memory accesses
        
        Cache
        
        The remedy is to add fast memory between the CPU and main memory, typically on the CPU chip for fast access
        
        To manage a cache built into the CPU, the hardware automatically speeds up memory access without any operating-system control
    - - Protect the operating system from access by user processes
      - Protect user processes from one another
      - This protection must be provided by the hardware, because the operating system doesn’t usually intervene between the CPU and its memory accesses (because of the resulting performance penalty).
      - Implementation
        
        We first need to make sure that each process has a separate memory space
        
        Separate per-process memory space protects the processes from each other and is fundamental to having multiple processes loaded in memory for concurrent execution
        
        To separate memory spaces, we need the ability to determine the range of legal addresses that the process may access and to ensure that the process can access only these legal addresses
        
        We can provide this protection by using two registers, usually a base and a limit
        
        Base Register
        
        The base register holds the smallest legal physical memory address
        
        Limit Register
        
        The limit register specifies the size of the range
        
        Protection of memory space is accomplished by having the CPU hardware compare every address generated in user mode with the registers
        
        Any attempt by a program executing in user mode to access operating-system memory or other users’ memory results in a trap to the operating system, which treats the attempt as a fatal error
        
        The base and limit registers can be loaded only by the operating system, which uses a special privileged instruction
        
        Since privileged instructions can be executed only in kernel mode, and since only the operating system executes in kernel mode, only the operating system can load the base and limit registers
        
        This scheme allows the operating system to change the value of the registers but prevents user programs from changing the registers’ contents
        
        The operating system, executing in kernel mode, is given unrestricted access to both operating-system memory and users’ memory
        
        This provision allows the operating system to load users’ programs into users’ memory, to dump out those programs in case of errors, to access and modify parameters of system calls, to perform I/O to and from user memory, and to provide many other services
    - - Address
        
        A user program goes through several steps—some of which may be optional—before being executed
        
        Addresses may be represented in different ways during these steps
        
        Addresses in the source program are generally symbolic (such as the variable count)
        
        A compiler typically binds these symbolic addresses to relocatable addresses
        
        The linker or loader in turn binds the relocatable addresses to absolute addresses
        
        Each binding is a mapping from one address space to another
      - Compile Time
        
        If you know at compile time where the process will reside in memory, then absolute code can be generated
      - Load Time
        
        If it is not known at compile time where the process will reside
        in memory, then the compiler must generate relocatable code
        
        In this case, final binding is delayed until load time
        
        If the starting address changes, we need only reload the user code to incorporate this changed value
      - Execution time
        
        If the process can be moved during its execution from one
        memory segment to another, then binding must be delayed until run time
        
        Special hardware must be available for this scheme to work
    - - Logical Address
        
        An address generated by the CPU is commonly referred to as a logical address
        
        We usually refer to the logical address as a virtual address
        
        The set of all logical addresses generated by a program is a logical address space
      - Physical Address
        
        An address seen by the memory unit—that is, the one loaded into the memory-address register of the memory—is commonly referred to as a physical address
        
        The set of all physical addresses corresponding to these logical addresses is a physical address space
      - Binding addresses at either compile or load time generates identical logical and physical addresses
      - The execution-time address-binding scheme results in differing logical and physical addresses
      - In the execution-time address-binding scheme, the logical and physical address spaces differ
    - - The run-time mapping from virtual to physical addresses is done by a hardware device called the memory-management unit (MMU)
      - MMU Schemes
        
        Scheme 1
        
        Relocation Register
        
        The value in the relocation register is added to every address generated by a user process at the time the address is sent to memory
        
        The user program never accesses the real physical addresses
        
        Only when it is used as a memory address (in an indirect load or store, perhaps) is it relocated relative to the base register
        
        The user program deals with logical addresses
        
        The memory mapping hardware converts logical addresses into physical addresses
        
        The final location of a referenced memory address is not determined until the reference is made
    - - A routine is not loaded until it is called
      - All routines are kept on disk in a relocatable load format
      - The main program is loaded into memory and is executed
      - When a routine needs to call another routine, the calling routine first checks to see whether the other routine has been loaded
      - If it has not, the relocatable linking loader is called to load the desired routine into memory and to update the program’s address tables to reflect this change
      - Advantage
        
        The advantage of dynamic loading is that a routine is loaded only when it is needed
        
        This method is particularly useful when large amounts of code are
        needed to handle infrequently occurring cases, such as error routines
        
        Although the total program size may be large, the portion that is
        used (and hence loaded) may be much smaller
      - Dynamic loading does not require special support from the operating system
    - - Linking is postponed until execution time
      - This feature is usually used with system libraries, such as the standard C language library
      - Without this facility, each program on a system must include a
        copy of its language library (or at least the routines referenced by the program) in the executable image
      - This requirement not only increases the size of an executable image but also may waste main memory
      - DLL
        
        When a program references a routine that is in a dynamic library, the loader locates the DLL, loading it into memory if necessary
        
        It then adjusts addresses that reference functions in the dynamic library to the location in memory where the DLL is stored
        
        Updates
        
        Dynamically linked libraries can be extended to library updates
        
        A library may be replaced by a new version, and all programs that reference the library will automatically use the new version
        
        More than one version of a library may be loaded
        into memory, and each program uses its version information to decide which copy of the library to use
      - Dynamic linking and shared libraries generally require help from the operating system
      - If the processes in memory are protected from one another, then the operating system is the only entity that can check to see whether the needed routine is in another process’s memory space or that can allow multiple processes to access the same memory addresses
    - - Each process is contained in a single section of memory that is contiguous to the section containing the next process
      - Memory Protection
        
        Implemented using base and limit registers
      - Dynamic Storage Allocation Problem
        
        Types
        
        First Fit
        
        Searching can start either at the beginning of the set of holes or at the location where the previous first-fit search ended
        
        We can stop searching as soon as we find a free hole that is large enough
        
        Allocate the first hole that is big enough
        
        Best Fit
        
        Allocate the smallest hole that is big enough
        
        We must search the entire list, unless the list is ordered by size
        
        This strategy produces the smallest leftover hole
        
        Worst Fit
        
        Allocate the largest hole
        
        Again, we must search the entire list, unless it is sorted by size
        
        This strategy produces the largest leftover hole, which may be more useful than the smaller leftover hole from a best-fit approach
        
        Next Fit
        
        Next fit is a modified version of ‘first fit’
        
        It begins as the first fit to find a free partition but when called next time it starts searching from where it left off, not from the beginning
        
        This policy makes use of a roving pointer
        
        The pointer moves along the memory chain to search for a next fit
        
        Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization
        
        Neither first fit nor best fit is clearly better than the other in terms of storage utilization, but first fit is generally faster
        
        Fragmentation
        
        External Fragmentation
        
        External fragmentation exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous: storage is fragmented into a large number of small
        holes
        
        Another factor is which end of a free block is allocated. (Which is the leftover piece—the one on the top or the one on the bottom
        
        50-percent rule
        
        Statistical analysis of first fit, for instance, reveals that, even with some optimization, given N allocated blocks, another 0.5 N blocks will be lost to fragmentation
        
        Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation
        
        Solution
        
        Compaction
        
        Shuffle the memory contents so as to place all free memory together in one large block
        
        Compaction is not always possible, however
        
        If relocation is static and is done at assembly or load time, compaction cannot be done
        
        It is possible only if relocation is dynamic and is done at execution time
        
        If addresses are relocated dynamically, relocation requires only moving the program and data and then changing the base register to reflect the new base address
        
        When compaction is possible, we must determine its cost
        
        Scheme 1
        
        2 more items...
        
        Paging
        
        Permit the logical address space of processes to be noncontiguous, thus allowing a process to be allocated physical memory wherever such memory is available
        
        Internal Fragmentation
        
        Keeping track of small holes has overhead of book-keeping
        
        Block sizes can be aligned to avoid overhead
        
        This leads to wasted space at the end of the allocated block
    - - Paging is a memory management scheme that permits a process’s physical address space to be noncontiguous
      - Frames
        
        Breaking physical memory into fixed-sized blocks called frames
      - Pages
        
        Breaking logical memory into blocks of the same size called pages
      - When a process is to be executed, its pages are loaded into any available memory frames from their source (a file system or
        the backing store)
      - The backing store is divided into fixed-sized blocks that are the same size as the memory frames or clusters of multiple frames
      - CPU Address parts
        
        Page Number p
        
        Page Offset d
      - The page number is used as an index into a per-process page table
      - The page table contains the base address of each frame in physical memory, and the offset is the location in the frame being referenced
      - The base address of the frame is combined with the page offset to define the physical memory address
      - The size of a page is a power of 2, typically varying between 4 KB and 1 GB per page
      - If the size of the logical address space is 2^m, and a page size is 2^n bytes, then the high-order m−n bits of a logical address designate the page number, and the n low-order bits designate the page offset
      - Fragmentation
        
        When we use a paging scheme, we have no external fragmentation: any free frame can be allocated to a process that needs it. However, we may have some internal fragmentation
        
        If process size is independent of page size, we expect internal fragmentation to average one-half page per process
        
        This consideration suggests that small page sizes are desirable.
        
        Overhead is involved in each page table entry, and this overhead is reduced as the size of the pages increases
        
        Disk I/O is more efficient when the amount of data being transferred is larger
        
        Generally, page sizes have grown over time as processes, data
        sets, and main memory have become larger
        
        Today, pages are typically either 4 KB or 8 KB in size, and some systems support even larger page sizes
      - Other information must be kept in the page-table entries which reduces the number of bits available to address page frames
      - Frame Table
        
        Since the operating system is managing physical memory, it must be aware of the allocation details of physical memory—which frames are allocated, which frames are available, how many total frames there are, and so on
        
        This information is generally kept in a single, system-wide data structure called a frame table
        
        The frame table has one entry for each physical page frame,
        indicating whether the latter is free or allocated and, if it is allocated, to which page of which process (or processes).
      - OS Handling
        
        The operating system maintains a copy of the page table for each process
        
        This copy is used to translate logical addresses to physical addresses whenever the operating system must map a logical address to a physical address manually
        
        It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU
        
        Paging therefore increases the context-switch time
      - Hardware Support
        
        As page tables are per-process data structures, a pointer to the page table is stored with the other register values (like the instruction pointer) in the process control block of each process
        
        When the CPU scheduler selects a process for execution, it must reload the user registers and the appropriate hardware page-table values from the stored user page table
        
        Hardware Implementation
        
        Implementation 1
        
        The page table is implemented as a set of dedicated high-speed hardware registers, which makes the page-address translation very efficient
        
        This approach increases context-switch time, as each one of
        these registers must be exchanged during a context switch
        
        The use of registers for the page table is satisfactory if the page table is reasonably small
        
        Implementation 2
        
        The page table is kept in main memory, and a page-table base register (PTBR) points to the page table
        
        Changing page tables requires changing only this one register, substantially reducing context-switch time
        
        TLB
        
        The TLB is associative, high-speed memory
        
        Each entry in the TLB consists of two parts: a key (or tag) and a value
        
        When the associative memory is presented with an item, the item is compared with all keys simultaneously
        
        If the item is found, the corresponding value field is returned
        
        The search is fast; a TLB lookup in modern hardware is part of the instruction pipeline, essentially adding no performance penalty
        
        To be able to execute the search within a pipeline step, however, the TLB must be kept small
        
        It is typically between 32 and 1,024 entries in size
        
        Some CPUs implement separate instruction and data address TLBs
        
        That can double the number of TLB entries available, because those lookups occur in different pipeline steps
        
        Replacement
        
        LRU
        
        RR
        
        Random
        
        Some CPUs allow the operating system to participate in LRU entry replacement, while others handle the matter themselves
        
        Wired Down
        
        Some TLBs allow certain entries to be wired down, meaning that they cannot be removed from the TLB
        
        TLB entries for key kernel code are wired down
        
        ASID
        
        Some TLBs store address-space identifier (ASIDs) in each TLB entry
        
        An ASID uniquely identifies each process and is used to provide address-space protection for that process
        
        When the TLB attempts to resolve virtual page numbers, it ensures that the ASID for the currently running process matches the ASID associated with the virtual page
        
        If the ASIDs do not match, the attempt is treated as a TLB miss
        
        In addition to providing address-space protection, an ASID allows the TLB to contain entries for several different processes simultaneously
        
        If the TLB does not support separate ASIDs, then every time a new page table is selected (for instance, with each context switch), the TLB must be flushed (or erased) to ensure that the next executing process does not use the wrong translation information
        
        Otherwise, the TLB could include old entries that contain valid virtual addresses but have incorrect or invalid physical addresses left over from the previous process
        
        Effective memory-access time
        
        The percentage of times that the page number of interest is found in the TLB is called the hit ratio
        
        If it takes 10 nanoseconds to access memory, then a mapped-memory access takes 10 nanoseconds when the page number is in the TLB
        
        If we fail to find the page number in the TLB then we must first access memory for the page table and frame number (10 nanoseconds) and then access the desired byte in memory
        (10 nanoseconds), for a total of 20 nanoseconds
        
        Effective Access Time = hr × 10 + (1-hr) × 20
        
        Multi-Level
        
        CPUs today may provide multiple levels of TLBs
      - Protection
        
        RWX
        
        Normally, these bits are kept in the page table
        
        One bit can define a page to be read–write or read-only
        
        Memory protection in a paged environment is accomplished by protection bits associated with each frame
        
        At the same time that the physical address is being computed, the protection bits can be checked to verify that no writes are being made to a read-only page
        
        An attempt to write to a read-only page causes a hardware trap to the operating system (or memory-protection violation)
        
        Can be extended to read-only, read–write, or execute-only
        protection
        
        Valid
        
        When the valid-invalid bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page
        
        When the bit is set to invalid, the page is not in the process’s logical address space
        
        Illegal addresses are trapped by use of the valid–invalid bit
        
        The operating system sets this bit for each page to allow or disallow access to the page
        
        Internal fragmentation issue where due to page granularity some memory at the end of page may be invalid for a valid page to to program size not being a multiple of page size
        
        Page-table length register
        
        Many processes use only a small fraction of the address space available to them
        
        Some systems provide hardware, in the form of a page-table length register (PTLR), to indicate the size of the page table
        
        This value is checked against every logical address to verify that the address is in the valid range for the process
        
        Failure of this test causes an error trap to the operating system
      - Page Table Structure
        
        Hierarchical Paging
        
        Use a two-level paging algorithm, in which the page table itself is also paged
        
        A logical address is divided into a page number consisting of 20 bits and a page offset consisting of 12 bits
        
        The page number is further divided into a 10-bit page number and a 10-bit page offset
        
        Because address translation works from the outer page table inward, this scheme is also known as a forward-mapped page table
        
        Divides the page table into smaller pieces
        
        Can be extended to multiple levels
        
        Hashed Page Tables
        
        The virtual page number in the virtual address is hashed into the hash table
        
        The virtual page number is compared with field 1 in the first element in the linked list
        
        If there is a match, the corresponding page frame (field 2) is used to form the desired physical address
        
        If there is no match, subsequent entries in the linked list are searched for a matching virtual page number
        
        Clustered page tables
        
        Each entry in the hash table refers to several
        pages (such as 16) rather than a single page
        
        A single page-table entry can store the mappings for multiple physical-page frames
        
        Clustered page tables are particularly useful for sparse address spaces, where memory references are noncontiguous and scattered throughout the address space
        
        Inverted Page Tables
        
        An inverted page table has one entry for each real page (or frame) of memory
        
        Each entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns the page
        
        Only one page table is in the system, and it has only one entry for each page of physical memory
        
        Inverted page tables often require that an address-space identifier be stored in each entry of the page table, since the table usually contains several different address spaces mapping physical memory
        
        Storing the address-space identifier ensures that a logical page for a particular process is mapped to the corresponding physical page frame
        
        Each inverted page-table entry is a pair <process-id, page number> where the process-id assumes the role of the address-space identifier
        
        When a memory reference occurs, part of the virtual address, consisting of <process-id, page-number>, is presented to the memory subsystem
        
        The inverted page table is then searched for a match
        
        If a match is found—say, at entry i—then the physical address <i, offset> is generated. If no match is found, then an illegal address access has been attempted
        
        Cannot share pages across processes
    - - A process, or a portion of a process, can be swapped temporarily out of memory to a backing store and then brought back into memory for continued execution
      - Swapping makes it possible for the total physical address space of all processes to exceed the real physical memory of the system, thus increasing the degree of multiprogramming in a
        system
      - Standard Swapping
        
        Standard swapping involves moving entire processes between main memory and a backing store
        
        The backing store is commonly fast secondary storage
        
        It must be large enough to accommodate whatever parts of processes need to be stored and retrieved, and it must provide direct access to these memory images
        
        When a process or part is swapped to the backing store, the data
        structures associated with the process must be written to the backing store
        
        For a multithreaded process, all per-thread data structures must be swapped as well
        
        The operating system must also maintain metadata for processes that have been swapped out, so they can be restored when they are swapped back in to memory
      - Swapping with Paging
        
        pages of a process—rather than an entire process—can be swapped
        
        This strategy still allows physical memory to be oversubscribed, but does not incur the cost of swapping entire processes, as presumably only a small number of page swill be involved in swapping
        
        Page out
        
        A page out operation moves a page from memory to the backing store
        
        Page In
        
        A page in operation moves a page from backing
        store to the memory
    - - Demand Paging
        
        Pages are loaded only when they are demanded during program execution
        
        While a process is executing, some pages will be in memory, and some will be in secondary storage
        
        Pages that are never accessed are thus never loaded into physical memory
        
        A demand-paging system is similar to a paging system with swapping where processes reside in secondary memory (usually an HDD or NVM device)
        
        Implementation
        
        Uses Valid/Invalid bit
        
        When the bit is set to “valid,” the associated page is both legal and in memory
        
        If the bit is set to “invalid,” the page either is not valid (that
        is, not in the logical address space of the process) or is valid but is currently in secondary storage
        
        Page Fault
        
        Access to a page marked invalid causes a page fault
        
        The paging hardware, in translating the address through the page table, will notice that the invalid bit is set, causing a trap to the operating system
        
        This trap is the result of the operating system’s failure to bring the desired page into memory
        
        Handling
        
        We check an internal table (usually kept with the process control block) for this process to determine whether the reference was a valid or an invalid memory access
        
        If the reference was invalid, we terminate the process
        
        If it was valid but we have not yet brought in that page, we now page it in
        
        We find a free frame
        
        We schedule a secondary storage operation to read the desired page into the newly allocated frame
        
        When the storage read is complete, we modify the internal table kept with the process and the page table to indicate that the page is now in memory
        
        We restart the instruction that was interrupted by the trap
        
        The process can now access the page as though it had always been in memory
        
        Pure demand paging
        
        Never bring a page into memory until it is required
        
        Process State
        
        A crucial requirement for demand paging is the ability to restart any instruction after a page fault
        
        Because we save the state (registers, condition code, instruction counter) of the interrupted process when the page fault occurs, we must be able to restart the process in exactly the same place and state, except that the desired page is now in memory and is accessible
        
        A page fault may occur at any memory reference
        
        If the page fault occurs on the instruction fetch, we can restart by fetching the instruction again
        
        If a page fault occurs while we are fetching an operand, we must fetch and decode the instruction again and then fetch the operand
        
        Entire instruction till the point of fault will be repeated which may involve loading some operands again as well
        
        Re-Execution
        Handling
        
        Access pages before execution so faults occur before any data is partially modified
        
        Keep partial data in registers to restore on second execution
        
        Free Frame List
        
        When a page fault occurs, the operating system must bring the desired page from secondary storage into main memory
        
        To resolve page faults, most operating systems maintain a free-frame list, a pool of free frames for satisfying such requests
        
        Free frames must also be allocated when the stack or heap segments from a process expand
        
        Zero-fill-on-demand
        
        Zero-fill-on- demand frames are “zeroed-out” before being allocated, thus erasing their previous contents
        
        When a system starts up, all available memory is placed on the free-frame list
        
        Performance
        
        Effective Access Time
        
        Effective Access Time = (1 − p) × ma + p × page fault time
        
        EMAT = h*(T + M) + (1 - h)*((1 - p)*2M + p*((1 - d)*(D + M) + d*(2D + M))
        
        Page Fault Sequence
        
        Trap to the operating system
        
        Save the registers and process state
        
        Determine that the interrupt was a page fault
        
        Check that the page reference was legal, and determine the location of the page in secondary storage
        
        Issue a read from the
        storage to a free frame
        
        Wait in a queue until the read request is serviced
        
        Wait for the device seek and/or latency time
        
        Begin the transfer of the page to a free frame
        
        While waiting, allocate the CPU core to some other process
        
        Receive an interrupt from the storage I/O subsystem (I/O completed).
        
        Save the registers and process state for the other process
        
        Determine that the interrupt was from the secondary storage device
        
        Correct the page table and other tables to show that the desired page is now in memory
        
        Wait for the CPU core to be allocated to this process again
        
        Restore the registers, process state, and new page table, and then resume the interrupted instruction
        
        The effective access time is directly proportional to the page-fault rate
        
        Swap IO
        
        I/O to swap space is generally faster than that to the file system
        
        Faster because
        
        swap space is allocated in much larger blocks
        
        File lookups and indirect allocation methods are not used
        
        Gain better paging throughput is by copying an entire file image into the swap space at process startup and then performing demand paging from the swap space
        
        The obvious disadvantage of this approach is the copying of the file image at program start-up
        
        A second option—and one practiced by several operating systems, including Linux and Windows—is to demand-page
        from the file system initially but to write the pages to swap space as they are replaced
        
        This approach will ensure that only needed pages are read from the file system but that all subsequent paging is done from swap space
        
        Some systems attempt to limit the amount of swap space used through demand paging of binary executable files
        
        Demand pages for such files are brought directly from the file system
        
        When page replacement is called for, these frames can simply be overwritten (because they are never modified), and the pages can be read in from the file system again if needed
        
        Using this approach, the file system itself serves as the backing store
        
        Swap space must still be used for pages not associated with a file (known as anonymous memory); these pages include the stack and heap for a process
        
        Copy On Write
        
        Allowing the parent and child processes initially to share the same pages
        
        These shared pages are marked as copy-on-write pages, meaning that if either process writes to a shared page, a copy of the shared page is created
        
        Only the pages that are modified by either process are copied; all unmodified pages can be shared by the parent and child processes
        
        Only pages that can be modified need be marked as copy-on-write
        
        Pages that cannot be modified (pages containing executable code) can be shared by the parent and child
        
        vfork
        
        vfork() does not use copy-on-write, if the child process changes any pages of the parent’s address space, the altered pages will be visible to the parent once it resumes.
        
        vfork() must be used with caution to ensure that the child process does not modify the address space of the parent
        
        vfork() is intended to be used when the child process calls exec() immediately after creation
      - Virtual memory involves the separation of logical memory as perceived by developers from physical memory
      - This separation allows an extremely large virtual memory to be provided for programmers when only a smaller physical memory is available
      - Virtual memory makes the task of programming much easier, because the programmer no longer needs to worry about the amount of physical memory available; she can concentrate instead on programming the problem that is to be solved
      - The virtual address space of a process refers to the logical (or virtual) view of how a process is stored in memory
      - This view is that a process begins at a certain logical address—say, address 0—and exists in contiguous memory
      - Sparse Address
        
        Virtual address spaces that include holes are known as sparse address spaces
        
        Using a sparse address space is beneficial because the holes can be filled as the stack or heap segments grow or if we wish to dynamically link libraries (or possibly other shared objects) during program execution
      - Advantages
        
        System libraries such as the standard C library can be shared by several processes through mapping of the shared object into a virtual address space
        
        Processes can share memory
        
        Pages can be shared during process creation with the fork() system call, thus speeding up process creation
      - Page Replacement
        
        Frame-allocation algorithm
        
        Page-replacement algorithm
        
        FIFO Page Replacement
        
        Second Chance Page Replacement
        
        A simple modification to FIFO that avoids the problem of throwing out a heavily used page is to inspect the R bit of the oldest page
        
        If it is 0, the page is both old and unused, so it is replaced immediately
        
        If the R bit is 1, the bit is cleared, the page is put onto the end of the list of pages, and its load time is updated as though it had just arrived in memory
        
        Then the search continues
        
        Belady’s anomaly
        
        For some page-replacement algorithms, the page-fault rate may increase as the number of allocated frames increases
        
        Reason
        
        With larger memory, pages near back of queue can be recently accessed pages
        
        As faults occurs, these pages will be removed, and if the access order is same the pages at the end of the queue, more faults occur
        
        With smaller memory size, there is less probability of pages at the back of queue being recently accessed as page faults will move the pages out of the queue
        
        Algorithms with this anomaly
        
        FIFO Page Replacement Algorithm
        
        Random Page Replacement Algorithm
        
        Second Chance Algorithm
        
        Stack Based Algorithms
        
        A stack based algorithm is one for which it can be shown that the set of pages in memory for N frames is always a subset of the set of pages that would be in memory with N + 1 frames
        
        For LRU replacement, the set of pages in memory would be the n most recently referenced pages
        
        If the number of frames increases then these n pages will still be the most recently referenced and so, will still be in the memory
        
        Belady’s Anamoly can never occur in these algorithms for any reference string as they belong to a class of stack based page replacement algorithms
        
        Optimal Page Replacement
        
        Replace the page that will not be used for the longest period of time
        
        Use of this page-replacement algorithm guarantees the lowest possible page fault rate for a fixed number of frames
        
        Difficult to implement, because it requires future knowledge of the reference string
        
        The optimal algorithm is used mainly for comparison
        studies
        
        LRU Page Replacement
        
        Replace the page that has not been used for the longest period of time
        
        LRU replacement associates with each page the time of that page’s last use
        
        When a page must be replaced, LRU chooses the page that has not been used for the longest period of time
        
        LRU-Approximation
        Page Replacement
        
        Additional-Reference-Bits Algorithm
        
        Second-Chance Algorithm
        
        Enhanced Second-Chance Algorithm
        
        Counting-Based
        Page Replacement
        
        Least Frequently Used(LFU)
        
        Most Frequently Used(MFU)
        
        Page-Buffering Algorithms
        
        When a page fault occurs, a victim frame is chosen as before
        
        The desired page is read into a free frame from the pool before the victim is written out
        
        This procedure allows the process to restart as soon as possible, without waiting for the victim page to be written out
        
        When the victim is later written out, its frame is added to the free-frame pool
        
        Modification 1
        
        Whenever the paging device is idle, a modified page is selected and is written to secondary storage
        
        Its modify bit is then reset
        
        This scheme increases the probability that a page will be clean when it is selected for replacement and will not need to be
        written out
        
        An expansion of this idea is to maintain a list of modified pages
        
        Modification 2
        
        Another modification is to keep a pool of free frames but to remember which page was in each frame
        
        Since the frame contents are not modified when a frame is written to secondary storage, the old page can be reused directly from
        the free-frame pool if it is needed before that frame is reused
        
        No I/O is needed in this case
        
        When a page fault occurs, we first check whether the desired page is in the free-frame pool
        
        If it is not, we must select a free frame and read into it
        
        Results
        
        Repeated Sequence Of Page Numbers
        
        Optimal page replacement algorithm replaces the most recently used page to minimize the page faults
        
        This is because most recently page will be required after the longest time
        
        Optimal page replacement algorithm acts as Most Recently Used (MRU) page replacement algorithm
        
        CPU may generate such a reference string when executing loops
        
        This is because while executing loops, same set of instructions have to be executed again and again
        
        The behavior of Optimal page replacement algorithm contradicts with the principle of locality
        
        Optimal algorithm replaces the most recently used page to give the optimal performance
        
        We can infer that principle of locality does not hold true in certain scenarios
        
        Principle of locality states that the next reference would be most probably from the most recently used pages
        
        First Half String Is a Mirror Image Of Other Half
        
        Optimal page replacement algorithm replaces the least recently used page or firstly arrived page to minimize page faults
        
        This is because such a page will be required after the longest time
        
        Optimal page replacement algorithm acts as LRU and FIFO page replacement algorithm
        
        LRU and FIFO page replacement algorithm will behave as Optimal page replacement algorithm
        
        LRU and FIFO page replacement algorithm gives the optimal performance
        
        FIFO page fauts
        
        2*L-N
        
        L = Length of first half
        
        N = Number of page frames
        
        The first half will generate L page faults
        
        The reverse direct N frames will not cause page faults
        
        Remaining L-N frame will cause page faults
      - Frame Allocation
        
        Minimum Number of Frames
        
        The minimum number of frames per process is defined by the architecture
        
        Allocation Algorithms
        
        Equal Allocation
        
        The easiest way to split m frames among n processes is to give everyone an equal share, m/n frames
        
        Proportional allocation
        
        Allocate available memory to each process according to its size
        
        Global versus Local Allocation
        
        Global Replacement
        
        Global replacement allows a process to select a replacement frame from the set of all frames, even if that frame is currently allocated to some other process
        
        Schemes
        
        We allow high priority processes to select frames from low-priority processes for replacement
        
        A process can select a replacement from among its own frames or the frames of any lower-priority process
        
        Local Replacement
        
        Local replacement requires that each process select from only its own set of allocated frames
      - Kernel Memory Allocation
        
        Buddy System
        
        Memory is allocated from this segment using a power-of-2 allocator, which satisfies requests in units sized as a power of 2
        
        A request in units not appropriately sized is rounded up to the next highest power of 2
        
        An advantage of the buddy system is how quickly adjacent buddies can be combined to form larger segments using a technique known as coalescing
        
        When a larger block is split, it is divided into two smaller blocks, and each smaller block becomes a unique buddy to the other
        
        A split block can only be merged with its unique buddy block, which then reforms the larger block they were split from
        
        The buddy system allocates memory from a fixed-size segment consisting of physically contiguous pages
        
        Slab Allocation
        
        A slab is made up of one or more physically contiguous pages
        
        A cache consists of one or more slabs
        
        There is a single cache for each unique kernel data structure
        
        Each cache is populated with objects that are instantiations of the kernel data structure the cache represents
        
        Other Factors
        
        Prepaging
        
        Bring some—or all—of the pages that will be needed into memory at one time
        
        Pre-paging is an attempt to prevent this high level of initial paging
        
        Page Size
        
        Decreasing the page size increases the number of pages and hence the size of the page table
        
        Decreasing page size reduces internal fragmentation
        
        A desire to minimize I/O time argues for a larger page size
        
        With a smaller page size, though, total I/O should be reduced, since locality will be improved
        
        A smaller page size allows each page to match program locality more accurately
        
        TLB Reach
        
        TLB reach refers to the amount of memory accessible from the TLB and is simply the number of entries multiplied by the page size
        
        Ideally, the working set for a process is stored in the TLB
        
        If it is not, the process will spend a considerable amount of time resolving memory references in the page table rather than the TLB
        
        If we double the number of entries in the TLB, we double the TLB reach
        
        Another approach for increasing the TLB reach is to either increase the size of the page or provide multiple page sizes
        
        I/O Interlock and Page Locking
        
        Allow pages to be locked into memory
        
        A lock bit is associated with every frame
        
        If the frame is locked, it cannot be selected for replacement
        
        To write a block to disk, we lock into memory the pages containing the block
        
        Locked pages cannot be replaced.
        
        When the I/O is complete, the pages are unlocked
    - - Cache Write Policy.
        
        Write Hit
        
        Write Through
        
        Simpler and more reliable
        
        Used when number of write operation is less
        
        It helps in data recovery (In case of power outage or system failure)
        
        A data write will experience latency (delay) as we have to write to two locations (both Memory and Cache)
        
        It solves the inconsistency problem
        
        But it questions the advantage of having a cache in write operation
        
        Data is simultaneously updated to cache and memory
        
        Write Back
        
        The data is updated only in the cache and updated into the memory in later time
        
        Data is updated in the memory only when the cache line is ready to replaced
        
        Cache line replacement is done using Least Recently Used Algorithm, FIFO, LIFO and others depending on the application
        
        Write Back is also known as Write Deferred
        
        Dirty Bit
        
        Each Block in the cache needs a bit to indicate if the data present in the cache was modified(Dirty) or not modified(Clean)
        
        If it is clean there is no need to write it into the memory
        
        Write Miss
        
        Write Allocation
        
        Write allocation works with both Write back and Write through
        
        But it is generally used with Write Back because it is unnecessary to bring data from the memory to cache and then updating the data in both cache and main memory
        
        In Write Allocation data is loaded from the memory into cache and then updated
        
        Write Around/No-Write Allocate
        
        Directly written/updated to main memory without disturbing cache
        
        It is better to use this when the data is not immediately used again
        
        Write-through caches often use no-write allocate
  - - - Memory Management
      - Storage Management
      - Process Management
      - Security
      - Resource Management
  - - - C-SCAN
        
        Circular SCAN (C-SCAN) scheduling is a variant of SCAN designed to provide a more uniform wait time
        
        C-SCAN moves the head from one end of the disk to the other, servicing requests along the way
        
        When the head reaches the other end, however, it immediately returns to the beginning of the disk without servicing any requests on the return trip
        
        Preconditions
        
        Initial position of head
        
        Initial direction of head movement
      - SCAN
        
        Algo
        
        At the other end, the direction of head movement is reversed, and servicing continues
        
        The head continuously scans back and forth across the disk
        
        The disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk
        
        Preconditions
        
        Initial position of head
        
        Initial direction of head movement
        
        SCAN Algorithm is also called as Elevator Algorithm
      - FCFS
        
        Service each request in order without any optimization
      - LOOK
        
        Continue moving in initial direction to the last requested track(not the end track) in the initial direction
        
        Return back to the last request on the other end(not the end track)
        
        Reverse direction and service the remaining requests
        
        Preconditions
        
        Initial position of head
        
        Initial direction of head movement
      - SSTF
        
        This algorithm services that request next which requires least number of head movements from its current position regardless of the direction.
        
        It breaks the tie in the direction of head movement.
      - C-LOOK
        
        In CLOOK, the disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request
      - N-STEP SCAN
      - FSCAN
        
        FSCAN along with N-Step-SCAN prevents "arm stickiness" unlike SSTF, SCAN, and C-SCAN
        
        Arm stickiness in those other algorithms occurs when a stream of requests for the same track causes the disk arm to stop progressing at that track, preferring to satisfy the no-seek requests for the track it is on
  - - - In Kernel mode, the executing code has complete and unrestricted access to the underlying hardware
      - It can execute any CPU instruction and reference any memory address
      - Kernel mode is generally reserved for the lowest-level, most trusted functions of the operating system
      - Crashes in kernel mode are catastrophic; they will halt the entire PC
    - - In User mode, the executing code has no ability to directly access hardware or reference memory
      - Code running in user mode must delegate to system APIs to access hardware or memory
      - Due to the protection afforded by this sort of isolation, crashes in user mode are always recoverable
      - Most of the code running on your computer will execute in user mode
    - - User Mode to Kernel Mode
        
        Software Interrupt
        
        A software interrupt is requested by the processor itself upon executing particular instructions or when certain conditions are met
        
        Every software interrupt signal is associated with a particular interrupt handler
        
        Software interrupts may also be unexpectedly triggered by program execution errors
        
        These interrupts typically are called traps or exceptions
        
        For example, a divide-by-zero exception will be "thrown" (a software interrupt is requested) if the processor executes a divide instruction with divisor equal to zero
        
        Typically, the operating system will catch and handle this exception
        
        A software interrupt may be intentionally caused by executing a special instruction which, by design, invokes an interrupt when executed
        
        Such instructions function similarly to subroutine calls and are used for a variety of purposes, such as requesting operating system services and interacting with device drivers (e.g., to read or write storage media)
      - Kernel Mode to User Mode
        
        Unprivileged Instruction can be used to
        change from Kernel Mode to user Mode
  - - - Per-process table
        
        The per-process table tracks all files that a process has open
        
        Stored in this table is information regarding the process’s use of the file
        
        Access rights to the file and accounting information can
        also be included
        
        Each entry in the per-process table in turn points to a system-wide open-file table
      - System-wide table
        
        The system-wide table contains process-independent information, such as the location of the file on disk, access dates, and file size
        
        Once a file has been opened by one process, the system-wide table includes an entry for the file
        
        When another process executes an open() call, a new entry is simply added to the process’s open-file table pointing to the appropriate entry in the systemwide table
        
        The open-file table also has an open count associated with
        each file to indicate how many processes have the file open
        
        Each close() decreases this open count, and when the open count reaches zero, the file is no longer in use, and the file’s entry is removed from the open-file table
    - - File pointer
      - File-open count
      - Location of the file
      - Access rights
    - - File locks allow one process to lock a file and prevent other processes from gaining access to it
      - File locks are useful for files that are shared by several processes
      - Types
        
        Exclusive Lock
        
        If the locking scheme is mandatory,
        the operating system ensures locking integrity
        
        Shared Lock
        
        A shared lock is akin to a reader lock in that several processes can acquire the lock concurrently
        
        Mandatory Lock
        
        Once a process acquires an exclusive lock, the operating system will prevent any other process from accessing the locked file
        
        Advisory Lock
        
        It is up to software developers to ensure that locks are appropriately acquired and released
      - Lock Granularity
        
        Locking entire file
        
        Locking range of bytes
    - - File extension in file name
      - Magic number
    - - File types also can be used to indicate the internal structure of the file
      - Source and object files have structures that match the expectations of the programs that read them
      - This scheme provides maximum flexibility but little support
      - The operating system requires that an executable file have a specific structure so that it can determine where in memory to load the file and what the location of the first instruction is
      - This approach has been adopted in UNIX, Windows, and others.
        UNIX considers each file to be a sequence of 8-bit bytes; no interpretation of these bits is made by the operating system
      - Some operating systems impose (and support) a minimal number of file structures
      - Having the operating system support multiple file structures: it makes the operating system large and cumbersome
      - Some operating systems extend this idea into a set of system-supported file structures, with sets of special operations for manipulating files with those structures
      - Each application program must include its own code to interpret an input file as to the appropriate structure
      - All operating systems must support at least one structure—that of an executable file—so that the system is able to load and run programs
      - Internal File Structure
        
        Logical Record
        
        Physical Record
        
        It is unlikely that the physical record size will exactly match the length of the desired logical record
        
        Logical records may even vary in length
        
        Packing a number of logical records into physical blocks is a common solution to this problem
        
        The logical record size, physical block size, and packing technique determine how many logical records are in each physical block
        
        All the basic I/O functions operate in terms of blocks
        
        The conversion from logical records to physical blocks is a relatively simple software problem
        
        Fragmentation
        
        The waste incurred to keep everything in units of blocks (instead of bytes) is internal fragmentation
    - - Sequential Access
        
        The simplest access method is sequential access
        
        Information in the file is processed in order, one record after the other
        
        Reads and writes make up the bulk of the operations on a file
        
        This mode of access is by far the most common
        
        Such a file can be reset to the beginning, and on some systems, a program may be able to skip forward or backward n records for some integer n—perhaps only for n = 1.
        
        The write operation—write next()—appends to the end of the file and advances to the end of the newly written material (the new end of file)
        
        A read operation—read next()—reads the next portion of the file and automatically advances a file pointer, which tracks the I/O location
        
        Sequential access is based on a tape model of a file and
        works as well on sequential-access devices as it does on random-access ones
      - Direct/Relative Access
        
        A file is made up of fixed-length logical records that allow programs to read and write records rapidly in no particular order
        
        The direct-access method is based on a disk model of a file, since disks allow random access to any file block
        
        The file is viewed as a numbered sequence of blocks or records
        
        Direct-access files are of great use for immediate access to large amounts of information
        
        For the direct-access method, the file operations must be modified to include the block number as a parameter
        
        Implementation
        
        Read/Write with block number
        
        Read/Write_next with positioning call
        
        Block Number
        
        The block number provided by the user to the operating system is normally a relative block number
        
        A relative block number is an index relative to the beginning of the file
      - Indexed Access
        
        Primary/Seconday Index
        
        ISAM
        
        Indexed Sequential Access Method
    - - The directory can be viewed as a symbol table that translates file names into their file control blocks
      - Operations
        
        Search for a file
        
        Create a file
        
        Delete a file
        
        Rename a file
        
        List a directory
        
        Traverse a file
      - Directory Structure
        
        Single Level
        
        Two Level
        
        User File Directory(UFD)
        
        Master File Directory(MFD)
        
        Tree Structured
        
        Acyclic Graph
        
        General Graph
    - - Use the virtual memory techniques to treat file I/O as routine memory accesses
      - It allows a part of the virtual address space to be logically associated with the file
      - Memory mapping a file is accomplished by mapping a disk block to a page (or pages) in memory
      - This can lead to significant performance increases
      - A page-sized portion of the file is read from the file system into a physical page (some systems may opt to read in more than a page-sized chunk of memory at a time)
      - Subsequent reads and writes to the file are handled as routine memory accesses
      - Manipulating files through memory rather than incurring the overhead of using the read() and write() system calls simplifies and speeds up file access and usage
      - Initial access to the file proceeds through ordinary demand paging, resulting in a page fault
      - Writes to the file mapped in memory are not necessarily immediate (synchronous) writes to the file on secondary storage
      - Systems update the file based on changes to the memory image only when the file is closed
      - Under memory pressure, systems will have any intermediate changes to swap space to not lose them when freeing memory for other uses
      - When the file is closed, all the memory-mapped data are written back to the file on secondary storage and removed from the virtual memory of the process
      - Some operating systems provide memory mapping only through a specific system call and use the standard system calls to perform all other file I/O
      - some systems choose to memory-map a file regardless of whether the file was specified as memory-mapped
      - Solaris treats all file I/O as memory mapped, allowing file access to take place via the efficient memory subsystem and avoiding system call overhead caused by each traditional read() and write()
      - Solaris still memory-maps the file; however, the file is mapped to the kernel address space, file was not explicitly mapped by user
      - Multiple processes may be allowed to map the same file concurrently, to allow sharing of data
      - Writes by any of the processes modify the data in virtual memory and can be seen by all others that map the same section of the file
      - The memory-mapping system calls can also support copy-on-write functionality, allowing processes to share a file in read-only
        mode but to have their own copies of any data they modify
    - - Disks are preferred
        
        A disk can be rewritten in place
        
        It is possible to read a block from the disk, modify the block, and write it back into the same block
        
        A disk can access directly any block of information it contains
      - To improve I/O efficiency, I/O transfers between memory and mass storage are performed in units of blocks
      - Each block on a hard disk drive has one or more sectors
      - File systems provide efficient and convenient access to the storage device by allowing data to be stored, located, and retrieved easily
      - File System Design Problems
        
        Defining how the file system should look to the user
        
        Defining a file and its attributes
        
        The operations allowed on a file
        
        The directory structure for organizing files
        
        Creating algorithms and data structures to map the logical file system onto the physical secondary-storage devices
      - Layers FS
        
        Layers
        
        Logical file system
        
        Manages metadata information
        
        Metadata includes all of the file-system structure except the actual data (or contents of the files)
        
        The logical file system manages the directory structure to provide
        the file-organization module with the information the latter needs, given a symbolic file name
        
        It maintains file structure via file-control blocks
        
        A file control block (FCB) (an inode in UNIX file systems) contains information about the file, including ownership, permissions, and location of the file contents
        
        The logical file system is also responsible for protection
        
        File-organization module
        
        Knows about files and their logical blocks
        
        Each file’s logical blocks are numbered from 0 (or 1) through N
        
        The file organization module also includes the free-space manager, which tracks unallocated blocks and provides these blocks to the file-organization module when requested
        
        Basic file system
        
        Issue generic commands to the appropriate device driver to read and write blocks on the storage device
        
        It issues commands to the drive based on logical block addresses
        
        It is also concerned with I/O request scheduling
        
        This layer also manages the memory buffers and caches that hold various filesystem, directory, and data blocks
        
        A block in the buffer is allocated before the transfer of a mass storage block can occur
        
        When the buffer is full, the buffer manager must find more buffer memory or free up buffer space to allow a requested I/O to complete
        
        Caches are used to hold frequently used file-system metadata to improve performance, so managing their contents is critical for
        optimum system performance
        
        I/O control
        
        The I/O control level consists of device drivers and interrupt handlers to transfer information between the main memory and the disk system
        
        Its input consists of high level commands, such as “retrieve block 123.”
        
        Its output consists of low-level, hardware-specific instructions that are used by the hardware controller, which interfaces the I/O device to the rest of the system
        
        The device driver usually writes specific bit patterns to special locations in the I/O controller’s memory to tell the controller which device location to act on and what actions to take
        
        Devices
        
        Application programs
        
        When a layered structure is used for file-system implementation, duplication of code is minimized
        
        The I/O control and sometimes the basic file-system
        code can be used by multiple file systems
        
        The use of layering, including the decision about how many layers to use and what each layer should do, is a major challenge in designing new systems
        
        Each file system can then have its own logical file-system and file-organization modules
        
        Layering can introduce more operating-system overhead, which may result in decreased performance
    - - On Storage Structures
        
        Boot Control Block
        
        A boot control block (per volume) can contain information needed by the system to boot an operating system from that volume
        
        If the disk does not contain an operating system, this block can be empty
        
        It is typically the first block of a volume
        
        In UFS, it is called the boot block. In NTFS, it is the partition boot sector
        
        Volume Control Block
        
        Contains volume details
        
        Number of blocks in the volume
        
        The size of the blocks
        
        Free-block count
        
        Free-block pointers
        
        Free-FCB count
        
        FCB pointers
        
        In UFS, this is called a superblock. In NTFS, it is stored in the master file table
        
        Directory Structure
        
        A directory structure (per file system) is used to organize the files
        
        In UFS, this includes file names and associated inode numbers. In NTFS, it is stored in the master file table
        
        File Control Block
        
        A per-file FCB contains many details about the file
        
        It has a unique identifier number to allow association with a directory entry
        
        In NTFS, this information is actually stored within the master file table, which uses a relational database structure, with a row per file
      - In Memory Structures
        
        An in-memory mount table contains information about each mounted volume
        
        An in-memory directory-structure cache holds the directory information of recently accessed directories
        
        The per-process open-file table contains pointers to the appropriate entries in the system-wide open-file table, as well as other information, for all files the process has open
        
        The system-wide open-file table contains a copy of the FCB of each open file, as well as other information
        
        Buffers hold file-system blocks when they are being read from or written to a file system
      - File Creation Process
        
        A process calls the logical file system
        
        The logical file system knows the format of the directory structures
        
        To create a new file, it allocates a new FCB
        
        The system then reads the appropriate directory into memory, updates it with the new file name and FCB, and writes it back to the file system
      - File Usage Process
        
        The open() call passes a file name to the logical file system
        
        The open() system call first searches the system-wide open-file table to see if the file is already in use by another process
        
        If the file is not already open, the directory structure is searched for the given file name
        
        If it is, a per-process open-file table entry is created pointing to the existing system-wide open-file table
        
        Parts of the directory structure are usually cached in memory to speed directory operations
        
        Once the file is found, the FCB is copied into a system-wide open-file table in memory
        
        This table not only stores the FCB but also tracks the number of processes that have the file open
        
        An entry is made in the per-process open-file table, with a pointer
        to the entry in the system-wide open-file table and some other fields
        
        Other fields may include a pointer to the current location in the file (for the next read() or write() operation) and the access mode in which the file is open
        
        The open() call returns a pointer to the appropriate entry in the per-process file-system table
        
        All file operations are then performed via this pointer
        
        The file name may not be part of the open-file table, as the system has no use for it once the appropriate FCB is located on disk
        
        It could be cached, though, to save time on subsequent opens of the same file
        
        The name given to the entry varies. UNIX systems refer to it as a fil descriptor; Windows refers to it as a fil handle
        
        When a process closes the file, the per-process table entry is removed, and the system-wide entry’s open count is decremented
        
        When all users that have opened the file close it, any updated metadata are copied back to the disk-based directory structure, and the system-wide open-file table entry is removed
      - Directory Implementation
        
        The selection of directory-allocation and directory-management algorithms significantly affects the efficiency, performance, and reliability of the file system
        
        Linear List
        
        Hash Table
      - Allocation Methods
        
        The direct-access nature of secondary storage gives us flexibility in the implementation of files
        
        In almost every case, many files are stored on the same
        device
        
        The main problem is how to allocate space to these files so that storage space is utilized effectively and files can be accessed quickly
        
        Methods
        
        Contiguous
        
        External fragmentation
        
        Extent
        
        Supports both sequential and random access
        
        Linked
        
        Supports only sequential access
        
        Pointers waste space in block
        
        Clustering is solution
        
        Reliability issue
        
        Solution
        
        Doubly Linked List
        
        Store Name, Relative Block number in each block
        
        Variation
        
        File Allocation Table
        
        A section of storage at the beginning of each
        volume is set aside to contain the table
        
        The table has one entry for each block and is indexed by block number
        
        The directory entry contains the block number of the first block of the file
        
        The table entry indexed by that block number contains the block number of the next block in the file
        
        This chain continues until it reaches the last block, which has a special end-of-file value as the table entry
        
        An unused block is indicated by a table value of 0
        
        Allocating a new block to a file is a simple matter of finding the first 0-valued table entry and replacing the previous end-of-file value with the address of the new block
        
        The 0 is then replaced with the end-of-file value
        
        The FAT allocation scheme can result in a significant number of disk head seeks, unless the FAT is cached
        
        The disk head must move to the start of the volume to read the FAT and find the location of the block in question, then move to the location of the block itself
        
        In the worst case, both moves occur for each of the blocks
        
        A benefit is that random-access time is improved, because
        the disk head can find the location of any block by reading the information in the FAT
        
        Indexed
        
        Index Block
        
        Each file has its own index block, which is an array of storage-block addresses
        
        The ith entry in the index block points to the ith block of the file
        
        The directory contains the address of the index block
        
        To find and read the ith block, we use the pointer in the ith index-block entry
        
        When the file is created, all pointers in the index block are set to null
        
        When the ith block is first written, a block is obtained from the free-space manager, and its address is put in the ith index-block entry
        
        The pointer overhead of the index block is generally greater than the pointer overhead of linked allocation
        
        Index block allocation
        
        Linked scheme
        
        Link together several index blocks
        
        Multilevel index
        
        Uses a first-level index block to point to a set of second-level index blocks, which in turn point to the file blocks
        
        To access a block, the operating system uses the first-level
        index to find a second-level index block and then uses that block
        to find the desired data block
        
        Combined scheme
        
        Direct Block
        
        Double Indirect Block
        
        Triple Indirect Block
        
        Single Indirect Block
    - - To keep track of free disk space, the system maintains a free-space list.
      - The free-space list records all free device blocks—those not allocated to some file or directory
      - Techniques
        
        Bit Vector
        
        Linked List
        
        Grouping
        
        Counting
- - - - This information comes mainly in the form of symbol definitions, which come in two varieties
      - The objects are program modules containing machine code and information for the linker
      - Defined or exported symbols are functions or variables that are present in the module represented by the object, and which should be available for use by other modules
      - Undefined or imported symbols are functions or variables that are called or referenced by this object, but not internally defined
    - - The term dynamically linked means that the program and the particular library it references are not combined together by the linker at linktime
      - The linker places information into the executable that tells the loader which shared object module the code is in and which runtime linker should be used to find and bind the references
      - This means that the binding between the program and the shared object is done at runtime — before the program starts, the appropriate shared objects are found and bound
      - This similar to shared libs specified in android make files
      - This type of program is called a partially bound executable, because it isn't fully resolved — the linker, at linktime, didn't cause all the referenced symbols in the program to be associated with specific code from the library
      - Instead, the linker simply said: “This program calls some functions within a particular shared object, so I'll just make a note of which shared object these functions are in, and continue on.”
      - Effectively, this defers the binding until runtime.
    - - Static linking is the process of copying all library modules used in the program into the final executable image
      - This is performed by the linker and it is done as the last step of the compilation process
      - The linker combines library routines with the program code in order to resolve external references, and to generate an executable image suitable for loading into memory
      - When the program is loaded, the operating system places into memory a single file that contains the executable code and data
      - This statically linked file includes both the calling program and the called program
  - - - With Dynamic Linking
        
        This is how dynamic libraries specified at compile time usually work
        
        The executable contains a reference to the dynamic/shared library, but the symbol table is missing or incomplete
        
        Both loading and linking occur at process start, which is considered "dynamic" for linking but not for loading
      - With Static Linking
        
        Everything is resolved at compile time
        
        At process start everything is loaded into memory immediately and no extra resolution (linking) is necessary
      - Static loading happens before a program starts
    - - Dynamic loading refers to mapping (or less often copying) an executable or library into a process's memory after is has started
- - - - Software interrupts may also be unexpectedly triggered by program execution errors
      - These interrupts typically are called traps or exceptions
      - For example, a divide-by-zero exception will be "thrown" (a software interrupt is requested) if the processor executes a divide instruction with divisor equal to zero
      - Typically, the operating system will catch and handle this exception
    - - A software interrupt may be intentionally caused by executing a special instruction which, by design, invokes an interrupt when executed
      - Such instructions function similarly to subroutine calls and are used for a variety of purposes, such as requesting operating system services and interacting with device drivers (e.g., to read or write storage media)