Notes Home

CA644, System Software
Table of Contents

Operating Systems, Part 2

CA644, System Software

Dr. Niall McMahon

2022-10-04

If you print these slides, think about using two pages per sheet although don't worry too much about it!

Credits

Dr. Niall McMahon
Drawing on previous work by:
Dr. Michael Scriney
Dr. Long Cheng
With help from Mark Humphrys. And sources credited in the references.
And sources credited in the references.
Autumn 2022.

Processes

What is a Process?

A process is a running program and all the things it needs to run. There could be many copies of the same program running, i.e. multiple processes.

  • A program is a static thing - a list of written instructions.
  • When a program is launched the operating system sets up the environment in which that program will run i.e. it provides the address space in which the program will execute.
  • Once an address space is set up program execution can begin.
  • You can think of the process address space as a box in memory to which the process is confined during its lifetime.
  • A process is the combination of the address space and the activity (or thread) of execution.

Process Address Space

Isolating each process in its address space - a region in primary memory - is useful because:

  1. One process cannot access the memory used by another process.
  2. If a process goes haywire it can only crash itself.
  3. From the process' point of view, it has complete control of the (virtual) machine.

Process in Memory

A process inhabits a space in memory with these components:

	    	Stack
	        -----
	    	Heap
	    	-----
	    	Data
	    	-----
	    	Text
	    	-----
	    

Components of a Process in Memory

A process inhabits a space in memory with these components:

  • Text contains the code.
  • Data is global static data to be used by the process.
  • The heap supports dynamic memory requirements, i.e. variables assigned values on the fly during execution.
  • The stack is used by the process to store return addresses, temporarily saved registers, local variables and similar things.

Programs in Action

We can think of a process as a "program in action" or a "sequence of states":

  • Processes are dynamic things. A program is a set of instructions for assembling a desk; a process a program during execution
  • A state is a snapshot of a process at a particular processor timestep, i.e. if the processor frequency is 3.6 GHz, the processor timestep is 1/3.6 billionth of a second.
  • The state means all data related to that process, e.g. values in registers, data in memory, process priority, remaining number of timesteps available to the process at that moment.
  • As the program instructions are executed, the state changes. At the very least the instruction pointer number increases by one.

Process States

  • States can be saved and restored.
  • An operating system is typically dealing with hundreds of processes (practically) simultaneously.
  • The Process Control Block (PCB) is the data structure used to keep track of process states.
  • The OS uses the PCB to keep track of a process, including memory requirements, open files and priority level.
  • The OS keeps all the PCBs together on a linked list in kernel memory.

Creating a Process

  • The syscall that creates a new process is called fork.
  • fork makes an exact copy of the calling process.
  • After the call there are two identical processes, parent and child. Both are executing the same program at the same point.

Exec

  • Once the process is forked, a system call to exec from the child process writes a new progam into its address space.
  • fork creates the address space and exec loads in a new program.

Multitasking

What is Multitasking?

  • CPUs execute programs in the text section of process address spaces.
  • Exactly in the same way as the clerk in the Feynman story.
  • Only one process can be executing at any instant.
  • Multitasking means using the CPU to run multiple processes at the same time, from the user's perspective. In reality, only one process is running on the processor at a time.
  • When the CPU is switching from one process (A) to another (B), the state of A is written to its PCB and the state of B is read from its PCB and the values of registers and memory are reset from where B last left off.
  • Figuring out which process should go next is called scheduling and it's a primary function of the OS.

Releasing the CPU

When has a process had enough time on the CPU? Well:

  1. If its program has been running on the CPU for too long.
  2. If a higher priority process is in line for the CPU.
  3. If it is waiting for something, e.g. data to be read.
  4. If it terminates.

Cooperative vs Preemptive Multitasking

  • Cooperative: the process program indicates that it will release the CPU.
  • Preemptive: the OS takes back control of the CPU from the process.

The Illusion of Simultaneous Execution

  • With multitasking, programs seem to be running at the same time.
  • For a machine with one processor, i.e. a uniprocessor, this is only an illusion.
  • Each process has the CPU for some small amount of time, perhaps millions of processor timesteps, before another one takes over.
  • From the user's perspective, the execution appears to be simultaneous.

