System Software

⚙️ 20.03 Process scheduling

Managing the CPU mostly means scheduling it so that it is used efficiently. Here the CPU is treated as a single unit; multiprocessor issues are left out.

Programs start out on disk. A user can submit a program as a job: the program plus instructions on how it should run.

• A long-term or high-level scheduler chooses which program on disk is moved into main memory.
• If memory gets overcrowded, a medium-term scheduler may move a program back out to disk.
• Once a program is in memory, a short-term or low-level scheduler decides when it gets the CPU.

🔄 Process states Figure 20.05

Chapter 8 defined a process as "a program being executed". A better definition includes its state from the moment it arrives in memory. At that point a process control block (PCB) is created, ready to hold the data the process needs while it runs. After that, the process moves between states:

• A new process arrives in memory and a PCB is created → ready.
• The dispatcher gives a ready process the CPU → running.
• A running process is halted by an interrupt → back to ready.
• A running process cannot continue until some event happens (I/O, perhaps) → waiting (also called suspended or blocked).
• A waiting process is told its event has completed → ready.
• A running process finishes → terminated.

A process can be split into parts that run separately, called threads. Each thread is then handled as an individual process.

⚡ Interrupts

Some interrupts are caused by errors that end a running process early. Otherwise there are two reasons for an interrupt:

• A process alternates between bursts of CPU use and I/O. I/O takes far too long for the CPU to wait idle, so when a running process makes a system call that needs I/O, an interrupt moves it to the waiting state.
• The scheduler decides to halt the process, for one of the reasons in the scheduling algorithms below.

Whatever the reason, the kernel runs an interrupt-handling routine. It may have to decide the interrupt's priority. One thing it must do is save the current register values into the process's PCB, so the process can carry on exactly where it stopped when it next runs.

📋 Scheduling algorithms

The high-level scheduler also makes decisions, but here we look at the options for the low-level scheduler.

Possible criteria for priority

• estimated time the process will take to run
• Estimated time remaining
• how long it has already spent in the ready queue
• whether it is I/O bound or CPU bound

More than one criterion may be used, and estimating run time is not easy. Take a process that prints employees' wage slips: it needs a lot of I/O and very little CPU. It makes sense to give it a high priority so its short CPU bursts happen quickly; it then spends most of its time waiting while the printer works, out of everyone's way.

🧠 20.04 Memory management

Memory management covers several jobs:

• providing protected memory for the OS kernel
• loading a program: deciding the memory addresses for the program, its procedures and its data
• in a multiprogramming system, coping with fragmentation of main memory (just like files on a hard disk); the medium-term scheduler may move a process out to ease the problem
• deciding how much memory each process sharing memory should get

Partitions and segments

An early approach was to partition memory and load the whole of a process into one partition. That wasted memory whenever the process was smaller than its partition. Dynamic partitioning let the partition size match the process, but the rule stayed "one process per partition".

Segmentation extended this to larger processes: the process was split into segments, and each segment was loaded into a dynamic partition. Two things limited it:

• segments did not have to be the same size;
• there was not always room for all of one process's segments at once, so segments were shuffled between disk and memory.

Together these caused fragmentation of both memory and disk, and the system slowed down.

📄 Paging and virtual memory

The modern approach is paging. The process is divided into equal-sized pages, and memory is divided into frames of the same size. Secondary storage can be divided into frames too.

All the pages could be loaded at once, but usually not every part of a program is needed at the same time; large programs have optional routes. A special case is a program whose address space is bigger than the memory itself. Paging then supports virtual memory.

The CPU passes addresses to a memory management unit (MMU), which finds the matching place in a page frame. An address has two parts: the page number and the offset from the start of the page. The MMU uses a page table.

• Left: a program of 48 instructions occupies three pages, the first 48 logical addresses. With 8-bit logical addresses, the top 4 bits are the page number (so only 16 pages) and the bottom 4 bits are the offset.
• Right: page frames with physical addresses. The first two program pages have been loaded; the frames used do not have to be next to each other.
• Centre: this process's page table (every process has its own). The page number is the index; the presence flag says whether the page is in memory; the third column is the frame number (it could instead hold the physical address of the frame's first item).

Page faults and replacement

A process starts with all its pages on disk. One or more are loaded as it moves to the ready state. While it runs it will, sooner or later, need a page the page table says is not in memory: a page fault. Usually a page must be taken out of memory first to make room, chosen by a page replacement algorithm. The simple choice is first-in first-out; a more sensible one is least recently used (LRU), but that needs statistics of page use to be kept.

