OperatingSystem.md

Operating Systems

• What is an Operating System? What are the different types of Operating systems?

  • OS performs all the basic tasks like managing files and processes and memory.
  • Batch Operating System
  • Time-Sharing Operating System
  • Distributed Operating System
  • Network Operating System
  • Real-Time Operating System

• What is a monolithic kernel?

  • The kernel is basically the heart of an OS
  • Kernel loads when we boot our PC/Laptop.
  • The kernel is a block of code that runs the whole OS. It is stored in the protected area of the main memory.
  • It acts as a bridge between the applications and the internal blocks like CPU, memory and IO devices.
  • A monolithic kernel is a type of kernel where all the components of OS are shared by the same part of memory. This makes the OS fast.
  • There is direct communication between the modules as they are sharing the same part.

• Process Vs Program

  • The .exe file generated by a code is stored in the secondary memory. It is called as a program.
  • When the.exe file is brought into the main memory, it becomes a process. A process has a definite structure.
  • The structure of a process is divided into 4 parts. They are 1) Code, 2) Data, 3) Heap, 4) Stack.
  • The code part has the .exe file.
  • The Data part stores all the global and the static variables.
  • The Heap is used to store dynamically allocated memory.
  • The Stack is used to store your temporary variables and function calls.

• Process Vs Threads

  • Processes are a complete block. Basically, If we create a new child process from a parent process, everything will be generated newly. We will have a new stack, new heap, new data, and new code. On the other hand, threads only generate new stacks and heaps. The data and code are shared with the parent.
  • Context Switching is slower in processes but faster in threads because of sharing of memory and addresses.
  • Blocking a single process won't affect or block the parent, but blocking a thread will completely stop the parent process. Hence they are interdependent.

• What is Virtual Memory?

  • Virtual Memory is used when we need to process a program whose size is bigger than the main memory.
  • We load the main memory with multiple processes. We take x number of pages of process 1, y number of pages of process 2, and so on. We won’t try to load the main memory with a single process. We will try to accumulate as many processes as we can.
  • A lot of page faults can lead to thrashing and make the computer slow.

• User Level Thread vs Kernel Level Thread

  • User Level Thread is created on a user level by using libraries. Whereas Kernel level threads are created by the kernel by making system calls.
  • User Level Threads are faster than Kernel level threads. The context switching is faster in User Level threads because of no system calls involvement.
  • If a single thread from a user-level thread is blocked, the whole process gets blocked but if a single thread is blocked from a kernel-level thread, it does not block the whole process.

• What is a Critical Section?

  • A critical Section is a place where all the common code/data/resources are stored which can be accessed by various processes.
  • Before accessing the critical section, a process has to run a certain entry code which checks if whether it is safe for the process to enter the section or not.
  • Similarly, before exiting the critical section, there is an exit code that has to be run which lets the other processes know about the current state of the critical section.
  • This is done to solve problems related to synchronization and racing.
  • There are various things that work as an entry/exit code before accessing the critical section. For example, semaphores and mutex.
  • Any entry/exit code must follow 4 conditions. 1) Mutual Exclusion, 2) Progress, 3) Bounded Waiting, and 4) No hardware/software dependancy.

• What is Mutual Exclusion?

  • Mutual Exclusion is a state where only one process out of the two processes that share the same data can access the critical section at a time. If this is followed, then we can say that these 2 processes are mutually exclusive

• What is Context Switching?

  • Context Switching means saving the context of a current process in the PCB (Process Control Block) and bringing a new process from the ready queue to the running queue.

