Skip to content
Author: Tianle Yuan

👨‍💻 Operating System⚓︎

Interview Questions for Operating System

Table of Content

Operating System⚓︎

Click for answers 👇

The system software that controls computer hardware and software resources.

  • Its main functions include:
    1. Managing resources such as processes, memory, files, and devices;
    2. Providing an interface for user programs;
    3. Ensuring the normal operation of computer systems.

picture 1 picture 2

  • The purpose of an operating system is to:
    1. Provide a good user experience;
    2. Enable computer to excute programs efficiently and reliably.

Classifications of OS⚓︎

Click for answers 👇

  • Time-sharing OS: allows multiple users to share the resources of the single computer system simultaneously.

  • Batch processing OS: loads a batchprogramsfrom the user into the computer system to run according to certain rules until all programs are completed.

  • General purpose OS: has both the functions of Time-sharing and Batch processing. E.g Windows, Linux, MacOS.

  • Real-time OS: has high requirements for the response time of the computer system and can complete tasks within a specified time.

  • Distributed OS:

    • distributes the resources of the computer system across multiple computer nodes;
    • cooperates through a network to improve the reliability and performance of the computer system.

  • Embedded OS: an operating system designed for devices with small sizes, low power consumption, and high reliability.

OS components⚓︎

Click for answers 👇

  • Kernel: the core part of the operating system, responsible for managing computer hardware and providing basic functions, such as system calls.

  • Process manager: responsible for the efficient operation of the computer system, including:

    • creating, deleting, scheduling, and managing processes.

  • Storage manager: responsible for managing computer memory resources, including:

    • memory allocation, recovery, and protection.

  • File system: responsible for managing files and directories in the computer system, including:

    • file reading, writing, creation, deletion, and protection.

  • Input/output manager: responsible for managing data transfer between the computer system and external devices, including:

    • input/output buffering, device drivers, and interrupt handling.

Process and thread⚓︎

Click for answers 👇

Definition with comparison

  • Definition:

    • Process is an instance of a running program with its own independent instruction address space and system resources (program code, data, stack, and process control blocks).
    • Thread is an execution unit in a process, sharing resources of the process including address space, file descriptors, signal handlers, and process ID.

  • Scheduling:

    • Process is the basic scheduling unit in an operating system, and the operating system manages processes through process control blocks.
    • Threads are scheduling units within a process, and the operating system schedules threads.

  • Concurrency:

    • Processes are independent of each other. Different processes run concurrently, with each process having its own independent address space and resources.
    • Threads within the same process share resources and data. Threads executed on the same CPU are executed concurrently, whereas threads executed on different CPUs are executed in parallel.

  • System overhead:

    • Process switching requires saving and restoring all process states, so process switching incurs a larger system overhead.
    • Thread switching only requires saving and restoring part of the thread state, so thread switching incurs a smaller system overhead.

Different states of processes⚓︎

Click for answers 👇

Three states: running, ready, or waiting:

  • Running: the process has all the resources it needs for execution, and it has been given permission by the OS to use the processor.
  • Ready: the process is waiting for permission to use the processor.
  • Waiting: the process is waiting for some external event to occur, such as user input or disk access.
  • Only one process can be in the running state at any given time.
  • The remaining processes are either in a waiting state or a ready state.
  • In a real operating system, the waiting and ready states are implemented as queues that hold the processes in these states.

Parameters for process scheduling⚓︎

Click for answers 👇

Definition with comparison

  • Moment：
    • Arrival Time (AT): Time at which the process arrives in the ready queue.
    • Completion Time (CT): Time at which the process completes its execution.
  • Period:
    • Burst Time (BT): Time required by a process for CPU execution.
    • Turn Around Time (TAT): Completion Time - Arrival Time
    • Waiting Time (WT): Turn around time -Burst time.

Necessity of process⚓︎

Click for answers 👇

A typical process involves both I/O time and CPU time.

In a uniprogramming system like MS-DOS, time spent waiting for I/O is wasted and CPU is free during this time.

In multiprogramming systems, one process can use CPU while another is waiting for I/O. This is possible only with process scheduling.

Different process scheduling algorithms (PSA)⚓︎

