16.1 Purposes of an Operating System (OS)

## Purposes of an Operating System (OS)

- Optimizes the use of computer resources
  - Implements process scheduling to ensure efficient CPU use
  - Manages main memory usage
  - Optimizes I/O
    - Dictates whether I/O passes through CPU or not
##### User Interface
- The user interface hides the complexities of the computer hardware/operating system from the user
- It provides appropriate access systems for users with differing needs
- Complex commands involving memory locations/buses/computer hardware/ are avoided
- Example: 
  - Clicking on icon rather than writing code 
  - Using a graphical user interface / icons for navigation 
##### Multi-tasking
- Running multiple processes concurrently
- which benefits process management by allowing more tasks to complete than would be the case if they had to run one task after another.
##### Process
A program being executed which has an associated Process Control Block (PCB) in memory
- **PCB:** a complex data structure containing all data relevant to the execution of a process
Process states
- **Ready:** 
	- The process is not being executed
	- The process is in the queue waiting for the processor’s attention / time slice
- **Running:** 
	- The process is being executed by the processor
	- The process is currently using its allocated processor time / time slice
- **Blocked:** 
	- The process is waiting for an event so it cannot be executed at the moment
	- e.g. input/output
**running state → ready state Conditions**
- When the time slice of the running process expires (round robin).
- …and there is a process with a higher priority in the ready queue, the running process is pre-empted
- When an interrupt arrives at the CPU, (the process running on the CPU gets pre-empted).  
**ready state → running state Conditions**
a process’s turn to use the processor; the OS scheduler allocates CPU time to the process so that it can be executed
**running state → blocked state Conditions**
the process needs to carry out an I/O operation; the OS scheduler places the process into the BLOCKED queue
**blocked state → ready state Conditions**
the process is waiting for an I/O resource; an I/O operation is ready to be completed by the process
##### Paging
Reading/writing same-size blocks of data from/to secondary storage when required
The operating system divides the memory into pages
Access times for paging is faster than for segmentation.
##### Segmentation
Divides the memory into variable sized blocks
the compiler is responsible for calculating the segment size
##### Interrupt handling
Transferring control to another routine when a service is required
##### Scheduling
Managing the processes running on the CPU
###### the need for scheduling in process management
- Process scheduling allows more than one program/task to appear to be executed at the same time / enables multi-tasking / multiprogramming.
- To allow high priority jobs to be completed first.
- To keep the CPU busy all the time
- … to ensure that all processes execute efficiently
- … and to have reduced wait times for all processes / to ensure all processes have fair access to the CPU / prevent starvation of some processes.   
#### Scheduling routines
##### Shortest job first(SJF)
- Process are executed in ascending order of the amount of CPU time required // Short processes are executed first **and** followed by longer processes.
- …which leads to an increased throughput (because more processes can be executed in a smaller amount of time).
**Shortest remaining time first scheduling (SRTF)**
- The processes are queued as they arrive
- Processes with the shortest burst time are executed first
- It is a pre-emptive scheduling function // When a process with a shorter burst time arrives the existing process is replaced by the shorter process.
- The scheduler will continue to choose shorter processes over longer processes if they continue to be added to the queue can cause starvation for longer jobs
Benefit
- Processes with a short burst time are processed very quickly
- Waiting time is minimised