• Producer-Consumer Problem

  • The Producer-Consumer problem is a classic Process synchronization problem.
  • Assume there are two cases, Case I is an ideal case. Here a producer block runs and produces an item and puts it into the buffer and maintains the count of total items. After this, the consumer block runs and consumes an item from the buffer and reduces the count by one. All works fine here.
  • Case II: Here suppose the producer block ran fine till this statement: count=count+1.
  • The internal working of this statement is something like this. First, the current value of count is stored in a register, after that the register is incremented by one and then the value of the register is copied back into the variable.
  • Now suppose the first two internal steps work fine, but when the register was going to copy the value back in the variable, the whole process gets preempted from the CPU. (Can be any reason, priority/time quantum, etc).
  • Now the consumer starts running and does it work. The consumer code block also reaches the same line of code. In consumer since we are consuming something, the line would be count = count-1.
  • The internal working with the register is the same for both, in producer it was increment, here it would be decrement. So suppose after decrementing the value in the register, the consumer process preempts.
  • Now producer will run again and finish that last bit of work, i.e copying the value back in the count variable. And after that, the consumer will also execute its last bit, i.e copy the decremented value back in the variable. Now if you think carefully, the number of items in the buffer is not equal to the count variable.
  • Let's look at both the cases in numbers. In Case I, the producer produces a block, stores it in buffer, and count becomes 1, then the consumer consumes and removes the block from the buffer and the count becomes 0. So count equals the number of blocks in buffer.
  • Now let's see case 2. Suppose there are 3 blocks already in the buffer. So the count is 3. Now the producer produces and tries to make count 4 but as discussed above, the process preempts. So the count should be 4 but is still 3. The number of blocks in the buffer is 4.
  • Now consumer runs and removes a block from the buffer and decrements the count but as discussed above, it preempts before the value is stored. So the count value should be 2 but is still 3.
  • Now the produces executes its last step and stores the register value in the variable and hence the count gets updated from 3 to 4.
  • Now the consumer executes its last line and hence the count gets updated with the value in the register of the consumer code. which was 2.
  • So the no of items in the buffer is 3 but the count variable is 2. So this is the producer-consumer problem of process synchronization.

• Preemptive vs Non-Preemptive Scheduling

  • In Preemptive scheduling, we can take one process from the ready queue and push it in the running queue and we can take that process out of the running queue in midway and put it back in the ready queue. In short, we have the flexibility to stop that process anytime we want and then use it later.
  • In Non-Preemptive Scheduling, we don't have such a facility. Once a process is pushed in the running queue, it will only come out when it is done. So the process executes fully in non-preemptive scheduling.

• What is FCFS Scheduling

  • FCFS means First-Come-First-Serve. It is a non-preemptive scheduling algorithm.
  • Just like its name, In FCFS, the process which comes first in the ready queue gets completed first.

  FCFS Example

  • Turn Around Time is the total time spend by the process in the queue. So Turn Around Time equals Completion Time-Arrival Time.
  • Waiting Time is the time for which the process has waited to get executed. So it will be turnaround time-burst time. In Non-Preemptive scheduling, waiting time is equal to the response time.

• What is SJF Scheduling

  • SJF means Shortest Job First. It is a non-preemptive scheduling algorithm
  • As the name suggests, the main criteria of this algorithm are to look at the burst time. Priority is given to the processes that have a shorter burst time.
  • If the burst time is the same then pick the process who arrived earlier.

• What is SRTF Scheduling

  • Shortest Remaining Time First is a preemptive scheduling algorithm.
  • The main criterion for assigning the process is its burst time. The lesser the burst time, the higher its priority.
  • For example, if a process arrives at 0 and has a burst time of 5 and the next process arrives at 1 and has a burst time of 4, so we first start with process 0 and do it for 1 quantum of time. Then we check if any new process has arrived. In this case, yes it has and its burst time is less than the current process' burst time. So we preempt the running process and take process 1 and start executing it.
  • If two processes have the same burst time then we look at the arrival time.
  • In short, whenever a new process arrives, just compare it to the current process' remaining burst time. If it is smaller, then just preempt the running process and prioritize the new process
  • In preemptive scheduling algorithms, the response time is calculated as CPU first time-arrival time. CPU first time is the time at which the process got the CPU for the very first time.