Click for answers 👇
  • First Come First Serve (FCFS): processes are scheduled according to their arrival times.
  • Shortest Job First (SJF): processes with the shortest burst time are scheduled first.
  • Shortest Remaining Time First (SRTF): processes are scheduled with the shortest remaining time -- amount of time left for a process to complete its execution (preemptive mode of SJF algorithm)
  • Round Robin (RR) Scheduling: each process is assigned a fixed time; in a cyclic way.
  • Priority Based scheduling (Non Preemptive): processes are scheduled according to their priorities. If priorities of two processes match, then scheduling is according to the arrival time.
  • Highest Response Ratio Next (HRRN): processes with highest response ratio(Turn around time / Burst time) is scheduled. This algorithm avoids starvation (Consider a situation when a long process is there in the ready queue and shorter processes keep coming.).
  • Multilevel Queue Scheduling (MLQ): According to the priority of process, processes are placed in the different queues. Generally high priority process are placed in the top level queue. Only after completion of processes from top level queue, lower level queued processes are scheduled.
  • Multilevel Feedback Queue (MLFQ) Scheduling: It allows the process to move in between queues. The idea is to separate processes according to the characteristics of their CPU bursts. If a process uses too much CPU time, it is moved to a lower-priority queue.
  • FCFS can cause long waiting times, especially when the first job takes too much CPU time.
  • Both SJF and SRTF algorithms may cause starvation. HRRN can solve it.
  • If time quantum for RRS is very large, then it behaves same as FCFS scheduling.
  • SJF is optimal in terms of average waiting time for a given set of processes. SJF gives minimum average waiting time, but problems with SJF is how to know/predict the time of next job.

Objectives of PSA⚓︎

Click for answers 👇
  • Max CPU utilization (Keep CPU as busy as possible)
  • Fair allocation of CPU.
  • Max throughput (Number of processes that complete their execution per time unit)
  • Min turnaround time (Time taken by a process to finish execution)
  • Min waiting time (Time for which a process waits in ready queue)
  • Min response time (Time when a process produces first response)

Critical section problem & solution⚓︎

Click for answers 👇

The critical section problem arises when multiple processes or threads need to access shared resources simultaneously, such as data structures or hardware devices. Without proper synchronization mechanisms in place, this can lead to unexpected results or unintended behavior, known as race conditions. Here are some concepts you need to know:

  • Critical Section – The portion of the code in the program where shared variables are accessed and/or updated.
  • Remainder Section – The remaining portion of the program excluding the Critical Section.
  • Race around Condition – The final output of the code depends on the order in which the variables are accessed.

A solution for the critical section problem must satisfy the following three conditions:

  • Mutual Exclusion: If a process is executing in its critical section, then do not allow other processes to enter into the critical section.
  • Progress: If no process is executing in the critical section, then the decision of a process to enter a critical section cannot be made by any other process that is executing in its remainder section. The selection of the process cannot be postponed indefinitely.
  • Bounded Waiting: There exists a bound on the number of times other processes can enter into the critical section after a process has made request to access the critical section and before the requested is granted.

Synchronization Tools⚓︎

Click for answers 👇

A Semaphore is an integer variable that is accessed only through two atomic operations, wait() and signal(). An atomic operation is executed in a single CPU time slice without any pre-emption.

Semaphores are of two types:

  • Binary Semaphore: It has two states, 0 and 1. It is used for mutual exclusion, where only one process can access the critical section at a time.

  • Counting Semaphore: It has a positive integer value that can be incremented or decremented. It is used to control access to a shared resource where multiple processes can access the critical section simultaneously, but the maximum number of processes that can access it at any given time is limited by the value of the semaphore.

Deadlock⚓︎

Click for answers 👇

A situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

Deadlock can arise with four necessary Conditions hold simultaneously:

  • Mutual Exclusion – One or more than one resource are non-sharable (Only one process can use at a time).
  • Hold and Wait – A process is holding at least one resource and waiting for resources.
  • No Preemption – A resource cannot be taken from a process unless the process releases the resource.
  • Circular Wait – A set of processes are waiting for each other in circular form.

There are three ways to handle deadlock:

  • Deadlock prevention or avoidance: The idea is to not let the system into deadlock state.
  • Deadlock detection and recovery: Let deadlock occur, then do preemption to handle it once occurred.
  • Ignore the problem all together: If deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.

Memory Management⚓︎

Click for answers 👇

The techniques allow multiple processes to share the same memory.

Here are two techniques:

  • Overlays: The memory should contain only those instructions and data that are required at a given time.
  • Swapping: In multiprogramming, the instructions that have used the time slice are swapped out from the memory.

Memory Management Techniques⚓︎

Click for answers 👇

(a) Single Partition Allocation Schemes – The memory is divided into two parts. One part is kept to be used by the OS, and the other is kept to be used by the users.

