OPS 1-4 Theory

Operating system

Chief software component of the computer system; manages all hardware and software, acts as an interface between user and system, controls and manages computer resources, schedules tasks, manages storage, and makes the computer system convenient to use effectively.

Components of a computer system

Hardware, Operating system, Application programs, and Users.

Hardware

Provides basic computing resources such as CPU, memory, and I/O devices.

Operating system role

Controls and coordinates the use of the hardware among the various application programs for the various users.

Application programs

Define the ways in which the system resources are used to solve the computing problems of the users; examples include compilers, database systems, video games, and business programs.

Users

People, machines, or other computers.

Three types of program

User / application program, System program, Driver program.

User / application program

Programs used by users to perform tasks; e.g. MS Office.

System program

Interface between user and computer; e.g. defragmentation, BIOS, system restore.

Driver program

Communicates an I/O device with the computer.

Four sub-system managers of OS

Memory manager, Processor manager, Device manager, File manager.

Network manager

Coordinates the services required for multiple systems to work cohesively together and manages shared network resources such as memory space, processors, printers, databases, and applications.

User Command Interface

Provides user communication with the operating system; user issues commands to the OS; unique to each operating system and may vary between versions.

Two primary user command interface types

Graphical User Interface (GUI) and Command Line Interface (CLI).

Tasks of a manager

Monitor its resources continuously; enforce policies determining who gets what, when, and how much; allocate the resource; de-allocate the resource.

Memory manager

In charge of main memory (RAM).

Functions of the memory manager

Preserves space in main memory occupied by the OS; checks validity and legality of memory space requests; allocates memory to processes and de-allocates it when they are done; sets up a memory tracking table; tracks usage of memory by sections.

Processor manager

In charge of allocating the Central Processing Unit (CPU).

Functions of the processor manager

Tracks process status; handles jobs as they enter the system through the Job Scheduler; manages creation and deletion of processes; manages each process within those jobs through the Process Scheduler.

Device manager

In charge of monitoring peripheral devices, channels, and control units.

Functions of the device manager

Chooses the most efficient resource allocation method; allocates and de-allocates devices; consists of policies and procedures for handling I/O devices; accepts input from user and gives corresponding output.

File manager

Manages files stored on disk.

Functions of the file manager

Tracks every file in the system; controls user/program modification restrictions; enforces user/program resource access restrictions; allocates resources by opening files and de-allocates resources by closing files.

Cooperation issues

No single manager performs tasks in isolation; each element of an operating system performs individual tasks and harmoniously interacts with other managers.

Cloud computing

Practice of using Internet-connected resources to perform processing, storage, or other operations while the operating system maintains responsibility for managing local resources and coordinating data transfer to and from the cloud.

Why use cloud computing

Social networking, e-mail services, document hosting services, backup services, banking and financial services, health care, and government services.

Types of operating systems

Batch processing, Time-sharing, Hybrid OS, Real-time OS, Distributed OS, Embedded OS, Interactive OS.

Two distinguishing features of operating systems

Response time and how data enters into the system.

Features of operating systems

Multiprocessing, Multitasking, Multiprogramming.

Multiprocessing

Allows parallel program execution; two or more CPUs handle jobs.

Multitasking

Handles two or more programs at the same time from a user’s perception; the CPU runs so fast that two or more jobs seem to execute at the same time.

Multiprogramming

Two or more programs are stored in main memory at the same time; when one job needs to wait, the CPU switches to another job, then returns when the first job finishes waiting; efficiently utilizes computing resources.

Most common overall goal of OS design

Maximize use of the system’s resources such as memory, processing, devices, and files, and minimize downtime.

Design considerations

RAM resources, CPUs available, likely peripheral devices, networking capability, security requirements.

Program

A non-active set of instructions stored on disk.

Job

A program from the moment it is selected for execution until it has finished running and becomes a program again.

Process

A program in execution; it has started but has not finished.

Thread

Multiple actions that can be executed at the same time; a process can be made up of several threads.

Memory management

Management of main memory; system performance depends on how much memory is available and how well memory is optimized during job processing.

Logical address

A value generated by the CPU that specifies a generic location relative to the program; also called a virtual or relative address.

Physical address

An actual address in the main memory device; a logical address added to the starting location of the program in main memory.

Operating systems must employ techniques to

Track where and how a program resides in memory and convert logical addresses into physical addresses.

Four types of memory allocation schemes

Single-user contiguous scheme, Fixed partitions, Dynamic partitions, Relocatable dynamic partitions.

Single-user contiguous scheme

Entire program loaded into memory; one contiguous memory space allocated as needed; jobs processed sequentially; the memory manager performs minimal work.

Disadvantages of single-user contiguous scheme

No support for multiprogramming or networking; not cost effective; program size must be less than memory size to execute.

Fixed partitions

Main memory is partitioned at system startup; one contiguous partition per job; permits multiprogramming; partition sizes remain static.

Fixed partition requirements

Protection of the job’s memory space and matching job size with partition size.

Fixed partition job allocation method

