CSE 3430 Final Exam

Operating system definition

Software that converts hardware into a useful form for applications.

3 pieces of every modern OS

virtualization, concurrency, persistence

Reasons for studying operating systems

- build, modify, and administer an OS

- understand system performance (behavior, tune workload performance, apply knowledge across many layers)

- fun and challenging to understand, complex system

Definition of a process

an execution stream in the context of a process execution

Definition of an execution stream

A stream of executing instructions, a running piece of code, "thread of control"

What is a process execution state?

Everything that the running code can affect: register, address space, open files

Process vs Program: Process Definition

A process is a dynamic instance of code and data that actually is able to execute

What are typical interfaces/actions provided by the process API?

create, destroy, wait

What does the OS (unix/linux) do to create a process?

The OS brings (at least part of) the program's code and static data from the disk. It then allocates space for a stack segment and heap segment, sets up all I/O facilities, then when it's time to run the process, the OS will start running it at it's entry point which is stored as part of the executable which runs as a process.

3 processes state

ready, running, blocked

How is the CPU shared by processes in the system?

Processes share the CPU by using time-sharing.

Limited Direct Execution

Limited direct execution allows the hardware and OS to maintain some control.

Problems with direct execution

- process can do something it isn't allowed to do

- process could run forever

- process could do something slow like I/O

How does the hardware and OS provide limited direct execution by processes on the CPU?

a status bit, system calls, and interrupts and exceptions

What is the status bit

Which mode the process is running in. User processes run in user mode/restricted and OS runs in kernel mode/unrestricted

What is the difference between an interrupt and an exception?

Interrupts are raised by a device such as the disk drive during I/O while exceptions are interrupts from the software such as division by zero.

2 types of exceptions

traps, faults

Why doe the CPU rather than the OS have to change the status bit from user to privileged mode?

If the mode bit is set to user and the kernel is able to change it, then the user process would be allowed to make this change and the purpose of the mode bit is defeated.

Does the CPU or the OS change the status bit from privileged mode to user mode? When does this happen?

When the kernel is ready to transition back to user mode, the OS changes the status bit and puts the address of the next instruction of the user process to run on the PC.

What kinds of things are user processes not allowed to do in user mode?

General memory access, disk I/O, special y86 instructions like changing the PC address

What happens if a user process tries to do something which is restricted?

The CPU is taken away from it and the OS kills the process. This is called a segmentation fault.

How is the CPU taken away from a user process which is executing instructions?

option 1: cooperative multitasking = trusting the process will relinquishes CPU to OS through traps

option 2: true multitasking = guarantees that the OS will obtain control periodically (WHAT IS ACTUALLY USED)

What is a context switch?

Saves the context or process execution state of a process that was interrupted in a PCB.

What data is saved for one process and restored for another when a context switch occurs?

PID, process state, execution state (registers, PC, stack pointer), scheduling priority, accounting information, credentials, pointers to other allocated resources like open files

Problems with cooperative multitasking

BUGGY, hogs CPU

What does uninx/linux fork do? What are the things that must be done to create a new process?

Fork calls to the OS which causes a new process (child of its parent) to be created. It returns the PID of this child to the parent and 0 to the child if successful. When the OS creates the child, it is assigned its own PID, gets a separate address space which contains a copy of its parents to begin. The OS also creates a PCB for the child and it gets a copy of the parents register values.

What is the relationship between the parent's address space and the child's address space?

The child gets a copy of the parents address space

Which parameters may a scheduler attempt to minimize?

turnaround time, response time, waiting time, and overhead

Which parameters may a scheduler attempt to maximize?

Throughput, resource utilization, and fairness

Turnaround time (with equation)

How long we wait for a job to complete

completion_time - arrival_time

Response time (with equation)

How quickly we see output

initial_schedule_time - arrival_time

Waiting time (with equation)

How much time we spend waiting in the ready queue

turnaround_time - burst_time

Overhead in scheduling

number of context switches from memory

Throughput in scheduling

the jobs we complete per unit time

Resource utilization in scheduling

keeping expensive devices the busiest

Fairness in scheduling

all jobs get the same amount of CPU over some time interval

FIFO

NON-PREEMPTIVE

first in, first out

SJF

NON-PREEMPTIVE

shortest job first

STCF

PREEMPTIVE

Shortest time to completion first

RR

PREEMPTIVE

alternate processes every fixed-length time slice

Which scheduler is subject to the convoy effect?

FIFO

Why can an RR scheduler provide better response time?

Because it gives short jobs a chance to run and finish quickly by giving each process a fixed-length time slice.

MLFQ scheduler

Multilevel feedback queue which uses multiple levels of RR scheduling.

How is history used by the MLFQ scheduler?

Uses past code behavior to predict future behavior. The process alternates between I/O and CPU work. It guesses how CPU bursts will behave based on past CPU bursts of the process.

What are the goals of the MLFQ scheduler?

General-purpose scheduling to support both interactive and batch programs where interactive programs care about response time and batch programs care about turnaround time.

Problems with MLFQ scheduler?

inflexibility, starvation

Why do we virtualize memory?

Provides an illustration of private address space for each process by the OS.

4 goals of multiprogramming?

transparency, protection, efficiency, sharing

What is in the address space of a process?

Code, heap, and stack

Which parts of the address space of a process are dynamic?

Stack and heap

