OS Cheatsheet

Operating System

A system software. It works as an interface between user and hardware (CPU, I/O Devices, RAM). We access these hardware through the Operating System. But why? Why can’t we directly access hardware? 1. Because then we will need to write a program to access the device. 2. Interaction between user and hardware will become too complex. Example - Windows, GNU Linux, MacOS.

Functions

  1. Resource Manager/Governor

  2. Process Management - CPU Scheduling algorithms are used here.

  3. Storage Management (Hard disk) - How to save data permanently in a hard disk is managed by OS. We do this through the file system.

  4. Memory Management (RAM) - Whatever the processes we need to execute should be brought to RAM. And after successful execution it should move from RAM to HD.

  5. Security and Privacy

Throughput - Number of tasks executed per unit time.

System Call - It is a programmatic way in which a computer program requests a service from the kernel of the OS. These calls are generally available as calls written in C or C++. Types of system call: Process Control, File Manipulation, Device Management, Information Maintenance, Communication, Protection.

  1. File related - open(), read(), write(), close(), create file

  2. Device related - read, write, reposition, ioctl (I/O control), fcntl (File control)

  3. Information related - get pid, attributes, get system time and data

  4. Process control - execute, abort, fork, load, wait, signal, allocate

  5. Communication - pipe(), create/delete connections, shmget() (Shared Memory get)

Fork() -> We use this to create a child process. Child is a parent's clone. We can also use thread. Fork is almost completely different from its parent, but the thread is similar to its parent. Fork returns 0, 1, or -1. 0 means child process. 1 or positive means parent process. -1 if the child process is not created.

Types of OS

  1. Batch OS - Similar kinds of jobs make a batch. Used in the 1960s. While processing a batch of jobs, if the process needs some kind of input output devices then during that time the CPU stays idle. Disadvantages. Non-preemption.

  2. Multi-programmed OS - Bring as many processes in RAM as possible. Multiple processes. Non-preemptive. If a process P1 is taken from RAM and provided to CPU, then CPU will perform P1 completely then only moves to some other process. Advantage - CPU does not stay idle. Now if P1 needs some input devices, it will do that. During this time the CPU doesn’t stay idle. Because we already have a lot of processes in RAM. So the CPU takes another process. If in a class of 10 students, every student has 5 doubts. I go to solve their doubts. Then I will solve all 5 doubts of the 1st student until and unless he/she himself/herself needs a break. Then only I shall move to the next student.

  3. Multitasking or Time sharing OS - Preemptive. We beforehand provide some time for each process. So if the process gets executed within that time, well and good. Otherwise reschedule in the future. Advantage - No idleness. Response time - In multiprogrammed 10th student gets his doubts resolved after waiting the most. But here, response time is faster. Used in everyday life in our laptops.

  4. Real time OS

Semaphore is simply a non-negative variable which is used to solve the critical section problem and to achieve process synchronization in the multiprocessing environment. For the critical section, Semaphore is 1. Wait and Signal Semaphore.

Spooling

SPOOL is an acronym for simultaneous peripheral operations on-line. It is a kind of buffering mechanism or a process in which data is temporarily held to be used and executed by a device, program or the system. Data is sent to and stored in memory or other volatile storage until the program or computer requests it for execution. The most common can be found in I/O devices like keyboard printers and mouse. For example, In printer, the documents/files that are sent to the printer are first stored in the memory or the printer spooler. Once the printer is ready, it fetches the data from the spool and prints it., system call.

Critical Section

When more than one process accesses the same code segment that segment is known as the critical section. Critical section contains shared variables or resources which need to be synchronized to maintain consistency of data variables.

Race around condition

Process intro, PCB - A process control block (PCB) contains information about the process, i.e. registers, quantum, priority, etc. The process table is an array of PCB’s, that means logically contains a PCB for all of the current processes in the system.

A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms.

Process - A program in execution is called a process. An OS executes a variety of programs: Batch System- Jobs, Time-shared System- User programs or Tasks. A process includes- Program Counter, Stack, Data Section. A program is a passive entity and a process is an active entity. Process associates PC and other resources with it. A program becomes a process when an executable file is loaded into memory.

Set of Values held by a process - #Current Value of Program Counter, #Contents of the Processors Registers, Value of the variables, #Process Stack which typically contains temporary data such as subroutine parameter, return address, and temporary variables. #Data Section that contains Global Variables.

