|OS||A collection of
computer programs which integrate the software and hardware resources of the
computer, and make them available to the user in a productive, timely and
It provides three kinds of services:
1. Accepts commands from the user and the user's programs.
2. Manages, loads and run programs.
3. Manages the hardware resources of the computer.
than one processes can exist in the memory and be concurrently executed.
1. Physical resource sharing.
2. High utilization of resource.
3. Allows for modular construction of systems.
4. Allows individual users to work on several tasks simultaneously.
CPU running several processes. Different processes share CPU with two
1. Non-pre-emptive scheduling: a process runs until it must wait, most probably for IO requests.
2. Pre-emptive scheduling: using a regular clock interrupt, the CPU is switched between difference processes.
|Process||A program in execution, including an executable program, its data and stack, its PC and other information needed to restart it. It can be further broken down into threads.|
|Thread||A light-weigth sub-process running within a process. It can be executed concurrently with other part of the process i.e. other threads.|
|Process table & process control block (PCB)||When a process is interrupted, its current state especially its volitile environment such as register values must be saved so that it can be resumed later. This information is saved in a process control block. A process table consists many process control blocks.|
|Parent process||A process which creates other processes is parent process, and the created processes are child processes. Each process has its own identification. Basis of client-server systems.|
|Long-term / high-level scheduling||Determines
which job on the waiting queue to be admitted to the system for processing.
It is used for batch job processing, but not relevant for interactive
environments. It is invoked every time a job is finished, to exam the queue
of waiting jobs.
If there is not enough memory, it may swap jobs from memory to disk and vice versa.
|Short-term scheduling / Dispatcher||Select
from the processes already in memory the next one to run. It is invoked when
the current process stops. Uses non-pre-amptive and pre-emptive scheduling.
Pre-emptive scheduling is better for interactive systems, leads to more
efficient use of resources, but has higher overhead.
After it has selected the process to be run, it will load in all the saved values for the registers from the PCB. The last register to be loaded is the PC. This activity is called context switching.
|Non-pre-emptive scheduling algorithms||1. FIFO. 2. Shortest-job-first. 3. Priority scheduling|
process get the same time slice or quantum to run. All runnable processes are
maintained in a circular queue (linked list).
Advantages: Simple, quite fair. Reasonably good on maxmimum thoughput. No CPU starvation.
Disadvantage: There is not priority issue. Processes that uses IO frequently are panalized.
|Multilevel feedback queue||Processes are give initial priority levels. Processes in the same priority group are maintained with round robin. To prevent CPU starvation of some low-priority jobs, they can have a temporary priority boosting. After they have their turns of CPU time, their priorities are dropped back to normal.|
|Dynamic priority scheduling||The other way is to assign priorities to processes dynamically. The system calculates a dynamic priority based on the ratio of the CPU time consumed by a process to the total time that a process has been in the system. The smaller the ratio, the higher the priority.|
Maximize the memory available to multiple processes;
2. Respond quickly to memory changing demand from individual processes;
3. Prevent unauthorized change to a process's memory region;
4. Allow the sharing of program portions like editors and compilers;
5. Allow program relocation during run time.
addresses are transformed or mapped to physical addresses by adding base or
fence register value. Limit register stores the upper bound of the allowed
Two ways of program relocation:
1. Static relocation: base register value is fixed once the program is loaded.
2. Dynamic relocation: base register value can be changed each time the program is relocated.
|Internal fragmentation||The part of unused memory within a memory segment. Happens for fixed partition method.|
|External fragmentation||The part of unused memory between memory segments. Happens for variable partition method.|
|Multitasking with memory partition -- fixed partition||Partition of memory is fixed. Major problem is internal fragmentation.|
|Multitasking with memory partition -- variable partition||More
flexible than fixed partition. Additional overhead to keep a table of
available memory blocks. When a new job arrives, that table is searched for a
place to load it. Can cause external fragmentation.
Two ways: 1. Best fit. 2. Worst fit (largest fit) -- always choose the largest available memory. 3. First fit.
program address from physical address using dynamic relocation. Makes the
computer to appear to have more memory than physically. It divides program
into small sections which can be stored in different parts of memory. By only loading the currently running
sections into memory, it allows the execution of a program larger than the
Virtual memory can be implemented with paging or fragmentation.
are divided into sections called pages. Physical memory is divided into
sections called frames, which are of the same size as pages. This eliminates
external fragmentation. Physical address is converted into a page number plus
a page offset.
Page size is hardware-defined. Usually in the power of 2 (512, 1024, etc.). Commonly 2 ~ 4k. Large page size increases internal fragmentation but reduces overhead of page tables.
During execution, some pages of the program are present in memory, others are on secondary storage.
process has its own page table, which contains an unique index of a program's
page numbers and their corresponding frame numbers. It also indicates with
the valid/invalid bit whether the page is in memory or on disk.
The address of the table is stored as a member of the PCB. If the page table is too large it itself may be paged too.
page table needs to be accessed with high spead, high-speed memory called
associative memory is provided for part of the page table . It only stores
page numbers of active pages. When the OS searches for a page number, it will
search the associative memory first. If not found, it will then search the
page table in normal memory.
Hit ratio is the percentage of times that a page number can be found in associative memory.
|Page loading and swapping||If
the required page of program is not found in the memory, an interrupt called
PAGE FAULT will happen. Required page will be loaded in memory, and the page
table will be updated.
If all allocated frames are used, then a page which is already in memory will be replaced by the newly required one. This is called page swapping. If the evicted frame has been modified, it should be written on to disk before replaced. Otherwise it will just be overwritten by the new page.
|Page replacement algorithms||1.
Least recently used.
2. Least frequently used. Count needs to be aged.
3. FIFO. Heavily used pages may be replaced.
4. Use a reference bit which is set when a page is used, and periodically reset by system.
5. Not used recently -- modification of least recently used.
6. Second chance algorithm -- modification of FIFO.
|Program locality||Only a small number of pages from a few modules in the program are in use at one time. If the current working set can be properly tracked by the OS, than always only a small part of the program pages is needed to be loaded into the memory.|
|Working set||The minimum amount of primary memory frames required for a program to make effective progress without excessive paging. Some OS maintain estimates of all running process's working sets.|
|Thrashing||When the number of frames allocated to a process is less than the working set, PAGE FAULT interrputs will happen so frequently that most activity is paging in and out while CPU is blocked waiting for IO.|
is divided into segments which reflects the logical division in programs and
data, such as segments for global variables, procedure call stack, etc. Each
segment may vary in size. Program address is segment number plus segment
The mapping of logical address to physical address is maintained in segment table. Each segment is a logical entity of which programmer is aware, which facilitates protection and sharing of procedures and data
|Segmented/demand-paged memory allocation||Large segments could also experience oversize problem. They can be paged too. Each segment can have its own page table. This technique combines the logical benefits of segmentation with the physical benefits of paging. Eliminates external fragmentation and minimises internal fragmentation.|
|Advantages of virtual memory technique||1.
Paging and segmentation can be extended to include sharing of code
pages/segments (i.e. pointers to the same frame), and protection (i.e.
associate a modify-allowed bit with each frame). Both simple to implement in
2. Less IO resources. Only currently used program sections is loaded.
3. More programs can be loaded and run concurrently, increasing the degree of multiprogramming.
|Computer performance enhancement||1.
Faster CPU and multiple CPUs.
2. More and faster memory and advanced cache techniques.
3. Wider and faster instruction/data path i.e. buses.
4. Faster disk access.
5. Faster and better-quality display.
1. clock speed
2. instruction set
3. pipeline techniques and superscalar architecture.
|Reduced Instruction Set Computer (RISC)||Among
all CISC instructions, only a small amount of instructions are frequently
used. Complex instructions are avoided by programmers and compiler
RISC are achieved with
1. Register-based instructions, typically with Load mem and Store mem as the only instruction that reference primary memory.
2. Fixed-length-and-format instructions simplify the Control Unit design. Instruction fatch and decode can be done in parallel.
3. Limitted addressing mode.
4. Large register bank.
|Pipeline/Scalar processing||Pipelining overlaps the the fatch and execute cycle, but the instructions are still executed one at a time.|
|Superscalar processing||Executes several instructions at the same time with multiple execution units. It is highly complex, with problems such as instructions completing in wrong order, register conflict, etc.|
More memory: bigger buffer can be used to retrieve more data from disk.
Because of the locality rule, more needed data and instructions are likely to
be found in the buffer, thus reducing IO time. More memory also provides more
support for display.
2. Faster memory: reduces the time of Fatch and Store operations, thus significantly improves performance.
3. Wider access path: more bytes can be read and written at the same time.
4. Synchronous and read-ahead memory operation.
5. Memory interleaving: reading different parts of memory simultaneously.
6. Improved cache technology: Amount, speed and levels of cache all increases, including on-chip cache, more level-2 cache, etc.
7. RAM disk: large amount of slower RAM are used as an intermediary between the hard disk and the primary memory.
|Memory improvement -- cache||A
small amount of faster memory between CPU and primary memory.
Writing strategies: 1. Write through. 2. Write back.
|Bus technology||Wider bus and new bus standard which allows higher bus clock speed.|
|Disk access improvement||1.
Increased data density.
2. Increased rotation speed.
3. Disk scheduling algorithm optimizes data retrieval for multitasking systems.
4. Buffer and cache.
Faster screen refresh rates.
2. Large amount of on-board memory and sophisticated processor on the graphics accelerators.
3. Dedicated local buses.
Clock speed: inaccurate due to pipelining and superscalar processing.
2. MIPS: more accurate, but affected by RISC v/s CISC.
3. Benchmarking programs: most accurate, but task dependent.
a normal program, save its current state, jump to the interrupt handling
program. When finished, resume the interrupted program. So an interrupt is
like a subroutine.
The use of interrupts:
1. External event notifier.
2. Abnormal event notifier.
3. Task completion signal.
4. Allocating CPU time.
5. Software interrupts.
|Two models of distributed systems||client-server and peer-peer.|
|Motivation of distributed systems||1.
2. Access to remote data
3. Computational speedup
|Model of communication link||sender, receiver, medium, message|
Simplex: one-direction information flow, such as TV broadcast.
2. Half duplex: allows information to flow on both directions, but one at a time.
3. Full duplex: allows information to flow on both directions meantime.
|Bandwidth||The upper limit of information transmission frequency, which determines the maximum amount of information that can be transmitted per unit time. The greater the bandwidth, the greater amount of the information.|
multiple channels of information on one communication line at the same time.
Two types of multiplexing:
1. Time division: giving each channel a time slice.
2. Frequency division: dividing the bandwidth of the communication line into different subchannels.
Noise: caused by thermal, crosstalk, impulse, etc.
2. Attenuation: signal strength derease over distance. Corrected by repeaters and amplifiers.
3. Delay distortion: high-frequency part of signal travels faster than low-frequency part.
Wires, including single wire, twisted pair and boundled wires.
2. Co-axial cable - can be divided into several channels.
3. Optical fibre.
4. Microwave (including satellite).
6. Infrared light.
|Digital data||Has only two possible values: 0 or 1. Data is coded in binary digits.|
|Analog data||Can be any value of a continuous spectrum.|
|Characteristics of analog signal||Continuous signal in form of sine wave. Characteristics: amplitude, phase (relative starting point of the wave cycle) and frequency.|
|Analog => digital||pulse code modulation|
|digital => analog||modem (modulate - demodulate)|
|Modulation techniques||Amplitude modulation, frequency modulation and phase modulation.|
|Serial & parallel data transmission||1.
Serial data transmission: us one channel to transmit data bit by bit. Start
and stop bits needed. Transmitter and receiver must agree on framing.
2. Parallel data transmission: using nine channels to transmit nine bits at a time (eight for data and one for control).
|Asychronous & synchronous communication||1.
Asynchronous communication: data is divided into characters. Each character
is framed with a start bit and a stop bit, altogether 10 bits. Character
stream can be intermittent.
2. Synchronous communication: data is sent continuously. When there is no data, just send a group of synchronization bits in a unique pre-defined pattern repeatedly. Start of data is indicated by pre-defined pattern too.
or more computers connected via a communication medium. It is made up
2. Network interface cards.
3. Network hubs and cabling.
4. Network operating system.
|Goals of Networks||1.
Sharing of resource.
2. Distribution of processing functions and interprocess communication.
3. Opportunity for centralized management control.
4. Compatibility of dissimilar equment and software.
5. Increased perfromance with reduced cost.
Geographically: LAN, MAN, WAN.
2. Ownership: public and private.
3. Transmission mechanism: switched and broadcast.
|LAN, MAN & WAN||1.
WANs are used when computers are distant to each other. Generally mash topology is used.
2. LANs are generally used in one or several buildings.
3. WANs may be used across an area of city.
LANs and WANs offer higher transmission rate than WANs.
Circuit switched: a dedicated network through nodes are maintained for
duration of call.
2. Message switched: a dedicated channel path is maintained for an entire message.
3. Packet switched: data is transmitted in chunks from node to node. No dedicated circuit is required.
4. Virtual circuit switched: sequential arrival of data guaranteed.
set of rules governing the way two entities exchange data. Functions of data
transmission protocol include:
1. Flow control.
2. Formatting of data.
4. Error handling.
|Examples of protocols||1.
TCP/IP: TCP (transmission control protocol) provides error handling and
sequencing, while IP (Internet protocol) provides addressing and formatting
of data. Designed for reliable end-to-end connection.
2. IPX/SPX: Novell Netware transport protocol.
3. SNA protocol suite: layered model from IBM.
4. OSI model from ISO.
|OSI (open systems interconnection)||Identifies
all factors that must be standardized in order for two computers to
communicate completely and successfully at every possible level.
It has seven layers, each layer presents an attempt to isolate a single factor that is relevant to communicate between computers. Each layer only communicates with adjacent layers.
Intention is to create a single protocol standard that would be used internationally for all computer communications.
|Type of LANs||1.
Peer to peer.
3. Computerized branch exchange (PBX).
Office automation: sharing local resource and organizational data, providing
access to WAN, using groupware.
2. CAD/CAM: high tranmission rate of LAN enables transmission of large amount of data in CAD. Users can work in group and share their drawings and local plotter. CAM controls assembly lines, robots and machinery.
3. Education: group access to education software, allow students to collaborate, library on-line catalog, abstracts and journal papers, on-line marking and feedback.
2. Network topology
3. Mac protocol
4. LAN software
Bus/tree topology: no closed loops, all stations attach directly to the
medium. Transmission can be received by all stations.
2. Ring topology: a set of repeaters joined by point-to-point links in a closed loop.
3. Star topology: each station connects directly to the central hub.
|Medium access control protocols||Medium access control protocol is needed because of shared medium. There are two major protocols:CSMA/CD and token passing method.|
sense multiple access/collision detection. Used by bus topology. Main
1. Listen to network.
2. Wait if there is other signal. If not send data.
3. After transmission, continue to listen.
4. If collision detected, wait for a random amount of time, then transmit again.
|Token passing access method||There
are two types: token ring access method and token bus access method. Both use
a token circulating through all stations:
1. At one time only one station can be transmitting.
2. When one station who wants to send data receives a free token, it will mark it as busy, then append data packet to it.
3. The receiver acquires the data and marks the token as received.
4. The sender removes the packet and marks it free.
In a ring topology network, tokens are circulated one by one along the ring. In a bus topology network, tokens are circulated from the highest address to the lowest.