Operating Systems Day 04

Virtual memory: a technique that allows programs to be executed even though they are not stored entirely in memory.

Virtual memory’s important advantages such as

• A job’s size is no longer restricted to the size of main memory.
• It eliminates external fragmentation and minimizes internal fragmentation.
• It allows the sharing of code and data.
• It facilitates dynamic linking of program segments, and an unlimited amount of multiprogramming is possible.

The disadvantages of virtual memory include 

• increased processor hardware costs, 
• increased overhead for handling paging interrupts, and 
• increased software complexity to prevent thrashing.

Cache memory: a small, fast memory used to hold selected data and to provide faster access than would otherwise be possible.

Thrashing: a phenomenon in a virtual memory system where an excessive amount of page swapping back and forth between main memory and secondary storage results in higher overhead and little useful work.

Memory Map Table (MMT): a table in main memory that contains as many entries as there are page frames and lists the location and free/busy status for each one.

Page: a fixed-size section of a user’s job that corresponds in size to page frames in main memory.

Paged memory allocation: a memory allocation scheme based on the concept of dividing a user’s job into sections of equal size to allow for noncontiguous program storage during execution.

Demand paging: a memory allocation scheme that loads a program’s page into memory at the time it is needed for processing.

Page Map Table (PMT): a table in main memory with the vital information for each page including the page number and its corresponding page frame memory address.

Page fault: a type of hardware interrupt caused by a reference to a page not residing in memory. The effect is to move a page out of main memory and into secondary storage so another page can be moved into memory.

Working set: a collection of pages to be kept in main memory for each active process in a virtual memory environment.

Processor Manager allocates CPU among all users.

Processor Manager manages and allocates a single central processing unit (CPU) to execute the incoming jobs.

• The difference between job scheduling and process scheduling, and how they relate.

The advantages and disadvantages of process scheduling algorithms that are preemptive versus those that are nonpreemptive.

Up to six different process scheduling algorithms.

Explain the two states in a single-user system (busy and idle).

Understand the difference between a job and a process.

Explanations of the terms program or job, process, thread, processor, interrupt, higher priority, and context switch.

Program (Job)

• instructions defining job to be performed, usually stored as a file
• a ‘unit of work’ submitted by a user
• passive entity

Process (task)

• single instance of a running program
• active entity
• Requires resources to perform function
• CPU + registers + memory (code  & data) + devices (files…)

Thread

• ‘lightweight’ process
• runs independently

Processor

• Central Processing Unit (CPU)
• performs calculations and executes programs (code)

Interrupt

• Notification of important event
• Activates higher-priority program (interrupt handler)
• Supported by CPU hardware…

Context Switch

• Occurs when changing from one process to another
• Saves process information (registers) when interrupted

Job is divided into a set of pages with a fixed size for each page.

Each frame in the main memory has the same size as each page?

Physical address = starting address of the frame + the offset 

For 16-bit address

The first 6 bits are for identifying the page number.

The last 10 bits are for offset.

Objective: Minimise Page Faults

• Replace a page that isn’t going to be wanted again
• Avoid having to save the page

Algorithms:

• First In - First Out (FIFO):
• Simple queue, oldest frame at head of the queue
• Least Recently Used (LRU):
• List in time sequence
• This algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. The setting of the bits is usually done by the hardware, although it is possible to do so on the software level as well.
• At a certain fixed time interval, the clock interrupt triggers and clears the referenced bit of all the pages, so only pages referenced within the current clock interval are marked with a referenced bit. When a page needs to be replaced, the operating system divides the pages into four classes:
• not referenced, not modified
• not referenced, modified
• referenced, not modified
• referenced, modified
• Although it does not seem possible for a page to be not referenced yet modified, this happens when a class 3 page has its referenced bit cleared by the clock interrupt. The NRU algorithm picks a random page from the lowest category for removal. Note that this algorithm implies that a modified (within clock interval) but not referenced page is less important than a not modified page that is intensely referenced.
• Least Frequently Used (LFU):
• List by frequency of use

Working set:

• The collection of pages a process is using actively
• Must be memory-resident to prevent thrashing
• It changes over process execution
• Golden rule: never remove from memory pages of the working set

Cache memory: small high-speed intermediate memory unit

• Cache memory is not accessible by the programmer
• Performance of computer system usually increased
• Memory access time usually significantly reduced
• Faster processor access compared to memory
• Stores frequently used data and instructions
• Two levels of cache
• L2: Connected to CPU; contains copy of bus data
• L1: Pair built into CPU; one stores instructions and one data

Four cache memory design factors:

• Cache size, block size, block replacement method, rewrite policy
• Optimal selection of cache and replacement method necessary
• May lead to 80-90% of all requests in cache

Efficiency measures

• Cache hit ratio (h) 
• Percentage of total cache hits
• Miss ratio (1-h)
• Average memory access time
• AvgCacheAccessTime + (1-h) * AvgMemACCTime

Cache transfer method

1. CPU puts the address of a memory location in the Memory Address Register and requests data or an instruction to be retrieved from that address
2. A test is performed to determine if the block containing this address is already in a Cache slot
1. YES (hit): Transfer the information to CPU register – DONE
1. Much faster than accessing main memory
2. NO (miss): Get the block containing that address from Memory
1. Allocate a free Cache block slot to the block
2. Perform these in parallel: Transfer the data to CPU
1. Load the block into slot - DONE
3. A bit slower than accessing main memory

The segmented approach to memory management

• Programs often divide memory into areas
• Code: may have several subroutines or modules
• Data: may be organised into variables tables, lists…
• Overheads
• Each segment must have own base and limit registers
• Each segment has its own page table

The segmented memory allocation scheme, in which each job is divided into several segments of different sizes, one for each module that contains pieces that perform related functions. Note that it is based upon the concept of programming modules.

The notion of placing modules in different sized segments. Explain how this concept reduces page faults using the loop with a program example. Note that this is fundamentally different from a paging scheme that uses pages of the same size. Also note that memory is allocated dynamically.

The role of the Segment Map Table (SMT) and the information contained in it, such as segment numbers, their lengths, access rights, status, and (when each is loaded into memory) its location in memory.

References

1. McHoes, A., & Flynn, I.M. (2008). Understanding operating systems (5th ed.). CENGAGE Learning. 
2. Melbourne Institute of Technology (Semester 1, 2012). BN104 Operating Systems Lecture Notes.