Process States

  1. New - Stored in Secondary Memory. A new state. Stable state.

  2. Ready - Queue. Process in RAM. Short term scheduler. From ready to running.

  3. Running - Process in RAM. The number of processes running depends on the number of CPUs. We are giving the instructions of the process to the CPU and CPU executes them. If a higher priority process turns up, we stop the already running process and move it to RAM. This higher priority process is now entered to the CPU and executed. Multitasking. Our time limit is there then also we block some processes and move it back to RAM.

  4. Terminated - De-allocation. Resources given to processes are taken back.

  5. Block - Also in RAM. If a process says it needs some I/O or whatever from secondary memory, then the CPU tells it to move to a block state. And then moves back to Ready after doing its work.

  6. Suspend Wait - If our wait queue (which is in RAM) gets filled because all the processes need I/O devices or secondary memory, we create another state: suspend wait. And we move the process to Secondary memory (swap out). Medium Term Scheduler handles this.

  7. Suspend Ready State - If our ready queue is filled completely, then we will of course stop the newer states from coming. But just in case a very high priority process comes like a kernel call, system call we will have to allow it. This is when we use the suspended ready state. MTS handles this too.

  8. Backing Store - If the block state queue is getting filled up continuously, and the process in the suspend block state can’t move back to the wait state, they move to the ready queue or suspend ready queue again.

What brings the new processes from stable state to Ready state or within the RAM? - Long Term Scheduler. LTS is responsible for bringing as many processes to the ready state as possible. Multiprogramming Concept.

User Mode vs Kernel Mode - By default, we are in user mode. Processor switches between user mode and kernel mode. Suppose I open a text editor in Linux. I used the in-built API and opened it. User mode. Suppose in a C Program I have to read a file. So I will use System Call (read). System Call is a way to access the kernel. User mode bit = 1, kernel mode bit = 0. When we shift from User Mode to kernel mode, a trap is generated.

Process vs Threads

We are talking about a multiprocessing multitasking environment. We either need multiple CPUs. Or in one CPU we use multiprocessing or multithreading. In the fork we create a complete clone. So data and all are copied which is an overhead. In a thread, data is shared.

  1. Process is a heavy weight task vs thread is a light weight task.

  2. System call is involved in process vs no system call is used in thread.

  3. OS treats different processes differently. (Pid is different from process and forked process). But in thread, all user level threads are treated as a single task for the OS.

  4. Different processes have different copies of data. Threads share the same code and data. (Only stack, register are different in thread)

  5. Context Switching is faster in threads.

  6. Blocking a process will not block other processes. Blocking a thread blocks all the threads of the process because for an OS thread is just a single process.

  7. Processes are independent, and threads are interdependent.

User level thread vs Kernel Level thread

  1. Managed by user level library, managed by OS.

  2. User level threads are typically fast, but kernel levels are slower.

  3. Context switching faster than kernel level thread.

  4. If a user level thread gets blocked the entire process is blocked. But if the kernel level thread is blocked, it has no effect on others.

CPU Scheduling

  1. Arrival Time - time at which process enters the ready queue.

  2. Burst time - time required by process to get executed on CPU. It depends on the CPU.

  3. Completion time - time at which process gets completed.

  4. Turnaround time - (completion time - arrival time)

  5. Waiting time - (turnaround time - burst time)

  6. Response time - (Time at which process gets CPU first time - Arrival time)

Process Scheduling Algorithms - A way of selecting a process from the ready queue or RAM and executing them in the CPU.

  1. Pre-emptive

    1. *SRTF (Shortest Remaining Time First)

    2. LRTF (Longest Remaining Time First)

    3. *Round Robin Scheduling

    4. Priority Based

  2. Non preemptive (Process will get executed completely)

    1. FCFS (First come, First serve)

    2. SJF (Shortest Job First)

    3. LJF (Longest Job First)

    4. HRRN (Highest Response Ratio Next)

    5. Multilevel Queue

Two reasons of preemptive - Response Time and Priority

Process Synchronization

  1. Cooperative Process - Execution of a process affects another because they share something (variable, buffer, code, resource).

  2. Independent Process

Critical Section

It is the part of the problem where shared resources are accessed by various cooperative processes. If one process is executing the Critical Section code, then the other processes should not be allowed to execute Critical Section code otherwise we will face Race conditions. To solve this and execute Critical Section, a process will have to execute Entry section code.

  1. Mutual Exclusion - Primary rule. If P1 has entered the Critical Section and executed it, then if P2 simultaneously wants to enter the Critical Section we can’t allow it.

  2. Progress - Primary rule. No one is using Critical Section atm. P1 wants to enter CS, but P2 stops it. (Maybe because some code written in Entry Section of P2 stops P1).

  3. Bounded Wait - Secondary rule. If P1 is in CS, and P2 outside. P1 uses CS and comes out. And then again moves into CS and comes out. P1 executed CS thrice, fourth and then infinitely. So this doesn’t happen. P2 should get a chance. There should be a limit. P2 Starved.

  4. No assumption related to hardware speed - Secondary rule. Whatever the synchronization solution is should work on every system and not have hardware specifications. Like it should work in all OS, all architectures.