Multitasking Example

  • Process A and Process B are running on a machine.
  • A has the CPU. However, A is blocked! It's waiting for data from a read.
  • A notes its state as non-runnable.
  • It removes itself from the CPU.
  • B is loaded in from its PCB and starts executing its program from where it left off.
  • Meanwhile, that data that A was waiting for arrives and is written to its address space. This action creates an interrupt and A's state is updated as runnable.
  • Whenever A next gets time on the CPU, the data will be available to it.
  • So, by getting A out of the way while it was waiting on data, B got some run time and the processor was utilised more efficiently.

Context Switching

  • Context switching is the simulation of parallel processing by switching the processor between processes.

Process Life Cycle States

A process can be in one of five life-cycle states.

  • New: the process is being created but not yet runnable/ready.
  • Runnable / Ready: the process has all it needs to run, waiting for time on the CPU.
  • Running: the CPU is running the process program right now.
  • Waiting / blocked: the program is waiting for some resource, e.g. on data, for a time period to elapse, for a child process to return.
  • Exit: the process has finished.

Other state models exist.

Summary

  • Multitasking allows the user to experience simultaneous program execution.

There are some problems, however:

  • Sharing information between processes is difficult because of how address spaces are implemented.
  • Context switching between processes is a relatively big operation - saving and loading states - using a lot of CPU cycles.

Multithreading

What is a Thread? An Analogy

  • If we imagine a company occupying an office block in a strange kind of world. In this (slightly overdone) analogy, the company might represent the computer system and operating system.
  • Each office has one employee and a whiteboard. The employee does calculations and writes their workings and answers on the board. The office is a like a process address space, the employee the program and the white board is the memory available to the process.
  • The company owns only one calculator and it's shared between the offices. When an employee needs it, they push a button that turns on a light in the manager's room. The manager then walks down to transfer the calculator from one place to another. The manager decides who has a go next. This is like context switching a CPU.
  • Sometimes it happens that one employee needs help. But sharing information between offices requires the manager. It's a bit cumbersome (to say the least). So, the manager assigns a second employee to the office.
  • This allows the office to get more done. While one employee is writing to the board that they both have easy access to, the other can be calculating. The two employees are to the office what threads are to a process.

The two employees need to be careful, however:

  • It'd be easy for one of the employees to accidentally erase the work of the other.
  • A lack of proper coordination could produce a bad solution to the problem.
  • A lack of any coordination could produce no solution at all.

(I'm not sure about this office analogy - it was inherited! - but I'll leave it in place for now.)

What is a Thread?

A thread:

  • Is a sub-process that can be scheduled with time on the CPU.
  • Gives lightweight multitasking within a process, without a full context change between processes.

Thread Control Block

  • Process control blocks (PCBs) represent processes and thread control blocks (TCBs) keep track of threads.
  • TCBs are smaller than PCBs.
  • Switching between threads is faster than switching between processes.
  • TCBs keep track of things specific to each thread, e.g. CPU register values - the instruction pointer, stack pointer.
  • PCBs keep track of things common across threads, e.g. the process address space.

Multithread Process Address Space

		    Stack (Thread A)
		    Stack (Thread B)
		    ----------------
		    Heap (Shared)
		    ----------------
		    Data (Shared)
		    ----------------
		    Text (Shared)
		

Advantages of Threads

  • Fast thread context switches.
  • Threads require complex programs to be broken into simpler ones; this is good programming practice.
  • While one thread is blocked, another can execute.
  • Threaded programs can execute fully parallel on multiprocessors.
  • Sharing information is fast, thanks to a shared address space.

Function Call vs. Thread Creation

Creating a new thread is not the same as calling a function.

	     Main Function                  Main Function
	          ||                             ||
	          \/                             \/
	           ========>                      ========>
	                   Function              ||       ||
	           <========                     \/       \/     
	          ||
	          \/

	     FUNCTION CALL                   THREAD CREATION
		

Concurrency

Multitasking and Multithreading

There are two sources of concurrency on a computer:

  1. Multitasking: processes may be context switched, simulating parallel program execution.
  2. Multithreading: threads within a process may be switched.

Predicting when a context switch between threads in a process will occur is impractical; they can occur in any order, with instructions interleaved differently each time the program is run.

This means that multithreaded programs must function correctly under all possible orderings.

Concurrency Challenges

Take the following pseudo-code:

/* Thread A */
x = 1;
x = y + 1;

/* Thread B */
y = 2;
y = y * 2;

