Computer System

Computer System

1. Processor

   • Controls the operation of the computer and performs its data processing functions
   • One of the processor's functions is to exchange data with memory, for this purpose, it typically makes use of two internal registers: a memory address register (MAR) which specifies the address in memory for the next read or write; and a memory buffer register (MBR), which contains the data to be written into memory or which receives the data read from memory. (Fig.1.1 P30)   
   • Process
     • Unit of resource allocation and execution, with its own memory (address space), file descriptors, file system context. It encapsulates one or more threads.
     • Instruction Cycle (fetch/execute) processor fetches the next instruction to execute from the PC and loads it in the instruction register (IR) 
     • Thread
       • A single unit of execution. With Independent fetch/decode/execute, unit of scheduling, and operating in some address space.
       • User-Level Threads
         • Threads created and managed by the user using the thread library. 
         • Advantages include that there is no mode switching when managing threads, as all the thread managing is done within user space, schedulling can also be application specific and these applications can run on any OS.
         • Disadvantages are however that typically, system calls are blocking. As a result, when a ULT executes a system call, not only is that thread blocked, but also all of the threads within the process are blocked.In a pure ULT strategy, a multi-threaded application can't take advantage of multiprocessing. A kernel assigns one process to only one processor at a time. Therefore, a single thread within a process can execute at a time. In effect, we have application-level multiprogramming within a single process. While this can result in a significant speedup of the application, there are applications that would benefit from the ability to execute portions of code simultaneously.   
       • Kernel-level threads
         • All the work of thread management is done by the kernel. There is no thread management code in the application level, simply an application programming interface to the kernel thread facility   
         •  First, the kernel can simultaneously schedule multiple threads from the same process on multiple processors. Second, if one thread in a process is blocked, the kernel can schedule another thread of the same process.    Another advantage of the KLT approach is the kernel routines themselves can be multi threaded.   
         •    The principal disadvantage of the KLT approach compared to the ULT approach is that the transfer of control from one thread to another within the same process requires a mode switch to the kernel.   
   • Concurrency
     • Can happen when there is Mutual Exclusion.
     • Semaphores
       • An integer value used for signalling among processes. 
       • Only three operations may be performed on a semaphore, all of which are atomic: initialize, decrement and increment. 
       • The decrement operation may result in the blocking of a process, and the increment operation may result in the unblocking. 
       • Similarly binary semaphores do the same but with 0 being blocking and 1 unblocking.
       •  Problems: Could be difficult to produce a correct program - the semWait and semSignal operations could spread all over the program... difficult to completely access the overall affect.   
     • Monitor
       • A programming language construct that encapsulates variables, access procedures and initialization code within an abstract data type. 
       • The monitor's variable may only be accessed via its access procedures and only one process may be actively accessing the monitor at any one time. The acess procedures are critical setions. A monitor may have a queue of processes that are waiting to access it.
     • Event flags
       •  A memory word used as a synchronisation mechanism.  
       • Application code may associate a different event with each bit in a flag.
       • A thread can wait for either a single event or a combination of events by checking one or multiple bits in the corresponding flag.  The thread is blocked until all of the required bits are set (AND) or until at least one of the bit is set (OR) 
     • Mailboxes/Messages
     • Spinlocks
       • Mutual exclusion mechanism in which a process executes in an infinite loop waiting for the value of a lock variable to indicate availability.  
     • Race Condition
       • When multiple processes or thread read and write a shared data so that the final value depends on the order of execution of the instruction.
     • Deadlock
       • A situation in which two or more processes can't execute each waiting for the other to do something.
       • Approaches to overcome it
         • Prevention
         • Avoidance
         • Detection
     • Livelock
       • A situation in which two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work.
     • Mutual Exclusion, Automic operation & Critical Condition
       • Critical section - A section of code within a process that requires access to a shared resource and that must not be executed while another process is in a corresponding section of code.
       • Atomic operation: Smallest executable section which can't be interupted
       • Mutual exclusion: The requirement that when a process is in critical section using a shared resource, no other process can be in a critical section that access any of those shared resources. The ability to exclude all other processes from a course of action while one process is granted that ability.
     • Starvation
       • A situation in which a runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it never is chosen :(

2. Operating System

   •   Program development: editors, debuggers; application program development tools.Program execution: Instructions and data must load into main memory, I/O devices and files must be initialized, other resources must be prepared. The OS handles these schedulingAccess to I/O devices: Each I/O device requires its own peculiar set of instructions or control signals for operation. OS provides a uniform interface that hides these details so programmers access devices using simple read & writes.Controlled access to files.System access: for shared or public systems, the OS controls access to the system as a whole and to specific system resourcesError detection and response: internal and external hardware errors, etc.Accounting: usage statistics for resources and performance monitoring.Instruction set architecture (ISA): The ISA defines the repertoire of machine language instructions that a computer can follow. The interface is the boundary between hardware and software. Application binary interface (IBA) The ABI defines a standard for binary portability across programs. The ABI defines the system call interface to the operation system and the hardware resources and services available in the system through the ISA. Application programming interface (API): The IPA gives a program access to the hardware resources and services available in a system through the user ISA supplemented with high-level language library calls. Any system calls are usually performed through libraries.     
   • Convienence (Kernel)
     • Manages I/O operations with the aid of firmware and device drivers. (determines which gets access to where) 
   • Efficiency
     • Resource manager
       • OS maintains tables to keep track of resource information: memory, I/O file and process tables
       • manages and schedules processes
         • Three factors to be considered: 1. Fairness: This is especially for jobs of the same class. 2. Differential responsiveness 3. Efficiency: Maximize throughput, minimize responsiveness & accommodate as many users as possible.
         • Scheduling algorithms
           • Criteria to check which algorithm is best for: 1.User oriented - performance *turnaround time - subission to completion *response time - Interactive processes *deadlines
           • 2. System orientated *Throughput - maximize the number of process completed in unit of time *processor utilization - reduce idle time
           • Other:  predictability fairness enforcing priorities (could result in starvation) balancing resources
           • RoundRobin
             • Employs a circular queue with a timer to allow each process to execute in the processor for a set amount of time.
           • FCFS
           • SPN
           • SRT
           • Higher Response ratio next
       • File management
     • Distributive processing and process communication
     • Networked Systems
   • Ability to evolve

3. Memory Management

   • 5 Principles:  1. Process Isolation 2. Automatic allocation and management 3. Support of modular programming 4. Protection and access control 5. Long-term storage
   • Requirements Relocation Protection Sharing Logical Organisation Physical Organisation
   • Virtual Memory
     • Meets 4 of the requirements for memory management. It allows programs to address memory from a logical point of view without regard to the amount of main memory physically available.
     • Thrashing
       • When VM is a constant state of paging - result is page faults and deterioration of performance.
   • Paging and using VM
     • (1)All memory references within a process are logical addresses that are dynamically translated into physical addresses at runtime. (2) A process can be broken into a number of pieces and these pieces need not to be contiguously located in main memory during execution. 
     • The combination of (1) &(2) dynamic run-time address translation and use of page or segments permit it to not be necessary that all pieces of a process to be loaded in main memory during execution. 
     • If the piece that holds the next instruction to be fetched and the piece that holds the next data location to be accessed are in the main memory, then at least some execution may proceed.
     • Page tables
       •   In this case the page entries become more complex because only some of the pages of a process may be in main memory; a bit is needed to check if the page is present (P) in main memory or not. If so then the entry also includes the frame number of that page.  The page table entry includes (M) modify bit, indicating whether the content of the page have been altered or not since last loaded. Other controls such as protection or sharing may be present in the table too.  
       •   The page table entry includes (M) modify bit, indicating whether the content of the page have been altered or not since last loaded. Other controls such as protection or sharing may be present in the table too.   
       • In the case of Paging and VM, page tables are more complex because only some pages may be loaded into main memory; a bit is needed to check if the page is present (P) in the main memory or not. If so then the entry also includes the frame number of that page.The page table entry includes (M) modify bit, indicating whether the content of the page have been altered or not since last loaded. Other controls such as protection or sharing may be present in the table too.   
       • The basic mechanism for reading a word from memory involves the translation of a virtual, or logical, address consisting of page number and offset, into a physical address consisting of frame and offset, using a page table
       • Because the page table is of variable length, depending on the process' size, it can't be held in a register, its held in the main memory. A register holds the starting address of the page table for a process that is running.  Each process can occupy huge amounts of virtual memory; to overcome this, most virtual memory schemes store page tables in virtual memory rather than real memory.  
     • Inverted page tables
       • Inverted page tables are an alternative to normal page tables. The page number portion of a virtual address is mapped into a hash value using a simple hashing function.  The hash value is a pointer to the inverted page table, which contains the page table entries. There is one entry in the inverted page table for each real memory page frame rather than one per virtual page. Because more than one virtual address may map into the same hash table entry, chaining technique is used for managing overflow.   
   • Memory Partitioning
     • Multiprogramming requires ability to run multiple programs simultaneously which equals into memory partitioning
     • Fixed Partitioning
       • Memory Partitioned into regions with fixed boundaries - static sizes. 
       • Processes of smaller size than the partition still occupy one partition wasting internal space aka internal fragmantation
       • Maximum number of processes is fixed
       • Using unequal partition lessens the problem but doesn't fix it.
     • Dynamic Partitioning
       • Partitions created dynamically - size as required - variable length and number
       • Could lead to inefficient use of memory - empty blocks which are of no use - external fragmentation
       • Compaction used to get around fragmentation (similar to defragging). This wastes processor time.
     • Simple Paging
       • Main Memory is divided in equal-sized frames
       • Process also divided in similar sized frames/pages - and load to memory frames; contiguity not a requirement because of logical addressing(overcomes external fragmentation)
       • Page Tables
         • Are used to keep track of all the pages in a process. Each process has a page table and they are stored into main memory. Each page table entry contains the frame number of the corresponding page in main memory
     • Simple Segmentation
       • Program divided into unequal segments - maximum segment length is constant
       • No internal fragment but external fragmentation is a possibility

4. File Storage

   • File system architecture
     • Device Drivers
       • Communicate directly with peripheral devices or their controllers or channels.  - It's responsible for starting I/O operation on a device and processing the completion of an I/O request.  - Typical devices controlled are disk and tape drives.
     • Basic file system
       • Or Physical I/O level. It's the primary interface with the environment outside of the computer system.
       •  - It deals with blocks of data that are exchanged with disk or tape systems.
       •  - it is concerned with the placement of those blocks on the secondary device and on the buffering of those blocks in main memory.
     • Basic I/O supervisor
       • It's responsible for all file I/O initiation and termination.   - It is part of the OS.
       •  - Basic I/O supervisor selects the device on which file I/O is to be performed
       •  - It is also concerned with scheduling disk and tape accesses to optimize performance
     • Logical I/O level
       • or Access method, enables users and applications access to records.  - Thus whereas basic file system deals with blocks of data, logical I/O module deals with file records  - It provides a general-purpose record I/O capability and maintains basic data about files.
     • FAT32
       • Is a hard drive formatting system most popular for its compatibility. It's good for portable storage, and supported by more tools 
       • It has smaller partition size (on XP 32Gb). Smaller file size (4Gb). FAT32 offers little in the way of security. If you have access to a drive you have access to the whole drive. No file compression. Prone to errors.
     • NTFS
       • New Technology file systems. Another hard drive formatting technology which offers advantages over FAT32:  - File and folder level security  - Disk compression  - Disk Quota per user  - Encryption
       • NTFS introduced metadata for objects on the file system, allowing many more file system capabilities, such as security configuration and auditing information.  A subset of the metadata for each file is stored in the master file table (MFT), which is used to quickly see free space on a volume, determine where to place new files, and cut down on fragmentation. 
       • It also has Recoverability - it is able to reconstruct disk volumes and return them to a constant state. It does so using a transaction-processing model for changes to the file system; each significant step is treated as an atomic action that is either entirely performed or not performed at all.
       • Sector
         • Smallest physical storage unit on a disk - usually 512 bytes
       • Cluster
         • - one or more contiguous sectors  power of 2 sectors.  - Fundamental unit of allocation in NTFS.  - The use of clusters means that NTFS can operate on non-standard disks.  - Clusters also mean that file systems on larger disks are more efficient, because cluster size increases meaning there are fewer items to manage
       • Volume
         • A logical partition on a disk, consisting of file system information, files and unallocated space. An entire volume can span over multiple disks.
       • Partition Boots sector
         • Up to 16 sectors long, It boots start up information, and information about the volume layout and file system structures.
       • System Files
         • MFT
           • Information about all directories and files in the volume.  - Relational database structure.
         • MFT 2
           • Like a backup MFT. A mirror of the first few rows of the MFT, used to guarantee access to the volume in case of a single-sector failure in the sectors storing MFT
         • Log file
           • A list of transaction steps concerning the file system. Like Journalling, it keeps a log of changes made to files on the volume. Programs such as desktop search can read the journal to identify what files have changed.
         • Cluster bitmap
           • marking which clusters are in use.
         • Attribute definition table
           • Things that are not part of the file itself - access attributes, owner, filename etc
   • File Allocation
     • Alternatives
       • Blocks
         • Small fixed portions provide greater flexibility. They may require large tables or complex structure for their allocation. Contiguity has been abandoned as a primary goal; blocks are allocated as needed.   
       • Variable, large contiguous portions
         • Will provide better performance, the variable size avoids waste, file allocation tables are small however space is hard to reuse
     • Methods
       • Contiguous Allocation
         • Preallocation, variable size portions, needs compaction to overcome eternal fragmentation
       • Chained allocation
         • Space allocated block by block, each block points to the next, requires consolidation
       • Indexed Allocation
         • An index to the block that make up a file is kept in another block to separate to the file rather than in FAT. It may use block by block or variable sized portions.