Semaphore

It is a method or tool used to prevent race conditions in co-operative processes. Semaphore is an integer variable which is used in a mutually exclusive manner by various concurrent cooperative processes in order to achieve synchronization.

  1. Counting - (-Infinity, +Infinity)

  2. Binary - {0, 1}

Deadlock

If two or more processes are waiting on happening on the same event, which never happens then we say these processes are involved in deadlock and are in a deadlock state. A is moving towards B, and B is moving towards A. Now either of the cars have to move back otherwise both are in a deadlocked state. Suppose a process needs two semaphores S1 and S2. And P2 needs S2 and S1. P1 takes S1 and waits for S2. And P2 has S2 and waits for S1. This is a deadlock situation. Both are waiting now. Suppose there are two resources R1 and R2 and two processes P1 and P2. Resource R1 is allocated to P1 and now P1 needs R2 to execute successfully. Similarly, resource R2 is allocated to P2 and P2 now needs R1. But R1 is allocated to P1. DEADLOCK.

Necessary conditions for deadlock to occur:

  1. Mutual Exclusion - Whatever resource is being talked about should be used in a mutually exclusive way. This means no two processes can share the same resource simultaneously. Example - Printer. At a time only one process’s document is printed.

  2. No preemption - We can’t tell a process to preempt and release all its resources so that some other process can use it. Here all the processes are of equal priority. Example - Suppose the car example. If a car is an ambulance, and the other is someone’s private vehicle then the ambulance has a higher priority so the private vehicle will have to leave the road. But that’s not the case here. No process will get preempted.

  3. Hold and wait - P1 is holding resource R1 and waiting for R2. P2 is holding resource R2 and waiting for R1.

  4. Circular Wait - An infinite loop of resources and processes. P1 has resource R1 and requests R2. P2 has resource R2 and requests R3. P3 has resource R3 and requests R1.

Methods to handle deadlock situation:

  1. Deadlock Ignorance (Ostrich Method) - Ignore the deadlock. Used widely. Because a deadlock occurs very rarely. Ostriches during a sandstorm just put their neck under the sand, and pretend that there is no sandstorm. We are ignoring deadlock because we do not want to affect speed and performance.

  2. Deadlock Prevention - Prevention is better than cure. So here we try to prevent a deadlock before it even occurs. We try to prevent mutual exclusion, no preemption, hold and wait or circular wait.

  3. Deadlock Avoidance (Banker’s Algorithm) - Whenever we provide any resource to a process we try to figure out if it is a safe situation or not.

  4. Deadlock Detection & Recovery - We first detect a deadlock, and then try to recover it. Kill the process or preempt the resource.

Memory Management

It is a method to manage various kinds of memories like RAM, hard disk, registers. Method of managing primary memory. Goal of memory management is efficient utilization of memory. Multiprogramming means bringing multiple programs from Secondary memory to primary memory. Higher the degree of multiprogramming, more is the CPU utilization. Suppose a process is in the RAM and getting executed. Now it wants some I/O devices. So the process will leave. At this point our CPU stays idle. To prevent that we bring multiple or you can say as many programs from secondary memory as possible to the primary memory.

Memory management techniques

The whole and sole purpose is to keep the maximum number of processes in RAM so that CPU utilization is maximum.

  1. Contiguous

    1. Fixed Partition or Static - Used in 1960s in mainframes. Number of partitions is fixed beforehand. While the number of partitions is static, the size of each partition may or may not be the same. Contiguous allocation, hence spanning (a process will have to enter a complete partition) is not allowed.

      1. Internal Fragmentation - Suppose the partition size is 8MB. And a process of size 6MB mounts on this. The remaining 2 MB are wasted and can’t be used in any way.

      2. Limit in process size - If the maximum size of partition is 8MB then a process of size 10MB can’t be executed at all.

      3. Limitation on degree of multiprogramming - If the total number of partitions is n, then we can not bring more than n processes. And this puts a limit on the degree of multiprogramming.

      4. External Fragmentation

    2. Variable Partition or Dynamic - Space is allocated to processes only when they come in RAM. If a process sized 2MB comes in RAM, we allocate 2MB in RAM at runtime. So there is no chance of Internal Fragmentation here. Yay!

      1. Advantages

        1. No internal fragmentation

        2. No limitation on number of processes

        3. No limitation on the process size

      2. Disadvantages

        1. External Fragmentation - Suppose there are 5 processes namely P1, P2 (4MB), P3, P4 (4MB) and P5. Now P2 gets executed and leaves. Then there will be a hole of 4 MB space. Now suppose P4 also leaves. There is another hole of 4 MB. Now a process P6 enters. It is of size 8 MB. Despite having 2 holes which will sum up to our required memory size, we cannot allocate P6 any memory because we do not have 8 MB in continuous fashion. We can handle this through compaction.

        2. Allocation and deallocation are a bit complex.

  2. Non-Contiguous - A process is divided into different blocks. In RAM, they are not stored sequentially but in a non continuous way. A process can span among different memory locations. We remove external fragmentation with this.

    1. Paging - A process is divided into pages in the secondary memory itself. And the main memory is also divided into frames beforehand. And the very important point here is that the size of the frame should be equal to the size of the page.

    2. Multilevel paging

    3. Inverted Paging

    4. Segmentation

    5. Segmented Paging