Since A and B may execute with their instructions interleaving at different points each time the program is run, there is no way to guarantee a single value for x with this program as it is.

  • Correct programs will produce the same result for all runs, across every possible scheduling ordering.
  • Bugs that happen only on particular runs, due to a particular scheduling ordering, are called race conditions.
  • Race condition bugs are hard to detect.

Mutual Exclusion

  • Each thread will have some section of code that affects the data used by the other threads.
  • If multiple threads are executing instructions from this critical section at (more or less) the same time, this could cause problems with the data in memory.
  • Preventing this from happening is call enforcing mutual exclusion.
  • This is a service that the OS can provide.

More about Input and Output (I/O)

Device Drivers

  • Hardware interfaces are often not user-friendly, with different interfaces used by different devices and device manufacturers.
  • The OS tries to provide a standard device interface to programmers; this is achieved using device drivers.
  • Device drivers are codes that act as a translator between the OS and the hardware.
  • Device drivers, supplied by the hardware manufacturer or written by others, are inserted into the kernel as required.
  • Device drivers run in kernel mode.
  • Devices drivers help protect devices by limiting access; programmers must use trusted syscalls.

A Standard Interface

  • Files: the OS can open, read from, write to and close files.
  • Microphones: the OS can open, read from and close microphone audio devices.
  • Speakers: the OS can open, write to and close speaker audio devices.
  • Printers: the OS can open, write to and close printer devices.

The OS can use device drivers, and the filesystem, to implement a standard set of interface syscalls for devices and files.

Device Interface

With this standard interface:

  • All devices "speak" the same language.
  • There is a consistent interface.
  • The same syscalls are used for all devices.

Device Independence

  • Coding for a device becomes independent of the device; this is device independence.
  • The open syscall will establish a connection with all devices.
  • The specific version of open for a device is defined in the device's driver.
  • The OS loads the relevant driver code when open is used.

ioctl

  • For operations not covered by read, write, open or close, a generic syscall, ioctl, is used.
  • A device driver can define an operation that requires ioctl with additional arguments.
  • For example, to set the sample rate on an audio device you might call ioctl but pass it the value for a variable named AUDIO_SETINFO as an argument.

Devices as Files

  • Devices, in Unix-like systems, look the same as files to the user.
  • Attached devices will be mounted like files at /dev and /media.
  • /dev/dsp is the machine's audio device; to play music, an app uses open, write, close /dev/dsp.
  • Priviliges can be set for devices in the same way as files.

I/O Subsystem

  • The I/O subsystem treats devices as files; it has no "knowledge" of the underlying driver code.
		               Users
		                 |
		         System call interface 
		                 |
		           I/O subsystem
		                 |
		        Device driver interface
		        |        |            |
		Disk driver  Audio driver   Printer driver
		    |            |            |
		    Disk      Audio device   Printer
		

Blocking I/O

  • Imagine an interprocess communication (IPC) channel open between two processes, A and B.
  • Process A is waiting for a 100 byte message to arrive from process B.
  • A makes a read syscall requesting 100 bytes.
  • With default blocking I/O, A blocks until the entire 100 bytes arrives.
  • Multithreading allows practical use of blocking I/O, with only one thread blocked waiting on data.

Non-blocking I/O

  • With non-blocking I/O, A does not block; it takes however many bytes are available, returning them immediately.
  • With non-blocking I/O, process A polls process B at regular intervals for additional data until the entire 100 bytes has been retrieved.
  • Non-blocking I/O is more complicated.

Asynchronous I/O

  • Asynchronous I/O uses a signal to alert process A when the 100 bytes has been transferred into its address space.
  • The signal interrupts the process.
  • Asynchronous I/O is more complicated than simple blocking I/O.

Multiplexing I/O

  • Data can arrive via many channels: the keyboard, a set of network connections, etc.
  • With blocking I/O, a read issued on any one channel may block indefinitely.
  • While blocked inside a read, the application cannot "see" data arriving on other channels.
  • select can be used together with a parameter; this parameter is a data structure representing all the data channels.
  • select blocks until data is available on one of the channels. When data is available, is is retrieved.

References

  • Structured Computer Organization by Andrew Tanenbaum. Tanenbaum has several other books about operating systems; his book, Operating Systems: Design and Implementation, was sold with Minix, his Unix-like system developed for learning. Linus Torvalds first mentioned Linux publicly as a Minix-related project on comp.os.minix.