CSE 3430 Part C

Define an operating system

Software (a program) that converts hardware into a useful form for applications, making sure the system operates correctly, efficiently, and in an easy-to-use manner

What does OS provide?

1. Abstraction (standard library for resources)

   1. Resources are anything valuable for executing programs

2. Resource Management (share resources well to protect applications from each other & provide fair/efficient access)

Three pieces of OS

1. Virtualization (behave so that each application can run as though it has certain resources to itself)

2. Concurrency (handling events occurring simultaneously)

3. Persistence (preserve info permanently, even when power goes off)

Why study operating systems?

To understand system performance—behavior of OS impacts entire machine

Tune workload performance

Apply knowledge across many layers

Define a process

An execution stream in the context of a process execution state (A running/active/working program)

What is an execution stream?

A stream/sequence of executing instructions (a running piece of code)

What is a process execution state

Everything that the running code can affect or be affected by (registers, address space, open files)

Process vs Program

A program is static code & static data (on disk)

A proces is a dynamic instance of code and data (in memory)

Can have multiple process instances of same programs

What are typical interfaces/actions provided by the process API

Create

Destroy

Wait

What does the OS do to create a process

Bring at least part of the program’s code & static data from disk into memory

Allocate space for stack segment

Allocate some space for the heap

Set up I/O facilities

After creation, what must be done for the process to start execution?

Start the process running at its entry point (the first instruction in main())

What are the three process states?

Ready - everything in memory & I/O set up, but not executing instructions on CPU (waiting)

Running - actually executing instructions on CpU

Blocked - waiting in line for some event to occur

How is the CPU shared by processes in the system?

Give each process the impression it alone is using the CPU, sharing resources in time & space

Time-sharing means only one process at a time uses the resource

Direct execution vs limited direct execution

Direct means processes run directly on hardware, getting control from OS at starting point

Limited direct means OS & hardware maintain some control

Problems with direct execution?

Process could do something that shouldn’t be allowed (mess with other processes’ data)

Process could run forever

Process could do something slow (like I/O)

How does hardware & OS provide limited direct execution

Status bit - indicates privilege level (user vs kernel mode), could have more than 2 levels (requiring more than 1 bit)

System calls - when the user process calls to a function implemented by OS to access devices

Interrupts - transition to OS control raised by a device (like disk drive), CPU changes the status bit to kernel

Exceptions - either traps (the instruction doesn’t execute again after handled by the OS, like for errors & system calls) or faults (the instruction executes again after the OS handles the fault)

Why must the CPU change the status bit from user to kernel? When does it do this?

If OS could change user to kernel, user process could too. This happens when an interrupt or exception happens

Who changes the status bit rom kernel to user? When?

Kernel changes the status bit to user mode when it puts the address of the next instruction of the user process in the PC

What are user processes not allowed to do?

• General memory access

• Disk I/O

• Other special instructions like changing the PC address

What happens if user process tries to break restriction?

The CPU calls the OS, and the process is terminated (segmentation fault)

How is the CPU taken from the user process?

The OS uses a periodic alarm clock via a timer interrupt generated by the hardware (ex. every 10 ms)

What is a context switch & what data is saved for one process/restored for the next?

When the dispatcher preserves info from a process before switching over:

1. PID (process identifier)

2. Process State (running, ready, blocked)

3. Execution state (all registers, including PC, & stack ptr)

What are the problems with cooperative multi-tasking?

Processes may not cooperate, hogging the CPU or having malicious code

What is true multi-tasking?

Use of periodic alarm clock to guarantee OS/dispatcher can obtain control

What transitions in process state can occur and when?

Descheduling (running to ready)

Scheduling (ready to running)

I/O initating (running to blocked)

I/O finishing (blocked to ready)

What parameters may a scheduler attempt to minimize/maximize?

Minimize turnaround time, response time, waiting time, overhead

Maximize throughput, resource utilization, fairness

Formulas for turnaround time, response time, and wait time:

turnaround time = completion time - arrival time

response time = initial schedule time - arrival time

wait time = completion time - arrival time - run time

Describe the following schedulers (with acronym) and if they’re pre-emptive:

1. FIFO/FCFS

2. SJF

3. STCF

4. RR

1. FIFO/FCFS: first in, first out/first come, first served - run jobs in arrival time order (non-preemptive)

2. SJF: shortest job first - choose job with smallest run_time (non-preemptive)

3. STCF: Shortest Time-to-Completion - run job that will complete the quickest (preemptive)

   1. RR: Round Robin. alternate ready processes every time-slice

What is a time quantum or time slice?

In RR scheduling, the interval at which processes are switched out

In what way is an RR scheduler usually worse than FIFO (for equal-length jobs)?

Avg. turnaround time horrible

How do I/O system calls interact with CPU scheduling?

While a job is blocked for I/O, schedule another ready job

Which schedulers are subject to the convoy effect?

FIFO & SJF

Why can an RR scheduler provide better response time?

Jobs are guaranteed to start sooner since they’re rotating every time quantum

How does the MLFQ scheduler work?

Multi-Level Feedback Queue, uses multiple levels of round-robin with different priority

If processes share priority level, they run RR

Priority set either by past behavior, but all processes start at top priority and drop down if they use whole slice

So interactive processes that never use the entire time slice are never demoted

What are the potential problems with the MFLQ scheduler & how are they addressed?

Inflexibility & Possibility of Starvation - periodically boost priority of all jobs (or all jobs that haven’t been scheduled for a time period) back to top priority