• What is Round Robin Scheduling?

  • Round Robin Scheduling Algorithm is a preemptive algorithm.
  • The main criteria in the Round Robin Scheduling is the time quantum.
  • We set a time quantum and every process runs for that time quantum and then it is pushed back in the ready queue once again.
  • Let's suppose the time quantum(TQ) is 2. In the start, we first take a process from the ready queue and execute it for 2 TQ. We stop and look if any new process has arrived in the ready queue or not. If yes, we save the context of the current process and push it back to the ready queue. Then we bring the second process to the running queue and execute it for 2 TQ.
  • So now at 4 TQ, we check if there are any new processes, if yes then we do the above step again. If no, we bring back to process 1 in the running queue and send process 2 in the ready queue. We keep on doing this till our ready queue is not empty/ all processes have finished.

• What is Priority Scheduling?

  • Priority Scheduling is an algorithm that can be done in a preemptive as well as non-preemptive manner.
  • The main criterion of this algorithm is priority. Every process is assigned with a priority. The higher the priority, the earlier it gets the CPU.
  • Suppose we start with a process p1 with priority 10 at TQ=0. We run this process for 1 TQ and then see if we have a new process in the ready queue or not. If yes and if the priority of the new process is greater than the current process, we push the current process back in the ready queue and start executing the new process.
  • We do this step till all the processes are finished and the ready queue is empty.

• What is deadlock?

  • Deadlock is basically a condition that arises due to some situations. There are 4 necessary things that must happen to declare a certain state as a deadlock. These 4 conditions are
  • 1. Mutual Exclusion, 2) No Preemption, 3) Hold and Wait, and 4) Circular Wait.

  

  • The above diagram meets all 4 conditions, hence we can say that it is in a deadlock.
  • Process 1 has resource 1 and it is waiting for resource 2. It won't release resource 1 unless and until it gets resource 2. Similarly, Process 2 has resource 2 but it needs resource 1. It will also not leave resource 2 until it gets resource 1.
  • Obviously, we can't preempt the processes. If preemption was possible, this state would have never arrived. Both of them are holding on to their resources and waiting for the new one and as you can see it is forming a circular loop.

• What is Fragmentation?

  • Fragmentation is a concept. Fragmentation occurs during contiguous memory allocation.
  • There are 2 types of Fragmentation. 1) Internal, and 2) External Fragmentation.
  • Internal Fragmentation occurs when there is a small chunk of memory left even after allocating a process the whole partition.
  • For Example, suppose a 10 MB memory has been partitioned into 5 equal parts. So each partition has 2MB of memory. Now, a process of 1MB needs some space. So you give it the first partition. The process occupies 1MB of space and 1MB is empty.
  • Since we are doing contiguous memory allocation, we cannot assign the next process that remaining 1MB of space. We will have to assign it to the next partition. So hence we have that 1 MB of space empty which will remain empty throughout.
  • Suppose 5 such 1 MB processes take up all the 5 partitions. Now we have 5 MB of free space left which cannot be used by any other process. Suppose a process arrives which needs 5 MB of space but since we are using contiguous memory allocation, we cannot use those 5 MB and assign it to the 6th process. Because all the chunks of 5MB are present in different partitions. This is called External Fragmentation.
  • So internal fragmentation is the space leftover in a partition after assigning a process and external fragmentation is the concept of being unable to assign the leftover space to a new process.

• What is a semaphore?

  • Semaphore is a variable which is used to avoid creation of racing conditions. Semaphore is used to achieve synchronization between two co-operative processes in a mutually exclusive manner. Producer-Consumer problem can be solved using semaphores.
  • There are 2 types of semaphores. Counting Semaphore and binary semaphore.

