CPSC/ECE 3220

Operating Systems Final

Operating System definition

System software that manages a computer’s hardware and software resources which acts as an intermediary between the user and computer’s hardware.

Operating System Roles

Referee, Illusionist, Glue

OS - Referee

The OS manages resources shared between different applications running on the same machine

OS - Illusionist

The OS gives the illusion that a process has isolated access to all the computer’s resources.

OS - Glue

The OS provides a set of common services that facilitate sharing among applications.

Kernel Defintion

The kernel is the lowest level of software running on the system which has access to all hardware.

Microkernel

An OS that is designed to run as much of the OS as possible in user-level servers.

Benefits of Microkernels:

• Security

• Modularity

• Portability

• Less kernel error

Cons of Microkernels

• Slow (due to IPC)

What is REQUIRED to be in the kernel?

• Memory management

• Process scheduling

• Interrupt handling

• Direct hardware access

What is a trap (user → kernel)?

A synchronous, software initiated exception that causes a mode switch

What are some triggers of traps?

• System calls

• Software exceptions

Mode switch definition

A change between user → kernel (or vice versa). This can occur due to system calls, interrupts, or exceptions/traps.

What happens during a trap?

1. CPU switches privilege level (mode switch) from user → kernel

2. Saves user-mode state (registers, PC) to kernel stack

3. Switches to kernel stack

4. Jumps to appropriate kernel handler

5. Kernel executes required operation

6. Returns to user mode (mode switch) which restores registers and switches back to user stack

What is a context switch (kernel → user)?

A context switch is when the CPU switches from one process to another.

What happens during a context switch?

1. Timer interrupt or system call triggers kernel mode

2. Kernel saves Process A’s entire context (PCB)

3. Scheduler selects process B

4. Kernel restores process B’s context from its PCB

5. Switch page tables (change virtual memory mapping)

6. Return to user mode in Process B

What are system calls?

Synchronous requests for kernel services or access to system resources (managed by kernel)

What are interrupts?

Asynchronous signals to the processor that some event has occurred that may require attention (I/O completion, error)

What are library calls?

User-space functions that run entirely in user mode (no kernel involvement, fast)

What is a signal?

Software notifications/interrupts sent to a process to notify it of an event (integer)

SIGINT

Ctrl + C

SIGKILL

Force kill (can’t be caught or ignored)

SIGTERM

Polite termination request (can be caught)

SIGSTOP

Pause the process (can’t be caught)

What is the role of interrupts in modern operating systems?

Interrupts allow the OS to regain control of the processor. Allows for preemptive scheduling and responds to hardware events asynchronously

Timer interrupts

Will interrupt the processor after a specified time period (force mode switch to kernel)

Device Interrupts

Notify when I/O completes

What does a process look like to the programmer?

To the programmer, a process has a code body, global variables, heap memory, and stack memory.

What does a process look like to the operating system?

To the OS, a process is portrayed as a PCB which contains registers, memory information, address space, and process ID.

What is a thread?

A lightweight execution unit within a process

A process differs from a thread in which ways?

• Separate address space

• Independent resources

• Isolated

A thread differs from a process in which ways?

• Shared address space

• Shared resources

• Own stack and registers

What is a PCB?

The PCB is what contains information about a process’s state. It is what is tracked by the OS.

What is a TCB?

The TCB contains registers and anything needed to resume the thread.

What is held within the PCB?

• Process ID

• Process state

• PC

• I/O status

• Memory information

• Address space

• Processor Registers

What is held within the TCB?

• The stack pointer to the thread’s stack

• Copy of processor registers

• PC

• Thread ID

• Thread state

• Pointer to thread’s PCB

• Scheduling information

pthread_create()

int pthread_create(thread ID, thread Attributes, Function to run, Argument to pass)

pthread_join()

• Waits for target thread to finish

• int pthread_join() thread ID, void **return value)

What are kernel threads?

Threads that are created and scheduled by the kernel (pthread_create)

What are user threads?

Threads that the kernel is not aware of (virtual threads)

• Requires at least 1 kernel thread to have user-threads

• CANNOT achieve parallel processing since all user-threads are on the same core

• Switching from one thread to another is more efficient using user-threads since switching threads does not need to go through the kernel

What is a shim?

An intermediary layer that intercepts function calls between a program and a library

What do shims allow us to do?

Allows us to modify, monitor, or replace the behavior of function calls without changing the original process code.

What does LD_PRELOAD do?

LD_PRELOAD allows us to load our libraries prior to code execution.

Signals IPC and Pros & Cons

Sends the process an integer

• Fast

• Can be asynchronous

Shared memory IPC and Pros & Cons

Allows many processes to access a common memory region

• Fastest

• Concurrent access can cause data corruption

• Memory region persists until explicitly removed or system reboot

Pipes IPC and Pros & Cons

A communication channel that connects a related process’s output to another process’s input

• Allows for chaining

• 1 direction for communication

• Easy IPC

• Fast

Named Pipes IPC and Pros & Cons

Allows unrelated processes to communicate by sending and receiving data through a special file in the filesystem

• Opening a named pipe blocks until both a reader and writer are present

• Rely on conventions (white space or newline) for termination

Messages IPC and Pros & Cons

Uses a key-based queue system to allow communication

