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
Q
Data Manipulation Language
A
- Used to query and sort data
- Used to add, update and delete data from a database
26
Q
SQL
A
- Structured Query Language
27
Q
Reports
A
- A presentation of selected data, usually in table form
- Features include: a query and a display order
28
Q
Static data structure
A
- Data structure with a fixed size when created
29
Q
Dynamic data structure
A
- Data structure which changes size as data is added and removed.
30
Q
Advantage of static data structures
A
- The amount of storage required is known so easier to program
31
Q
Disadvantage of dynamic data structures
A
- The amount of storage required is not known so more complex to program
32
Q
Stack
A
- A list in which insertion and deletion take place at the same end
- A LIFO data structure
- Has only one pointer; TOP
33
Q
LIFO
A
Last In First Out
34
Q
Uses of a stack in a computer system
A
- Storing return addresses (during subroutine calling)
- Passing parameters
- Storing contents of registers while processing interrupt
- Reversing the order of a set of data
35
Q
Error that could be encountered when adding to a stack
A
- Stack overflow error (stack is alredy full)
36
Q
Error that could be encountered when removing from a stack
A
- Stack underflow error (stack is already empty)
37
Q
Algorithm for adding an item to a stack (push item onto stack)
A
- If Stack is full then
- Output error and stop
- Else
- Increment StackPointer
- Add item at position of StackPointer
- End If
38
Q
Algorithm for removing an item from a stack (pop item off stack)
A
- If Stack is empty then
- Output error and stop
- Else
- Return data item at position of StackPointer
- Decrement StackPointer
- End If
39
Q
Queue
A
- A list
- Insertion and deletion take place at opposite ends
- A FIFO data structure
- Has two pointers: Front and Next
40
Q
FIFO
A
- First In First Out
41
Q
Queue overflow error
A
- When after an attempt to enqueue an item onto a full queue
42
Q
Queue underflow error
A
When after an attempt to dequeue an item off of an empty queue
43
Q
Uses of a queue in a computer system
A
- Jobs waiting for a printer in a spool queue
- Job queue batch processing system
- Keyboard buffer
44
Q
Shuffle queue
A
Front index always fixed (items shuffle up to front when an item is dequeued)
45
Q
Circular queue
A
- 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
Q
Algorithm for circular queue enqueue
A
- 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
Q
Algorithm for circular queue dequeue
A
- 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
Q
Tree
A
- Represents the relationship between data items
49
Q
Uses of trees
A
- 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
Q
Algorithm for inserting an item to a tree
A
- 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
Q
Algorithm for retrieving an item from a tree
A
- 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
Q
Algorithm for deleting an item from a tree
A
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
Q
Binary search
A
- More efficient than linear searching
- Requires data to already be sorted in order
54
Q
Binary search algorithm
A
- 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
Q
Advantages of binary searching
A
- Usually faster because half of the data is discarded at each step and fewer items checked
- More efficient for large files
56
Q
Disadvantages of binary searching
A
- Items must be in an order to allow appropriate items to be discarded
57
Q
Serial (linear) search
A
- 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
Q
Advantages of serial searching
A
- A serial search can be used on unordered sets of data
59
Q
Disadvantages of serial searching
A
- Generally slower because all data must be checked until the item is found or the end of the list is reached
60
Q
Algorithm for merging data files
A
- 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
Q
Insertion sort
A
- Insert one number at a time into correct position…
- So list of sorted numbers is built up
62
Q
Advantages of insertion sort
A
- 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
Q
Disadvantages of insertion sort
A
- Inefficient for large sets of data
64
Q
Quick sort
A
- 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
Q
Advantages of quick sort
A
- Very quick for large sets of data
66
Q
Disadvantages of quick sort
A
- Initial arrangement of data affects the time taken
- Harder to code
67
Q
Stepwise refinement
A
Breaking down a problem into progressively smaller sections until each section can be represented by a procedure / function
68
Q
Top-down design
A
- The produced result of stepwise refinemeent
69
Q
Procedure
A
- A block of code which performs a task
- Receives parameter values
- Uses local variables
- May/may not produce a single value
70
Q
Function
A
- A block of code which performs a task
- Uses local variables
- Returns a single value
71
Q
Benefits of using procedures and functions
A
- Each one can be tested separately
- Program is more easily maintainable
- Code is clearly structured
- Code is reusable
- Library routines save time
72
Q
Variable
A
.- An identifier / memory location representing a value needed by the program
73
Q
Parameter
A
- An item of data supplied to a procedure or function
- That can be passed by reference or by value
- Uses local variables
74
Q
Pass by value
A
- Only actual value passed
- Procedure / function can only modify a copy of original variable
75
Q
Pass by reference
A
- Provides procedure/function with actual address to original variable therefore allowing it to permanently alter its contents
76
Q
Local variables
A
- 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
Q
Example of a local variable
A
- A loop counter
78
Q
Global variables
A
- 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
Q
Example of a global variable
A
- VAT rate
80
Q
Uses of a stack with relation to procedures
A
- 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
Q
Backus-Naur Form (BNF)
A
- A notation technique used to unambiguously describe the syntax of a programming language / computer language
82
Q
Recursion in BNF
A
::= 0|1|2|3|4|5|6|7|8|9
::= |
83
Q
Infix notation
A
- The common arithmetic and logical formula notation, in which operators are written between the operands
- Eg. 2 + 4
84
Q
Reverse Polish Notation (RPN)
A
- Also known as postfix notation
- A mathematical notation in which every operator follows all of its operands
- Eg. 24+
- Does not require parentheses
85
Q
RPN to infix conversion
A
- Completely parenthesize the infix expression according to order of priority you want
- Move each operator to its corresponding right parenthesis
- Remove all parentheses
86
Q
RPN and infix - stacks
A
- Stacks are used in the evaluation of Reverse Polish Notation expressions
87
Q
RPN and infix - trees
A
- Trees can be traversed in-order to obtain the infix and post-order to obtain the RPN (postfix
88
Q
In-order tree traversal
A
- Place a dot under each node
- Trace around tree starting to left of root
- As you pass underneath a node output its data
89
Q
Post-order traversal
A
- 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
Q
In-order algorithm
A
- 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
Q
Post-order algorithm
A
- 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
Q
Low-level language
A
- Machine-oriented
- Usually one instruction to one machine code instruction
- Mnemonics for operations
- Labels for addresses
93
Q
Uses of low-level language
A
- Coding device drivers
- Embedded systems where processing capabilities and memory capacity are limited
94
Q
Object-oriented language
A
- Solution for a problem can be visualised in terms of objects that interact passing messages back and forth
- Classes and objects
95
Q
Uses of object-oriented language
A
- Producing re-usable code
- Use in large software projects where data and the methods acting on are kept together
96
Q
Declarative language
A
- Program consists of facts and rules
- States what is required but not how to do it
- Statements not needed in specific order
97
Q
Uses of declarative language
A
- Expert systems (knowledge based systems) (Eg. medical diagnosis)
- Artificial Intelligence
- Pattern Recognition
98
Q
Procedural language
A
- 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
Q
Uses of procedural language
A
- 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
Q
Data encapsulation
A
- Data can only be accessed using the operations defined for the class
- This maintains data integrity
101
Q
A class
A
- A template for a set of objects that have state and behaviour
102
Q
An object
A
- An instance of a class
- A real-world entity and holds attributes and operations
103
Q
Derived class
A
- 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
Q
Inheritance
A
- A derived class inherits all the attributes and operations from its superclass
105
Q
Unified Modelling Language
A
- 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
Q
Class diagram
A
- Describes the classes to achieve the tasks that the system must perform and the relationships between them
107
Q
Object diagram
A
- 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
Q
Use case diagram
A
- Describes the tasks which the system must help to perform
- Describes the requirements of a system
109
Q
State diagram
A
- 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
Q
Sequence diagram
A
- 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
Q
Activity diagram
A
- 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
Q
Communication diagram
A
- 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
Q
Backtracking
A
- Going back to a previously found successful match in order to continue a search
114
Q
Instantiation
A
- Giving a value to a variable in a statement
115
Q
Predicate Logic
A
- A branch of mathematics that manipulates logical statements that can be either True or False
116
Q
Variable (declarative languages)
A
- Written as a sequence of letters and digits, beginning with a capital letter (or underscore)
- Eg. A, Male, _male
117
Q
Goal
A
- A statement we are trying to prove either True or False
118
Q
Reasons to use high-level languages
A
- Reflects type of problem
- Allows use of mathematical functions
- Portability
- Uses library routines
- Complexity of problem
- Easy to maintain
119
Q
Reasons to use low-level languages
A
- 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
Q
Advantages of library routines
A
- 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
Q
Machine Code
A
- 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
Q
Assembly Language
A
- 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
Q
Why registers are important
A
- 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
Q
JUMP instruction
A
- 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
Q
Index register
A
- 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
Q
Opcode
A
- The nmemonic part of an instruction
- … that indicates what it is to do (eg ADD)
127
Q
Operand
A
- The address field in an instruction which holds data or address to be used
128
Q
Mnemonic
A
- 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
Q
Flow control
A
- The order in which instructions are executed
- The order may be altered by a JUMP instruction / conditional JUMP instruction
130
Q
Immediate addressing
A
- 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
Q
Direct addressing
A
- 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
Q
Indirect addressing
A
- 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
Q
Indexed addressing
A
- 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
Q
Relative addressing
A
- 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
Q
Symbolic addressing
A
- -The use of characters to represent the address of a store location (in the operand)
136
Q
Purpose of translators
A
- To convert source code into object code
- To detect errors in source code
137
Q
Compiler
A
- 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
Q
Interpreter
A
- 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
Q
Assemblers
A
- 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
Q
Advantages of compilers
A
- Results in an executable code that requires no further translation
- Therefore programs execute faster than if they were interpreted
141
Q
Disadvantages of compilers
A
- 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
Q
Advantages of interpreters
A
- 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
Q
Disadvantages of interpreters
A
- 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
Q
Interpreter error handling
A
- 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
Q
Source code
A
- 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
Q
Object code
A
- Could be machine code or intermediate code
147
Q
Intermediate code
A
- 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
Q
Advantages of intermediate code
A
- Allows sections of program to be written in different high-level languages
- Platform independent so improves portability
- Is compiled so is error free
149
Q
Disadvantages of intermediate code
A
- 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
Q
Virtual machine
A
- Intermediate code is run using an interpreter (for the specific computer)
151
Q
Reasons to compile to machine code
A
- Compiled programs are executable, run quickly, do not need a translator to run and use less memory
152
Q
Tasks of an assembler
A
- 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
Q
Library routines
A
- Are pieces of software which perform common tasks such as sorting and searching
- Are already compiled
154
Q
Reasons to use library routines
A
- 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
Q
Linker
A
- 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
Q
Loader
A
.- Copies modules into memory
- … from backing store
- … when program is to be run
- Handles addresses ready for execution
157
Q
Linking errors
A
- 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
Q
Compiled code may not be executable…
A
- As it may need to be linked to library routines (Eg. library for I/O routines or for mathematical functions)
159
Q
Lexical analysis
A
- 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
Q
Tokens
A
- A token is a fixed length string of binary digits
161
Q
Syntax analysis
A
- 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
Q
Example Syntax errors
A
- 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
Q
Code generation
A
- 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
Q
(code) Optimisation
A
- Makes code as efficient as possible
- Improves processing speed
- Reduces number of instructions
- Programmer can choose between speed and size
165
Q
Operating System (OS)
A
Software that handles the interface to the hardware and manages resources
166
Q
Features of operating systems
A
- 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
Q
Management of hardware resources
A
- Management of memory (partitioning, allocating memory, virtual memory)
- Scheduling of jobs (including interrupt handling)
168
Q
Interrupt
A
- 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
Q
Reasons to use interrupts
A
- 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
Q
Sources of interrupt
A
- 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
Q
Hardware interrupt
A
- 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
Q
Software interrupt
A
- An interrupt generated within a processor by executing an instruction
- E.g.. Divide by zero
173
Q
Processing interrupts
A
- 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
Q
Resuming after interrupt
A
- 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
Q
Purpose of scheduling
A
- 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
Q
High level scheduler
A
- 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
Q
Medium level scheduler
A
- 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
Q
Low level scheduler
A
- Controls the movement of jobs between main memory and secondary storage
179
Q
Priority
A
- An order of importance
180
Q
Job states
A
- Ready
- Running
- Blocked
181
Q
Priorities within the job queue
A
- 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
Q
Reasons for jobs leaving the running state
A
- 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
Q
Scheduling algorithms
A
- Round robin
- System of priorities
- Length of job
- First come, first served
- Multi-level feedback queues
184
Q
Round robin
A
- 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
Q
Multilevel feedback queue
A
- 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
Q
Time slice (also called quantum)
A
- 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
Q
Why memory management is needed
A
- 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
Q
Virtual memory
A
- 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
Q
Paging
A
- 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
Q
Segmentation
A
- 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
Q
Disk threshing
A
- 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
Q
Spooling
A
- 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
Q
Reasons to use spooling
A
- 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
Q
Print spooling
A
- 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
Q
Uses of spooling
A
- 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
Q
Boot file
A
- 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
Q
Purpose of the boot file
A
- Provides personal settings
- Initialises operating system
- Passes control to operating system (by setting program counter)
- Checks hardware
- Checks memory
198
Q
Booting up
A
- 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
Q
Power-On-Self-Test (POST)
A
- 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
Q
Duties of BIOS during POST
A
- 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
Q
BEEP codes
A
- 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
Q
File Allocation Table (FAT)
A
- A map of where files are stored on the hard disk
203
Q
Use of the FAT
A
- Updated by the OS when files are saved / deleted
- Used by the OS when files are accessed
204
Q
Contents of the FAT
A
- 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
Q
Features of Von Neumann
A
- 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
Q
Fetch-Execute Cycle
A
- 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
Q
Execution of JUMP instruction
A
- Changing contents of PC (to address part of instruction)
- Copy address part of instruction
- … in CIR to PC
208
Q
Registers
A
- Location in the processor used for a particular purpose
- Temporarily stores data / control information
- Allows very high speed access
209
Q
Program Counter (PC)
A
- 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
Q
Memory Address Register (MAR)
A
- Receives address of instruction (from PC)
- Holds address of data/instruction to be used
- Receives operand part of instruction from CIR
211
Q
Memory Data Register (MDR)
A
- 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
Q
Current Instruction Register (CIR)
A
- 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
Q
Accumulator
A
- Temporary storage in the Arithmetic Locic Unit
- Holds data being processed during calculations
- Deals with the input / output in the processor
214
Q
Parallel processor system
A
- 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
Q
Advantages of parallel processors
A
- 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
Q
Disadvantages of parallel processors
A
- 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
Q
Array (Vector) Processor system
A
- 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
Q
Advantages of array processors
A
- 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
Q
Disadvantages of array processors
A
- High price of array memory systems
- Increased code complexity
220
Q
RISC
A
- 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
Q
CISC
A
- 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
Q
Advantages of RISC
A
- Programs run more quickly due to less complicated instructions / circuit and more easily pipelined
223
Q
Disadvantages of RISC
A
Programs take up more memory because more instructions are required to complete a task (than with CISC)
224
Q
Advantages of CISC
A
- Programs take up less space on backing store and in main memory
- … as fewer instructions required for task
225
Q
Disadvantages of CISC
A
- Programs run more slowly
- … due to the more complicated instructions / circuit.
226
Q
Mantissa
A
The part of a floating-point number which represents the significant digits of that number (and the sign of the number)
227
Q
Exponent
A
- 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
Q
Reasons to normalise floating-point numbers
A
- 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
Q
How to normalise floating-point numbers
A
- 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
Q
Floating-point binary accuracy and range
A
- 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)
