cs4310 midterm 2

What are the three main scheduling algorithm categories?

Batch Systems, Interactive Systems, and Real-time Systems

What are batch systems?

Maximize jobs per hours, minimize time between submission and termination, keeps CPU busy all the time

What are interactive systems?

Responds to requests quickly and meet user expectations

What are real time systems?

Avoid losing data and avoid quality degradation in multimedia systems

What is FCFS in Batch Systems?

Jobs come in and put in queue FIFO

What is Shorted Job First

Requires knowledge of process runtime only optimal when all jobs are available simultaneously

What is Shortest Remaining Time Next

Also requires knowledge of process run time. When new job arrives, total time is compared to current process remaining time, if new job needs less, replaces current job

What is Round Robin Scheduling?

Each process is assigned a time interval (quantum)

What is a quantum?

A time interval

What is priority scheduling?

Not all processes are equal, each process assigned a priority, highest runnable priority is allowed to run

What is shortest process next?

Estimates processes with shorter upcoming run time based on past-behavior and approximates by using a technique called aging

What is a real time system?

Where time plays an essential role. One or more physical devices generate stimuli and the computer must react appropriately to them within a fixed amount of time

In real time systems what are the two times?

Hard real time and soft real time

What is hard real time?

Deadlines are absolute and must be met

What is soft real time?

Missing an occasional deadline is undesirable but tolerable

The events that a real-time system may have to respond to can be categorized into what?

Periodic and aperiodic

What is periodic?

Events occur at regular intervals

What is aperiodic?

Events occur unpredictably

When is a real-time system schedulable?

If all the processes can actually be implemented

What happens if one process has many children running under its control?

Separate the scheduling mechanism from the scheduling policy

What does it mean to separate the scheduling mechanism from the scheduling policy?

Scheduling algorithm is parameterized in some way, but the parameters can be filled by the user processes

Policy-mechanism separation

Kernel handles priority-scheduling but provides a syscall by which a process can set and change how its children are scheduled. Mechanism is in kernel, but policy is set by a user process

What is the major difference between user and kernel level threads in performance?

Thread switch with user-level takes a handful of machine instructions. Kernel-level threads require a full context switch changing the memory map and invaliding the cache

What are Interprocess Communication?

Well structured way of processes communicating with other processes

What issues do IPC want to solve and which affect multithreading?

1. How can one process pass information to another

2. How can we make sure two or more processes don’t get in each others way?

3. How do we ensure proper sequencing when dependencies are present?

2 and 3 affect multithreading

What are race conditions?

When two or more processes are writing to some shared resource

What is mutual exclusion?

Prevent other processes from accessing a resource if one process is already using it

What is a critical region or section?

The part of memory process needs to access that is a shared resource

What is mutual exclusion?

While one process is busy updating shared memory in its critical region, no other process will enter its own critical region and cause trouble

What is disable interrupts?

Have each process disable all interrupts after entering its critical region and reenable just before leaving it. However, this can slow down everything, another process might be as critical, or priority isn’t as high as thought

What are lock variables?

Software based solution. Have a single shared variable set to 0. When process wants to enter critical region, tests the lock and set to 1 if successful then change back to 0 when leaving. However, state of lock might’ve changed during the check

What is busy waiting?

Testing a variable until some value appears, avoided because it waits CPU time. Only used when the wait is short, called a spin lock

What is sleep and wakeup?

Sleep sets a process to be suspended until woken up by wakeup

What are semaphores?

Values of 0 = no wakeups saved and have two operations down and up

What is an atomic action and where is it used?

When checking the value, changing it, and possibly go to sleep are done in a single indivisible action, used by semaphores. Either all actions are performed without interruption or none are performed at all

What are mutexes?

Binary semaphores, 1 is locked

What is a monitor?

Collection of procedures, variables, and data structures that are all grouped together into a special kind of module or package. Processes may call the procedures in a monitor whenever they want to, but cannot directly access the monitor’s internal data structure from procedures declared outside the monitor

Problems with monitor and semaphores?

Only work on one CPU that have access to common memory, if working with a distributed system with multiple CPUs and multiple private memory, these primitives become inapplicable

What is message passing?

Method of IPC using two primitives, send and receive

What are barriers?

Used for groups of processes, some applications are divided into phases and no process may proceed into next phase until all are ready

What is the memory hierarchy?

1. A few megabytes of fast, expensive, volatile cache memory

2. A few gb of medium speed, medium priced, volatile main memory

3. A few tb of slow, cheap nonvolatile ssd storage

What is the memory manager?

The part of the OS that manages the memory hierarchy, job is to keep track of which parts of memory are in use, allocate memory to processes when they need it, and deallocate it when those processes are done

What is swapping?

Save the entire contents of a program in memory to a file on nonvolatile storage, then bring it in and run the next program. Used to run multiple programs at the same time

Core problem with loading programs consecutively onto memory?

Don’t know where memory places you and jump programs with just integers wouldn’t work with multiple programs

What is static allocation?

Gets around problem of loading consecutive programs into memory by adding starting memory location to each program address. Bad because memory can’t be changed while program is running

Why does absolute memory work on radios, washing machines, and microwaves?

No user programs and time doesn’t matter and only one program is usually run

Exposing physical memory to processes is bad because

1. Protection: If the user programs can address every byte of memory, they can easily trash the OS intentionally or by accident

2. Isolation: It is difficult to have multiple programs running at once

What is an address space?

Set of addresses that a process can use to address memory. Each process has its own address space independent of those of other process

What is dynamic relocation?

