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!
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.
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.
Isolating each process in its address space - a region in primary memory - is useful because:
-
One process cannot access the memory used by another process.
-
If a process goes haywire it can only crash itself.
-
From the process' point of view, it has complete control of the (virtual) machine.
A process inhabits a space in memory with these components:
Stack
-----
Heap
-----
Data
-----
Text
-----
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.
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.
-
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.
-
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.
-
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.
-
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.
When has a process had enough time on the CPU? Well:
-
If its program has been running on the CPU for too long.
-
If a higher priority process is in line for the CPU.
-
If it is waiting for something, e.g. data to be read.
-
If it terminates.
-
Cooperative: the process program indicates that it will release the CPU.
-
Preemptive: the OS takes back control of the CPU from the process.
-
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.
-
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 is the simulation of parallel processing by switching the processor between processes.
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.
-
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.
-
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.)
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.
-
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.
Stack (Thread A)
Stack (Thread B)
----------------
Heap (Shared)
----------------
Data (Shared)
----------------
Text (Shared)
-
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.
Creating a new thread is not the same as calling a function.
Main Function Main Function
|| ||
\/ \/
========> ========>
Function || ||
<======== \/ \/
||
\/
FUNCTION CALL THREAD CREATION
There are two sources of concurrency on a computer:
-
Multitasking: processes may be context switched, simulating parallel program execution.
-
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.
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.
-
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.
-
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.
-
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.
With this standard interface:
-
All devices "speak" the same language.
-
There is a consistent interface.
-
The same syscalls are used for all devices.
-
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.
-
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, 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.
-
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
-
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.
-
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 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.
-
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.
-
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.