Further Reading : Memory Management Unit (MMU)

Thrashing

It is linked to the degree of multiprogramming. How to handle thrashing?

  1. Increase main memory size

  2. Long term scheduler - Tell LTS to decrease the degree of multiprogramming

Segmentation

A method where a process will be divided into parts or segments and placed in main memory. Difference with paging: In paging, whatever program we have written will be divided into pages without knowing what it contains. Page size is the same in paging. But in Segmentation, the size of different segments vary.

Virtual Memory

It is a concept. It provides an illusion to the programmer that a process whose size is larger than the size of main Memory can also be executed.

Page Fault - When a CPU is looking for a page, but that is not present in the Main memory it is called page fault.

Page Replacement Algorithms

To reduce the number of page faults and bring pages from Secondary Memory efficiently into the Main Memory.

  1. First In First Out (FIFO)

  2. Optimal Page Replacement - Replace the page which is not used in the longest dimension of time in future.

  3. Least Recently Used (LRU) - Replace the least recently used page in the past. Disadvantage - Speed.

  4. Most Recently Used (MRU) - Replace the most recently used page.

Disk Architecture

Disk Access Time

  1. *Seek time - time taken by read/write head to reach the desired track.

  2. Rotation time - time taken for 1 full rotation (360).

  3. Rotational latency - time taken to reach to desired sector (half of rotation time)

  4. Transfer time - Data to be transfer/transfer rate

  5. Transfer rate - No of heads * Capacity of 1 track * no of rotations in 1 second

Further Reading : Belady's Anomaly

Disk Scheduling Algorithm

To minimize the seek time (time taken to reach desired track).

  1. First come first serve (FCFS) - No starvation.

  2. Shortest Seek time first (SSTF) - Find nearest value to current position. Seek time lesser than FCFS on an average. Response time is better than FCFS. But starvation is a problem. It may happen that a request waits too long. Overhead to find the nearest value to the current position.

  3. SCAN or Elevator Algorithm - Move towards a particular direction completely, and then move to other directions. 50 to 199 and then 199 to 16.

  4. LOOK - 50 to 190 and then 190 to 16.

  5. CSCAN - 50 to 199 and then 199 to 0 and then 0 to 43.

  6. CLOOK - 50 to 190 and then 190 to 16 and then 16 to 43.

Different memory allocation algorithms

  1. First fit - Allocate the first hole that is big enough.

  2. Next fit - Same as first fit but start searching always from the last allocated hole.

  3. Best fit - Allocate the smallest hole that will be enough.

  4. Worst fit - Allocate the largest hole.

Functions of OS

  1. Memory Management

  2. Device Management

  3. Processor Management

  4. Security

  5. Error Detection

  6. Coordination between Software and User

  7. Job Accounting

  8. File Management

Evolution of OS - Serial Processing: No Operating System, Programmers interacted directly with Computer Hardware → Batch Processing: Users do not interact directly with the computer, The early mechanics of processing a batch involved feeding a computer a stack of punched cards that held commands, or directions, for the computer to follow. → Multiprogramming: Two or more user programs can be in memory and are executed one after another. → Time Sharing → Parallel System: Breaking up a task into smaller pieces and executing those pieces at the same time, each on their own processor → Distributed System: Client-server system or peer-to-peer system. Collection of independent, networked, communicating, and physically separate computational nodes.

Further Reading : 1. https://leetcode.com/discuss/interview-question/operating-system/124638/what-happens-in-the-background-from-the-time-you-press-the-Power-button-until-the-Linux-login-prompt-appears 2. https://leetcode.com/discuss/interview-question/operating-system/125107/What-happens-when-we-turn-on-computer

Last updated