- is a preemptive version of the Shortest Job Next (SJN) scheduling algorithm.
- the process requiring the least CPU time is executed first
##### Round robin
- Each process is served by the CPU for a fixed time/time slice (so all processes are given the same priority).
- Starvation doesn’t occur (because for each round robin cycle, every process is given a fixed time/time slice to execute).
##### First come first served(FCFS)
- No complex logic, each process request is queued as it is received and executed one by one.
- Starvation doesn’t occur (because every process will eventually get a chance to run) // less processor overhead.
- SJF is non-preemptive
##### Virtual memory
Using secondary storage to simulate additional main memory
- Disk / secondary storage is used to extend the RAM / memory available 
- .. so the CPU appears to be able to access more memory space than the available RAM
- Only the data in use needs to be in main memory so data can be swapped between RAM and virtual memory as necessary
- Virtual memory is created temporarily.
##### Why use virtual memory?
-  Virtual memory is used when RAM is running low
-  …such as when a computer is running many processes at once. 
-  Virtual memory may be used for efficient use of RAM / the processor
-  …such as if data / programs are not immediately needed, they can be moved from RAM to virtual memory  
###### Drawback
When using HDD is that, as main memory fills, more and more data/pages need to be swapped in and out of virtual memory. This leads to a high rate of hard disk read/write head movements; this is known as **disk thrashing**.
##### Explain the circumstances in which disk thrashing could occur.
- Disk thrashing is a problem that may occur when frequent transfers between main memory and secondary memory take place // Disk thrashing is a problem that may occur when virtual memory is being used
- As main memory fills up, more pages need to be swapped in and out of secondary/virtual memory
- This swapping leads to a very high rate of hard disk head movements
- Eventually, more time is spent swapping the pages/data than processing the data.
##### Explain why Reverse Polish Notation (RPN) is used to carry out the evaluation of expressions.
- Reverse Polish Notation provides an unambiguous method of representing an expression
- .. reading from left to right 
- ..without the need to use brackets
- ...with no need for rules of precedence
##### Data structure that could be used to evaluate an expression in RPN.
###### Binary tree
-  A (binary) tree allows both infix and postfix to be evaluated (tree traversal)
###### stack
- The operands are popped from the stack in the reverse order to how they were pushed
##### Describe the main steps in the evaluation of this RPN expression using a stack.
- Working from left to right in the expression
- PUSH data onto the stack
- PUSH the following numbers onto the stack
- When the first operator is reached
- ... POP the top two numbers,and apply the operation
- PUSH result back onto stack
- Continue to the end of the expression
##### State two other uses of a stack.
- recursion
- implementation of ADTs e.g. linked lists procedure calls
- interrupt handling (storing contents of registers etc)
#### Compilation and Interpreter
#### stage of compilation
###### Lexical analysis
converting a sequence of characters into a sequence of tokens
###### Syntax analysis
using parsing algorithms to interpret the meaning of a sequence of tokens
-  It checks that the code matches the grammar of the language // It checks that the tokens conform with the rules of the programming language 
-  Syntax errors are reported
-  A parse tree is produced
###### Code generation
converting an intermediate representation of source code into an executable form
###### Optimisation
minimising a program's execution time and memory requirement
##### How an interpreter executes a program

- The interpreter translates the source code one line at a time
- If the line is syntax error free it is executed
- It is not stored in executable format
- If an error is found, the program halts with an error message
- Each line must be translated every time it is run, including lines running multiple times for example in loops

- An interpreter examines source code one statement at a time
- Check each statement for errors
- ...lf no error is found the statement is executed
- ...If an error is found this is reported and the interpreter halts
- Interpretation is repeated for every iteration in repeated sections of code/in loops
- Interpretation has to be repeated every time the program is run
#### Operating System Term
##### Multi-tasking
Managing the execution of many programs that appear to run at the same time
##### Paging
Reading/writing same-size blocks of data from/to secondary storage when required
The operating system divides the memory into pages
Access times for paging is faster than for segmentation.
##### Segmentation
Divides the memory into variable sized blocks
the compiler is responsible for calculating the segment size
##### Interrupt handling
Transferring control to another routine when a service is required
##### Scheduling
Managing the processes running on the CPU
##### Virtual memory
Using secondary storage to simulate additional main memory
- Disk / secondary storage is used to extend the RAM / memory available 
- .. so the CPU appears to be able to access more memory space than the available RAM
- Only the data in use needs to be in main memory so data can be swapped between RAM and virtual memory as necessary
- Virtual memory is created temporarily.
#### Type of Processor
##### Reduced Instruction Set Computers (RISC)
- Uses simple instructions
- Uses fixed length instructions
- Instructions only require one clock cycle
- Uses many registers
- Makes use of pipelining
- Hardwired CU
##### Complex Instruction Set Computers (CISC)
- Uses many instruction formats
- Uses variable length instructions
- Makes use of different addressing modes
- Uses few registers
- Has a large instruction set
- Requires complex circuits
- Frequently uses cache
- Instructions (converted to sub-instructions that) may require many clock cycles
- Programmable CU
##### three other categories of computer architecture
SIMD (1) many/array processors execute the same instruction using different data sets (1)
MISD (1) many processors (using different instructions) use the same data set (1)
MIND (1) many processors (using different instructions) using different data set (1)

