16 - system software + virtual machines Flashcards
interpreter
- executes the program line by line - outputs error messages as it encounters them
- used evert time a program is executed
- constructs a symbol table - allocates space in memory for constants, variables and data
compiler
- the source code is input and either object code or error messages are output at the end
- source code can be run without translation again/ distrubuted
- constructs a symbol table
stages of compilation
- lexical analysis
- syntax analysis
- code generation
- optimisation
translators
compiler
interpreter
assembler
lexical analysis
first stage in compilation
- all unnecessary characters eg white space/ comments are removed
- program is converted into tokens - tokenisation
- variables and constants are also added to a symbol table
keyword table
- all the reserved words and symbols that can be used in the programming language are stored - with their corresponding token eg 2 hex numbers
tokenisation
in lexical analysis to convert the program into tokens
- a key word table is used that contains all tokens for words/ symbols in a programing lang
syntax analysis
- the output from lexical analysis is checked for syntax errors
- the tokenised list is checked for errors using syntax rules for the programming lang (parsing)
- if errors found each statement and the errors are output but in the next stage code generation wont be attempted
- if error free its passes to the next stage to generate object code
parsing
checking the tokenised list for errors using grammatical rules for the programming lang
lexeme
each meaningful character or collection of characters
may be used as an identifier or may be a key word
- in lexical analysis the whitespace and comments are removed and each lexeme is identified before categorising each lexeme to tokenise it
code generation
produces object code to perform the task defined by the source code
- must be syntactically correct to produce obj code
- in machine code (binary)
- either in executable machine code or an intermediate form (converted to MC when program is loaded)
benefits of intermediate code (code generation)
supports
- use of relocatable code so program can be stored anywhere in main memory
- addition of library routines to minimise storage size
- linking of programs to run together
optimisation
- improves efficiency
- performs task with minimum resources used
eg time, storage space, memory and CPU use - can take place after syntax analysis or as part of code regeneration
bootstrap
- loads part of the OS into RAM from the hard disk
- initiates start up procedures
when comp is switched on
BIOS starts off bootstrap
flash memory
used as main memory on phones - explains why their start up is so fast
2 parts
- OS - read only - can be updated by manufacturers but user cant access
- apps (+ data) - user cant access
resource management
split into 3 areas: CPU, memory, I/O system
- involves scheduling to allow for better utilisation of time and resources
- for I/O operations deals with: I/O operations that have been initiated, I/O operations that occur wile software is run and resources are requested
direct memory access controller (DMA)
- allows hardware to access main memory independently of CPU
- frees up the CPU to allow it to do other tasks while slower I/O operations take place
- initiates data transfers - CPU does other tasks at same time
- once data transfer is done an interrupt is sent to the CPU from the DMA
kernel
- central component of OS
- responsible for communication between hardware, software and memory
- responsible for process
management, device management, memory management, interrupt handling and input/output file
communications
how the OS hides the complexity of hardware from users
- using GUI interfaces
- using device drivers (simplifies the complexity of hardware interfaces)
- simplifying saving/ retrieving data from memory and storage
- carrying out background utilities eg virus scanning
syntax diagrams
- anything with alternatives eg variable, letter, digit, operators goes in a square
- items with no alternatives eg a specfic symbol or letter goes in a circle
- have arrows showing the order of things
- if in parallel you can have either of those options - iteration eg multiple letters is shown with an arrow looping
Backus Naur form (BNF)
- set of symbols used to describe the grammar rules in a programming language
BNF notation symbols
<> encloses an item
::= separates an item from its definition ‘is defined as’
; end of a rule
eg <variable> ::= <letter> | <digit>;</digit></letter></variable>
<letter> ::= A | B | C;
<digit> ::= 1 | 2 | 3;
a vairbale consisting of any number of letters or digits could be defined as
<variable> ::= <Letter>|<variable><Letter>|<variable><Digit>
| between items indicates a choice
</Digit></variable></Letter></variable></Letter></variable></digit></letter>
Reverse Polish notation (RPN)
- used to represent an arithmetic or logical expression - without brackets or special punctuation
- uses postfix notation - operator is after the variables it acts on eg A+ B > A B +
- compilers use bc any expression is processed left to right without backtracking - converted using a binary tree
how to evaluate to RPN
eg a+ b *c
whichever has the higher precidence in this case * is done first
so put bc *
then after put a on the far left and. + on the righ to give
abc * +
the comp will automatically do the 2 things next to the operator first then result, next one and the next operator
evaluating RPN using a stack
- values are added to the stack in turn from left to right
- when you get to an operator it is used to operate on the top two values which are popped off
- the result is then pushed back on
- this is repeated until there is one value on the stack - the answer to the expression
converting back from RPN
whenever you have two variables and a sign after them pit the sign in the middle and rewrite the expression
eg ba * cda ++-
(ba)c(d+a)+-
(ba)(c+d+a)-
(b*a) - (c+d+a)
prcoess managemtn
- multitasking
- low level scheduling
- process scheduler
multitasking
- comps can carry out more than one task
- scheduling is used to decide which is carried out at each time
- monitors state of each process
- gives appearance that prcoess are carried out a same time
- kernel overlaps the execution of each process using scheduling
- 2 types - preemtive, non preemtive
preemptive
processes pre-empted after each quantum
- resources allocated for a limited time
- can be interrupted
- high priority processes arriving frequently means there is a risk low priorit processes are starved
- more flexible
non preemptive
- once the resources are allocated they are retained until it has completed its burst time or has switched to waiting
- cant be interrupted - must finish or switch to waiting
- if process with long burst time is running there is a risk another process with short time is starved of resources
- more rigid
low level scheduling
- decides which process should get next use of CPU
- maximises system to and ensure a stable system
process priority depends on
- category (batch, online, real time)
- if its CPU bound or I/O bound (needs more CPU or I/O devices)
- resource requirements
- turnaround, waiting and response time
- whether the process can be interrupted during running
once a priority is given a task is still affected by
- deadline for the completion of process
- how much CPU time is needed to run
- wait time and CPU time
- memory requirements
process control blcok
- data structure containing all data needed for a process to run
- created in memory when data needs to be received during execution
process control block stores
- current process state
- process privileges (which resources it can access)
- register values
- process priority and scheduling info
- amount of CPU time needed to complete
- unique process ID
process state
- running
- ready
- blocked
running > ready
- program executed during time slice
- when slice is done interrupt occurs and is moved to ready
ready > running
- once process is first in ready queue
- OS scheduler allocates CPU time to process so it can be executed
running > blocked
- process needs to carry out an I/O operation
- the OS scheduler puts process in blocked
blocked > ready
process is waiting for I/O resource
an I/O operation is ready to be completed by the process
scheduling routine algorithms
- first come first served scheduling (FCFS)
- shortest job first scheduling (SJF)
- shortest remaining time first scheduling (SRTF)
- round robin
ensure system is running efficiently and stable
have to manage ready queue to minimise waiting time
first come first served
data added to queue first is data that leaves first
+ no risk of starvation
shortest job first
non preemptive
burs time shoudl be known in advance
job qith the shortest burst time is completed first
shortest remaining time first
preemptive
processes placed in the queue as the arrive
if a process with a shorter burst time arrives the xisting process is remover (preempted) from execution
round robin
a fixed time slice is given to each process (quantum)
once a process is executed for its time slice its removed and placed in the blocked and the next process in the ready queue is executed in its slice
Context switching is used to save the state of the pre-empted processes
interrupt handling
the CPU checks for interrupt signals
the system will enter the kernel mode if any of these interrupts are sent:
- device interrupt eg printer out of paper
- exceptions eg /0
- traps/software interrupt eg process requesting a resource
interrupt dispatch table
when an interrupt is received the kernel consults the IDT
- this links a device description with the appropriate interrupt routine
- supplies the address of low level routine to handle the interrupt
- kernel saves the state of the interrupt process on the stack
- the state is restored once the interrupt is serviced
interrupt priority levels
how interrupts are priorities
a process is suspended only if its IPL is greater than that of the current task
the process with the lower IPL is saved and handled when the IPL falls bellow it
interrupt process
- interrupt recieved
- state of current process is saved on kernel stack
- source is identified and priority is checked
- the system now jumps to the ISR
- once completed the state of the interrupted process is restored and continues
memory management
- determines which processes should be in main memory and where they are stored (optimisation)
single contiguous allocation
all memory is made available to a single application
paged memory
- memory is split up into fixed size partitions
- physical memory (frames) and logical memory (pages) are split up into fixed sized blocks
- program is allocated just more pages than it needs
page table
uses page number as index
maps logical address onto physical address
shows page num, flag status, page fram adress and time of entry
segmented memory
logical address space is broken up into variable size memory blocks (segments)
each has a name and size
to execute segments from logical are loaded into physical memory
segments are numbered and used as index in a segment map table
paging vs segmentation
logical vs physical memory
virtual memory
if a process runs out of RAM uses swap space on the hard disk
implemented using in demand paging
pages are loaded into memory from the disk when required
benefits of virtual memory
- programs can be larger than physical memory and executed
- more efficient multi programming - less I/O loading and swapping programs into/out of memory
- no need to waste memory with unused data
- eliminates external fragmentation/ reduces internal fragmentation
- no need to buy/ install expensive RAM
disk thrashing
- when there is a high rate of read/write head movements
- increases as main memory fills when using virtual memory
- if more time is spent moving pages than processing then the processing speed decreases
- can lead to premature failure of a hard disk
thrash point
when the execution of a process comes to a halt as the system is so busy paging in and out of memory
how do programs access data using virtual memory
- program executes the load process with a virtual address
- comp translates address into a physical address
- if not in memory then loads from disk
- reads RAM using the physical address and returns data
page replacement
occurs when a requested page isnt in memory
if a new page is requested but not in memory then page fault occurs
OS replaces the existing oage with a new page
page replacement algorithms
first in first out
optimal page replacement
least recently used page replacement
clock page replacement/ second chance page replacement
first in first out
OS keeps track of all pages usinga queue
oldest page is at front and first to be removed when new page to be added
- dont consider page usage
- beladys anomaly - possible to have more faults when increasing number of frames
optimal page replacement
looks to see which frame it can replace before a fault happens
+ free of beladys anomaly
least recently used page replacment
the page not used for the longest time is replaced
need to maintain a linked list of all pages in memory with most recently at front and least at the rear
clock page replacement/ second chance page replacement
- use a circular queue with a single pointer serving as both head and tail
- when a page fault occurs the page pointed to is expected and action depends on R flag if R = 0 its removed if not its kept
processor management vs memory management
- processor decides which processes will be executed and in which order
eg multitasking, scheduling - memory decide where in memory data is stored and how they are stored
eg paging, segmentation
virtual machines
- an emulation of an existing computer system
- runs the existing and oversees the virtual hardware using a guest OS
emulation
- the use of an app/device to imitate the behaviour of another program/device; for example, running an OS on a computer which is not normally compatible
host OS
- This is the OS that is controlling the actual physical hardware.
- It is the normal OS for the host/physical computer.
- The OS runs/monitors the virtual machine software
guest OS
- This is the OS running in a virtual machine.
- It controls the virtual hardware during the emulation.
- This OS is being emulated within another OS (the host OS).
- The guest OS is running under the control of the host OS software.
hypervisor
virtual machine software that creates and runs virtual machines
+ virtual machines
- can be used without impacting anything outside the VM - hsot is protected
- can run apps not compatible with host OS
- useful to emulate old software on a new system
- useful for testing a new OS or app since they will not crash host comp if something goes wrong
- virtual machines
- not same performance on guest OS as when running real system
- can be pricy
- complex to manage and maintain