• The client can send a message and terminate with the server being able to retrieve the message later

• Clear sender/receiver roles

• Each process works with its own queue

• Can cause collisions if another program uses the same keys

Sockets IPC and Pros & Cons

A server sets up a network (localhost), which is used to communicate with clients

• slow

• flexible

• can be asynchronous

What is a TCP socket?

A socket that is only connected by the client and the server which can see the message.

What is a UPD socket?

A socket that allows many processes to receive the same message.

What are the exec variations and what do they do? (4 of them)

• l = list (arguments as separate parameters)

• v = vector (arguments as an array)

• p = PATH (search PATH for executable)

• e = environment (specify custom environment variables)

What is the ptrace structure?

long ptrace(int request, pid_t pid, void *addr, void *data)

What does ptrace allow us to do?

Allows us to observe and control another process

What are race conditions?

Race conditions occur when multiple threads access shared data concurrently and the final result depends on the timing/ordering of their execution.

How do we prevent race conditions?

• Mutex locks

• Semaphores

• Condition Variables

• Atomic Operation

• Spin locks

What are spinlocks?

Mutex locks that continuously check if the lock is free

• Good for short wait times

What are mutex locks?

Makes an operation atomic and sleeps an operation if the lock is not available

• Good for single core

What is a binary semaphore?

A semaphore whose value can only be 1 or 0

• 1 = available/unlocked

• 0 = unavailable/locked

What are counting semaphores?

A counting semaphore allows up to N threads to run at the same time

• N = amount of threads (initial val)

• 0 = block threads

What are condition variables?

Condition variables have a thread waiting queue for threads to wait when the work queue is empty.

• Producer/consumer relationship

What are Read and Write locks?

Locks that allow for many reader threads but only one writer at a given time.

What is a deadlock?

Waiting on a resource that will never become available

Requires:

• Mutual exclusion

• Hold and wait

• No preemption

• Circular wait

What does parallel mean?

Working on different processes at the same time

What does concurrency mean?

Working at several tasks at once (does not mean at the same time)

What is global scope/ system scope?

Scheduling that treats all threads as equal and does not look at which process they are from.

What is local scope/ process scope?

Scheduling that chooses a process and then threads within that process compete against each other.

What is CPU affinity?

Allows us to choose which core a thread runs on, and that thread cannot run on other cores.

Why do we use CPU affinity?

It is used for cache performance since we do not need to transfer cache since the thread stays on the same core.

pthreads condition variable implementation

// pthread condition variable
pthread_mutex_lock(&mutex);
pthread_cond_wait(&cond, &mutex);  
// When this returns, you HAVE the lock again!
pthread_mutex_unlock(&mutex);

pthreads mutex locks implementation

// pthread mutex lock
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&m);
pthread_mutex_unlock(&m);
pthread_mutex_trylock(&m);  // Returns 0 if successful

FSFC (FIFO) Scheduling

First come first serve

Round Robin Scheduling

Each process gets a designated amount of time with the CPU

SJF scheduling

The shortest job is scheduled first

Fair Share scheduling

Allocates CPU time based on the user/group that owns the process. Each user/group is designated the same amount of CPU time regardless of amount of processes.

EDF Scheduling

The process/thread with the earliest deadline first is scheduled

Least Slack scheduling

The process/thread with the least amount of time before its deadline (deadline - current progress) is scheduled first.

Rate monotonic scheduling

Processes/threads that occur the most often at a set rate are scheduled first.

What is priority?

A process/thread with the most priority is favored to be run first.

What is multilevel priority queueing?

Where there are several queues that represent priority levels.W

What is multilevel feedback queueing (MFQ)?

Multilevel priority queueing but processes can change priority queues based on their behavior.

What is an admission-control algorithm/system?

A system that decides whether to accept or reject a new process/thread based on whether the system has sufficient resources to handle it.

Why would we need an admission-control system?

To prevent system overload or thrashing

Short-term scheduler

Decides what process to run next

Medium-term scheduler

Decides how many process to run

Long-term scheduler

Decides whether to accept/reject a new process

Copy-On-Write

Multiple processes use the same frame, but will copy the data to another frame if a process has written to it.

Hugepages

OS have started to have designated memory blocks for processes that are much larger than the page size.

Explicit Memory Management

The programmer must free no-longer-needed memory.

Implicit Memory Management

The programmer does not need to free memory manually.

Garbage Collectors

Automatic memory management features that typically use reference counters to determine to free memory.

• If a reference counter hits 0, then we can free it

Why does C not have garbage collectors?

In C, we cast types to pointers and garbage collectors will view any 8-byte memory block as a pointer since there is no way for certain to determine that “this block is a pointer”.

Segment Table

A table that has an entry for each segment of memory and stores the base address for the segment and its size.

Segmentation Details

• Slow because of the comparison and addition instructions on every memory access

• External fragmentation

External Fragmentation

Little pieces of memory that are never used (too small to accommodate most processes).

Defragmentation

Copying memory and moving it up in the HHD/RAM/etc.

• If we do not care about security, we can leave old data in the old address spaces

• Costly

• Slow

Pages

Virtual memory chunks

Frames

Physical memory chunks

All memory chunks are the ____ size in both virtual and physical memory?

1. Same

2. Different

Internal Fragmentation

Wasted memory space within memory chunks.