(b) Multiple Partition Schemes:

  • Fixed Partition – The memory is divided into fixed size partitions.
  • Variable Partition – The memory is divided into variable sized partitions. Variable partition allocation schemes:
    • First Fit – The arriving process is allotted the first hole of memory in which it fits completely.
    • Best Fit – The arriving process is allotted the hole of memory in which it fits the best by leaving the minimum memory empty.
    • Worst Fit – The arriving process is allotted the hole of memory in which it leaves the maximum gap.
  • Best fit does not necessarily give the best results for memory allocation.
  • The cause of external fragmentation is the condition in Fixed partitioning and Variable partitioning saying that entire process should be allocated in a contiguous memory location. Therefore Paging is used.

Paging & Segmentation⚓︎

Click for answers 👇

Two techniques used by OS to manage the allocation of memory.

Paging: divides memory into logical units called pages. Each page represents a fixed-size chunk of memory, often 4KB in size.

  • When a program needs to access a memory location, the operating system maps the virtual address used by the program to a physical address in memory using a page table. This allows programs to access memory without knowing its physical location, and it also allows the operating system to manage physical memory more efficiently by loading pages into memory only when needed.

Segmentation: divides memory into logical units called segments. Each segment represents a specific part of the program, such as the code, data, or stack. Each segment has a unique size and is assigned a base address and a limit.

  • When a program needs to access a memory location, the operating system maps the logical address used by the program to a physical address in memory using a segment table. This allows programs to access memory more efficiently, as they only need to know the logical location of the data they need to access.

Logic memory & Virtual memory⚓︎

Click for answers 👇

  • Logical memory is the memory space that a process sees as its own, and it consists of several segments, such as the code segment, data segment, and stack segment. Each segment contains a different type of data that the process needs to execute.

  • Virtual memory on the other hand, is a technique used by operating systems to allow processes to use more memory than is physically available in the computer. It uses a combination of hardware and software to map a process's logical memory to physical memory or to a temporary storage area on disk called the swap file.

Page Fault⚓︎

Click for answers 👇

A page fault is a type of interrupt, raised by the hardware when a running program accesses a memory page that is mapped into the virtual address space, but not loaded in physical memory.

File System⚓︎

Click for answers 👇

File System: A file is a collection of related information that is recorded on secondary storage. Or file is a collection of logically related entities.

File Directories⚓︎

Click for answers 👇

File Directories: Collection of files is a file directory. The directory contains information about the files, including attributes, location and ownership. Here are several directory types:

  • SINGLE-LEVEL DIRECTORY: In this a single directory is maintained for all the users

  • TWO-LEVEL DIRECTORY: Due to two levels there is a path name for every file to locate that file.

  • TREE-STRUCTURED DIRECTORY: Directory is maintained in the form of a tree. Searching is efficient and also there is grouping capability.

Here are some file allocation ways:

  • Continuous Allocation: A single continuous set of blocks is allocated to a file at the time of file creation.

  • Linked Allocation(Non-contiguous allocation): Allocation is on an individual block basis. Each block contains a pointer to the next block in the chain.

  • Indexed Allocation: It addresses many of the problems of contiguous and chained allocation. In this case, the file allocation table contains a separate one-level index for each file

Disk time⚓︎

Click for answers 👇

  • Seek time is the time taken to locate the disk arm to a specified track where the data is to be read or write.

  • Rotational Latency is the time taken by the desired sector of the disk to rotate into a position so that it can access the read/write heads.

  • Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and number of bytes to be transferred.

  • Disk Access Time = Seek Time + Rotational Latency + Transfer Time

  • Response Time is the average of time spent by a request waiting to perform its I/O operation. Average Response time is the response time of the all requests.

Buffer⚓︎

Click for answers 👇

A buffer is a memory area that stores data being transferred between two devices or between a device and an application.

Disk Scheduling Algorithms⚓︎

Click for answers 👇
  • FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed in the order they arrive in the disk queue.
  • SSTF: In SSTF (Shortest Seek Time First), requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in a queue and then they are scheduled according to their calculated seek time. As a result, the request near the disk arm will get executed first.
  • SCAN: In SCAN algorithm the disk arm moves into a particular direction and services the requests coming in its path and after reaching the end of the disk, it reverses its direction and again services the request arriving in its path. So, this algorithm works like an elevator and hence also known as elevator algorithm.
  • CSCAN: In SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.
  • LOOK: It is similar to the SCAN disk scheduling algorithm except for the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.
  • CLOOK: As LOOK is similar to SCAN algorithm, in a similar way, CLOOK is similar to CSCAN disk scheduling algorithm. In CLOOK, the disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

References:⚓︎

Comments