F453 Key terms Flashcards
1
Q
Flat file database
A
- A single table containing all information.
2
Q
Relational database
A
- Linked tables, each representing an entity in the system
- Pieces of data are stored once and looked up via links from other tables
- DBMS manages tables and relationships between them
3
Q
Data redundancy
A
- The same piece of data in a database is stored in more than one place
4
Q
Data inconsistency
A
- Two versions of data in a database may be different.
5
Q
Advantages of flat file databases
A
- Databases are simple to construct
6
Q
Advantages of relational databases
A
- Reduced data duplication
- Reduced data redundancy
- Improved data consistency
- Improved data integrity/security
- Control over access to data
7
Q
Disadvantages of relational databases
A
- Complex to set up
- Requires a good DBMS to control efficient views of data
8
Q
Entity
A
- A thing about which data is stored
9
Q
Relationship
A
- A link between two entities
10
Q
Normalisation
A
- Resolves many to many relationships
- Ensures data is stored in one place
- Ensures data is stored in the most appropriate place
11
Q
First Normal Form (1NF)
A
- No repeating attributes
12
Q
Second Normal Form (2NF)
A
- No partial-key dependencies
- Non-key attributes are dependent on all of the primary key
13
Q
Third Normal Form (3NF)
A
- No non-key dependencies
- No non-key attributes can be dependent on another non-key attribute
14
Q
Primary key
A
- A unique identifier within a table
- Referred to as a composite key when comprised of multiple fields
15
Q
Composite key
A
- Two or more attributes which act to uniquely identify an entity occurrence
16
Q
Foreign key
A
- A primary key from one table used as an attribute in another
- Used to link the two tables
17
Q
Where foreign keys are always found
A
- In the table with the ‘many’ side of the relationship
18
Q
Secondary key
A
- An attribute that can be used to search or sort data
- They are indexed which allows for fast searching of data
19
Q
Database Management System (DBMS)
A
- Software to handle the complexities of managing a database
- Could provide a UI
- May used SQL to communicate with other programs
- Provides different views of data
20
Q
Tasks performed by the DBMS
A
- Manages access rights
- Adds new data
- Updates existing data
- Finds data
- Maintains indexes
- Enforces data integrity rule
21
Q
Access rights
A
- Controls what data each user is allowed to view
- Controls what each user is able to do with data (view, update etc)
22
Q
Data dictionary
A
- A file containing descriptions of data in a database
- Uses metadata to define tables
- Used by database managers when altering database structure
23
Q
Data contained within the data dictionary
A
- Names of table
- Relationships between data
- Primary and foreign keys
- Field characteristics (data type, length etc)
- Which programs can access the data
24
Q
Data Definition Language
A
- Used to create a database
- Used to create tables, the users, their access right, alter the table (eg defining a foreign key)
- Records the attributes, data types, validation used and relationships between entities, creates users, grant access rights
25
Data Manipulation Language
- Used to query and sort data
| - Used to add, update and delete data from a database
26
SQL
- Structured Query Language
27
Reports
- A presentation of selected data, usually in table form
| - Features include: a query and a display order
28
Static data structure
- Data structure with a fixed size when created
29
Dynamic data structure
- Data structure which changes size as data is added and removed.
30
Advantage of static data structures
- The amount of storage required is known so easier to program
31
Disadvantage of dynamic data structures
- The amount of storage required is not known so more complex to program
32
Stack
- A list in which insertion and deletion take place at the same end
- A LIFO data structure
- Has only one pointer; TOP
33
LIFO
Last In First Out
34
Uses of a stack in a computer system
- Storing return addresses (during subroutine calling)
- Passing parameters
- Storing contents of registers while processing interrupt
- Reversing the order of a set of data
35
Error that could be encountered when adding to a stack
- Stack overflow error (stack is alredy full)
36
Error that could be encountered when removing from a stack
- Stack underflow error (stack is already empty)
37
Algorithm for adding an item to a stack (push item onto stack)
- If Stack is full then
- Output error and stop
- Else
- Increment StackPointer
- Add item at position of StackPointer
- End If
38
Algorithm for removing an item from a stack (pop item off stack)
- If Stack is empty then
- Output error and stop
- Else
- Return data item at position of StackPointer
- Decrement StackPointer
- End If
39
Queue
- A list
- Insertion and deletion take place at opposite ends
- A FIFO data structure
- Has two pointers: Front and Next
40
FIFO
- First In First Out
41
Queue overflow error
- When after an attempt to enqueue an item onto a full queue
42
Queue underflow error
When after an attempt to dequeue an item off of an empty queue
43
Uses of a queue in a computer system
- Jobs waiting for a printer in a spool queue
- Job queue batch processing system
- Keyboard buffer
44
Shuffle queue
Front index always fixed (items shuffle up to front when an item is dequeued)
45
Circular queue
- When enqueuing next index moves forward
- When dequeuing the front index moves forward
- The Next pointer wraps to beginning once last index is reached.
46
Algorithm for circular queue enqueue
- If Queue is full then
- Output error and stop
- Else
- Add data item at position NextPointer
- Increment NextPointer
- If NextPointer > MaxIndex Then
- Assign the value of 1 to NextPointer
- End If
- End If
47
Algorithm for circular queue dequeue
- If Queue is empty then
- Output error and stop
- Else
- Retreive data item at position FrontPointer
- Increment FrontPointer
- If FrontPointer > MaxIndex Then
- Assign the value of 1 to FrontPointer
- End If
- End If
48
Tree
- Represents the relationship between data items
49
Uses of trees
- Binary search tree: storing data in such a way that it makes it easy and fast to search
- Representing sorted lists of data
- Most databases use this concept as the basis of storing, searching and sorting its records
50
Algorithm for inserting an item to a tree
- Start at root node
- REPEAT
- If new data < current data Then
- Follow left pointer
- Else
- Follow right pointer
- End If
- UNITIL pointer is Null
- Write new data
- Create (null) pointers for new data
51
Algorithm for retrieving an item from a tree
- Start at root node
- WHILE pointer is not Null
- If current data = required data Then
- Return current data
- Else If required data < current data Then
- Follow left pointer
- Else
- Follow right pointer
- End If
- End WHILE
52
Algorithm for deleting an item from a tree
Could be done by:
- Marking a node as deleted but leave it in the tree
- Deleting a node and reattaching any child nodes to the tree
- More difficult than just removing a node
53
Binary search
- More efficient than linear searching
| - Requires data to already be sorted in order
54
Binary search algorithm
- Look at the item at the midpoint of the list (the current item)
- If the current item is the item sought, then it has been found
- If the current item is not the item sought, discard the half of the list that can't contain the item sought and repeat the same method with the other half of the list
- Keep repeating these steps until the item is found or the list contains no items
55
Advantages of binary searching
- Usually faster because half of the data is discarded at each step and fewer items checked
- More efficient for large files
56
Disadvantages of binary searching
- Items must be in an order to allow appropriate items to be discarded
57
Serial (linear) search
- Search starts at the beginning of the list
| - Each element in turn is compared with the required value until a match is found or the end of the list is reached
58
Advantages of serial searching
- A serial search can be used on unordered sets of data
59
Disadvantages of serial searching
- Generally slower because all data must be checked until the item is found or the end of the list is reached
60
Algorithm for merging data files
- Open existing files
- Create a new file
- Check existing files are not empty
- Use pointers to identify records for comparison
- REPEAT
- Compare records indicated by pointers
- Copy earlier value record to new file
- Move correct pointer Until end of one file
- Copy the remaining records from the other file
- Close the files
61
Insertion sort
- Insert one number at a time into correct position...
| - So list of sorted numbers is built up
62
Advantages of insertion sort
- Simple sorting algorithm and relatively efficient for small sets of data and mostly-sorted lists
- Is relatively fast for adding a small number of new items periodically
63
Disadvantages of insertion sort
- Inefficient for large sets of data
64
Quick sort
- If the first pointer is less than the last pointer (if there are elements in the list) Then
- Select an item at random to act as the 'pivot'
- Create two new lists
- ... One with all items less than pivot
- ... Other with all items greater than pivot
- Repeat these four steps until all lists only have one item
65
Advantages of quick sort
- Very quick for large sets of data
66
Disadvantages of quick sort
- Initial arrangement of data affects the time taken
| - Harder to code
67
Stepwise refinement
Breaking down a problem into progressively smaller sections until each section can be represented by a procedure / function
68
Top-down design
- The produced result of stepwise refinemeent
69
Procedure
- A block of code which performs a task
- Receives parameter values
- Uses local variables
- May/may not produce a single value
70
Function
- A block of code which performs a task
- Uses local variables
- Returns a single value
71
Benefits of using procedures and functions
- Each one can be tested separately
- Program is more easily maintainable
- Code is clearly structured
- Code is reusable
- Library routines save time
72
Variable
.- An identifier / memory location representing a value needed by the program
73
Parameter
- An item of data supplied to a procedure or function
- That can be passed by reference or by value
- Uses local variables
74
Pass by value
- Only actual value passed
| - Procedure / function can only modify a copy of original variable
75
Pass by reference
- Provides procedure/function with actual address to original variable therefore allowing it to permanently alter its contents
76
Local variables
- A variable defined and only accessible within one part of the program (procedure/function)
- Data contained is lost when execution of that part of program is completed
- The same variable names can be used in different procedures and functions
77
Example of a local variable
- A loop counter
78
Global variables
- Defined at the start of the program and exists throughout the program (including within functions and procedures)
- Allow data to be shared by modules
- Are overridden by local variables with the same name
79
Example of a global variable
- VAT rate
80
Uses of a stack with relation to procedures
- To help control the flow of instructions
- When a subroutine is called the return address is placed on the stack followed by the parameters of the subroutine (if there are any)
- When the subroutine executes, it first pops the parameters off the stack
- When it finishes it pops the return address off the stack so control can pass back to the instruction at the calling address
81
Backus-Naur Form (BNF)
- A notation technique used to unambiguously describe the syntax of a programming language / computer language
82
Recursion in BNF
::= 0|1|2|3|4|5|6|7|8|9
| ::= |
83
Infix notation
- The common arithmetic and logical formula notation, in which operators are written between the operands
- Eg. 2 + 4
84
Reverse Polish Notation (RPN)
- Also known as postfix notation
- A mathematical notation in which every operator follows all of its operands
- Eg. 24+
- Does not require parentheses
85
RPN to infix conversion
- Completely parenthesize the infix expression according to order of priority you want
- Move each operator to its corresponding right parenthesis
- Remove all parentheses
86
RPN and infix - stacks
- Stacks are used in the evaluation of Reverse Polish Notation expressions
87
RPN and infix - trees
- Trees can be traversed in-order to obtain the infix and post-order to obtain the RPN (postfix
88
In-order tree traversal
- Place a dot under each node
- Trace around tree starting to left of root
- As you pass underneath a node output its data
89
Post-order traversal
- Place a dot on the right of each node
- Trace around tree starting to left of root
- As you pass to right of node output its data
90
In-order algorithm
- Traverse the left branch until there is no left branch
- Visit the root of the current branch
- Traverse the right sub tree if there is one
- Repeat previous steps until every node has been visited
91
Post-order algorithm
- Traverse the left sub tree until there isn't one
- Traverse the right sub tree (if there is one)
- Re-visit the root of the current branch
- Repeat previous steps until every node has been visited
92
Low-level language
- Machine-oriented
- Usually one instruction to one machine code instruction
- Mnemonics for operations
- Labels for addresses
93
Uses of low-level language
- Coding device drivers
| - Embedded systems where processing capabilities and memory capacity are limited
94
Object-oriented language
- Solution for a problem can be visualised in terms of objects that interact passing messages back and forth
- Classes and objects
95
Uses of object-oriented language
- Producing re-usable code
| - Use in large software projects where data and the methods acting on are kept together
96
Declarative language
- Program consists of facts and rules
- States what is required but not how to do it
- Statements not needed in specific order
97
Uses of declarative language
- Expert systems (knowledge based systems) (Eg. medical diagnosis)
- Artificial Intelligence
- Pattern Recognition
98
Procedural language
- Language is imperative
- Uses sequence, selection, iteration, procedures and functions
- States what to do and how to do it
- Statements need to be in a specific order
99
Uses of procedural language
- Language is imperative
- Uses sequence, selection, iteration, procedures and functions
- States what to do and how to do it
- Statements need to be in a specific order
100
Data encapsulation
- Data can only be accessed using the operations defined for the class
- This maintains data integrity
101
A class
- A template for a set of objects that have state and behaviour
102
An object
- An instance of a class
| - A real-world entity and holds attributes and operations
103
Derived class
- A class that has all the attributes and operations of its superclass and may have attributes and operations of its own
- Also called a sub class
104
Inheritance
- A derived class inherits all the attributes and operations from its superclass
105
Unified Modelling Language
- Standard way to present the design of a system
- Visual representation of data so easy to understand
- Allows analysts, programmers and clients to communicate
- makes system maintenance easier when modifying a system
106
Class diagram
- Describes the classes to achieve the tasks that the system must perform and the relationships between them
107
Object diagram
- Shows the individual attributes of a specific object from a class and the operations including parameter values / return value that are active at that specific point in time
- Shows association between objects with lines
108
Use case diagram
- Describes the tasks which the system must help to perform
| - Describes the requirements of a system
109
State diagram
- In order to implement, maintain or test a class we need to understand what the dependencies are between the state of an object and its reactions to messages or other events
110
Sequence diagram
- A type of interaction diagram
- Describe record in detail how objects interact to perform a task
- Shows the objects (and actors) which take part in a collaboration at the top of dashed lines
111
Activity diagram
- Describe how activities are co-ordinated
- Could be used to show how an operation could be implemented
- They are also useful for describing use cases in detail
112
Communication diagram
- A type of interaction diagram
- Also known as a collaboration diagram
- Describe how objects interact to perform a task
- Show the order of messages / signals passed between the linked objects
113
Backtracking
- Going back to a previously found successful match in order to continue a search
114
Instantiation
- Giving a value to a variable in a statement
115
Predicate Logic
- A branch of mathematics that manipulates logical statements that can be either True or False
116
Variable (declarative languages)
- Written as a sequence of letters and digits, beginning with a capital letter (or underscore)
- Eg. A, Male, _male
117
Goal
- A statement we are trying to prove either True or False
118
Reasons to use high-level languages
- Reflects type of problem
- Allows use of mathematical functions
- Portability
- Uses library routines
- Complexity of problem
- Easy to maintain
119
Reasons to use low-level languages
- Close to design of processor
- Can access memory locations directly
- Able to program very memory efficient programs which is necessary when the processor has limited memory
120
Advantages of library routines
- They have already been tested and are error free
- Saves time when programming
- Multiple programmers can understand them, and work on the same code
121
Machine Code
- Binary / hexadecimal notation
- Set of all instructions available to the architecture
- Depends on the hardware design of the processor
- Instructions operate on bytes of data
- No translation needed
- Very difficult to write
122
Assembly Language
- Related closely to the computer being programmed
- Low level language, so machine specific
- Uses descriptive names (for data stores), mnemonics (for instructions), labels to allow branching (selection)
- Each instruction is generally translated into one machine code instruction
- Translated by an assembler
- Typically used for writing drivers / easier than machine code, but harder than high-level languages
123
Why registers are important
- Low level languages make direct use of the hardware within the CPU so programmers need to know about the registers of the CPU in order to write low level code
124
JUMP instruction
- When a program is running, the Program Counter will often just be incrementing as it addresses one instruction after the other
- However, the instructions will often modify the next address, for example, 305 becomes 39
125
Index register
- Used in indexed addressing
- Stores a number used to modify the address (in address field)
- Provides an efficient way to access a number of consecutive locations
- Used for arrays
126
Opcode
- The nmemonic part of an instruction
| - ... that indicates what it is to do (eg ADD)
127
Operand
- The address field in an instruction which holds data or address to be used
128
Mnemonic
- Easily memorable code used to represent of the opcode of an operation
- The operation part of the instruction (opcode)
- Replaced by binary code during assembly
129
Flow control
- The order in which instructions are executed
| - The order may be altered by a JUMP instruction / conditional JUMP instruction
130
Immediate addressing
- Data from the operand is the value to be used by the operator
- Eg ADD #25 ... the value 25 is added into the accumulator
- Very useful to carry out instructions involving constant
131
Direct addressing
- Data in the operand is used as the address of the data
- This address is where data can be found or is to be written to (without modification)
- It uses a fixed memory location therefore it is not re-locatable
- Number of addresses available is limited by the size of the address field
132
Indirect addressing
- Data in the operand is used as the address of the data
- This address is where data can be found or is to be written to (without modification)
- It uses a fixed memory location therefore it is not re-locatable
- Number of addresses available is limited by the size of the address field
133
Indexed addressing
- Modifies the address given
- ... by adding the number
- ...from the index register
- ...to address in instruction
- Used to address items in an array
- Easy to alter index register
- Easy to access a range of memory locations
- Only the base address needs to be changed if array is relocated in memory
134
Relative addressing
- Allows a real address to be calculated
- ...by adding a base address
- ... to the operand
- It is an offset
- Can be used for arrays and branching
135
Symbolic addressing
- -The use of characters to represent the address of a store location (in the operand)
136
Purpose of translators
- To convert source code into object code
| - To detect errors in source code
137
Compiler
- Translates whole program as a unit
- Uses high-level source code
- Gives list of errors at end of compilation
- Creates an executable program or intermediate program when program is completed
- Protects program from malicious use
- Are architecture specific
- Can carry out optimisation which improves program speed and size
- Is no longer needed once executable code is produce
138
Interpreter
- Translates and executes one line at a time
- Uses high-level source code
- Reports errors as they are found one at a time
- It must be present each time program is run
- Program runs more slowly due to translation
139
Assemblers
- Translates a program from assembly language to machine code
- Translates whole program as a unit
- Uses low-level source code
- Gives list of errors at end of assembly
- One assembly language instruction is (generally) changed into one machine code instruction
140
Advantages of compilers
- Results in an executable code that requires no further translation
- Therefore programs execute faster than if they were interpreted
141
Disadvantages of compilers
- Use a lot of computer resources
- Has to be loaded in the computer's memory at the same time as the source code and there has to be sufficient memory to hold the object code
- Has to be sufficient memory for working storage while the translation is taking place
- Errors in the original program are difficult to pin-point
142
Advantages of interpreters
- Need less memory than compiler
- Each error message is produced on the line where the error was encountered, making it is easier to identify the instruction causing the problem
- Individual segments can be run without needing compile the whole program
143
Disadvantages of interpreters
- Slower execution as the original program has to be translated every time it is executed
- Instructions inside a loop have to be translated each time the loop is entered
144
Interpreter error handling
- Stops at first error
- An error message is produced
- Error would be corrected
- Program can restart from any point
- This is repeated until all errors are removed when program will run
145
Source code
- The original code written by the programmer
- Often in a high-level language (may be in assembly language)
- Can be understood by people but cannot be executed by computers(until translated)
146
Object code
- Could be machine code or intermediate code
147
Intermediate code
- Simplified code which is partly translated
- Can run on a variety of computers (using an interpreter)
- ... which improves portability
- The same intermediate code can be obtained from different high level languages
- Is used in a virtual machine (Eg Java)
148
Advantages of intermediate code
- Allows sections of program to be written in different high-level languages
- Platform independent so improves portability
- Is compiled so is error free
149
Disadvantages of intermediate code
- Program runs more slowly than executable code because it has to be translated each time it is run
- Need additional software (interpreter or virtual machine)
150
Virtual machine
- Intermediate code is run using an interpreter (for the specific computer)
151
Reasons to compile to machine code
- Compiled programs are executable, run quickly, do not need a translator to run and use less memory
152
Tasks of an assembler
- Reserves storage for instructions and data
- Replaces mnemonic opcodes by machine codes
- Replaces symbolic addresses by numeric addresses
- Creates symbol table to match labels to addresses
- Checks syntax and offers diagnostics for errors
153
Library routines
- Are pieces of software which perform common tasks such as sorting and searching
- Are already compiled
154
Reasons to use library routines
- To perform common tasks
- They are error free and tested
- Ready to use so saves work and time
- May be used multiple times
- May have been written in a different source language
- Use other programmers' expertise
155
Linker
- Is used to combine modules / library routines
- ... that are already compiled / in object code / in executable form
- ... with program by completing address links to program
156
Loader
.- Copies modules into memory
- ... from backing store
- ... when program is to be run
- Handles addresses ready for execution
157
Linking errors
- Occur when a compiled program is linked to library routines. (Eg. if a particular subroutine is not present in the library or the number of parameters provided is wrong)
158
Compiled code may not be executable...
- As it may need to be linked to library routines (Eg. library for I/O routines or for mathematical functions)
159
Lexical analysis
- Source code is used as input
- Reserved words are replaced by tokens
- Variable names are checked and entered in the symbol table
- Constants are entered in the symbol table
- Data type/space required is entered in the symbol table
- Error reporting occurs
- Unnecessary characters (white space, comments) are removed / program is formatted ready for the next stage of compilation
160
Tokens
- A token is a fixed length string of binary digits
161
Syntax analysis
- Accepts output from lexical analysis
- Statements, arithmetic expressions and tokens are checked against the rules of the language (Eg. matching brackets)
- The parser checks the tokens generated by the lexical analyser to see if they are grammatically correct
- Parse trees are generated (from which machine / executable / intermediate code can be generated)
- Further detail is added to the symbol table (Eg.data type / scope / address)
- Errors are reported
- ... as a list at the end of compilation to alert the programmer
- Some reported errors may be spurious (not being what it purports to be; false or fake)
- If no errors, code is passed to the code generator
162
Example Syntax errors
- Missing the end statement in a selection or iteration construct (Eg. missing closing part of a loop statement: "Next i", or missing closing part of an IF statement: "End If")
163
Code generation
- Occurs after syntax analysis
- Is the last phase of compilation
- Produces machine code program, executable or intermediate code which is equivalent to the source program
- Variables and constants are given addresses
- Relative addresses are calculated
164
(code) Optimisation
- Makes code as efficient as possible
- Improves processing speed
- Reduces number of instructions
- Programmer can choose between speed and size
165
Operating System (OS)
Software that handles the interface to the hardware and manages resources
166
Features of operating systems
- Provide and manage hardware resources
- Provide an interface between the user and the machine "Eg. CLI, GUI)
- Provide an interface between applications software and the machine (Eg. saving to disk)
- Provide security for the data on the system (Eg. passwords, access rights, encryption)
- Provide utility software to allow maintenance to be done (Eg. housekeeping, anti-virus)
167
Management of hardware resources
- Management of memory (partitioning, allocating memory, virtual memory)
- Scheduling of jobs (including interrupt handling)
168
Interrupt
- A signal(interrupt) sent to the processor
- Request for processing time
- Allows importand tasks to be processed
- May cause a break in execution of the current routine so it can be resumed later
169
Reasons to use interrupts
- To obtain processor time
- ... for a task of higher priority
- To avoid delays
- To avoid loss of data
- As an indicator to the processor
- ... that a device needs to be serviced
170
Sources of interrupt
- User (Eg.new user logon request)
- Power failure (Eg. to allow orderly shut-down to prevent data loss)
- System failure
- Peripheral (Eg. printer buffer empty, printer out of paper)
- Clock
- Software (Eg. divide by zero error)
171
Hardware interrupt
- An electronic alerting signal sent to the processor from an external device, either a part of the computer itself such as a disk controller or an external peripheral
- E.g.. imminent power failure
172
Software interrupt
- An interrupt generated within a processor by executing an instruction
- E.g.. Divide by zero
173
Processing interrupts
- After each cycle is completed (execute instruction), the processor checks the interrupt register by comparing priority of the current task with the highest priority interrupt
- If interrupt is of higher priority the contents of the registers is put onto a stack
- ... program counter set to start address of interrupt service routine
- ... interrupt is processed
- ... check for further interrupts
- ... contents of registers restored from stack and original task continues
- If the interrupt was not of a higher priority than the current task then it starts the fetch-execute cycle again
174
Resuming after interrupt
- Reset interrupt request flag so interrupt is shown to have been serviced
- Check interrupt register for further interrupts and service them if they are of higher priority than task to be resumed
- If there are no higher priority interrupts then restore the contents of the registers from the stack and resume task
175
Purpose of scheduling
- Ensures that all jobs are processed by changing priorities where necessary
- Prevents jobs from monopolising the processor
- Prevents low priority jobs from never getting processed
- Process as many jobs as possible in the least possible time
- Maximise the number of interactive users receiving fast response times
- Maximise throughput by utilising resources and processor time efficiently
176
High level scheduler
- When a jobs wants to be processed, it must enter the system and be placed in a queue of jobs waiting for processing called the ready queue
177
Medium level scheduler
- When a job that is already running has had to stop, the job at the top of the ready queue is loaded into the processor and run
178
Low level scheduler
- Controls the movement of jobs between main memory and secondary storage
179
Priority
- An order of importance
180
Job states
- Ready
- Running
- Blocked
181
Priorities within the job queue
- Jobs are given different priorities when in a job queue
- This is because some jobs are more urgent than others
- Priorities are also used to maximise the use of the computer resources
- A low priority job can have its priority changed by the operating system
182
Reasons for jobs leaving the running state
- Job may have finished running
- Job may require services of a peripheral (placed in the blocked queue to await servicing)
- Job has had long enough and it has to give up its place so that the other jobs get a chance
- A higher priority interrupt comes along
183
Scheduling algorithms
- Round robin
- System of priorities
- Length of job
- First come, first served
- Multi-level feedback queues
184
Round robin
- Each user is allocated a time slice
- When time slice is up, system moves to next user
- If next user needs processor, user given time slice
- Repeat this for all users in turn (until all users serviced)
- Users may have different priorities which can change the order
- Time slices are very small with no apparent delay for any user
185
Multilevel feedback queue
- A complex scheduling algorithm involving a number of queues set up according to rules and acting like a set of league table
- As jobs are given lots of peripheral time, they drop down the tables to let other jobs get processed
- When a jobs if finished it leaves the system and allows other jobs up the tables
- This algorithm prevents jobs from monopolising the processor
- If two jobs have the same priority, a round robin system is used to process both of them simultaneously
186
Time slice (also called quantum)
- The period of time for which a process is allowed to run in a pre-emptive multitasking system
- Very small fractions of time
- There is no apparent delay to the user when transitioning between time slices
187
Why memory management is needed
- To allocate memory to allow separate processes to run apparently simultaneously
- To deal with allocation when paging / segmenting
- To reallocate when necessary
- To protect processes and data from each other
- To protect the operating system and provide security
- To enable memory to be shared
188
Virtual memory
- Combines active RAM and inactive memory on secondary storage to form a large range of contiguous addresses
- Allows programs to run when there is insufficient memory available
189
Paging
- A way of partitioning memory
- Used for virtual memory
- Segments stored on backing store and assigned to memory when needed
- Pages are of a fixed size, are made to fit sections of memory and are physical divisions
- Paged allocation divides the computer's primary memory into fixed-size units called page frames, and the program's address space into pages of the same size
190
Segmentation
- Way of partitioning memory
- Used for virtual memory
- Segments stored on backing store and assigned to memory when needed
- Segments are different sizes, are complete sections of programs and are logical divisions
191
Disk threshing
- Occurs when using virtual memory moving pages between memory & disk
- Disk is relatively slow
- High rate of disk access means more time spent swapping pages than on processing
- Computer may 'hang'
192
Spooling
- A type of buffering
- It is used to place input and output on a fast access storage device, such as a disk, so that slow peripheral devices do not hold up the processor
- Stands for Simultaneous Peripheral Operations On-Line
193
Reasons to use spooling
- It allows sharing of a printer on a network with different users
- It avoids delays and frees up the processor
- It avoids the speed mismatch between the slow printer and fast processor
- It allows jobs to be prioritised.
194
Print spooling
- Output data to disk drive / storage device for printing at another time
- To allow sharing on a network
- Job references stored in a queue
- Avoids speed mismatch as printers are relatively slow
- Jobs can be prioritised
- Print Spoolers can notify users when their output has been printed, distribute jobs among several printers and generate banner pages to identify and separate print jobs.
195
Uses of spooling
- When printing on a network
- A batch processing system uses spooling to maintain a queue of ready-to-run jobs which can be started as soon as the system has the resources to process them
196
Boot file
- A computer program executed automatically that loads the main operating system for the computer after completion of the Power-On-Self-Test (POST)
- It is stored on ROM
197
Purpose of the boot file
- Provides personal settings
- Initialises operating system
- Passes control to operating system (by setting program counter)
- Checks hardware
- Checks memory
198
Booting up
- The initial set of operations performed after CPU receives power or when the computer is reset
- The first step is for the computer to run the Power-On-Self-Test (POST) routine resident in permanent memory
- The boot program is stored in ROM and contains the skeleton of the Basic I/O System
- Control is now passed to the boot program. The boot program instructs the CPU to send signals to check hardware (buses, system clock, memory) and peripherals
- The boot program takes account of any personal settings (Eg. which operating system to boot)
- The boot program now reads the operating system into memory and then executes it (by setting Program Counter)
199
Power-On-Self-Test (POST)
- A process performed by firmware or software routines immediately after many devices are powered on
- The routines are part of a device's pre-boot sequence
- Once POST completes successfully, bootstrap loader code is called upon
200
Duties of BIOS during POST
- Verify CPU registers
- Find, size, and verify system main memory
- Initialize BIOS
- Identify, organize, and select which devices are available for booting
- Provide a user interface for system's configuration
- BEEP codes to indicate errors
201
BEEP codes
- Audio signals given out by a computer to announce the result of a short diagnostic testing sequence the computer performs when first powering up (POST)
202
File Allocation Table (FAT)
- A map of where files are stored on the hard disk
203
Use of the FAT
- Updated by the OS when files are saved / deleted
| - Used by the OS when files are accessed
204
Contents of the FAT
- Provides addresses / pointers to the start of files
- Provides pointers to further clusters (in a chain)
- Stores file names
- Stores file sizes
- Stores access rights
- Identifies free space
205
Features of Von Neumann
- A single main memory unit shared between program instructions and data, meaning that the program is stored with the data in the same format
- A single control unit managing program control
- Sequential processing takes place with instructions being fetched from memory, decoded and executed one after another, one at a time, in a serial manner
206
Fetch-Execute Cycle
- PC holds address of next instruction
- Copy contents of PC to MAR
- ... while the PC is simultaneously increment
- Load instruction pointed to by the MAR to MDR
- Copy instruction from MDR to CIR
- Decode (and execute) instruction in CIR
207
Execution of JUMP instruction
- Changing contents of PC (to address part of instruction)
- Copy address part of instruction
- ... in CIR to PC
208
Registers
- Location in the processor used for a particular purpose
- Temporarily stores data / control information
- Allows very high speed access
209
Program Counter (PC)
- Contains the address of the next machine code instruction to be executed
- During the fetch-execute cycle, its contents are copied into the Memory Adress Register
- ... and it is simultaneously incremented (each cycle)
- For jump instructions, the address of the Current Instruction Register is put in it
210
Memory Address Register (MAR)
- Receives address of instruction (from PC)
- Holds address of data/instruction to be used
- Receives operand part of instruction from CIR
211
Memory Data Register (MDR)
- Receives an instruction/data
- ... from memory location in MAR
- Receives data / instruction from memory location in address part of instruction/accumulator
- Instruction in MDR is copied to CIR
- MDR acts as a buffer / temporary store
- Storing data / an instruction
- ... when being transferred between memory & processor
- Also know as the Memory Buffer Register (MBR)
212
Current Instruction Register (CIR)
- Contains the instruction to be executed
- Splits instruction into component parts
- Holds opcode while it is decoded
- Sends the address to the MAR for accessing data / value to accumulator
- Sends address to PC for jump instruction
- Determines the type of addressing to be used
- Also known as Instruction Register
213
Accumulator
- Temporary storage in the Arithmetic Locic Unit
- Holds data being processed during calculations
- Deals with the input / output in the processor
214
Parallel processor system
- Multiple processors working together to perform a single job
- Jobs are split into tasks
- Each task may be processed by any processor
- Processors are controlled by a complex operating system
215
Advantages of parallel processors
- Allows faster processing which greatly increases the speed programs can execute
- More than one instruction (of a program) is processed at the same time
- Different processors can handle different tasks of same job
- Speeds up the processing of data from many inputs
216
Disadvantages of parallel processors
- A more complex program must be developed, compared to the traditional sequential program, to allow execution of different parts at the same time
- A complex OS is required to ensure synchronisation between the processors
217
Array (Vector) Processor system
- A processor that allows the same instruction to operate simultaneously on multiple data locations
- ... using multiple ALUs
- Single Instruction Multiple Data (SIMD)
- Lots of data items get processed with a single instruction
- Eg. Weather forecasting, airflow simulation around new aircraft
218
Advantages of array processors
- Many ALUs so useful for manipulating 1 dimensional arrays where the same calculation can be applied to every element in the array in one cycle
- Is very fast (takes one cycle)
219
Disadvantages of array processors
- High price of array memory systems
| - Increased code complexity
220
RISC
- Reduced Instruction Set Computer
- A limited number of instructions is available
- Has several register sets
- An instruction performs a simple task
- Uses only simple instructions
- Complex tasks can only be performed by combining a number of instructions
- ... so a task may take a number of machine cycles
221
CISC
- Complex Instruction Set Computer
- Uses (complex) instructions, each of which may take multiple cycles (but some can be completed in a single cycle)
- Single register set
- Instructions have variable format
- Many instructions are available
- Many addressing modes are available
222
Advantages of RISC
- Programs run more quickly due to less complicated instructions / circuit and more easily pipelined
223
Disadvantages of RISC
Programs take up more memory because more instructions are required to complete a task (than with CISC)
224
Advantages of CISC
- Programs take up less space on backing store and in main memory
- ... as fewer instructions required for task
225
Disadvantages of CISC
- Programs run more slowly
| - ... due to the more complicated instructions / circuit.
226
Mantissa
The part of a floating-point number which represents the significant digits of that number (and the sign of the number)
227
Exponent
- The part of a floating-point number which defines where the point needs to be (positive exponent moves point right and negative exponent moves point left)
228
Reasons to normalise floating-point numbers
- Normalisation is a way of storing numbers so that maximum precision and accuracy is obtained
- It also ensures that a specific representation of a number is unique
- It allows for more accurate multiplication (as it maintains the maximum number of bits of precision for a computation
229
How to normalise floating-point numbers
- Normalised mantissas always start '01' or '10' ('01' for positive number, '10' for negative number)
- The mantissa's first two bits must be different for the number to be normalised
- Normalisation is achieved by adjusting the exponent
230
Floating-point binary accuracy and range
- If the number of bits for the mantissa is increased, a greater accuracy of values can be represented (but range is reduced)
- If the number of bits for the exponent is increased, a greater range of values can be represented (but accuracy is reduced)
