Processes

Created

Core problem: when the CPU is available, how should the OS kernel decide which process should be run.

Before the notion of a process / OS, batch processing was the norm. The process was the following: 1) reset computer 2) load program from media 3) execute program 4) wait for program to finish and store / print its output. A human operator was needed.

  • drawback: 1) users had to wait hours / days for a job to run. Imagine if there was a bug. 2) lots of CPU idle time.
  • Still good in the case that we want a single programs to have full access to the CPU. E.g., CPU-intensive scientific computations on high-performance computing clusters where we don’t want it to compete with the other processes.

In modern OS we want to run multiple programs at once. I.e., if a process is ready to be executed and a CPU is available, then it should run.

  • if the system has multiple users, the processes can run at the same time. This is called “time sharing”
  • Perfect utilization of system resources is impossible because it requires knowledge of the future.

Multiprogramming (i.e., multitasking): run multiple processes ”at the same time” and exist simultaneously

  • The two priorities the scheduler wants to balance: fairness (equitable access to the CPU) and processes that require some priority (an interactive process is importantly otherwise the system feels laggy to the user).

Throughput: work finished per unit of time

  • Having multiple process available for scheduling allows the OS kernel to avoid leaving the CPU idle during I/O operations.

Latency: time between when a task starts and when it finishes

  • E.g., imagine A takes 8 seconds and B takes 2 seconds. If you run them one at a time, the average latency is 9s but if you switch between them then the average latency is 7s

From kernel POV, a process has the following data:

  • The address space (the memory its using and the content)
    • Pages of memory granted by OS like heap / stack pages, code segment, data, etc.
  • CPU registers (context information)
    • The stack (memory in the address space pointed to by the stack program)
    • Program counter (which instruction will be executed next)
    • Values of CPU registers (if the process is suspended, theses are needed when the OS kernel resumes execution)
  • Resources used (files, terminal, network connection, etc.)

From the process POV:

  • Only sees memory in its own address space
  • Has its own CPU, meaning it doesn’t know or care that the OS kernel is actually switching processes
  • It has its own set of open files
  • Virtual memory: an address within a process that has no meaning to other process. E.g,. address 0xdfba260 in process A is a different physical location than address 0xdfba260 in process B.
  • Each process has its own isolated collection of resources, as though each process has its own virtual computer system. A self contained sandbox.

Processes maintain a unique identifier to name the process. It’s called the process id (PID)

Inter process communication: processes are isolated with each other and by default, their processes are private. So how do we make two processes interact with each other.

  • E.g., write and read from the same file, share memory (memory regions in two processes should map to the same physical memory), communication channel (pipe, network connections, sockets), or signals (one process sends a signal to another like a notification)
  • Some of these mechanisms require synchronization to use correctly but some are sequential.

Process Control Block (PCB) represents each process.

  • Linux is the struct task_struct data type.
    • The struct mm_struct is the data structure *mm that describes the virtual address space (which memory regions exist, what is mapped in each region, etc)
    • struct files_struct is the *files, a table of open file. When the system call provides a file descriptor then it is stored here so that it can access it.
    • volatile long is a state that describes the process state.

Process states:

  • When you run ps or top on Unix/Linux, they have a STAT or S column that indicates the state of each process
    • Running: currently executed (scheduled on a CPU) (R)
    • Ready: Process is ready to run but isn’t currently executing. The OS kernel chooses a Ready process when making its scheduling decision
    • Waiting: the process is suspended while it waits for an event to occur (usually waiting for the completion of an I/O request)
  • Process lifecycle:
    • created
    • When start, it is ready
    • when resume, then it’s Running
      • If it requests I/O then it is waiting.
        • When I/O is done then it returns to ready
      • When suspend, it goes back to ready state
      • When exit, then it’s terminated
  • the kernel needs to find a process in a particular state, so it could either search through a list of all processes (inefficient) or it maintains a list for processes in different states. The process PCBs move from queue to queue when the state changres
    • Ready queue: list of all processes in the Ready state
    • Waiting queue: there is a separate queue per event time (e.g., queue of processes waiting on disk I/O)
      • When the I/O is done then it goes through the disk queue and updates. The order within this queue is not guaranteed to be relevant
    • Running states don’t need a queue because there’s only one process in this state anyways (when there’s one CPU).