Which parts of the address space of a process are static?

Code

Mechanisms for virtualizing memory?

1. time sharing

4. dynamic relocation w/ base & bounds

5. segmentation

6. paging

What does time sharing of memory involve?

OS gives illusion of many virtual CPUs by saving CPU registers to memory when a process isn’t running

Which entity does the translation of addresses with the base register in dynamic relocation with a base?

Hardware (MMU)

Which entity modifies the base register in dynamic relocation with a base?

The OS.

How does dynamic relocation with base/bounds work?

provide protection by limiting the size of address space with a bounds register

Advantages of dynamic relocation with base/bounds?

- provides protection across address space

- supports dynamic relocation

- simple, inexpensive implementation

- fast

Disadvantages of dynamic relocation with base/bounnds?

- each process must be allocated continuously in physical memory

- no partial sharing

How does segmentation work?

Divide address space into logical segments

How are the bits in a virtual address used when segmentation is employed?

Logical/virtual addresses now have 2 parts; specifying the segment and then the offset. The top bits select the segment and the lower the offset.

Advantages of segmentation

- enables sparse allocation of address space

- different protection for different segments

- enables sharing of selected segments

- supports dynamic relocation of each segment

Disadvantages of segmentation

each segment must be allocated contiguously

Size of a page

always a number of bytes equal to a power of 2

Relationship between the size of a virtual page and the size of the physical page

They must be the same

Fundamental idea behind paging

Divide process address spaces and physical memory into fixed-size pages

How does paging work?

Divide process address spaces and physical memory into fixed-sized pages

How are the bits in a virtual address divided when paging is employed?

VPN bits are the most significant and the page offset is the least significant

Which type of fragmentation does paging eliminate?

External

Which type of fragmentation can still occur if paging is used?

Internal

Page table

The table containing the virtual to physical address translations in a virtual memory system. The table, which is stored in memory, is typically indexed by the virtual page number; each entry in the table contains the physical page number for that virtual page if the page is currently in memory.

How is the translation of virtual addresses to physical address performed?

MMU

Where are page tables stored?

In memory

What kinds of information besides physical page numbers are stored in the page table entries

Valid bit, protection bit, present bit, reference bit, dirty bit

Advantages of paging

- no external fragmentation

- fast to allocate and free

- simple to swap-out portions of memory to disk

Disadvantages of paging

- internal fragmentation

- need to store page table for every process

Paging in

When page are returned to physical memory or RAM from the disk.

What is used as the "cache" for disk storage?

The whole virtual address space for a process that is running is on the disk. The cache for the storage of pages of a process that is running is RAM or main memory.

What is the mechanism the OS uses to identify the location of a particular page in a process's virtual address space?

Extend the page tables with an extra bit called the present bit

What is the purpose of a present bit in PTE of a process's page table?

Indicates which pages are present in physical memory or on the disk.

What is a page fault exception?

Traps into the OS and selects a victim page in memory to replace. The OS then reads the referenced page from the disk into memory and the page table and present bit are updated.

What does the scheduler do when a page fault exception occurs in a running state?

Executes the instruction again because the first time the page wasn't in memory and now it most likely is since we have attempted to move it.

What is a file

an array of persistent bytes that can be read/written

Inode

Each file has only one unique number at once. Arbitrary and non meaningful to humans.

Path name

Friendlier than an inode and more meaningful but has expensive traversal on each access

File descriptor

information kept in the directory to describe a file or file extent, does an expensive traversal through the directory tree and moves it into the cache so we don't have to do this again

What methods are used to allocate blocks for a file in a file system?

- contiguous

- small # of extents

- linked allocation

- FAT (file allocation table)

- indexed

Contiguous file allocation

Each file is allocated a contiguous sector on the disk. The meta-data is the starting block and the size of the file.

Files stored in sequential block/cluster addresses

Small # of extents

Allocate multiple contiguous regions (extents) per file. Meta-data is a small array (2-6) designating each extent and each entry has the starting block and size.

Linked allocation

Allocate linked-list of fixed-size blocks.

Meta-data is the location of the first block of the file and each block also contains a pointer to the next block.

File allocation table

A variation of linked allocation where we keep linked-list information for all files in an on-disk FAT table and the meta-data is the location of the first block of the file and the FAT itself.

Indexed file organization

The storage of records either sequentially or non-sequentially with an index that allows software to locate individual records.

What are the policies the OS can use to determine when to bring a page in a process's virtual address space from disk into memory (RAM)?

Anticipatory paging or demand paging

If multiple processes or threads in a system are sharing data, in which part of memory must the data be stored

Shared data must be stored on the heap

What is a thread within a process

A sequence of execution which is separate from other sequences of execution in the process

What resources do threads within a process have

A thread ID (tid), and a register set, including a PC, IR and stack pointer, as well as data registers (rax, etc. in Intel, e.g.)

Be able to give a basic description of how multithreaded processes can improve performance in modern systems

Because the multiple threads can execute on different cores in a multicore CPU at the same time, so the process can finish its work faster

What is code which accesses shared data called?

A critical section

What is mutual exclusion for critical section code

The requirement that at most one critical section can be accessing shared data at any given time

What is indeterminate output

Running the same program twice with the smae input, and getting different output

Why is mutual exclusion important to prevent indeterminate output?

Guaranteeing mutual exclusion can be proven to prevent indeterminate output