Topics - NIX OS

An operating system (OS) is system software that manages computer hardware and software resources and provides common services for computer programs.

  • Wikipedia

Editor Note:

  • The material below was cobbled together for personal use, from attributed sources, and endured some mild look/feel massage.
  • Document Purpose: Conveniently scoped refresher on the listed Linux OS components.


Functional Concept - Concurrency

- Basics -
  • A multi-processing OS must arbitrate consumption of scarce, common resources.
    • Occurs through major concepts of Processes, Threads, Scheduling, Context Switching.
  • Enforcement of a mutual exclusion concurrency control policy is achieved through mutual exclusion concepts.
    • Monitors, Semaphores, Mutexs, Locks
  • Critisisms: Avoid deadlocks and resource-starvation in a concurrent system.
    • See “Dining Philosophers” Problem


- Basics -
  • Processes carry out tasks within the operating system. A program is a set of machine code instructions and data stored in an executable image on disk and is, as such, a passive entity.
  • A process can be thought of as a computer program in action.


  • System resources (CPU, memory, files, etc)


  • Running: The process is either running (it is the current process in the system) or it is ready to run (it is waiting to be assigned to one of the system’s CPUs).
  • Waiting:
    • The process is waiting for an event or for a resource.
    • Linux differentiates between two types of waiting process; interruptible and uninterruptible. Interruptible waiting processes can be interrupted by signals whereas uninterruptible waiting processes are waiting directly on hardware conditions and cannot be interrupted under any circumstances.
  • Stopped: The process has been stopped, usually by receiving a signal. A process that is being debugged can be in a stopped state.
  • Zombie:
    • This is a halted process which, for some reason, still has a task_struct data structure in the task vector.
    • It is what it sounds like, a dead process.
- In the weeds -
  • The scheduler needs the process state information in order to fairly decide which process in the system most deserves to run.


- Basics -
  • It is the scheduler that must select the most deserving process to run out of all of the runnable processes in the system.
  • Each process decides to relinquish the CPU that it is running on when it has to wait for some system event.
  • For example, a process may have to wait for a character to be read from a file.
    • This waiting happens within the system call, in system mode; the process used a library function to open and read the file and it, in turn made system calls to read bytes from the open file.
    • In this case the waiting process will be suspended and another, more deserving process will be chosen to run.
- In the weeds -
  • A runnable process is one which is waiting only for a CPU to run on.
  • Linux uses a reasonably simple priority based scheduling algorithm to choose between the current processes in the system.
  • When it has chosen a new process to run it saves the state of the current process, the processor specific registers and other context being saved in the processes task_struct data structure.
  • It then restores the state of the new process (again this is processor specific) to run and gives control of the system to that process.

Fair Scheduling

  • For the scheduler to fairly allocate CPU time between the runnable processes in the system it keeps information in the task_struct for each process:
    • policy:
      • This is the scheduling policy that will be applied to this process.
      • There are two types of Linux process, normal and real time.
    • priority:
      • This is the priority that the scheduler will give to this process.
      • It is also the amount of time (in jiffies) that this process will run for when it is allowed to run.
      • You can alter the priority of a process by means of system calls and the renice command.
    • rt priorty:
      • Linux supports real time processes and these are scheduled to have a higher priority than all of the other non-real time processes in system.
      • This field allows the scheduler to give each real time process a relative priority.
      • The priority of a real time processes can be altered using system calls.
    • counter:
      • This is the amount of time (in jiffies) that this process is allowed to run for.
      • It is set to priority when the process is first run and is decremented each clock tick.

Kernel relationship

  • The scheduler is run from several places within the kernel.
  • It is run after putting the current process onto a wait queue and it may also be run at the end of a system call, just before a process is returned to process mode from system mode.
  • One reason that it might need to run is because the system timer has just set the current processes counter to zero.
  • Each time the scheduler is run it does the following:
    • kernel work: The scheduler runs the bottom half handlers and processes the scheduler task queue (lightweight kernel threads).
    • Current process: The current process must be processed before another process can be selected to run.
    • Process selection: The scheduler looks through the processes on the run queue looking for the most deserving process to run.
    • Swap processes: If the most deserving process to run is not the current process, then the current process must be suspended and the new one made to run.


- Basics -
  • In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler.
  • Threads are “light weight processes” (LWPs).
  • The idea is a process has five fundamental parts: code (“text”), data (VM), stack, file I/O, and signal tables.
  • Threads reduce overhead by sharing fundamental parts. By sharing these parts, switching happens much more frequently and efficiently.
  • There are two types of threads: user-space and kernel-space.