The overhead of virtual memory can hurt. The worst case is disk thrashing: code on one page needs another page that is on disk; once that is loaded, it almost immediately needs the first page again… pages are loaded and unloaded almost endlessly. Algorithms exist to guard against this, but it can still happen.

🧑‍💻 20.05 Operating system facilities provided for the user

• User interface: a command line, a graphical display or voice recognition. Whatever the form, it lets the user interact with running programs.
• Device drivers: when a program uses a device, the OS provides the driver; the user just expects the device to work. (You might argue that printers don't always live up to this!)
• File system: the user chooses file names and a directory (folder) structure, but never has to organise the physical storage on the disk.
• Programming environment: a program can be written and run without the programmer knowing how the processor works.
• System calls: a running program is a kind of user too. If it needs to read a file, the request becomes a system call: the OS takes charge, finds the file and makes it available.
• Application programming interface (API): a set of calls, each doing a specific job such as creating a screen icon, each using one or more system calls. An API aims to make programs portable, so they run on different operating systems with minimal changes.

🛠️ 20.06 Translation software

Chapter 8 (Section 8.05) gave an overview of compilers and interpreters. Here we look inside a compiler, with a brief note on interpreters. Writing one is a specialist job and every team has its own methods, so these are general principles.

A compiler has a front end and a back end. The front end analyses the source code and, unless it finds errors, produces intermediate code that fully expresses the meaning (semantics) of the source. The back end takes that intermediate code and synthesises object code: the analysis–synthesis model.

Figure 20.07 assumes no errors. The source is read line by line and each line becomes matching intermediate code. An interpreter has the same analysis front end, but once a line is error-free and converted to intermediate code, it is executed straight away, so no translated version of the whole program is ever produced.

Front-end analysis stages

1. Lexical analysis
2. Syntax analysis
3. Semantic analysis
4. Intermediate code generation

1. Lexical analysis

The source code is just a sequence of characters. Each meaningful character or group of characters is a lexeme: an identifier chosen by the programmer, or a keyword, operator or symbol defined by the language. One approach is to remove all white space and comments, then take each line and identify every lexeme, a pattern-matching job that needs knowledge of the language.

Var Count : integer;

has five lexemes: Var Count : integer ;. And

PercentMark[Count] := Score * 10

has eight: PercentMark [ Count ] := Score * 10.

Each lexeme is then categorised so the line can be tokenised: Var and integer are keywords, Count is an identifier, and : and ; are distinct lexemes.

Every identifier gets an entry in the symbol table (it could have been called the identifier table). It holds attributes such as the data type, where it is declared and where it is assigned a value. Figure 20.08 shows it feeding syntax analysis, but later stages use it too, and most compilers are multi-pass, so the table is updated often.

Another table supplies the token for each lexeme that is not an identifier; sometimes identifiers are replaced by tokens too. Whatever the scheme, the output of lexical analysis is a tokenised version of the source code.

2. Syntax analysis (parsing)

Parsing analyses the program's constructs. The result is a syntax tree or parse tree. For

y := 2 * x + 4

Read correctly, the shape of the tree makes sure that 2 * x is worked out before 4 is added.

3. Semantic analysis

Semantic analysis establishes the full meaning of the code. It builds an annotated abstract syntax tree: each identifier in the tree gets attributes, such as its data type, which are also recorded in the symbol table.

4. Intermediate code generation

A common intermediate code is three-address code. This statement uses five identifiers, so it needs five addresses:

y := a + (b * c - d) / e

It can be rewritten as four statements, each using at most three addresses:

temp := b * c
temp := temp - d
temp := temp / e
y := a + temp

📐 Representation of the grammar of a language

Every programming language has a defined grammar, which both the programmer and the compiler writer must understand.

A syntax diagram is one way to present a grammar rule. Figure 20.10 says an identifier must start with a letter, followed by any combination of none or more letters or digits. The convention here: options are drawn above the main flow line and repetitions below it.

The alternative is Backus–Naur Form (BNF). A possible BNF definition of an identifier:

<Identifier> ::= <Letter>|<Identifier><Letter>|<Identifier><Digit>
<Digit> ::= 0|1|2|3|4|5|6|7|8|9
<Letter> ::= <UpperCaseLetter>|<LowerCaseLetter>
<UpperCaseLetter> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<LowerCaseLetter> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

• | separates the options; ::= reads "is defined as".
• The definition of <Identifier> is recursive: it uses itself. Without recursion it would have to list every possible combination after the first letter.

⚙️ Back-end synthesis stages

If the front end found syntax errors, the only back-end job is to list them, each with an explanation and its location in the source.

With no errors, the main back-end stage is machine code generation from the intermediate code. This may include optimisation, which aims to make the program efficient. One kind tidies up inefficiencies that were in the source and were carried into the intermediate code:

x := (a + b) * (a - b)
y := (a + 2 * b) * (a - b)

temp := (a - b)
x := (a + b) * temp
y := x + temp * b

Another example: a statement inside a loop that does the same thing every time round. Optimisation moves it to just before the loop.

The other kind of optimisation happens after the machine code has been created, e.g. making efficient use of registers or memory.

🔁 Evaluation of expressions

An assignment statement often has an algebraic expression. It can be evaluated by first converting its infix form into Reverse Polish Notation (RPN). RPN is a postfix notation: it never needs brackets and has no rules of precedence.

a + b c *

a b c * +

(x * 2) y 3 * + 6 /
(x * 2) (y * 3) + 6 /
(x * 2) + (y * 3) 6 /
((x * 2) + (y * 3)) / 6

Worked Example 20.02

Using a syntax tree to convert an expression to RPN

In syntax analysis, a + b * c becomes a syntax tree. The lowest-precedence operator (+) goes at the root; if several share the same precedence, the first one is used.

The RPN is read off by a post-order traversal: start at the lowest leaf left of the root and visit left – right – root each time, giving a b c * +.

Worked Example 20.03

Using a stack with an RPN expression

To convert infix to RPN with a stack, use the shunting-yard algorithm. Picture the tokens as railway wagons shunted from the infix line to the RPN line, with a siding (the stack) in between. Examine each token in turn:

• An identifier goes straight through to the RPN line.
• An operator:
  • if the stack is empty or its top operator has lower precedence, the operator goes onto the stack;
  • if the top has equal or higher precedence, that operator is popped to the RPN line and the new one takes its place on the stack.
• When the infix line is empty, the operators left on the stack are popped one by one onto the RPN line.

Infix line	Stack line	RPN line
a + b * c
+ b * c		a
b * c	+	a
* c	+	a b
c	+ *	a b
	+ *	a b c
	+	a b c *
		a b c * +

Table 20.02 Trace of the conversion process

Here + enters the stack first; * has higher precedence, so it joins it. At the end * is popped, then +. Had the expression been a * b + c, * would have entered first but been popped before + could enter.

Book wording fixed: the book says "equal or higher preference"; it means precedence. Also, the full algorithm keeps popping while the top of the stack has equal or higher precedence (try a * b - c + d below), and it handles brackets by stacking ( and popping back to it at ). The lab does both.

🥞 Evaluating an RPN expression

A stack can evaluate RPN. Take x 2 * y 3 * + 6 / with x = 3 and y = 4. Values are pushed in turn. When the next item is an operator, the top two items are popped, the operator combines them, and the result is pushed. Then carry on.

The figure shows the stack after each step, with the operator above when one is used. (States with two values popped are not shown.) The answer is 3.

RPN would be of little use on the simple processor of Chapter 6. Modern processors have stack instructions, so a compiler can convert expressions to RPN knowing the machine code can use the stack directly.

📌 Summary

• The operating system provides resource management, including scheduling of processes, memory management and control of the I/O system.
• For the user, the OS provides an interface, a file system and application programming interfaces.
• A modular approach gives a flexible structure for the OS.
• A process has five states: new, ready, running, waiting and terminated.
• A process may be interrupted by an error, a need for I/O, or the scheduling algorithm.
• A virtual memory system uses paging and a memory management unit that uses a page table.
• A compiler has a front end that analyses and a back end that synthesises.
• Backus–Naur Form represents the rules of a grammar.
• Reverse Polish Notation is used to evaluate expressions.

🃏 Key-term flashcards

Tap a card to flip it.

✅ Quick quiz

📝 Exam-style questions

Write your answer first, then open the model answer. These are my mark-scheme-style points, not official mark schemes.

<Digit> ::= 0|1|2|3|4|5|6|7|8|9
<Sign> ::= +|-
<Unsigned integer> ::= <Digit>|<Unsigned integer><Digit>
<Signed integer> ::= <Sign><Unsigned integer>

4 a Using the syntax diagrams, give the reason each assignment statement is invalid: (i) a = b + c (ii) a = b - 2; (iii) a = dd * cce;[3]›

• (i) There is no semicolon at the end.
• (ii) 2 is not a variable: a variable can only be made of letters.
• (iii) cce contains e, which is not one of the allowed letters a–d.

<assignmentstatement> ::= <variable> = <variable> <operator> <variable> ;
<variable> ::= <letter>|<letter><letter>|<letter><letter><letter>
<letter> ::= a|b|c|d
<operator> ::= +|-|*|÷