Motivation for memory virtualization?

We want multiprogramming but with the simplicity of uniprogramming

What are the four goals of multiprogramming?

transparency, protection, efficiency, and sharing

What is in the address space of a process?

Code (static), heap (static), stack (dynamic)

What is time sharing of memory & why doesn’t it work?

Saving memory to disk when a process isn’t running so only one process at a time uses main memory/RAM — requires too much time to swap processes to/from the disk on every context switch

What does dynamic relocation with base/bounds involve?

Move the address space of each process to a higher address so they never overlap addresses

The memory management unit (MMU) contains the base register for the process and adds it to virtual address to get physical address; OS terminates process if loads/stores at address that exceeds bounds.

What are the advantages/disadvantages of dynamic relocation with base/bounds?

Advantages: protection across address spaces, can move address spaces later if needed, simple & inexpensive, fast

Disadvantages: processes must be contiguously allocated, no partial sharing (can’t share limited parts of address space)

What’s segmentation?

Address space is divided into code, stack, heap; independently separated in physical memory & can grow/shrink & be protected via separate read/write/execute protection bits

How are bits in a virtual address used to translate virtual addresses to physical addresses in segmentation?

Segment bits determine which pair of base/bounds registers to look at; offset in address compared to bounds to see if it is less, then offset added to base register to get physical address

Advantages & disadvantages of segmentation:

Advantages: sparse allocation of space (segments can grow if needed & independent from one another); different protection for different segments; sharing selected segments; supports dynamic relocation if needed

Disadvantages: Each segment must be allocated contiguously, which could be a problem for large segments

What can we say about the size of a page?

Always a number of bytes equal to power of 2

What is the relationship between the size of a virtual page and the size of a physical page (or frame)

They must be the same size

What is the fundamental idea behind paging?

Eliminate the need for contiguous allocation & eliminate external fragmentation

How does paging work?

Address space & physical memory divided into fixed-size pages

How are bits in a virtual address divided with paging?

VPN bits are msbs, page offset bits are lsbs

Paging and fragmentation?

External eliminated, but internal always possible

How is mapping virtual page number to physical page number performed?

A page table is used for each process, mapping virtual pages to their physical locations

Where are page tables stored?

In main memory (the OS’ portion)

What other kinds of data besides physical page number are stored in page table entried?

PTEs also store a valid bit, protection bits, present bit, reference bit, and dirty bit

Advantages of paging:

No external fragmentation, fast and free to allocate pages, simple to swap out portions of memory to disk (page size matches disk block size & can run process when some pages are on disk)

Disadvantages of paging

Internal fragmentation & needing to store page table for every process

How can multiple processes that have a combined virtual address space which is larger than the amount of physical RAM installed in a system be run when paging is used?

Processes do not have their entire address space in memory while executing, but only the part of the address space they are currently using or have recently used (2-3% of the entire address space at a time)

What is paging in?

Having the disk drive copy the page from disk to main memory so the process can access it

What is used as the cache for disk storage, which holds the entire virtual address space of a process which is running in a system

Main memory/RAM

What is the mechanism the OS uses to identify the location of a particular page in a process’s virtual address space (in physical memory, the disk, or perhaps neither)

The present and valid bits in the PTE for the page

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

If page is in memory, PTE is 1; if on disk, PTE is 0; if referenced but not present, causes a trap into OS (page fault)

What is a page fault exception?

When a page is referenced but the present bit is 0; trap into OS

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

Process goes to blocked state (waiting for disk I/O) and CPU is given to another process

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 (aka prepaging, prefetching): OS predicts future accesses and brings pages into memory early

Demand paging: load page only when page fault occurs

If multiple processes or threads are sharing data, where is the data 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, stack pointer, and data registers

How can multithreaded processes improve performance in modern systems

Because 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 the 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 same input and getting different output

Why is mutual exclusion important to prevent indeterminate output?

Guaranteeing mutual exclusion can be proven to prevent indeterminate output

What is a binary semaphore, and what are the operations on binary semaphores?

A binary semaphore stores two possible states (0 or 1); the operations are semWaitB and semSignalB

How can a binary semaphore be used to implement a lock to ensure mutual exclusion for critical sections code?

semWaitB and semSignalB bookend the critical section—so the process will not run it until it ‘has’ the lock (is either unblocked by another process’ semSignalB or sets the semaphore to 0 from 1 itself), and will give it back once done.

What is a file?

An array of persistent bytes that can be read/written

File name systems & their advantages/disadvantage

1. inode number - ID number equal to index in the inode array (arbitrary and not human-meaningful)

2. paths - set of directories, store path-to-inode mappings in root file (typically inode 2) (but expensive traversal on every access

3. File descriptor - do expensive traversal once (open file), then store/cache inode in descriptor structure

What is the size of a block in the file system? What is the relationship between the size of a block and the size of a page in memory?

They are the same size, commonly 4 KB blocks (2^12 bytes)

Explain the methods used to allocate blocks for files in a file system & the metadata that must be stored for each:

1. Contiguous: allocate each file to contiguous sectors on disk. Metadata: starting block & size of file (must predict future size of file)

2. Small # of extents: allocate multiple contiguous regions (extents) per file. Metadata: small array (2-6) designating each extent (each entry is starting block and size)

3. Linked Allocation: Linked-list of fixed-size blocks. Metadata: location of first block + pointer to next block on each block.

4. File-Allocation Table (FAT): Linked-list information for all files in on-disk FAT table. Metadata: location of first block of file + FAT table itself