First available partition with required size.

Disadvantages of fixed partitions

Requires contiguous loading of the entire program; arbitrary partition sizes lead to undesired results; large jobs have longer turnaround time; memory waste occurs through internal fragmentation.

Dynamic partitions

Main memory is partitioned as jobs are loaded; jobs are given the memory requested when loaded; one contiguous partition per job.

Dynamic partition job allocation method

First come, first serve allocation method.

Advantage of dynamic partitions

Memory waste is comparatively small within partitions.

Disadvantages of dynamic partitions

Full memory utilization occurs only during loading of the first jobs; later allocations can waste memory; external fragmentation occurs between blocks.

Fragmentation

Internal fragmentation and External fragmentation.

Internal fragmentation

Allocated memory may be slightly larger than requested memory; this difference is memory internal to a partition but not being used.

External fragmentation

Dynamic allocation creates unusable fragments of free memory between blocks of busy memory; it is not contiguous.

Reducing external fragmentation

External fragmentation is reduced by compaction.

First-fit

First partition fitting the requirements; leads to fast allocation of memory space.

Best-fit

Smallest partition fitting the requirements; results in least wasted space; internal fragmentation is reduced, but not eliminated.

Worst-fit

Allocates the program to the largest partition big enough to hold it; opposite of best-fit; good for exploring theory of memory allocation, but not the best choice for an actual system.

Next-fit

Starts searching from the last allocated block for the next available block when a new job arrives.

Deallocation

Freeing allocated memory space.

Deallocation in a fixed-partition system

Straightforward process; the Memory Manager resets the status of the job’s memory block to “free” upon job completion.

Deallocation in a dynamic-partition system

More complex; the algorithm tries to combine free areas of memory.

Three dynamic partition deallocation cases

The block to be deallocated is adjacent to another free block; between two free blocks; isolated from other free blocks.

Relocatable dynamic partitions

The Memory Manager relocates programs, gathers all empty blocks together, compacts the empty blocks, and makes one block of memory large enough to accommodate some or all of the jobs waiting to get in.

Compaction

Reclaiming fragmented sections of memory space; every program in memory must be relocated so programs become contiguous.

Free list after relocation

Must show the partition for the new block of free memory.

Busy list after relocation

Must show the new locations for all jobs already in process that were relocated.

Bounds register

Stores the highest (last) location accessible by each program.

Relocation register

Contains the value that must be added to each address referenced in the program so the correct memory addresses can be accessed after relocation.

Relocation register value when a program is not relocated

Zero is stored in the program’s relocation register.

Purpose of compacting and relocating

Optimizes use of memory and improves throughput.

Options for timing compaction

When a certain percentage of memory is busy; when there are jobs waiting to get in; after a prescribed amount of time has elapsed.

Goal of compaction timing

Optimize processing time and memory use while keeping overhead as low as possible.

Paged Memory Allocation

Incoming job is divided into pages of equal size; memory manager determines number of pages, locates empty page frames, and loads all program pages into page frames; the program is stored in non-contiguous page frames.

Best condition for paged memory allocation

Pages, sectors, and page frames should be the same size.

Advantages of paged memory allocation

More efficient memory use; compaction is eliminated because there is no external fragmentation.

Problem introduced by paging

Increased operating system overhead because the job’s pages must be tracked.

Internal fragmentation in paging

Occurs only in the job’s last page frame.

Three tables for tracking pages

Job Table (JT), Page Map Table (PMT), Memory Map Table (MMT).

Job Table (JT)

Contains information for each active job, including job size and the memory location of the job’s PMT.

Page Map Table (PMT)

Contains information for each page, including page number and memory address.

Memory Map Table (MMT)

Has one entry for each page frame showing its location and free/busy status.

Line displacement / offset

Shows how far away a line is from the beginning of its page and is used to locate that line within its page frame.

Determining page number and displacement

Divide the job space address by the page size; the integer quotient is the page number and the remainder is the displacement.

Demand paging

Pages are swapped between main memory and secondary storage.

Page replacement policies

FIFO, LRU, MRU.

FIFO

First-In First-Out; removes the oldest page.

LRU

Least Recently Used; removes the page not referenced for the longest time.

MRU

Most Recently Used; removes the most recently used page.

Working set

During any phase of execution, a program references only a small fraction of its pages.

Locality of reference

Means that during any phase of execution, a program references only a small fraction of its pages.

Segmented memory allocation

Memory is divided into logical segments rather than equal-sized pages.

Address in segmented memory allocation

Composed of the segment number and the displacement.

Segmented/demand paged memory allocation

Combines segmentation and paging; segments are divided into pages.

3D addressing in segmented/demand paging

Segment, page, offset.

Associative memory

Several registers allocated to each active job; used to associate several segment and page numbers belonging to the job being processed and to speed up the process.

Virtual memory

Technique that allows execution of a program bigger than the physical memory of the computer system; the OS loads only the parts currently needed, while the rest is kept on disk until needed.

Virtual memory illusion

Gives the illusion that the system has a much larger memory than is actually available.