CST 334 – Week 2: Processes and CPU Scheduling

This week we got into the nitty-gritty details of process management and CPU scheduling. The assignments this week mostly dealt with how the OS decides which process the CPU should run. The lecture material and readings fit together nicely, with each lecture corresponding to a chapter in OSTEP.

Topics covered this week

Some of the topics we covered this week were:

• OSTEP Chapter 4: Processes
  • Processes as the main CPU virtualization abstraction
  • Program versus process
    • A program is just some data on a disk, which contains instructions on how to run the program, while a process is a program that is actually running. A process has an execution state and data in memory, and a single program can have multiple processes running at any given time
  • Machine state, including memory, registers, the program counter, and stack pointer
  • Process creation and process states
    • The OS creates a process by reading the program’s code from disk and loading it into memory, allocating memory for the run-time stack and the heap, then allows the program execute by transferring control to the program’s main entrypoint
  • OS process-management data structures, like the task_struct in Linux, which contains information about the execution state of the process
  • Multiprogramming and context switching, which allow multiple processes to appear to run at the same time, keeping the system responsive for users
  • The difference between a mechanism and a policy
    • A mechanism is how the OS performs some task, like context switching
    • A policy describes which processes the mechanism should be applied to
• OSTEP Chapter 5: The C process API
  • The process tree represents processes as parent and child nodes, so that a single parent process can have many child processes.
  • OS process creation with the C Process API
    • The C Process API provides functions to manage processes
      • fork() clones the calling process, creating a new process that continues execution from the same point as the calling process
      • wait() lets a parent pause until a child process finishes
      • exec() replaces the calling process with a new process
• OSTEP Chapter 6: Limited direct execution
  • How does the OS control processes if the process controls the CPU while it is running?
    • Limited Direct Execution allows processes to run directly on hardware, while allowing the OS to maintain control
  • Kernel mode vs. user mode
    • Kernel mode allows all instructions to run, allowing direct access to hardware and memory
    • User mode only allows non-privileged instructions to run, which is how programs normally run
  • Hardware interrupts allow devices to run instructions on the CPU through an interrupt handler
    • If a program needs to run a privileged instruction, it uses a system call, which triggers a trap into the kernel. The kernel handles the request and then returns control back to user mode
• OSTEP Chapter 7: Process Scheduling
  • Scheduling metrics
    • Turnaround time (TAT) measures how long it takes a job to finish after arriving
    • Response time measures how long it takes the system to start running the job after it arrives.
  • Scheduling policies
    • First-In First-Out (FIFO) or First-Come First-Served (FCFS)
      • Processes are run sequentially, in the order that they arrive
    • Shortest Job First (SJF)
      • The processes that will take the least time to complete will run first
    • Shortest Time to Completion First (STCF)
      • Processes that will complete quickly can preempt longer-running processes
    • Round Robin scheduling
      • Each process runs for a short time slice, so that processes appear to be running simultaneously
• OSTEP Chapter 8: Multi-Level Feedback Queue (MLFQ)
  • The OS does not know when jobs will arrive or how long they will take, so it uses a multi-level feedback queue (MLFQ) to dynamically balance the priority of processes, optimizing responsiveness and turnaround time
    • New jobs start at high priority, and the scheduler adjusts their priority based on how they behave
    • Jobs that use a lot of CPU gradually move down, while jobs that frequently give up the CPU, such as interactive programs, can stay higher
  • Problems
    • Starvation: lower-priority jobs will never run if there are always higher-priority jobs
    • Gaming the system: processes may be able to maintain high priority through certain tricks, like requesting I/O before the end of its time slice
  • Solutions
    • Boosting: intermittently move every job to highest-priority, so that it is guaranteed to run eventually
    • CPU allotment: give a process a certain amount of CPU time before moving it to a lower priority

Reflection

The most challenging concept this week was calculating scheduling metrics, like turnaround time. This is especially tricky to calculate when dealing with time-sliced scheduling and different job arrival times, since the jobs will all consume part of the CPU’s time, and there are a lot of different factors to keep track of.

For the lab this week, I made Gantt charts with matplotlib to visualize scheduling metrics, which involved creating a scheduling simulation algorithm in Python. This helped a lot with understanding the decisions that the OS makes when running processes.

It’s been interesting to learn about how a program actually runs, and I now have a better understanding of things I’ve used before but hadn’t thought about much. For example, I hadn’t really thought about what happens when entering a command into a command prompt, but now I have a better idea of how a shell can handle user input with the C Process API.