- In the weeds -

Contrast to Processes

  • Processes are typically independent, while threads exist as subsets of a process
  • Processes carry considerably more state information than threads, whereas multiple threads within a process share process state as well as memory and other resources
  • Processes have separate address spaces, whereas threads share their address space
  • Processes interact only through system-provided inter-process communication mechanisms
  • Context switching between threads in the same process is typically faster than context switching between processes.

How to shoot yourself in the foot

  • Since threads are in a shared space, care must be taken to avoid race, dead/livelock conditions. Use abstracts of syncronization primitives.
  • One awry thread can affect other process-owned threads, crash them.

Context Switching

- Basics -
  • A context switch is the computationally intensive switching of the CPU (central processing unit) from one process or thread to another.
  • A context is the contents of a CPU’s registers and program counter at any point in time.
    • A register is a small amount of very fast memory inside of a CPU (as opposed to the slower RAM main memory outside of the CPU) that is used to speed the execution of computer programs by providing quick access to commonly used values, generally those in the midst of a calculation.
  • A context switch is sometimes described as the kernel suspending execution of one process on the CPU and resuming execution of some other process that had previously been suspended.
    • Or suspending progression of a process.
- In the weeds -
  • The kernel performing the following activities with regard to processes (including threads) on the CPU:
    • (1) suspending the progression of one process and storing the CPU’s state (i.e., the context) for that process somewhere in memory,
    • (2) retrieving the context of the next process from memory and restoring it in the CPU’s registers and
    • (3) returning to the location indicated by the program counter (i.e., returning to the line of code at which the process was interrupted) in order to resume the process.


- Basics -
  • They are a primitive way of protecting a data structure or piece of code, look into “synchronization primitives”.
    • They only allow one process at a time to be within a critical region of code.
    • Aka spin locks
  • They are used in Linux to restrict access to fields in data structures, using a single integer field as a lock.
- In the weeds -
  • Each process wishing to enter the region attempts to change the lock’s initial value from 0 to 1.
  • If its current value is 1, the process tries again, spinning in a tight loop of code.
  • The access to the memory location holding the lock must be atomic, the action of reading its value, checking that it is 0 and then changing it to 1 cannot be interrupted by any other process.
  • When the owning process leaves the critical region of code it decrements the buzz lock, returning its value to 0.
  • Any processes spinning on the lock will now read it as 0, the first one to do this will increment it to 1 and enter the critical region.

How to shoot yourself in the foot

  • Deadlock/Livelock
    • If a thread tries to re-lock a locked mutex, results in deadlock condition. Resolution handed by OS implementation.
    • A possible avoidance strategy to standardize the lock acquisition sequences so that combinations of inter-dependent locks are always acquired in a specifically defined “cascade” order.
    • Livelock is a pitfall to be avoided when building OS deadlock recovery mechanisms. Care must be taken to select only one winner, or deadlock could reoccur.


- Basics -
  • Semaphores are used to protect critical regions of code or data structures.
    • Remember that each access of a critical piece of data such as a VFS inode describing a directory is made by kernel code running on behalf of a process.
  • Locks are a non-performant alternative.
    • Semaphores allow just one process at a time to access critical regions of code and data
    • The waiting processes are suspended, other processes in the system can continue to run as normal.
- In the weeds -

Semaphore data structure:

  • count: This field keeps track of the count of processes wishing to use this resource.
    • A positive value means that the resource is available.
    • A negative or zero value means that processes are waiting for it.
    • An initial value of 1 means that one and only one process at a time can use this resource.
    • When processes want this resource they decrement the count and when they have finished with this resource they increment the count.
  • waking: This is the count of processes waiting for this resource which is also the number of process waiting to be woken up when this resource becomes free,
  • wait queue: When processes are waiting for this resource they are put onto this wait queue,
  • lock: A lock used when accessing the waking field.
  • Summary: Processes use the count value as a “traffic light”, and will increment/decrement as they start and finish their uninterruptible business.


- Basics -
  • In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions.
- In the weeds -
  • Summary: Syncronization of competing threads. When comparing to a mutex, think of semaphore - signaling, mutex - locking. Solves resource sharing problems.


- Basics -
  • In concurrent programming, a monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait (block) for a certain condition to become true.
  • Monitors also have a mechanism for signaling other threads that their condition has been met.
    • The defining characteristic of a monitor is that its methods are executed with mutual exclusion.
- In the weeds -
  • Summary: A monitor is a construct of a mutex and condition variables, that safely coordinates access to a method or variable by 1+ threads.