Maurice's Notes
Blog
Low Level Computing
Low Level Computing
  • Operating Systems
    • General Operating Systems
      • OS Structure
      • Main Memory
        • Basic Hardware
        • Address Binding
        • Memory Address Register
      • Booting
        • MBR (Master Boot Record)
        • Global Descriptor Table
      • Direct Memory Access (DMA)
        • DMA
      • Processes
        • Basics
        • Process Scheduling
    • Linux Operating System
      • Linker Scripts
      • Position Independent Code/Executable
      • Relocation
      • Understanding PLT and GOT
    • Windows Operating System
      • Page 1
    • Real-Time Embedded Systems
      • Real-Time Scheduling
        • Cyclic Executive
  • Computer Architecture
    • Architecture Fundamentals
      • Introduction
      • Cache Basics
      • Cache Memory
      • A Few CPU Formulas
    • RISC Architectures
      • ARM
        • ARM Design Philosophy
        • RISC Review
        • Exceptions, Interrupts, & Vector Table
        • ARM Pipelines
        • ARM Registers
        • ARM Branch Instructions
        • ARM CSPR (Instructions)
        • ARM Data Processing Instructions
        • Load/Store Instructions
        • Profiling Cycle Counter
        • Compiler Optimizations
      • RISCV
    • CISC Architectures
    • Cache Coherency
      • Basic Introduction
      • Memory Sequential Consistency
  • Exploits
    • Walkthrough: Return-to-Libc
    • Access Physical Memory
  • Compilers & Runtime Systems
    • Introduction
      • Programming Language Basics
      • Static Scope
    • Syntax Translation
      • Syntax Defined
      • Parsing
    • Algorithms
      • FIRST FOLLOW (Top-Down) Parsing
      • Building a Recursive Descent Parser
      • Construction: Regular Expression -> NFA
Powered by GitBook
On this page
  • Process Scheduling
  • Scheduling Queues
  • CPU Scheduling

Was this helpful?

  1. Operating Systems
  2. General Operating Systems
  3. Processes

Process Scheduling

PreviousBasicsNextLinux Operating System

Last updated 2 months ago

Was this helpful?

Process Scheduling

the objective of multiprogramming is to have some process running at all times to maximize CPU utilization. Time-sharing operating systems switch between processes at very short intervals (microseconds), creating the illusion of concurrency.

The scheduler selects an available process from a pool of processes in a the READY state. Each core can run a single process (or process thread). Schedulers must consider the behavior of a process as well; I/O-bound processes are those that spend a majority of its time doing I/O, while CPU-bound spend the majority of time doing computations.

Scheduling Queues

Processes that are ready to be scheduled are placed in a ready queue--typically a linked list. The queue header contains a pointer to the first PCB in the list; each PCB in the list contains a pointer to the next PCB.

Additional queues such as a wait queue are used by the system to keep track of processes waiting for I/O interrupt, termination, or resumed execution after preemption.

I/O devices run much slower than the processor, making wait queues essential for optimal performance.

The following Queueing diagram shows the typical flow of a process. Processes in the ready queue are eventually scheduled to use a CPU core; afterwards, they are either complete or placed into one of the wait queues to continue operation.

The first wait queue is an I/O queue, which contains processes that issued an I/O request. Once the I/O device is ready, the process is removed from the queue and placed back into the ready queue.

Another possibility is that the process forks (or, creates) another, child, process. In such cases, the process is stored in a wait queue to wait for the child process to terminate.

Other possibilities include time slice expiration or waiting for an interrupt.

Linux Processes

The following diagrams provide a nice visual for files_struct and mm_struct, respectively.

CPU Scheduling

The CPU scheduler is responsible for scheduling processes in the ready queue to a CPU core. On Time-sharing OS's, the CPU scheduler will limit the amount of time any process has ownership of the core; this is known as time slicing. The CPU scheduler frequently switches between processes on a system (millisecond intervals). CPU-bound processes typically need more CPU time; nevertheless, slicing ensures other processes are able to access CPU and move through their life-cycle.

Swapping, whereby inactive processes (or those selected algorithmically) are removed from memory and thus do not compete for cpu, reduces the number of processes available for cpu scheduling and those in memory.

It may be helpful to view this information in the context of the Linux operating system. The PCB structure in Linux is call task_struct. Unfortunately, it's too large to copy to this page; however, you can easily view the structure online--the struct is defined in (see lines 748 - 1568).

<include/linux/sched.h>