Scheduling: which Ready process should the kernel choose?

  • recall the goals: fairness and avoid expensive operations
    • The scheduling algorithm and data structures also needs to be cheap
  • Pintos, by default, uses FIFO
    • Running -> Ready (suspend process): put process at the tail of Ready queue
    • Ready -> Running (resume process): remove process at head of the Ready queue
  • Note: there is always an “idle” process that never waits, this means there is always a process available to schedule (simplifies the scheduler implementation if there is a guarantee). This should only be scheduled if there is not another process int he ready state.

Preemption: every time the OS kernel regains control of the CPU, it can make a scheduling decision

  • interval timer ensures the OS kernel has the opportunity to make scheduling decision at regular intervals.
  • exception (hardware interrupt, fault, system call, etc.) are also opportunities
  • …

Context switch: saves the context of the process being suspended and restores the context of process being resumed.

  • “context” means the values of the CPU registers and switching back to the process’s virtual address space and floating point registers (and other special registers like the condition code register)
  • context is saved in the Process Control Block but it can also be saved on the process’s kernel stack.
  • restore means putting it back on the CPU registers

Todo… vody

Processes from the user (program) perspective

Programs should be able to create a child process.

  • Done with a system call

Every process has a parent

  • On Unix/Linux process ID 1 is the “init” process And is responsible for creating all the other processes.

On Windows, the CreateProcess system call creates a child process. What are the steps?

BOOL CreateProcess(char *prog, char *args, /* various optional arguments *);
  • Creates process control block (PCB) for new process
  • Creates new address space (e.g., setup page table)
  • Arrange for code and data of specified executable to be mapped into the new address space. These area of memory has runtime data and executables.
  • Copy args (CLI) into the new address space
  • Prepare initial context:
    • How do you restore a process that has never been executed? Preparing initial context (the kernel stack) means that it has to make it look like the process was interrupted just before executing the first instruction at the program’s entry point. Now you can “restore” this context even though it didn’t exist.
  • Put the PCB on the ready queue

In Unix/Linux: the fork() system call creates a child process with pid_t fork(void);

  • Creates PCB
  • Create a copy of the parent’s address space
    • exact duplicate so it inherits the parent’s access to file too
    • The difference is what does the fork return. For parent, it returns child’s process ID, and for the child process, fork() returns 0.
  • Duplicates parent process’s open file
  • Copy parent process’s context
  • Put PCB in the ready queue
  • Strange right?
    • More often we want the child process to be different from the parent process, so why is it like this?
    • Once the child process is in the ready queue, it competes for CPU time th estame as any process, so the execution of the child process is not synchronized with the aren’parent process.

Separate API call to run an arbitrary program in the context of the current process. These functions below return only if an error occurs and the new program can’t be executed.

int execv(char *prog, char *argv[]);
int execve(const char *filename, char *const argv[], char *const envp[]);
  1. Create new address space (replacing the current one)
  2. Map code and data of executable program into the new address space
  3. Set up context to begin execution at the new program’s entry point
  4. Place PCB back in the ready queue

fork() can be useful to set up, it inherits everything you need from the parent process, and then if you run exec() after, then it’s already pre setup.

  • e.g., open up a file and then let it

Example of why you would want the child to run the same thing as the parent. Network server:

for (;;) {
	int fd = accept(ssock, NULL, NULL);
	pid_t child = fork();
	if (child == 0) {
		chat_with_client(fd);
		exit(0);
	}
	close(fd);
}

To end a process: you just make sure it never appears in the ready queue again.

To wait for a child to finish: the parent process’s is suspended until the child process exit.

  • there is a wait queue for the parent process.

Linked from Operating Systems