Maps each process address space onto a different part of physical memory in a simple way. Equips each CPU with two special hardware registers, the base and limit registers

How is dynamic relocation similar to static relocation?

Work is done by CPU hardware. When process references memory, CPU automatically adds the base value to the address generated by the process before sending the process to the memory bus. It also checks whether the address offered is equal to or greater than the value in the limit register

Disadvantage of relocation using base and limit registers?

Need to perform addition and comparison on every memory reference. Comparison is fast, but addition is slow due to carry-propagation time

What are the two approaches to dealing with memory overload?

Swapping and virtual memory

What is memory compaction?

Since swapping creates multiple holes in memory, combine them all into one big one by moving all the processes downward as far as possible. Not usually done because it requires a lot of CPU time (seconds). Also process data segments can grow

What should you do when a process is swapped in or moved?

Allocate a little extra memory to reduce overhead associated with moving or swapping processes that no longer fit in memory

How to keep track of memory usage?

Bitmaps and free lists

What is a bitmap?

Memory is divided into allocation units. 0 if unit is free, 1 if it is occupied

What are free lists?

Maintain a linked list of allocated and free memory segments where a segment either contains a process or an empty hole between processes. Usually use double linked list since you can better deal with holes that start in the back

What are the memory allocation algorithms with linked lists?

First fit, best fit, worse fit, quick fit

What is first fit?

Scans along the list of segments until it finds a hole that is big enough. Hole node is broken up into one for the process and one for unused memory

What is best fit?

Searches the entire list then takes smallest hole that is adequate

What is worst fit?

Always takes the largest available hole so that the new hole will still be useful

What is quick fit?

Maintains separate list for more common sized requests

What are overlays?

Split programs into little pieces and only run what was needed

What is virtual memory?

Each program has its own address space, broken up into chunks called pages. Pages are mapped onto physical memory, but not all pages have to be in physical memory at the same time to run the program.

What is a page?

Each page is a contiguous array of addresses

What is paging?

Where the units are fixed size units

What are virtual addresses and what do they form?

Program-generated addresses and form the virtual address space

What is a Memory Management Unit?

Maps virtual address onto physical memory address

What are page frames?

Corresponding units in the physical memory

What is a page fault and what happens?

If a program references an unmapped address, the MMU sees the page is unmapped via present/absent bit and causes CPU to trap the OS. The OS will then swap a little used page frame onto storage and fetches the page that was actually referenced onto ram

What are present/absent bits?

Indicates whether entry is valid and can be used or not in physical memory 0 not in physical memory

What is a protection bit?

Tells what kinds of access are permitted. A single bit with 0 for read/write, 1 for read only.

What is a supervisor bit?

Indicates whether a page is accessible only to the privileged code (OS) or also to user programs. User program accessing a supervisor pages results in a fault

What is a modified bit?

Keeps track of page usage. When page is written to, hardware automatically sets this bit

What is the referenced bit?

Keeps track of when page is referenced for either reading or writing

What is caching bit?

Allows caching to be disabled for the page. Important for pages that map onto device registers rather than memory

Two majors issues that must be faced in order to speed up paging?

1. Mapping from virtual address to physical address must be fast

2. Even if virtual address space is huge, page table must not be too large

Why must mapping be fast?

Because virtual-to-physical mapping must be done on every memory reference. Page table lookup should be fast too

Why must page table not be to large?

Using hundreds of gb to store page table is excessive

What is the translation lookaside buffer?

A small hardware device for mapping virtual addresses to physical addresses without going through the table. Cache for page table entries, each TLB entry corresponds to a page table

What are the TLB mechanics?

1. When virtual address is presented to MMU for translation, hardware first checks if virtual page number is present in TLB by comparing it to all previous entries simultaneously in parallel

2. If a valid match is found and access does not violate protection bits, page frame is taken directly from TLB without going to page table in memory

3. If virtual page number is present in TLB, but instruction is trying to write to read-only page, protection fault is generated

What happens when virtual page number is not in the TLB?

1. MMU detects miss and does ordinary page table lookup

2. Evicts one of the entries from TLB and replaces it with page table entry

3. When entry is evicted from TLB, modified bit is copied back into the page table entry in memory. Other values are already there except the reference bit

What happens if OS wants to change the bits in the page table entry?

Modifies it in memory but has to flush the corresponding TLB entry too

How to deal with size of page tables?

Multilevel Page Tables

What are multilevel page tables?

Avoids keeping all the page tables in memory all the time

What happens what a page fault occurs?

1. OS chooses a page currently in frame to evict

2. If page has been modified, rewrite to disk

3. A page is allocated into the page frame which was used by the evicted page

What is the optimal page replacement algorithm and why is it impossible?

Know when each page will be referenced in the future to know when to put it in memory and when to remove, impossible to know what next instruction is.

What is Not Recently Used Page Replacement Algorithm?

When page fault occurs splits all pages into four categories

Class 0: Not referenced not modified

Class 1: Not referenced, modified

Class 2: Referenced, not modified

Class 3: Referenced, Modified
Then removes a page at random from the lowest numbered non empty class

FIFO Replacement Algorithm

OS maintains list of all pages currently in memory, when a page fault occurs it dequeues and enqueues new page

What is second chance replacement algorithm?

Uses FIFO, but checks reference bit. If 0 means page is both old and unused, if 1 bit is cleared and put into end of the list as if just arrived, and search continues until we can evict

What is Least Recently Used Replacement Algorithm?

Throws away pages that haven’t been used the longest, but increases memory size/page size