• What is a counting semaphore?

  • As discussed above, the semaphore is a variable. A counting semaphore is a variable whose value varies from -INF to +INF.
  • Every process has to go to a critical section before getting the CPU. So before getting into the critical section and before getting out of it, there is a code which has to be run. These codes maintain the semaphore count and also manages the critical section.
  • Before going in the critical section, a code called as Down()/ Wait / P() is executed.
  • Here is the code for the same.

  P(Semaphore s)
  {
      s.value = s.value - 1;
      if (s.value < 0) {
   
          // add process to queue
          // here p is a process which is currently executing
          q.push(p);
          block();
      }
      else
          return;
  }

  • For every process, the value of semaphore decrements by 1, and the process is pushed in the critical section. But when the value of the semaphore becomes negative, the current process that wants to go in the critical section is blocked and it is stored in a block list.
  • Now, let's look at the code which has to be executed before exiting the critical section. It is called as Up() / Signal / V().

  V(Semaphore s)
  {
      s.value = s.value + 1;
      if (s.value <= 0) {
   
          // remove process p from queue
          Process p=q.pop();
          wakeup(p);
      }
      else
          return;
  }

  • Before a process exits the critical section, this piece of code is run. So suppose our semaphore value is -1. 3 processes are in the critical section and 1 process is blocked.
  • Now let's say p1 wants to get out of the section, so this code runs and the semaphore value becomes 0. Since it is ≤ 0, the if condition executes and the process which was in the blocklist is activated again. By activated, we mean that it is sent to the ready queue once again.
  • Now suppose process p2 wants to exit the critical block. So the code runs and the semaphore value becomes 1. Since it is greater than 0, then if won't work.
  • So this was all about counting semaphores.

• What is a binary semaphore?

  • Binary Semaphore is a variable which will have only 2 values. 0 and 1. The working and concept is exactly as same as the counting semaphore. But the code for both of them is a bit different.
  • The P() code for Binary semaphore looks like this

  P(semaphore s)
  {
      if (s.value == 1) {
          s.value = 0;
      }
      else {
          // add the process to the waiting queue
          q.push(P)
          sleep();
      }
  }

  • The main thing to note here is, in binary semaphores, the semaphore value will always be initialized with 1. If it is initialized with 0, no process will ever get into the critical state and it will forever keep going in the block list.
  • Now before exiting the critical section, a V() / Signal / Down code has to be executed as we all know. So the code for that operation looks like this.

  V(Semaphore s)
  {
      if (s.q is empty) {
          s.value = 1;
      }
      else {
   
          // select a process from waiting queue
          Process p=q.pop();
          wakeup(p);
      }
  }

  • S.q is the block list. If the block list is empty, it means that we can now make semaphore 1 and let a new process in the critical section.
  • If the block list is not empty, then we pick a process from the block list and send it to ready queue.
  • Binary semaphores are generally used when there are 2 co-operative processes.

• What is a Lock (Mutex)

  • Mutex / Lock is a variable that is used to avoid race conditions.
  • There are a few similarities and differences between Mutex and Semaphore.
  • Mutex is an ownership model. Once a process locks a mutex and gets into the critical condition, no one apart from that process can unlock it. The working of semaphores is not like this.
  • Below is the table that compares a Mutex and a semaphore
  • Mutex and Binary Semaphore are not at all the same thing.

  Mutex vs Binary Semaphore

• What is a starvation problem and what is aging?

  • So, starvation is basically a problem which arises in priority scheduling.
  • Suppose there is a process with a priority of x. (lower the x, higher the priority).
  • Along with this process, there are multiple processes who has a priority lower than x. Now with time, let's say more processes arrive in the ready queue and all of them have a priority less than x.
  • So the process with priority x will never get executed. It will, but it will be the last process in the queue. So this is the starvation problem.
  • Aging is a technique used to solve this problem. In aging, suppose a process is in the ready queue for a long amount of time (decided by the OS) then it reduces its priority number by 1 at every t seconds( t is also determined by the OS).
  • So in this way, the priority of that process will gradually increase over the time and it wil get executed.
  • So by increasing the priority of the process after a certain interval of time t, we can solve this starvation problem.

• What is Bankers' Algorithm?

  • Bankers Algorithm is a way to detect Deadlock and avoid it. Well, the Bankers algorithm works only when we know about how much resources all the processes would need beforehand.
  • So it is not quite practical in nature but it is a very fundamental algorithm to detect and avoid deadlock.

  

  • In the above table, suppose we have 10 instances of A, 5 instances of B, and 7 instances of C
  • The initial allocation is given in column 2. The maximum allocation of a resource that any process needs is given in column 3 and the currently available no of resources is given in column 4.
  • We go in order from P0 and compare the values of A, B, and C in its (Max-already Allocated) column to the available A, B, and C.
  • If all three of A, B, and C in the max are less than the available, then we can successfully allocate the resources P0. In this case, that is not possible. So we move to P1 and do the same checking.
  • In P1, it is possible, so we allocate the needed resources, and p1 finishes its work. After it is done, it releases its Allocation instances which were given to it by default. (Present in Allocation Column)
  • Now the number of available resources has increased from 3,3,2 to 5,3,2. Now we go to process 3 and do the same checking.
  • In this way, we check for all processes and in the end, all the processes will work fine in a sequence. That sequence is called a safe sequence.
  • If none of the processes were able to get the remaining process in the first traversal of the column, it means that there will be a deadlock situation in the future.
  • So in this way, we detected the deadlock.

