EECS 3540_001 Operating Systems and Systems Programs PDF

za8/27/2024 Welcome to EECS 3540 ○ Instructor: Dr:Kishwar Ahmed ○ Office: NI 2055 ○ Phone: (419)530-8156 ○ Email: [email protected] (preferred mode of communication) ○ Office hours: Tues/Thurs 4:00pm - 5:00pm, Wed:1:00pm-4:00pm...

za8/27/2024 Welcome to EECS 3540 ○ Instructor: Dr:Kishwar Ahmed ○ Office: NI 2055 ○ Phone: (419)530-8156 ○ Email: [email protected] (preferred mode of communication) ○ Office hours: Tues/Thurs 4:00pm - 5:00pm, Wed:1:00pm-4:00pm ○ We meet at: Tues/Thurs 2:30pm-3:50pm ○ We meet in: North Engineering 2123 ○ NO LAB PORTION ○ Make sure to check blackboard announcements and Email Java or C for assignments ○ Need eclipse ○ Obtain VMware workstation player ○ And install VMWare Horizon client https://vlab.utoledo.edu/ 8/29/2024 Chapter 1 : Introduction ○ Chapter objectives Describe the general organization of computer system and the role of interrupts Describe the components in a modern multiprocessor computer system How to transition from user from to kernel mode How operating systems are used in various computing environments Operating systems Intermediary between user and hardware itself ○ What is an operating system An operating system is the software that manages a computer’s hardware Convenience of the user Make use hardware efficiently ○ A computer systems can be divided into four components Hardware - provides basic computing resources Cpu, memory, !/0 devices Operating system Controls and coordinates use of hardware among various applications and users Application programs - define the ways in which the system resources are used to solve the computing problems of the users The user ○ 1.1 What operating systems do C++ code exa Ifstream inputFIle; String text; inputFile.open(“C:\users\ka\Documents\text.txt”);  text > Appends output to a file  ○ | Pipe the output from one command to another command Gcc hello_world2 -o hello_world2 Editors in Linux ○ Vi: One of the first editors available in Unix The new version ○ 2g, goes ot the second line Basics of vim ○ Command mode ○ Insert mode I- 9/17/2024 Chapter 3 ○ 3.1 An operating system executes a variety of programs: Early batch systems execute on job after another Later time shared systems vave us the notion of user programs or tasks Textbook uses the terms job and process almost interchangeably Process - a program in execution 3.1.1 The memory layout of a process is shown in the figure ○ The program code also called text section ○ Data section containing global variables ○ Heap containing memory dynamically allocated during run time ○ Stack contating temporary data Function parameters, return address 3.1.2 As a process executes, it changes state, which could be ○ new : The process is being created ○ Running: Instructions are being executed ○ Waiting: The process is waiting for some event to occur ○ Ready: the process is waiting to be assigned to a processor ○ Terminated: the process has finished execution 3.1.3 Each process is represented in the operating system by a process control block (PCB), that includes information about the process including: ○ Process state -running, waiting, etc ○ Program counter - location of instruction to next execute  ○ CPU registers - contents of all process centric registers ○ CPU scheduling information - priorities , scheduling queue pointers ○ Memory-managment information - memor 3.1.4 So far, process has a single thread of execution Most modern operating systems support multiple threads per process PCB is expanded to include information for each thread ○ One program, running multiple things are once ○ 3.2 Process scheduling Maximimuse CPU use, quickly switch processes onto CPU for time sharing Process scheduler selected among available processes for the next execution on CPU If there are more processes than cores, excess processes will have to wait until a core is free and can be rescheduled ○ 3.2.2 CPU scheduling The cpu schedulures role is to s ○ 3.3 pstree 9/24/2024 Chapter 4 Chapter objective ○ Identify the basic components of a thread and contrast threads and processes ○ Describe the major benefits and challenges of designing multithreaded processes ○ Illustrate different approachers to implicit threading, including thread tools 4.1 ○ Overview A thread is a basic unit of CPU utilization A thread comprises a thread ID, a program counter (PC), a register set, and a stack It shares with other threads belonging to the same process its code section, data section, and other operating system resources Can split task among different threads ○ 4.1.1 Most modern applications are multithreaded An application is typically one process, with multiple threads Examples  An application that creates photo thumbnails from a collection of images may use a separate thread to generate a thumbnail from each separate image A web browser might hav eone thread display images or text while another thread retrieves data from the network A word processor mau have a thread fo displaying graphics Motivation Process creation is heavy weight while thread creation is light weight Kernels are generally multithreaded Can simplify code, increase efficiency Multithreaded server architecture K Benefits of multithreading Four major categories ○ Responsiveness ○ Resources sharing ○ Economy ○ scalability 4.2 ○ Multicore programming Note the distinction between “concurrent” and “parallel” Concurrency means all thread make progress on a single-core system as each thread gets to run for a short period of time on the single processing core Parallelism allows two thread to run at the same time as each thread runs on a separate processing core ○ Programming challenges There is pressure on system designs and application programmers to make better use of the multiple computing cores Designers of operating systems must write scheduling algorithms that use Five areas presenting challenges  Identifying tasks: This involves examining applications to find areas that can be divided into separate, concurrent tasks Balance: Programmers must also ensure that the tasks perform equal work of equal value Data splitting: The data accessed and manipulated by the tasks must be divided to run on separate cores Data dependency: When one task depends on data from another, programmers must ensure that the execution of the tasks is synchronized to accommodate the data dependency ○ Amdah’ls law Amdahl’s law is a formula that identifies potential performance gains from adding additional computing cores to an application that has both serial (Non parallel) and parallel and parallel components Example ○ Assume we have an application that is 75% parallel and 25 percent serial ○ 4.2.2 Types of parallelism There are 4.3 ○ Multithreading models Our discussion so far has treated threads in a generic sense Support for threads may be provides either at th euser level or the kernel level Kernel threads are supported and managed directly by the operating system A relationship must exists between user threads and kernel threads We look at three common ways of establishing such a relationship the many to one model, the one to one model, and the many to many model ○ 4.3.1 The many to one model THe many to one model maps many user levels thread to one kernel thread Only on thread can access the kernel at a time One th ○ 4.3.2 TH eone ot one model maps each usere level thread to a kernel thread Provides Many to many model 4.4 ○ Thread libraries Thread library provides programmer with API for creating and managing threads Two primary  Three main thread libraries ○ Header file ○ Include ○ Three main thread libraries are in use today POSIX Pthreads Windows threads Java theads 4.5 4.6 ○ The fork () and exec() system calls The fork() system is used to create a separate, duplicate process What happens if the parent has multiple threads? Does the new process duplicate all threads? Or is the new process single threaded It depends Soem UNIX systems have chosen to have two versions of fork(), one that duplicates all threads and other that duplicates only the thread that invoked the fork() system call ○ Signal Handling Signals are used in UNIX systems to notify a process that a particular event has occurred A signal may be received either synchronously or asynchronously, but they follow the same pattern The signal is generated The signal is delivered to a process Once received, the signal has to be handled Sync When a signal is generated by an event external to a running process, that process receives the signal asynchronously The standard UNIX function for delivering a signal is ○ Thread cancellation What if we want to terminate a thread before it’s finished Thread to be caneled is “tart 4.7 4.8 10/1/2024 Chapter 5 Basic ideas ○ When scheduling Want to have max throughput Want to minimize times Scheduling algorithms help with that Exterminatus ○ Objectives  Desrcibe various CPU scheduling algorithms Assess CPU scheduling algorithms based on scheduling criteria Explain the issues related to multiprocessor and multicore scheduling Describe various real time scheduling algorithms 5.0 ○ We have multiple processes in the memory trying to get CPU time ○ By switching the CPU among processes, the operating system can make the computer more productive Helps make the programs run concurrently 5.1 ○ The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization ○ A proc 5.1.1 ○ CPU-I/O Burst Cycle A program’s execution consists of a cycle of CPU execution and I/O wait Burst of activity / time spending on CPU / I/O jobs THe durations of CPU burst vary greatly form process to process THe curve is generally characterized as exponential, with a large number of short CPU bursts and a small number of long CPU bursts 5.1.2 ○ CPU scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process ○ CPU scheduling decisions may take place when a process:: Switches from running to waiting state Switches from running to ready state Switches form waiting to ready Terminates ○ Scheduling under 1 and 4 is non preemptive ○ All other scheduling preemptive Non preemptive Program has to stop Preemptive = interrutpable Can become inconsistent if Go back over that on zybooks 5.1.3 ○ Preemptive scheduling can result in race conditions when data are shared among several processes ○ Consider the case of two process that share data ○ While one process is update the data, it is prempted so that the second process can run ○ The second process then tries to read the data, which are in an inconsistent 5.1.4  ○ Dispatcher gives control of CPU to the process selected by the CPU scheduler ○ The dispatcher: Switches context from one process to another ○ Switches to the user mode ○ Jumps to the proper location in the user program to restart that program ○ Dispatch latency 5.2 ○ Scheduling criteria Many criteria have been suggest for comparing CPU scheduling algorithms CPU utilization:keep the CPU busy as possible Throughput: # of process that complete their execution per time unit Turn around time: amount of time to execute a particular process Waiting time: amount of time a process has been waiting in the ready queue Response time: amount of time it takes form when a request was submitted until the first response is produced, not output (for time sharing environment) 5.3 ○ Scheduling algorithms There are many different CPU -scheduling algorithms We describe these scheduling algorithm is the first-come, first served (FCFS) scheduling algorithm The implementation of FCFS policy is easily mnaged with a FIFO queue When a process becomes ready, it enters the tail of the ready queue When the CPU is free, it is allocated to the process at the head of the queue 5.3.2 ○ Shortest job first There is no way to know the length of the next CPU burst We can only estimate the length but should be similar to the previous one Then pick process with shortest predicted next CPU burst Use the length of previous CPU bursts, using exponential averaging 1. Tn = actual length of n^th CPU burst Τn+1 = predicted value for the next CPU burst Ɑ, 0 FIFO Q small -> Q must be large with respect to context switch, otherwise overhead is too high 5.3.3 RR, with q = 4 Process Burst time P1 24 P2 3 P3 3 Turnaround time varies with q The time quantum should not be too compared to the context switch time ○ 5.3.4 Priority scheduling A priority number (integer) is associated with each process The CPU is allocated ot the process with the highest priority (smallest integer = highest priority) Problem: Starvation - low priority processes may never execute  ○ Process Burst Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 ○ Practive gantt charts P2 P5 P1 P3 P4 0-1 1—-------6 6—------------------------------16 16—-------18 18-19 ○ Multilevel queue Scheduling With priority and RR scheduling, all processes may be placed in a single queue In practice, it is often easier to have separate queues for each priority level 5.3.6 ○ Multilevel feedback queue scheduling A process can move between the various queues; this is one way to implement aging Example: three queues The scheduler first executes all process in the queue 0 Only when queue 0 is empty will it execute processes in queue 1 If something in Q! Is running and a process arrives for Q0 new one will preempt the one thats already running After 5.4 is not on Exam 10/3/2024 Exam up until chapter 5 ○ Mostly 1 through 4 though I guess he’s still going through chapter 5 ○ CPU scheduling 10/8/2024 Oh this nigga is not doing review ○ He’s just going through new content 5.5.2 multicore preocesors ○ Intel processes use the term hyper threading to describe  ○ There are two general ways to handle the multithreading Coarse grained: A thread executes on a core until a long latency even such as a memory stall occurs Fine grained: 5.5.3 load balancing ○ On a SMP system, the workload needs to be balanced between processors ○ On a SMP system, the workload needs to be balance between processors [u] ○ Otherwise one (or more processor maybe idle, while one is busy and has a wait queue of threads wanting processing time ○ Load balancing attanpts to keep the workload evenly distributed 5.5.4 Processor affinity ○ Processor affinity - that is, a process has an affinity for the processor on which it is currently running ○ When a 5.5.5 Heterogeneous Multiprocessing ○ Some systems are now designed using cores that run the same instruction set, yet vary in terms of their clock spseed and power management - Heterogeneous Multiprocessing (HMP) ○ For ARM processors that support it, this type of architecture is known as big.LITTLE Big cores consume greater ener 5.6 Real - Time CPU scheduling ○ For some applications, timing is critical ○ SOft real-time systems - no guarantee as to when critical real-time process wull be scheduled ○ Hard real time systems - Task must be serviced by its deadline ○ Interrupt latency Time form arrival of interrupt to state of routing ○ Dispatch latency - The latency to switch ○ K 5.6.2 Priority based scheduling ○ For real time scheduling, scheduler must support preemptive, priority based scheduling But only guarantees soft real time ○ For heard real time must also provide ability to meet deadlines ○ Processes have new characteristics: periodic ones require CPU at constant intervals ○ ○ K EXAM Operating system services Go back over fork 10/17/2024 CHapter 6: sync tools Operating systems and system programming 6.0 intro A Cooperating process is one that affects or can be affected by other processes being executed in the system ○ (look up messaging) They can either directly share a logical address space (code and data) Can only share data through shared memory or message parsing 6.1 background Back in processes, we described how a bounded buffer could be used to enable processes to share memory We now return to our consideration of the bounded buffer ○ The producer produces an item, and if the buffer isn’t full, adds it ○ THe consumer removes items from the buffer if the buffer is not empty ○ The size of the buffer is BUFFER_SIZE ○ We will use an integer variable, count, to tell how many items are in the buffer ○ The producer uses variable in to keep track of where to get the next item The producer: While (true) { while (count == BUFFER_SIZE); buffer [ in ] = next_ produced; In = (in [NF] ○ If the buffer is full it will run forever The consumer While (true) { while (count == 0 ); next_consumed = buffer [ out ] ; out = (out + 1) % BUFFER_SIZE; count–; } The producers and consumer routines shown above are correct sep Talking notes ○ Slide 10 Producers produces an item and we get count++ Vice versa for consumer ○ Slide 11 Count++ could be implemented as Mov register1, count Inc register 1  Mov count, register 1 Count-- could be implemented as Mov register1, count dec register 1 Mov count, register 1 6.2 The critical section problem Slide 14 ○ Mutual exclusion: If a process Pi is executing in Its critical section, then no other processes can be executing in their critical sections ○ Progress: If 10/22/2024 6.6 semaphores In an os a semaphore is implemented as an integer S Can only be access via two atomic operations: wait() / signal() ○ Originally called P() and V() ○ defin 6.6.1 semaphore usage Suppose we have two processes, P1, and P2 P1 wants to execute statement S1, P2 wants to execute S2, and require S1 to happen before S2 ○ P1: S1; signal(sync); P2 wait(sync); S2; 6.6.2 semaphore implementation With each semaphore there is an associated waiting queue Each entry in a waiting queue has two data items: ○ Value (of type integer) ○ NF Implementation Wait(semaphore *S) { S->value–; if(S->value < 0 ) { Add this process to S->list; sleep(); // process waits in queue } } 10/24/2024 New data type in Monitor ○ Condition  6.7 monitors ○ We say semaphore is a simple way to do synchronicity between processes Two conditions Something and weight ○ Rather than (the correct) NF ○ If we use a binary semaphore to implement a mutex, each process must wait (mutex) before entering its critical section, and then signal(mutex) afterwards ○ If someone doesn’t play by the rules (intentionally or accidentally), two processes can be in their critical sections at the same time! ○ If a process uses wait (mutex) ….. wait (mutex) , it will lock up (as it executes the program without signaling another program) ○ If wait (mutex) or signal(mutex) (or both) is omitted, then either mutual exclusion is violated, or the process gets stuck permanently ○ An even higher-level construct can solve this problem - a monitor 6.7.1 Monitor Usage ○ A monitor is an ADT that includes a set of programmer - defined operations provided with mutual excluding within the monitor ○ Only one process may be active within the monitor at a time THe programmer doesn't need to worry about coding synchronization ○ But not powerful enough to model some synchronization schemes 6.7.1 Monitor Usage ( continued) ○ If we need a tailor made synch scheme, we can define one or more variables of type condition condition: Condition x, y; ○ Two operations are allowed on a k ○ EACH CONDITION IS LIKE A ARRAY OF PROCESSES Declaring wait and signal (x.signal()) determines the fates of the processes in the Monitor (main area thing) ○ Signal and wait vs signal and continue 6.8 Liveness ○ Liveness : Refers to a set of properties that a system must satisfy to ensure that process make progress during their execution lifecyle ○ Suppose we have three process(L,M, and H) with three levels of priority, Low, Medium, and Hugh (respectively) ○ H needs semaphore S, which is currently held by L 6.8.2 Priority inversion ○ K ○ K Chapter 8 introduction ○ In a multiprogramming environment=, several threads often compete for some finite set of resources  ○ If two threads each need to acquire (the same) two resources (so they can use and then release both), and each has acquire one of the two, they will become deadlocked Until one of the threads can get both of the resources, they can’t finish their critical section and release the one (resource) they already have plus the one they’re waiting for ○ K ○ K 10/29/2024 8.3.2 Resource allocation graphs There are no cycles in the graph, then there is no deadlock If a graph does contain a deadlock ○ If only one instance per resource type, then deadlock ○ If several instances per resource type, possibility of deadlock 8.4 Methods for handling deadlocks There are three basic ways to handle the deadlock situation Ignore the problem and pretend they never occur Ensure that the system will never enter a deadlock state: ○ Deadlock prevention ○ Deadlock avoidance Allow the system to enter a deadlock state and then recover 8.5 Deadlock prevention Restrain the ways request can be made ○ Mutual exclusion ○ Hold and wait ○ No preemption ○ Circular wait 8.6 Deadlock avoidance Requires that the system has some additional Simplest and most useful mode requires that each process declare 8.6.1 Safe state When a process requests and available resource, system must decide if immediate allocation leaves the system in a safe state System is in safe state if there exists a sequence of all the threads in the systems such that for each Ti, the resources that Ti can still request can be satisfied by currently available resources + resources held by all the TJ, with J < I Avoidance algorithm SIngle instance of a resource type ○ Multiple instances of resource type ○ Use the banker’s algorithm Resource allocation graph scheme Claim edge Ti → RJ indicates that the process TI may request resource Rj; represented by a dashed line  Claim edge converts to request edge when a thread requests a resource 8.6.3 Bankers algorithm REsource allocation graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type When a resource has multiple instances, we need something more sophisticated, and that is exactly what the B.A is When a new thread enters the system it must announce how many new threads it needs When a thread requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state Let n = number of processes, and m = number of resource types ○ Available: A vector of length m. if Available[j] ==k, then there are k instances of resource type Rj available ○ Max: an n x m matrix. If Max[i,j] == k, then process Pi may request at most K instances of resource type Rj ○ Allocation: An n x m matrix. If Allocation [i, j] == k, then Pi is currently allocated k instances of resource type Rj ○ Need [i, j] = Max[i,j] - allocation[i,j] 1. Let Work and Finish be vectores of length m and n, respectively. a. Initialize: b. Work = available c. Finish[i] = false for i = 0, 1 ,....., n -1 2. Find an index i such that both: ○ Finish[i] == false - and- Needi the base + limit, the CPU recognizes this and results in a trap in the OS Only the OS is allowed to access the base / limit registers with privileged instructions K 9.1.2 Address 9.1.3 logical vs. physical address space The concept of a logical address space that is bound to separate physical address space is central to proper memory management ○ Logical address ○ Physical address Logical and physical addresses are the same in compile time One simple scheme is to let the value in the base register be added to every address at execution time If the base register contains 300040, referencing 14 -> 300054 ○ Base register now called relocation register ○ MS-DOS on INtel 80 9.1.4 Dynamic loading With Dynamic loading, routines aren’t loaded until they’re called All routines are kept on disk in a relocatable format until needed When one needs to call another, it first checks to see if it’s loaded If so, the call process, if not, it gets loaded first and addresses get translated This helps with memory Memory allocation with first-fit algo Whenever you have a process that fits into a target location then put it there 9.2.2 Memory allocation First fit ○ Allocate to the first hole we Best fit Worst fit 11/7/2024 9.13 Logical vs Physical address space ○ Hardware device that at run time maps virtual to physical address is the MMU (memory management Unit) ○ Many methods possible, covered in the rest of this chapter 9.2.1 Memory protection ○ With a lmit register and a relocation register, we can keep a process from accessing memory it does not own ○ The relocation register contains value of the smallest physical address ○ The limit register contains range of logical addresses - each logical address must be less than the limit register 9.2.2 Memory allocation ○ In a variable- partition scheme, the system keeps a table that tells which parts of memory are occupied, and which are available ○ Initially (when the system boots), user space is all available ○ As processes come and go space will be allocated (and freed) in blocks ○ ○ When a process arrives iit is allocated memory from a hole large enough to accommodate it  ○ When a process ends, it frees its memory ○ How to satisfy a request of size 9.2.3 memory fragmentation ○ Both first ft and best fit tend to result in small blocks of memory called memory fragmentation ○ External fragmentiaiton - ○ What can be done about fragmentation Compact memory (if we can) Compaction Move all of the allocated blocks together (holes go the other direction) Change relocation for each process to their new “home” values ○ THe other option is paging - dividing memory up into fixed size frames, and allocating a list of (potentially non-contiguous) frames to a process 9.3 paging ○ Paging avoids the problem of external fragmentation, and the need for compacting ○ But it introduc 9.3.1 basic method ○ Divide physical memory into fixed size blocks called frames ○ Divide logical memory into same sized blocks called pages ○ SIze is power of 2 ○ ○ Page number is used as an index into a page table (each process has one) ○ A physical ○ The offset within the frame (d) is added to f to get the actual physical address - the frame number ○ Basically works like this  ○ Logical address equations ○ Logical address 0 (0000): a-> physical address address(5x4 + 0=20) ○ Logical address 13 (1101): n -> Physical address(2x4 + 1 = 9) ○ I have no clue how this works ○ J 11/12/2024 9.3.2 HARDWARE SUPPORT ○ Page table is kept in main memory ○ Page table base register (PTBR) points to the page table ○ In this scheme every data / instruction access requires two memory accesses One for the page table and one for the data / instruction ○ The two memory access problem can be solved by the use of a special fast lookup hardware cache called associative memory or translation look aside buffer  9.3.2.1 translation look aside buffer ○ BEcause the TLB is of limited size, the address wee’re looking for may or may not be in the table If it is, there’s essentially no slowdown If it’s not, we have a TLB miss, and have to look up the page table like before (with the corresponding performance hit) and add it to the TLB ○ If the TLB is full, then we have to device which entry to replace We can use any of the following LRU (least recently used) Round Robin Random ○ The likelihood that we have a TLB hit is the “hit ratio” PROBABLY WILL BE ON EXAM ⍶ = 80%, 10ns for memory access Effective access time (EAT) = 0.80 x10 + 0.20 x 20 = 12ns Consider more realistic hit ratio -> ⍶ = 99% EAT = 0.99 x 10 + 0.01 x 20 = 10.1ns ○ ⍶ 9.3.3 Protection ○ Techniques to protect paging ○ We can add a bit to the page table entries to make them read-only or write only Basically to protect information in the structure ○ Valid - Invalid bit attached to each entry in the page table Valid indicates that the associated page is in the process’ logical address space, and is thus a legal page Invalid means not that 9.3.4 Shared pages ○ Paging also affords us the opportunity for sharing common code ○ One (the heavily C-based) Linux, most programs will need access to the C Standard Library (libc) ○ If each process has its own copy of this code, it can require a lot of memory 9.4.1 Hierarchical Paging ○ Consider a 32-bit logical address space as on modern computers ○ Page size of 4KB (2^12) ○ Page table would have 1 million entries (2^32 / 2^12) ○ One way to handle this is via a two level paging system, where the page table is itself paged  ○ 9.4.2 Hashed Page Tables ○ To go beyond 32 bits, we can used a hashed page table (with chaining to handle collisions - the chains should be short anyway  ○ ○ K 9.4.3 Inverted Page tables ○ As the memory space gets huge for 64-bits , the page tables also get impractically large ○ An inverted page table has one henry for every frame of physical memory, and each energy as associated with it the ID of the process that is used it ○ This scheme uses less memory overall, but takes longer to do lookups, and we can’t do shared pages ○ The “longer lookups” 9.5 Swapping ○ Instructions and the data they operate on must be somewhere in physical memory to in order to execute Essentially sending processes to someplace more larger / slower  ○ This requires saving the entire process’s space, it’s associated data structures also need to be saved ○ IF a system supports multithreading, then all per thread data needs, to also be saved and restored ○ Idle or mostly idle processes are good candidates for this kind of swapping ○ THis lets us oversubcribe 9.5.2 Swapping with paging ○ In a modern system, a processes is likely too large for efficient all or nothing swapping ○ Most systems (including Linux and windows) implement swapping at the page level ○ This also lets us oversubcrive memory  ○ 11/14/2024 Chapter 10 Introduction ○ Virtual memory can be larger than the actual memory in the system ○ You need to have the whole process in the memory to run it 10.1 Background ○ Chapter 9 introduced memory management strategies ○ All of those strategies aimed to keep may processes in memory at once to allow multiprogramming ○ But they also required that all of the process be in memory at once ○ Virtual memory allows processes to execute even if they are not completely in memory ○ One Advantage: programs may be larger than physical memory ○ Virtual memory involves separating logical memory as perceived by developers form physical memory  This allows a larger logical space than there is physical memory ○ Programmers can now concentrate on the problem at hand; not how to manage memory requirements ○ Virtual address space Refers to the logical or virtual view of how a process is stored in memory Typically, program thinks the start at address 0, contiguous address until end of space We know that’s already not the case – the MMY handles the non-contiguous-ness Also the “hole between is the virtual address space and only requires physical pages if the heap or stack grows  The arrows on stack and heap indicate that they can grow in either direction K K 10.2 Demand Paging ○ Rather than loading all of a program into memory when it starts, suppose we only load the first page ○ Then we will load more pages as - needed ○ This is Demand paging ○ With Demand Paged virtual memory, pages are loaded only when they are demanded during execution ○ The general idea is to load pages only when needed ○ Therefore, an executing program may have some pages on disk ○ We need some from of hardware support to determine if an address is in-memory or swapped out ○ By adding the valid / invalid bit to every entry in the page table, we can tell whether a page is valid (both legal and in-memory) or invalid (either not legal or legal but not in-memory) 10.2.1 Basic Concepts ○ If a process attempts to access a page marked as invalid, it causes a page fault ○ The paging hardware sees the invalid bit, causing a trap in the O/S, because the needed page is not in memory ○ Then, the following sequence of events happens: 1. An internal table gets checked to see if the reference was valid 2. IF it wasn’t valid, the process is terminated a. If it was valid bit not in memory, we need to bring it in 3. Determine a freem frame  4. Read the desired page from storage into th free frame 5. Modify the internal table 6. ○ K 10.2.3 the performance of demand paging ○ We already covered the benefits to adding demand paging ○ It comes with a performance hit. How much of one? ○ It depends on: How like page faults are What memory access time would have been had the page been loaded How lo ○ 10.3 Copy-on-Write ○ Only copies the pages that is going to be written 10.4 Page Replacement ○ Which frames you wish to replace ○ Virtual memory lets us over-allocate memory (Total VM > physical) ○ When that happens, and we need to swap something in, what if there isn’t a free frame to put it into ○ We have to pick an unused (in-memory) frame, and write it to disk, so that we may free it up ○ This is page replacement ○ How do we pick the one to swap ○ Basic page replacement Find the location of the desired page on secondary storage Find a free frame: If there is a free frame, use it IF there is not free frame, use a page replacement algorithm to select a victim frame Write the victim frame to secondary storage (if necessary); change the page and frame tables accordingly Read the desired page into the newly freed fram; change the page and frame tables Continue the process from where the page fault occurred ○ A Page replacement algorithm: When it comes time to swap something out, how do we pick victims with low page-fault rate? ○ If we could get the memory system to log every reference it sees, we could analyze that to compare algorithms ○ We don’t need every individual address, just the page numbers ○ This is a Reference String ○ Slide 24 We’re going to use a reference string to evaluate several algorithms Suppose our reference string was 1,4,1,6,1,6,1,6,1,6,1 (those are page numbers for sequential accesses)  If there were three (or more) frames available, we could run the process with three faults IF there is only one frame available, then we have 11 faults - every access causes one ○ Slide 25 Having more physical memory gives us more frames to work with Allocating more frames to each process causes fewer page faults We’re going to examine several algorithms’ behavior with 3 frames and the reference string: 10.4.2 FIFO Page replacement ○ Reference string ○ 10.4.3 Optimal Page replacement ○ Suppose we could predict the future and pick the page that would not be used for the longest period of time as the victim ○ THere is no such algorithm, but the idea has been called OPT or MIN ○ This is similar to SJF scheduling - we won’t know what will be shortest  ○ 10.4.4 Least recently Used ○ Could use a timer for this in implem ○ ○ LRU needs special hardware and still slow  ○ Suppose the system provides a “reference bit” to simply flag that (not when) a page has been referenced With each page associate a bit, initially = 0 When page is referenced bit set to 1 10.4.5 Additional-Reference-Bits Algorithm ○ If we use a single byte associated with each page as an 8-bit shift register and periodically shift that byte to the right one bit, and those bytes are interpreted as unsigned integers, they give approximate page ages ○ Examples THe shift register contains 00000000 The shift register contains 111111111 10.4.6 cOUNTING BASED PAGE REPLACEMENT ○ Keeping a counter of the number of references that have been made to each page ○ Least frequently used (LFU) algorithm Allocation of frames Thrashing Memory Compression Allocating Kernel Memory Other Considerations 11/19/2024 Exam ○ Most questions will be from after the midterm 10.2.1 - Basic COncepts ○ If a process attempts to access a page marked as invalid, it causes a Page fault ○ 11/21/2024 10.5 Allocation of frames ○ Pages = physical memory ○ Frames = virtual memory ○ Each process needs a minimum number of frames Example: IBM 370 - 6 pages to handle SS move instruction ○ The maximum is the total number of frames in the system ○ Allocation algorithms Equal allocation - every process gets the same frames Proportional allocation - every process gets frames according to it’s size 10.5.3 Global vs local allocation ○ With multiple processes competing for frames, we can divide the page-replacement algorithms into two broad categories: ○ Global replacement - process selects a replacement frame from the set of all frames; one process can take a frame from another  Execution time can vary greatly But this produces greater throughput, so more common Accesses the memory more ○ Local replacement - each elsects from only it’s own set of allocated frames More consistent per process performance 10.6 Thrashing ○ If a process does not have enough pages, then the page-fault rate is very high A page fault gets a new page to replace the existing frame But then it quickly needs replaced page back, so it swaps again This leads to low CPU utilzation IF the system is monitoring CPU usage, it may increase multiprogramming to r ○ A process is just a lot of function calls ○ Locality Model A processes tend to stay in one “area” (locality) for “a while”, before moving to another area A running program Typically has several localities When a function is called, it entered  The figure shows locality in memory reference pattern At time (a), the program’s locality is pages 18-24,29 10.6.2 The working set model ○ We look at the last Δ (number of pages in each locality, the working-set window) number of page references ○ It is a sliding (over time) window that approximates the current locality IF 10.6.3 Page fault frequency ○ The working set model works, but it’s a clumsy way to control threshing, A simpler way is to monitor Page-fault frequency  ○ When a process’s page-fault rate goes up, it’s either entering a new locality, or it’s thrashing ○ We can set upper/lower limites for allowed page fault rates ○ When a process crosses the upper limit, it needs more frames ○ When it fall PUT ALL PARTICIPATION ACTIVIITES ON CHEAT SHEET, ALONG WITH ALL SLIDES 10.8 Allocating kernel memory ○ Treated differently from user memory ○ The kernel often uses a different memory pool, because The kernel may request various sizes at a time for various data structures Some I/O devices will require contiguous blocks of memory for their transfers, so paging won’t work for them ○ So how does the kernel manage free memory for it’s processors 10.8.1 The buddy system ○ The kernel starts with a power-of-two sized chunk and then repeatedly divides its size in half until it’s down to what the request fits in ○ For example, assume 256 KB chunk available, kernel requests 21KB 10.9.1 Other considerations – Prepaging ○ Pure demand paging results ○ 11/26/2024 EXAM ○ Handwritten final exam?? Chapter 11 Mass storage structure ○ Chapter objectives Desrcibe the physical structures of various secondary storage devices And the ○ 11.1 overview of mass storage structure  Each track contains a number of sectors Drives rotate at 60 to 250 times per second The transfer rate is the rate at which data flows between drive and computer Positioning time (random access time) cosnsists of two parts Time to move disk arm to desired cylinder (seek time) and Time for desired sector to rotate under the disk head (rotational latency) ○ 11.2 HDD scheduling The operating system is responsible for using hardware efficiently - for the disk drives, this means minimuze seek time and mazimize data transfer bandwidth We can improve both the access time and the bandwidth by managing the order in which storage I/o requests are serviced Several algorithms exists to schedule the servicing of storage I/O requests We illustrate scheduling algorithms with a request queue 98,183,37,122,14,124,65,67 FCFS scheduling ○ Request queue: 98,183,37,122,14,124,65,67 ○ Head pointer (what it’s currently at): 53  Scan scheduling ○ Request queue: 98,183,37,122,14,124,65,67 ○ Head pointer (what it’s currently at): 53 Disk arm moving towards 0 C-SCAN scheduling ○ Request queue: 98,183,37,122,14,124,65,67 ○ Head pointer (what it’s currently at): 53 Disk arm moving from 0 to 199 ○ ○ 11.3 NVM scheduling ○ 11.4 Error detection and correction Error detection Determines if a problem has occurred Each byte in a memory system has a parity bit associated with that records whether the number of bits in the byte set to 1 is even (parity = 0) or odd (parity = 1) ○ 11.5 storage device management ○ 11.6 Swap space management ○ 11.7 storage attachment ○ 11.8 RAID structure RAID (redundant array of independent disks) commonly used to address the reliability and performance issues Improvement in reliability via redundancy Store extra information that is not normally needed by can be used in the even of disk failure Improvement in performance via parallelism Strip data across multiple drives ○ 8 bit level striping ○ Block level striping Raid configurations  Raid level 6 ○ You keep a copy of parity bit Bleh PLEASE REVIEW THIS SECTION ○ 11.9 Summary Chapter 13 13.1 the concept of a file ○ The file system contains two basic parts: A collection of files A directory structure that organizes  ○ The OS abstracts the physical sectores, tracks, and heads in disk drives and provides the logical view of a file The operating system hides it in a way ○ The OS takes care of the physical - to - logical mapping ○ A file is a named collection of related information recorded on secondary (typically non-volatile) storage A simple file can be just a bit of bites Needs to be stored in secondary storage ○ AS far as the user can t ○ The creator of a file gives it a name Must give it a name With a extension (it’s purpose) ○ SOme OSs treat names as case-sensitive (Linux is; Windows isn’t) ○ Files have their own contents (Data), but they also have metadata (data about data) associated with them Data of the file itself ○ The exact metadata available for a file can vary from OS to OS and from file system 12/3/2024 13.1.1 File attributes ○ Name - only information kept in human - readable form ○ Identifier - a unique, non-human-readable tag to identify the file ○ Type - need for systems that support different types of files ○ Location - where is the file located on the disk ○ Size - number of bytes in the file ○ Protection - controls who can do reading, writing, executing ○ Timestamp - When it was created, when it was modified 13.1.2 File Operations ○ A file is an abstraction of storage space - an ADT ○ What functionality does a file support Creation- find space, and created a directory information for it Open - rather than specifying the file name for every operation (which would incur tremendous overhead), we check permissions, evaluate the file name, etc, once Writing- a system call specifies the file handle, and the information to be written to the file Reading - a system call specifies the file handle and where (in memoryO th next block of the file should be put Handle Is a pointer? A file is an abstraction of storage space - an ADT What functionality does a file support?  Seek - moving the read or write pointer, so we can read/write from some location in the file other than where the last read/write occurred Delete - releases the space the file was occupying Truncate -Delete the contents of the file 13.1.3 File Types ○ If the operating system knows or can recognize what type a give file is, it can handle the file in reasonable ways(e.g., it shouldn’t try to execute a text file) ○ A common way to designate the file’s type is to append the type information to the file’s name - an extension of the name ○ The system can examine the file’s extension, and then reat it appropriately Files with extensions of “.exe” or “.com” are binary executables (on Windows) Files with extensions of “.bat” or “.sh” are shell scripts 13.1.4 File Structure ○ How should the contents of a file be structured? ○ Windows and UNIX treat a file as a stream of bytes ○ Each application is responsible for reading/ creating the appropriate structure for the kinds of file it supports Excel knows how to read / write xsl files Specific to the application Chapter 14 14.1 File System Structure ○ File system resides on secondary storage (disks) ○ Disk provides in - place rewrite and random access Any block of data We can access any part of secondary storage ○ I/O transfers are performed in units of locks (usually 512 bytes or 4096 bytes) 14.4 Allocation methods ○ Allocated those blocks to the hard disk drive ○ An allocation method refers to how disk blocks are allocated for files ○ Three major methods Contiguous allocation Linked allocation Indexed allocation 14.4.1 Contiguous allocation ○ Contiguous allocation - Each file occupies set of contiguous blocks 14.4.1 Linked allocation ○ Linked allocation - Each file a linked list of blocks  ○ 14.4.3 Indexed allocation ○ Indexed allocation - Each file has its own index block(s) of points to its data blocks ○ 13.3 Directory structure ○ Operations we may want to perform a directory ○ Search for a file ○ Create a file ○ Delete a file ○ List a directory ○ Rename a file ○ Traverse the file system 13.3.1 Single-Level Directory ○ In a single level directory, there is on directory ○ Two files with the same name aren’t allowed 13.3.2 Two-level Directory ○ In a two-level directory, each user has their own directory of files ○ The mast files (MFD) lets the OS located each user’s file directory (UFD) ○ Files names can be duplicated between users ○ One user can’t create (or even see) files in other user’s directories  13.3.3 Tree structured Directories ○ THe natural extension of the two level directory is a directory structured as a tree of some arbitrary height ○ Path names can be either absolute (specified from the root down to some particular file names location) 13.3.4 Acyclic - Graph directory ○ Generalizing a tree to an acyclic graph allows the sharing of a single (copy of a single) file between two users ○ Single files or even whole directories …… 13.4 Protection ○ Protection can take the form of reliability (protection from loss from physical damage) or improper…. ○ Most systems provide access controls lists (ACLS) ○ Each file has an ALC associated with it - a list of which users are allowed which kinds of access to a file ○ The owner of a file can list all users allowed a given kind of access ○ With this approach, the lists can get long ○ Some systems use an abbreviated version, dividing the system’s users into the owner’s