[16] SYSTEM SOFTWARE

• Uses of a stack

  · RPN · Recursion · Implementing ADTs · Interrupt handling
• Stages of compilation

  · Lexical analysis · Syntax analysis · Code generation · Optimisation
• Purpose of syntax analysis (3)

  · Checks code conform with rules of the language

  · Syntax errors are reported

  · Parse tree produced
• Why RPN used to evaluate

  · Unambiguous method of representing expression · Reads left to right · Without need of brackets · Without need to follow rules of precedence (BODMAS)
• Reasons for optimising code

  · Minimises memory used · Minimises execution time
• How stack used to evaluate RPN

  · Working from left to right · Numbers (operands) pushed onto stack · Until operator reached · Pop first two numbers · Perform operation · Push result back on stack
• Lexical analysis

  converts sequence of characters into sequence of tokens removes unnecesary characters compares with table
• Code generation

  converts immediate representation of source code into executable code
• Difference between paging + segmentation (3)

  · Paging allows memory split into fixed size blocks. Segmentation variable

  · OS divides memory into pages. Compiler responsible for calculating segment size

  · Access time faster for paging
• Virtual memory description (4)

  · Secondary storage used to extend memory available

  · CPU able to access more memory than available RAM

  · Only data in use needed in main memory so data can be swapped between RAM + VM when needed

  · VM created temporarily
• The need for scheduling

  · Allows more than one program executed at once. Enables multi-tasking · Allow highest priority jobs completed first · Keep CPU busy all times · Ensure processes executed efficiently · Ensure all processes have fair access to CPU
• Describe + benefit of Shortest job first

  · Processes executed in ascending order of amount of CPU time needed · Shorter processes executed first · Increased output – more processed executed in less time
• Describe + benefit of Round Robin

  · Each process served by CPU for fixed time slice. Then returns to ready · Starvation doesn’t occur. All receive fair access
• Describe + benefit of First come first served

  · No complex logic

  · Process request queued and then executed

  · Starvation doesn’t occur

  · Less processor overhead
• How Interpreter executes program without producing translated version

  · Interpreter examines source code line by line

  · Check each line for errors

  · If no error, then execute

  · If error, report + interpreter halts

  · Interpretation repeated every time program run
• Paging (1)

  reading/writing fixed size blocks to/from secondary storage when required
• Interrupt handling

  transferring control to another routine (ISR) when service required
• Ready state:

  · Process not being executed · Process in queue · Waiting for processor’s attention/its time slice
• Running state

  · Process currently being executed by processor · Process currently using its allocated process time/ time slice
• Blocked state

  · Process waiting for event · So cannot currently be executed · E.g. user input
• Role of high level scheduler

  decides which process loaded into ready queue
• What is disk thrashing

  · Pages required back in RAM as soon as moved to disk

  · Continuous swapping of same page

  · No useful process happening

  · Pages in RAM + disk interdependent

  · All processing time used for swapping pages
• How paging is used to manage virtual memory (6)

  · Divide RAM into page frames

  · Divide VM into pages of fixed size

  · Pages + frames same fixed size

  · Set up a page table to translate logical to physical addresses

  · Keep track of all free frames

  · Swap pages in memory with new pages from disk when needed
• Difference between program + process

  · A program is the written code (“static”) · A process is the executing code (“dynamic”)
• Process states

  Ready Running Blocked
• Kernel interrupt handling

  Interrupts are used to enforce time slices in pre-emptive scheduling algorithms
• Interrupt handling in CISC and RISC Processors:

  As soon the interrupt is detected the current processes are paused and moved into registers

  The ISR (Interrupt Service Routine) is loaded on to the pipeline and is executed

  When the interrupt has been serviced, the paused processes are resumed by bringing them back from the registers to the pipeline
• BNF

  Backus-Naur Form

  Formal metalanguage for describing language syntax

  A statement in BNF can be only written in one way ::= 0 | 1

  ::= is read as "is defined by"

  | is read as representing the OR operation