PREFINALS OS PDF

IT2105 Memory Management o External fragmentation – This occurs when the allotted memory Memory Management Requirements blocks are of varying sizes. This builds up due to the cont...

IT2105 Memory Management o External fragmentation – This occurs when the allotted memory Memory Management Requirements blocks are of varying sizes. This builds up due to the continuous Memory management is the functionality of an operating system (OS) that removal of processes in the main memory. manages the primary memory, which includes the movement of processes o Internal fragmentation – This occurs when the allotted memory back and forth between the main and the secondary memory during execution. blocks are of fixed size, and specific processes need more space or Memory management tracks every memory location, whether it is allocated or less space than the size of the allotted memory block (Parahar, 2019) free, and checks the amount of memory to be allocated for each process. It also facilitates the process allocation and correspondingly updates the The following are the requirements that memory management intends to memory status (Tutorialspoint, n.d.). satisfy (Stallings, 2018): Relocation: It is not possible for a programmer to know in advance which Types of addresses used in a program before and after memory allocation programs will reside in the main memory at the exact time of the program (Tutorialspoint, n.d.): execution. Hence, the possibility that the program may be moved within Symbolic addresses – These are the addresses used in a source code. the main memory due to swapping should always be considered. In The variable names, constants, and instruction labels are the basic addition, swapping active processes in and out of the main memory to elements of a symbolic address space. maximize processor utilization is also highly observed. Relative addresses – These are the addresses at the time of compilation. Protection: Each process should be protected against unwanted A compiler converts symbolic addresses into relative addresses. interference by other processes, whether accidental or intentional. Thus, Physical addresses – These addresses are generated by the loader programs in other processes should not be able to reference memory when a program is loaded into the main memory. locations in a process, for reading or writing purposes, without permission. A user process cannot access any portion of the operating system, neither The following are the commonly used terms in memory management: program nor data. Usually, a program in one process cannot branch to an Frame – This pertains to a fixed-length block of main memory. instruction in another process, and without special arrangement, a Page – This refers to a fixed-length block of data that resides in the program in one process cannot access the data area of another process. secondary memory. A page of data may temporarily be copied into a frame Sharing: Any protection mechanism must have the flexibility to allow in the main memory. several processes to access the same portion of the main memory. If a Segment – A variable-length block of data that resides in the secondary number of processes are executing the same program, it is advantageous memory. An entire segment may temporarily be copied into an available to allow each process to access the same copy of the program rather than region of the main memory, or the segment may be divided into pages, have its own separate copy. In most cases, processes that are cooperating which can be individually copied into the main memory (Stallings, 2018). on some task may need to share access to the same data structure. Swapping – It is a mechanism in which a process can be swapped Logical organization: Most programs are organized into modules, some temporarily out of the main memory to the secondary memory in order to of which are unmodified, read-only or execute-only, and some of which make memory space available for other processes. It is also known as contain data that are modifiable. It would be a great advantage if the memory compaction. operating system and computer hardware could effectively manage user Fragmentation – This occurs due to the continuous loading and removal programs and data in modules. of processes in the memory, wherein free memory spaces are broken Physical organization: The task of moving and organizing information down into smaller fragments. This happens when processes cannot be flow between the main and the secondary memory should be a system allocated to memory blocks because of their small size and memory blocks responsibility. This task is the essence of memory management. remains unused (Tutorialspoint, n.d.). Computer memory is organized into at least two (2) levels, which are as follows: 05 Handout 1 *Property of STI  [email protected] Page 1 of 2  IT2105 o Main memory – This is a volatile memory that provides fast access at Simple Segmentation. Each process is divided into a number of segments, a relatively high cost. The main memory technically holds programs wherein a process is loaded by adding all of its segments into dynamic and data that are currently in use. partitions. o Secondary memory – This is usually a non-volatile memory at a There is no internal fragmentation in using this technique, resulting to an cheaper cost with slower access. A secondary memory of large improved memory utilization and reduced overhead compared to dynamic capacity is a good storage of programs and data for a longer term. partitioning. External fragmentation is a drawback of this technique. Memory Partitioning Techniques Fixed Partitioning. The main memory is divided into a number of static Virtual Memory partitions at system generation time, wherein a process may be loaded into a Virtual memory is an abstraction of the main memory, providing processes partition of equal or greater size. Nowadays, the use of fixed partitioning is and the kernel with their own, almost infinite, private view of the main memory. uncommon in the industry (Stallings, 2018). Virtual memory is made possible through the support from both the processor It is simple to implement and produces only a minimal operating system and operating system. Below are some characteristics of a virtual memory overhead. (Gregg, 2021): There is a high chance of inefficient use of memory due to internal It supports multitasking, allowing processes and the kernel to operate on fragmentation. their own private address space without worrying about contention. The maximum number of active processes that can be catered is fixed. It supports oversubscription of the main memory, allowing the operating system to transparently map virtual memory between the main and the Dynamic Partitioning. The partitions are created dynamically, wherein each secondary memory, as needed. process is loaded into a partition of exactly the same size as the process. It is not a real memory and most operating systems map virtual memory This technique has no internal fragmentation, which results in a more to real memory only on demand (when the memory is first populated or efficient use of the main memory. written). Inefficient use of the processor can transpire due to the need for memory compression to counter external fragmentation. Virtual Memory Paging. This partitioning method is similar to simple paging, Below are the three (3) possible placement algorithms that can be considered but does not necessarily load all of the pages of the process. This has no in implementing dynamic partitioning: external fragmentation and encompass large virtual address space, that may 1. Best-fit – This chooses the block that is closest to the requested size. lead to a higher degree of multiprogramming. 2. First-fit – This scans the memory from the beginning and chooses the first available block that is large enough to cater to the process. Virtual Memory Segmentation. This partitioning method is similar to simple 3. Next-fit – This scans the memory from the location of the last segmentation, but does not necessarily load all the segments of a process. placement and chooses the next available block that is large enough This has no internal fragmentation and encompass a large virtual address to cater to the process. space, that may also lead to a higher degree of multiprogramming. Simple Paging. The memory is divided into a number of equally sized frames, References: Gregg, B. (2021). System performance: Enterprise and Cloud (2nd ed.). Pearson Education, Inc. while each process is divided into a number of equally sized pages of the same Silberschatz, A., Galvin, P. & Gagne, G. (2018). Operating systems concepts (10th ed.). John Wiley & Sons, Inc. length as the frames. Then, a process is loaded by adding all of its pages into Stallings, W. (2018). Operating systems: Internal and design principles (9th ed.). Pearson Education Limited Tutorialspoint. (n.d.). Operating System – Memory Management. Retrieved on October 25, 2021 from the available frames (Stallings, 2018). https://www.tutorialspoint.com/operating_system/os_memory_management.htm Parahar, M. (2019, November 28). Difference between internal fragmentation and external fragmentation. Retrieved on October 26, 2021 It plays an important role in implementing virtual memory. from https://www.tutorialspoint.com/difference-between-internal-fragmentation-and-external-fragmentation This technique reduces external fragmentation. This technique may cause a small amount of internal fragmentation. 05 Handout 1 *Property of STI  [email protected] Page 2 of 2  IT2105 Scheduling of the ready state to the running state of the process. The dispatcher Process Scheduling executes more frequently compared to the job scheduler, and makes the Scheduling or process scheduling is the act of selecting a job or a task that fine-grained decisions of which process to execute next. The primary is to be dispatched. In some operating systems, other units of work, such as objective of the dispatcher is to increase the system performance in the input/output (I/O) operations, may also be scheduled (Stallings, 2018). This accordance with the chosen set of criteria. particular activity of the process manager handles the removal of a running Medium-term scheduling – This is a part of the swapping function. The process from the central processing unit (CPU), followed by the selection of medium-term scheduler is in charge of handling the swapped-out another process on the basis of a particular strategy or algorithm. The processes. On the other hand, the swapping-in decision is based on the operating system (OS) maintains the following important process scheduling need to manage the degree of multiprogramming. This actually reduces queues (Tutorialspoint, n.d.): the degree of multiprogramming. Job queue – This queue contains all the processes in the system. o Swapping: A running process becomes suspended if it makes an I/O Ready queue – This queue keeps a set of all processes residing in the request, wherein it cannot make any progress towards completion. In main memory, ready and waiting to execute. A new process is always order to remove the process from the memory and make space for added to this queue. other processes, the suspended process is moved to the secondary Device queue – This queue contains processes waiting for a device to storage. Hence, the process of swapping. become available. Note that there are unique queues available for each I/O device. Generally, a set of criteria is established against various scheduling policies that may be evaluated. Note that it is impossible to optimize all scheduling Process scheduling is an essential part of a multiprogramming operating criteria simultaneously. The following are the key scheduling criteria that are system. The basic intent of process scheduling is to divide CPU time among usually encountered in operating systems (Stallings, 2018): active processes and threads and maintain a notion of priority in order to Turnaround time: The interval of time between the submission of a execute a more important job or task sooner. The scheduling of processes on process and its completion. This involves the time spent waiting in the processors and individual CPUs are performed by the scheduler, a key ready queue, plus the actual execution time, plus the time spent waiting component of the OS kernel (Gregg, 2021). for resources, including the processor. Formula: Turnaround Time = Finish Time – Arrival Time Process scheduling assigns processes to be executed in a way that meets Response time: The time from the submission of a request until the system objectives, such as response time and throughput. The scheduling response begins to be received. In most cases, a process begins activity can be broken down into three (3) separate functions below. The producing some output to the user while continuing to process the request. names suggest the relative time scales with which these functions are Thus, this criteria is a better measure than the turnaround time from the performed (Stallings, 2018). user's point of view. In addition, the scheduling discipline should attempt Long-term scheduling – This involves a long-term scheduler, also known to achieve low response time and maximize the number of users receiving as a job scheduler, that determines which programs are admitted to the the acceptable response time. system for processing. Thus, it controls the degree of multiprogramming. Burst time: The amount of time required for a process to be executed by If the degree of multiprogramming is stable, then the average rate of the CPU. This criterion is also called the execution time or running time process creation must be equal to the average departure rate of processes (Ishaque, n.d.). of the system. The primary objective of the job scheduler is to provide a Waiting time: The scheduling algorithm also affects the amount of time balanced mix of jobs. that a process spends waiting in the ready queue. This is the sum of the Short-term scheduling – This involves a short-term scheduler, also periods spent waiting in the ready queue (Silberschatz, Galvin, & Gagne, known as the dispatcher, that is invoked whenever an event that may 2018). Formula: Waiting Time = Turnaround Time – Burst Time lead to the blocking of the current process occurs. It is actually the change 06 Handout 1 *Property of STI  [email protected] Page 1 of 4  IT2105 Throughput: The scheduling algorithm should attempt to maximize the Preemptive: The currently running processes may be interrupted and number of processes completed per unit of time. This is the measure of moved to the Ready State by the OS. The decision to preempt may be how much work is being performed by the processor. performed during the following circumstances: Processor utilization: The percentage of time that the processor is busy. o A new process arrives For exclusive shared systems, this criterion is significant. In other systems, o An interrupt occurs that places a blocked process in the Ready State including single-user systems, this criterion is less important. Conceptually, processor utilization can range from 0 to 100 percent. In a First-Come First-Serve (FCFS) real system, it should range from 40% (lightly loaded) to 90% (heavily In this algorithm, all incoming processes join the ready queue. Then, if the loaded). currently running process ceases to execute, the process that has been in the Priority: The process priority can be modified dynamically by the ready queue the longest is selected for running. FCFS performs better for long scheduler to improve the performance of certain workloads. Note that processes. It is not an appealing alternative on its own for a uniprocessor when processes are assigned with specific priorities, the scheduling system. However, it is often combined with a priority scheme to provide an algorithm should favor higher-priority processes. effective scheduler (Stallings, 2018). Fairness: In the absence of guidance from the user or other system- It is a non-preemptive algorithm. supplied guidance, processes should be treated the same, and no process It is easy to understand and implement. should suffer from starvation. It is also identified as a strict queuing scheme. Resource balancing: The scheduling algorithm should keep the All jobs are executed on a first-come first-serve basis. resources of the system busy. Processes that will underutilize stressed The performance of this algorithm is poor since the average waiting time resources should be favored. This criterion also involves is high. In operating systems, workloads can be categorized as either of the following FCFS Example: (Gregg, 2021): Process A B C D E CPU-bound – This includes applications that perform heavy compute Arrival Time 0 2 4 6 8 operations, such as scientific and mathematical analysis, which are Bust Time (Ts) 3 6 4 5 2 expected to have long runtimes. I/O-bound – This includes applications that perform input/output Finish Time 3 9 13 18 20 Turnaround operations, such as web servers, file servers, and interactive shells, where 3 7 9 12 12 Time (Tr) low-latency responses are desirable. Waiting Time 0 1 5 7 10 Tr/Ts 1.00 1.17 2.25 2.40 6.00 Process Scheduling Algorithms In process scheduling, each algorithm encompasses a specific selection function that determines which process among the ready processes is selected next for execution, and a decision mode that specifies the instants in time at which the selection function is exercised. The decision mode of an algorithm can either be (Stallings, 2018): Non-preemptive: Once a process is in the Running State, it continues to execute until it terminates or it blocks itself to wait for an I/O operation or to request some OS service. Average Turnaround Time: 43 / 5 = 8.60 Average Waiting Time: 23 / 5 = 4.60 Average Tr/Ts: 12.82 / 5 = 2.56 06 Handout 1 *Property of STI  [email protected] Page 2 of 4  IT2105 Shortest Job First (SJF) The scheduler always chooses and executes the process that has the This algorithm is easy to implement in batch systems, where the required CPU shortest expected remaining processing time. time is known in advance. On the other hand, this algorithm is impossible to This does not have the bias in favor of long processes found in a first- implement in interactive systems where the required CPU time is unknown. It come first-serve setup. is the best approach to minimize the waiting time (Tutorialspoint, n.d.). There are no additional interrupts generated, reducing the overhead. It is a non-preemptive algorithm. The elapsed service time can be recorded, contributing to the overhead. It is also called the shortest job next or shortest process next. This algorithm selects and executes the process with the shortest SRTF Example: expected or estimated processing time. Thus, the processing time must Process A B C D E be known in advance by the processor. Arrival Time 0 2 4 6 8 Bust Time (Ts) 3 6 4 5 2 SJF Example: Process A B C D E Finish Time 3 15 8 20 10 Arrival Time 0 2 4 6 8 Turnaround Time (Tr) 3 13 4 14 2 Bust Time (Ts) 3 6 4 5 2 Waiting Time 0 7 0 9 0 Tr/Ts 1.00 2.17 1.00 2.80 1.00 Finish Time 3 9 15 20 11 Turnaround Time (Tr) 3 7 11 14 3 Waiting Time 0 1 7 9 1 Tr/Ts 1.00 1.17 2.75 2.80 1.50 Average Turnaround Time: 36 / 5 = 7.20 Average Waiting Time: 16 / 5 = 3.20 Average Tr/Ts: 7.97 / 5 = 1.59 Average Turnaround Time: 38 / 5 = 7.60 Round Robin (RR) Average Waiting Time: 18 / 5 = 3.60 This algorithm involves the generation of a clock interrupt at periodic intervals. Average Tr/Ts: 9.22 / 5 = 1.84 When the interrupt occurs, the currently running process is placed in the ready queue, and the next ready job is selected on a first-come first-serve basis. This Shortest Remaining Time First (SRTF) technique is known as time slicing, because each process is given a slice of In this algorithm, when a new process with a shorter remaining time joins the time before being preempted (Stallings, 2018). ready queue, the scheduler may preempt the currently running process and It is a preemptive algorithm. execute the new one. The scheduler must have an estimate of the processing Each process is provided with a fixed time to execute, called the quantum. time to perform the selection function. In addition, the risk of starvation of long Once a process has consumed all its allotted execution time, it is processes exists (Stallings, 2018). automatically preempted and another process executes for a given period It is a preemptive version of the SJF algorithm. of time. 06 Handout 1 *Property of STI  [email protected] Page 3 of 4  IT2105 RR Example: NPP Example: Process A B C D E Process A B C D E Arrival Time 0 2 4 6 8 Arrival Time 0 0 6 11 12 Bust Time (Ts) 3 6 4 5 2 Bust Time (Ts) 4 3 7 4 2 Finish Time 3 17 11 20 19 Finish Time 4 7 14 20 16 Turnaround Turnaround Time (Tr) 3 15 7 14 11 Time (Tr) 4 7 8 9 4 Waiting Time 0 9 3 9 9 Waiting Time 0 4 1 5 2 Tr/Ts 1.00 2.50 1.75 2.80 5.50 Quantum = 4 Average Turnaround Time: 32 / 5 = 6.40 Average Waiting Time: 12 / 5 = 2.40 Average Turnaround Time: 50 / 5 = 10.00 Average Waiting Time: 30 / 5 = 6.00 References: Average Tr/Ts: 13.55 / 5 = 2.71 Gregg, B. (2021). System performance: Enterprise and Cloud (2 nd ed.). Pearson Education, Inc. Ishaque, S. (n.d.). Arrival, burst, completion, turnaround, waiting, & response time. Retrieved on November 15, 2021 from https://www.educative.io/edpresso/arrival-burst-completion-turnaround-waiting-response-time Non-Preemptive Priority (NPP) Scheduling Silberschatz, A., Galvin, P. & Gagne, G. (2018). Operating systems concepts (10 th ed.). John Wiley & Sons, Inc. In general, each system process is assigned with a corresponding priority, and Stallings, W. (2018). Operating systems: Internal and design principles (9 th ed.). Pearson Education Limited Tutorialspoint. (n.d.). Operating system scheduling algorithm. Retrieved on November 15, 2021 from the scheduler will always choose a process of higher priority. A particular https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm challenge exists in implementing a pure priority-based scheduling, and that is: Tutorialspoint. (n.d.). Operating Systems – Process Scheduling. Retrieved on November 15, 2021 from https://www.tutorialspoint.com/operating_system/os_process_scheduling.htm lower priority processes may suffer starvation. This can possibly occur if there is a constant and steady supply of higher-priority processes. On the other hand, the priority of a process can still change based on its age or execution history (Stallings, 2018). It is a non-preemptive algorithm. It is the most common scheduling algorithm in batch systems. Each process is assigned with a priority and the process with the highest priority will always be executed first. Processes with the same priority level are executed on a first-come first- serve basis. The priority of a process can be based on memory requirements, time requirements, or any other resource requirements. 06 Handout 1 *Property of STI  [email protected] Page 4 of 4