| RISC                                                         | CISC                                           |
| ------------------------------------------------------------ | ---------------------------------------------- |
| RISC has fewer instructions                                  | CISC has more instructions                     |
| RISC has many registers                                      | CISC has few registers                         |
| RISC's instructions are simpler                              | CISC's instructions are more complex           |
| RISC has a few instruction formats                           | CISC has many instruction formats              |
| RISC usually uses single-cycle instructions                  | CISC uses multi-cycle instructions             |
| RISC uses fixed-length instructions                          | CISC uses variable-length instructions         |
| RISC has better pipelineability                              | CISC has poorer pipelineability                |
| RISC requires less complex circuits                          | CISC requires more complex circuits            |
| RISC has fewer addressing modes                              | CISC has more addressing modes                 |
| RISC makes more use of RAM                                   | CISC makes more use of cache/less use of RAM   |
| RISC has a hard-wired control unit                           | CISC has a programmable control unit           |
| RISC only uses load and store instructions to address memory | CISC has many types of instructions to address |

##### the use of pipelining in Reduced Instruction Set Computers (RISC)

- Pipelining allows several instructions to be processed simultaneously /concurrently.
- .. therefore, increasing the CPU instruction throughput / the number of instructions completed per unit of time.
- Each instruction stage / subtask is completed during one clock cycle
- No two instructions can execute their same stage of instruction / subtask at the same clock cycle.
- .. e.g., while one instruction is being decoded, the next instruction can be fetched, etc.

##### virtual machine

- The emulation of a computer system / hardware and/or software
- ...using a host computer system.
- Using guest operating system(s) for emulation.

###### Benifits

- New system can be tried on different virtual hardware
- without need to purchase the hardware

- Easier to recover if software emulating the new computer causes system crash
- as VM provides protection to other software

- Emulate programs for the new computer system that are not compatible with the host computer / operating system
- by using the guest operating system on the old computer

- More than one new computer system can be emulated
- this allows multiple operating systems to coexist on a single computer

- There are security benefits // Trying a piece of suspicious software and if it is / has a virus, it will only infect the virtual machine.

###### limitation

- Virtual machines may not be able to emulate the new hardware
- because this hardware may have been developed since the virtual machine was developed

- Using virtual machine means execution of extra code // A virtual machine might not be as efficient // resources e.g. memory or processor time are shared
- processing time increased // performance degrades

- Use of a virtual machine increases the maintenance overheads
- because both host system and the virtual machine must be maintained

##### characteristics of massively parallel computers

- A large number of computer processors / separate computers connected together
- ... simultaneously performing a set of coordinated computations collaborative processing
- network infrastructure
- communicate using a message interface / by sending messages.

##### the process of pipelining during the fetch-execute cycle in RISC processors

- Instructions are divided into subtasks / 5 stages
-  ... Instruction fetch / IF, Instruction decode / ID, operand fetch / OF, opcode/instruction execute IE, result store / write back result / WB
- Each subtask is completed during one clock cycle
- No two instructions can execute their same stage at the same clock cycle
- The second instruction begins in the second clock cycle, while the first instruction has moved on to its second subtask. 
- The third instruction begins in the third clock cycle while the first and second instructions move on to their second and third subtasks, respectively, etc.