• What is Paging?

  • Paging is a concept that is used to efficiently manage processes in the memory.
  • The memory is divided into frames and the process is divided into pages.
  • The size of a single frame should be equal to the size of a particular page.
  • We then store the pages in frames in the main memory. When the CPU asks for a particular part of the process, we use the page table to retrieve the exact part of the process.
  • Page Table is a mapping concept. We map the page number to its frame.
  • The CPU sends a logical address, we find out the byte from it, then we search for the byte's page number, and then from the table, we get to know the frame number. In that frame, we find the exact position of the bit by using frame number and frame offset.
  • The logical address passed by the CPU can be divided into two parts, the first part is the page number and the second is the page offset.
  • The maximum number of bits in the page number part will depend upon the number of pages. Mathematically it would be Log(pg) [base 2]. If there are 8 pages then at max we need 3 bits to represent all of them.
  • Since Process size and Page size are predefined, we can find out the number of pages easily. Page size tells us the number of bytes a page can have at max.
  • The whole page logic can be applied to the frames. Where memory size and frame size are known and we can get the number of frames. Then the first part will be the frame number and the second would be the frame offset.
  • Frame offset tells us the exact position of that bit in that frame.

• What is Demand Paging?

  • Demand Paging is a concept where the pages of a process aren't loaded in the main memory unless and until there is a requirement for it.
  • So the frames of the main memory are empty. The pages are only filled in it when the user asks for a particular page of a process.
    • This helps in increasing the number of processes in the main memory. The number of page faults also increases.
  • So there must be a balance between the number of pages of a process so that page faults are not that high. If page faults occur more frequently, the CPU's utilization will fall down as it will take a lot of time to get those pages from the secondary memory to the main memory.
  • If a user demands for a page of a process and it is not found in the page table, then there is a context switch and the CPU brings the page from the secondary memory to the main memory. Then there is a context switch again and another call is made for the page. This time we will get the page in the main memory.

• Segmentation Vs Paging?

  • Segmentation is somewhat similar to Paging. In Segmentation, the sizes in which a process is divided are not equal.
  • They are divided by user perspective. For example, if there was an Add() function in the code, then in Paging, the process would be divided anyhow. So there could have been a possibility that some part of the add function was on some other page and the remaining part on other. So the CPU had to find two pages to execute this function.
  • In segmentation, the whole Add() function will be assigned to a single segment and then it will be stored in the memory.
  • Accessing a segment is similar to accessing a page from the frames. The CPU asks for the logical address, which is then converted into the physical address of the segment. The segments are tracked with the help of a segment table.
  • There are three columns. The first column gives us the segment number, the second column gives us the starting address of the segment in the main memory and the third column has the maximum size of a particular segment.
  • The CPU asks for a segment number and the size of that segment. If the size wanted by CPU is greater than the max size of that segment, then there is a TRAP generated which gives us an error.

• Multiprogramming vs Multitasking?

  • Multiprogramming means loading the Main memory with some number of resources and executing them in a non-preemptive manner.
  • Multitasking means loading the Main memory with some number of resources and executing them in a preemptive manner.
  • Multitasking is better because it gives a better response time. The time for which the CPU is idle is the same in both cases.

