<jupyter_start><jupyter_text>Operating Systems Mid Term ReviewIn class whenever the teacher put's Why on the board it means that the content will be discucesed on the exam.hw2, 3 is on exam. What is an OS? [Lecture 1]      A program that manges the hardware for the application and system programs. Task between the application and       hardwware. operating system is found to be defining program.            Ease of use is the main goal of any operating system            * Two different view points          - Users (Ease of Use)          - Systems (Resource Utilization)                BUS -> Data Transfer Highway       Operation      When a program in firmware exectues, it intializes aspects of the system, and loads the OS into emmory, the       OS will execute the first process and waits for the event to happen (Essentially in a while loop)            Events will typically be signaled by an interrupt. [Hardware and software]            Why Interrupts?            * To keep the CPU as busy as possible      * Also to improve CPU Utilization due to I/O devices being much slower than the CPU            Polling -> Is the act of checking every second if a process has completed yet, this is where interrupts come       into play.      When interpreting the interrupt processing, PC, PSW, and Registered all need to be stored.      ISR = Interrupt Service Routine       API's [Lecutre 2]      Why API's?            Advantages include:         * Portable         * Simple | Safe         * Elegant         * Version Control            * API's provide a set of functions (Parameters + Return Values) that are available to the programmer.      * System Calls are involved within the API.            There are 7 types of syscalls, they go as follows:      1. Proces Management (execute, terminate, fork, kill)      2. File Manupulation (open, delete, read, close, create, write)      3. Device Manipulation (read, power, unmount, write, mount)      4. Information Maintaince (get, set, time | date)      5. Communication (send, recieve, read, write, socket)      6. Protecion (chmod, user group ids)      7. Memory Management (malloc, mmap and munmap)            Most of these interrupt services have some form of overlap within them.       OS Strucutre       Two different approaches, simple vs layered approach              1. Simple          Examples include MS DOS                    General design is a monolithic kernal, which acts a whole system, when one thing goes wrong the whole           strucutre falls apart. OS interfaces through hardware -> kernal -> syscalls       2. Layered Approach           Modular System Design           UI -> Outtermost layer           HW -> Inner Most                      Advantages include:              * Easier to debug              * Every layer contains abstraction              * Hidding infomration              * Ability to debug each layer independently                      Disadvantages:               * Dependencies are not clear cut              * Determining functionality to a particular layer              * Definining the amount of layers              * Less Efficent                       3. Micro Kernels           Small kernal that is well debugged, that includes interprocess communication                      Adv (Component Based):           * Debugging           * High fault tolearance           * Easy to Extend           * A failing service does not crash the main kernal                      Dis:           * Alot of message passing           * High overhead due to message passing.                    4. Modules             Dynamic  loadable moduels              Computer System Architecture [Lecutre 3]        1. Single Processor System:             A single CPU executes general purpose insturctions, other proccessor's help the CPU                2. Multiprocessor System            Throughput -> two or more CPU's sharing a memory bus                        Why Mutliprocessor Systems?            * Increased Throughput                Speedup would be less than n due to there being an overhead keeping the correct work.                            * More Reliable                System still functions if some processor fails                            * Less Cost                Shared resources such as PSU, Storage, etc.                        Main comparrison is Asymetric (Not peers) vs Symmetric (Peers)                3. Multi-core            Processors are on the same chip                        Why?            * Faster Communication, less power, less space             Clustered System        Individual System Conneced through fast LAN        * High performance computing clusters        * parfor -> Matlab function each loop is ran on a different CPU         OS Structure        1. Multiprograming -> Goal to keep multiple process in memory            * once a process is blocked , another process gets the CPU                2. Time Sharing -> Switching between processes is done very fast, response time (From pressing enter on the         keyboard to recieving the first character in the terminal)                * Turn around time is the whole result         OS Operations and Functionalities        OS interrupt errors should not affect the process or the OS / other processes.                * Process Management            Ability to Create, terminate, suspend, schedule        * Memory Management            Tract memory, list storage / memory locations, and allocating and deallocating memory.        * Storage Managment            File system, I/O devices (through drivers)        * Power Managment                 Goal: Find right syscall via API                       Process Management [Lecutre 4]       A Program in execution, that goes through mulitple states:       * New: Process being created       * Running: Using the CPU, executing instructions       * Blocked: Blocked waiting for idle (waiting for an interupt)       * Terminated: Process is exiting       * Ready: Waiting for the CPU               In terms of the actual diagram itself Running -> Blocked then blocked to Ready       Terminated -> exit();              PCB (Proces Control Block) -> How the system views processes              Long-term Scheduler vs Short-term Schedueler vs Medium-term       L: Selects process memory       S: Select a proces to execute on the CPU       M: Swap processes in/out of memory to/ from disk              - CPU-Bound: Process spend most of its time executing       - I/O Bound: Process spends most of its time doing I/O's              Need the right mix of info/data Context Switching       * Done by short-term scheduler       - Switching the CPU to another process(invokes saving that state and restoring)         Process Creation       * A process creates another process (Child)         -> Parrent continues to run         -> Parrent waits till the child function finishes                 * Termination exit();        Why A parrent terminates a child processs?        1. Exceeded its wage        2. No longer needed        3. Parrent exiting Utilization [Lecutre 5]        1. Utilization - Percentage of time a resource is in use        2. Throughput - To measure the output of the system rate (Process/min)        3. Turn around time - Time taken between submitting a process until its completion        4. Response time - Time taken between submitting a process and getting the first resposne.                Uniprograming (Serial)        -> Avg CPU Utilization (duration * CPU) + ... /(total time period)                Multiprogramming (Parallel)        -> Stacking processes together                Interprocess Communication        Need for all process to communicate, establish a shared region in memory.                Why?        1. Shared Data            - Modularize the application design, speedup in mind (Multi-processor system)                    2. Shared Memory            - Message Passing, other process will attach to the reigion allocated              * Need to remove OS restrictions for protetion              * Acess synchronization                Message Passing            Every message requires the kernal for send & recieve commands which are symmetric Indirect Communication        Message sent / recieved through ports                 Nonblocking -> Don't have to wait (Asynchronous)        Blocking -> Wait till you get Something (Synchoronous)       Queuing Analysis [Lecutre 6]        Shared Memory, Message Passing        * Direct Communication -> send & recieve        * Indirect Communication -> Mailbox                Message passing is easier to implement but shared memory is faster         Poisson Distribution        Gives the probability of a given number of events i.e arrivals over a fixed period of time if the average         rate lambda is known                 Probability Queues [Lecutre 7]        Arrival rate lambda < u                Assumptions            * Arrivals following poisson            * Service times follow Exp            * Requests are either waiting or getting serviced                * each queue can be analyzed separately                                 Queuing Theory [Lecutre 8]        Threads -> Support multiple concurrent paths of execution within a single process                Why?         1. Scalability: Increased speedup in multi-processor systems                2. Responsiveness: An application can continue to run/ execte even if part of the program is being blocked                3. Economy: Thread creation is faster and efficent than process creation                4. Resource Sharing: Threads share same resources Many-to-one Model         Kernal threads will typically have only one while user threads will have multiple        This will include        * Create threads        * Kill threads / Synchronize        * Schedule threads                Taking this approach if one thread blocks then the whole applicatoni crashes                * Drawbacks            1. Process blocks if 1 thread blocks            2. no speedup on multiprocessor systems                    P-threads( Many-to-one)          One-to-one Model         Run in paralel (User and kernal will have an equal amount of threads)            * Typically will run in parallel, using OpenMP (One-to-one)                OpenMP (One-to-one)         Many-to-many Model         Interlaced to work with the influx of data.         CPU Scheduling [Lecutre 9-10]        Assigning process to the CPU, via short term scheduling                1. Nature of process            * CPU burst / I/O processes                2. When are scheduling decisions made?            a. A new process arrives            b. A process blocked (Another process must be served)            c. A process terminates (Another process must be served)            d. A process goes from blocked to ready            e. A process goes from running to ready                  non-preemptive = a process runs until completion or it blocks           preemptive = running process is interrupted and placed in the ready queue           How to evaluate different schedulers           1. CPU Utilization           2. Turn-around time           3. Response time           4. Throughput           5. Waiting Time           6. Fairness / priority/ deadline            First Come First Serve (Non-preemptive)                Gives CPU to the first requesting process                adv: Simple        disadv: Average waiting time                 Shortest Job First (Non-preemptive)        Associate with every process the length of its next CPU burst                Essnetially assign the CPU to the process with the shortest CPU burst -> STF is optimal minimum average         waiting time                disadv: Shortest job first may lead to process starvation Shortest Remaining Time First (Preemptive)        Shorter jobs being given immedieate attention over all via context switching                adv: Lower turn-around time than STF        Highest Response Ratio Next (Non-preemptive)        Minimize the normalized turnaround time                R = (w + s) / s                with s being the expected serivce time        with r being the response ratio        with w being the time spent waiting                Which ever process has the highest R that is the process to be be picked Round Robin (Preemptive)        Using a clock to base everything off of, in this case by using a quantum or time slice thats how its able         to manage.                Interrupts are guarnteed every time slice         * 80% if the CPU burst to be shorter than q.         * maximum waiting time = (n-1)q                     with n being process            with q being quantum                    Short Quantum => Overhead Context Switching        Long Quantum => Approaches FCFS         Priority Scheduling  (Preemptive / non-preemptive)        Select process with highest priority            * This could be internal or external        Starvation can happen        Aging -> Effectively increases priorty over time as processes have to wait.         Multi-level Queue Scheduling         Classify processes into different groups        -> Each group is assigned a ready queuue   Real-time-Scheduling  [Lecutre 11]        Resutls must be produces by a specific deadline        * Soft real time            -> Meeting deadlines are desirable        * Hard real time            -> You can't miss a deadline            How to provide real time scheduling?        1. Preemptive Priority-based Scheduler        2. Preemptive Kernal (Allows for preemption of processes exectuing kernel)           * disadv: Comple to design        Rate Monotonic Scheduler        Static priority with preemption priority is inversley based on period        therefore shorter period will equal a higher priority         Earliest Deadline First [EDF]        The eariler the deadline the higher the priorty (Dynamically assigned) Proportional Share Schedulers [EDF]                 Main Memory Lecutre April 9th    Base limit registers        Base where it starts and the limit being how large or the length of the area        - If it access a bounds outside of the limit it will lead to a segfault    When you bind instructions at load time that is considered relocatable code    Execution time (Dynamic timing)  Logical vs Physical Addresses    Logical (Virtual)    Physical is only seen by a memory unit (system).  Memory-management Unit    User program only deals with logical memory accesses    Take logical address and map it to physical addresses     Dynamic Loading    Don't load until its actually called.    * better utilization    * May not be requested    * No support from OS required    OS system call instead     Swapping    When you run out of memory, and you need to transfer it to the disk is call swapping, backingstore acts as the     same         For swapping the medium term        System maintains a ready queue of ready-to-run processes which have memory images on disk     Contiguos Allocation    Designed for making use of the space, when a process completes;     looking at the limit of the finished process, one has to look at the     size of the gap in order to determine if a process fits within that     space.     Dynamic Storage-Allocation Problem    best-fit -> Allocating the smallest hole. Block that is the largest     to accomadate the process this leads to fragmentation. Must search     through all of the list to determine the best-fit        worst-fit -> allocate the largest hole. Must search     through all of the list to determine the best-fit        first-fit -> Allocate the first hole that is big enough, instead of     traversing the whole list.        * External fragmentation -> total memory space exist, but  its not     contigous    * Interal fragmentation is when its given something bigger than it     needs hence it will waste the space.    * Compaction is only doable if the values are dynamic, hence why     relocatable code is a more perfered method of coding.         Paging    Seperation of logical address and physical addresses    With RAM it doesn't need to be contigous            How it works is by divinding the memory, into fixed size blocks         called frames in which are powers of 2. Frames = physical address                Logical memory is considered to be pages, in this case Pages must         be the same size of Frames                Pages (Logical) & Frames (Physical)         Address Translation Scheme    page number and page offset will be the same size     Paging Model    With the paging setup, within the page table it shows the location of     the address ni memory where the frames are lcoated at in phyiscal     memory.        Pages and frames will have a fixed size, and with using the page     table you will get the exact info.        With using a dirty bit, this allows for the allocation not to over     prescribe and access a memory location out of bounds.        Pages as being a fixed size of units        Hence why with using Page-table base registers (PTBR) points the         page table        In Correlation to the page-table length register will indicate         the size of the page table.            ASID which address has this entry Memory Protection    Addition of a bit in each entry in the page table    Valid - invalid bit        Within page table you have frame number then the invalid bit     identifier     Hashed Page Tables    Virtual Page Number is hased intoa page table, then based upon that     you do a search along the chain to determine the frame number.      Main Memory Lecutre April 11th Segmentation    Memory management scheme that supports user view of memory        Architecutre        Segment table maps 2D physical addresses        * Limit = Length        * Base = Starting Address                 Is the offset exceed the limit of the segment is one of the          checks it if it exceeds then it becomes an addressing error, but          in the case it passes then it continues to hpyiscal memory.          Demand Paging    Two Potential Issues:    * Page could possibly not be in memory -> disk into memory    * Invalid reference, in which the code needs to abort         p = page fault rate     Copy-on-write        Zero-out pages         Override all the contents of the page with 0's and random values.        * To remove all of the information                          Final Exam Review Definitions    *Thrashing -> Thrashing is when a process spends most of its time bring pages in and out of disk and memory     without doing any useful.         * Race Conditions -> More than one, the outcome depends on the order of the execution.        * Worst-fit Memory Allocation -> Request for some memory, and a list of free slots you pick the biggest one         (Space will be big enough to accomdate more space)             * Decices swapping         * Short term (who gets the CPU)        * Medium Term ( Who gets to stay in memory or disk)         * Long term (If it is admited to the system or not)        * Internal Fragmentation -> You waste part of the page of the segment that you don't end up using.        Essentially the allocated memory space may be slightly larger, and the size difference is the memory         to the internal partition that isn't being used.                        Waste part of the page or the sgement that you do not need/use            * External Fragmentation -> you have more space that ends up being wasted        Effectively the mememory space is there but its not contigous or together        Request memory but get a larger piece of block (more space)            * Page-table base register -> points to the page table        * Page-table length register -> indicates the size of the page table        * Priority Inversion -> Having two conflicting priorties such as a lower / medium / high priortiy process     conflicting for resources.           When you have a high priortiy process waiting for a resource or a low priority process       Solution: Priority inheritence when the lower priority process inherits the higher priority state of the        process waiting for it until it exectues then its put back to lower priority process.            * Prioirty Inheritance -> to give higher priority processes the higher priority as they need it to finish their     resources.        * Belady's anomaly -> The number of page faults rate may increase as the number of alocated frames increases        More frames = more page faults. (Simply defined)        * Medium-term scheduling -> In which you remove a process from memory and reduce the degree of multuprograming,     in which the process can be added later onto memory and continue. (Swapping between disk)        * Long-term scheudling -> If a process is admited to the system or not        * Short-term scheduling -> Is in regards to which process gets the CPU.<jupyter_code># Santa Code
while(1):
    signal(santa)
    wait(santa)
    get_gift()
    signal(gift)
    
# Child Code
while(1):
    wait(santa)
    signal(request)
    wait(gift)
    play()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.033447034299791546, 'fraction_numerical': 0.003268902785673678, 'mean_word_length': 2.162870842073719, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 52, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '385889', 'license': 'MIT', 'n_tokens_mistral': 4610, 'n_tokens_neox': 4371, 'n_words': 2698, 'path': '.ipynb_checkpoints/operating-systems-exam-reviews-checkpoint.ipynb', 'repo_name': 'trujamal/operating-systems', 'size': '21108'}