• What is Dynamic Binding?

  • Dynamic Binding is a way of memory management. It is used in contiguous memory allocation.
  • In Dynamic Binding, there is no predefined fixed partitioning of the main memory. Instead, the memory is assigned to a process dynamically,(in a continuous fashion) when it asks for it.
  • There are three advantages of Dynamic Binding over Static Binding.
  • 1. There is no internal fragmentation. As there is no predefined size, there is no chance of empty space in the main memory.
  • 2. The number of processes assigned to the main memory in Dynamic Binding is greater than the number of processes assigned in static binding.
  • 3. There is no limit on the maximum size a process can have in order to get into the memory. In static allocation, since we already divide the main memory into fixed-sized, there could have been a case where a process comes whose size is bigger than the greatest partition. This kind of scenario will never occur in dynamic binding.
  • There is a disadvantage of dynamic binding and that is external fragmentation. Since dynamic binding is a concept of contiguous memory allocation if suppose there are two processes whose work is done and now they leave the main memory but these two processes are in different locations.
  • Let's say process 1 had a size of X and process 2 had a size of Y. Now suppose a new process arrives of size X+Y. We won't be able to assign this process to the memory because the holes are not in contiguous locations. Hence there is an external fragmentation.

• What is Belady's Anomaly?

  • Belady's Anomaly is a kind of an exception that occurs in the FIFO page replacement policy.
  • There are a few patterns of page requests which generate absurd behavior.
  • The absurdness is that if the CPU asks for the pages of any process in these patterns, then there will be more page faults in a CPU with more frames.
  • Generally, if we increase the number of frames, the page faults count should reduce. But there are some patterns of requests which generate more page faults if the number of frames is higher.
  • An example is : 1 2 3 4 1 2 5 1 2 3 4 5.

• What is Cache?

  • The cache is basically a memory that is connected with the CPU and the RAM.
  • The cache is faster compared to RAM and secondary memory.
  • There are two main ways to store data/ process in the cache. They are direct mapping and associative mapping.

• What is RTOS?

  • RTOS means Real-Time Operating System. It is a very advanced operating system. There are two types of RTOS.
  • Hard RTOS and soft RTOS.
  • RTOS systems are very fast and there can't be any delay in the processing. Soft RTOS allows a bit of delay but hard RTOS doesn't allow any kind of delay whatsoever. A delay in RTOS can straightaway lead to system failure.
  • RTOS has faster task switching and it is less prone to error.

• What is Direct Mapping?

  • Direct Mapping is a way of mapping processes in the cache.
  • The main memory is divided into blocks of fixed sizes. The main memory has a fixed size and all the blocks are divided in accordance to the size.
  • Similarly, the cache is also divided into a fixed size and they are called lines. The size of the lines and the size of the blocks must be the same.
  • Processes are stored in the main memory initially. Processes are stored as words/bytes.
  • If the main memory's size is 128 words and every block can contain maximum 4 words, then the total number of blocks will be 32.
  • Similarly, if the cache's size is 16 words and each line can store 4 words, then there will be a total of 4 lines.
  • As the name suggests, a direct mapping is mapping the data in a direct form.
  • By direct form, what I mean is the blocks are stored in the cache by using this formula: K % n.
  • Here K is the block number and n is the total number of lines.
  • So suppose we needed all the words of Block 3 in the cache, then we would store it in line number 3. Because 3 % 4 is 3.
  • The CPU demands for process via logical address. The address is split into two halves, block number and block offset. The block number requires log(No of blocks) bits and the offset bits are the log of the size of a block.
  • When we store this data from RAM to cache, the address changes a bit, instead of block size and block offset, now we use a tag number, line number, and the block offset
  • The CPU, first searches for the process in the Cache, if found, we have a cache hit. If not, then it goes to the RAM and gets the process. And after that, it also stores it in the cache.

• What is Associative Mapping?

  • Associative Mapping is another type of Mapping processes to the cache.
  • Instead of hash function like k%n or something, any block can go in any line of the cache.
  • One major advantage of associative mapping over direct mapping is that there is no conflict miss in this method.
  • Since any block can go in any line, there is a better chance of cache hit rather than cache miss.
  • One disadvantage of associative mapping is that the size of the tag bits increases significantly.
  • Also, in direct mapping, we know the exact line where a block can be found since it is hashed. but in associative mapping, we will have to search one by one in every line for the particular block. So number of comparisons is greater.