Operating Systems Lecture Notes Review

Flashcards to review key concepts from operating systems lecture notes, covering IPC, networking, threads, synchronization, memory management, and CPU scheduling.

What is IPC?

Inter-Process Communication, a mechanism that allows processes to send and receive data from each other.

What are two general classes of IPC?

Shared Memory and Message Passing.

Can shared memory IPC be used for processes on different computers? Why?

No, it's typically limited to processes on the same computer due to the nature of shared memory.

What is a network?

A bunch of computers connected together to exchange data.

What is an IP address, and what does a classic IPv4 address look like?

A logical address used for addressing a destination computer. It looks like 146.86.5.20 (dotted-decimal notation).

Why isn't an IP address alone enough for networking communications?

It doesn't specify which process or application is being contacted and doesn't provide reliable end-to-end communication on its own.

What is the idea of shared memory for IPC, and what are its advantages and disadvantages?

A piece of memory shared between processes. Pro: faster than message passing. Con: hard to implement and only usable on the same computer (error-prone).

What is the idea of message passing for IPC, and what are its advantages and disadvantages?

Taking a piece of data from one process and asking the OS to send it to another. Pro: less error-prone. Con: slower than shared memory.

On what kind of computer(s) can shared memory be used?

Only used for processes running on the same computer.

On what kind of computer(s) can message passing be used?

Multiple computers.

What allows disparate computing devices to communicate?

Adopting standard communication protocols

What does an IP address specify?

Destination computer (host).

What does a network port specify?

A unique number that identifies where network connections start and end and specific receiving (and sending) process.

What is a networking port?

A unique number that identifies where network connections start and end.

What are well-known ports?

Port numbers that have a pre-defined function.

What is a networking socket?

Socket = IP address + Networking port. An endpoint for communication between two programs.

What is a server?

A computer that sends services/resources to clients that request them.

What is a client?

A computer that requests a service or resource from another process or entity.

What is a communication protocol?

Defines data exchange rules.

What is a URL?

Uniform Resource Locator - the address of a web resource that specifies its location on a computer network.

What is DNS?

Domain Name System - translates domain names to IP addresses to access a specific web resource.

What is RPC?

Remote Procedure Calls - a mechanism that abstracts procedure calls for use between systems with network connections.

What is a thread?

The sequence of instructions that can be executed independently by a CPU.

Why might you create new threads instead of processes?

Memory Efficiency -> RAM Efficient

Why might you create new processes instead of new threads?

Processes are Independent
Security: with isolation is enhanced security. Because processes have distinct memory spaces, it is more difficult for one process to maliciously (or accidentally) access or corrupt the data of another process.

What do threads belonging to the same process share?

Text sections, Data, Heap Memory.

What don't threads belonging to the same process share?

Stack.

What are synchronization problems?

Programming problems that arise when you create multithreaded code or a program that exchanges data with other programs.

What is a shared resource?

A resource used jointly by multiple programs/threads.

What is a race condition?

Corruption of shared data accessed by multiple threads. A bad scenario when data is corrupted because multiple processes try to access it simultaneously.

Explain how race conditions can happen.

When two threads running together both call increment() on a global variable or when multiple processes or threads access and manipulate the same data concurrently, and the outcome depends on the specific order of access.

Can race conditions happen if only one party modifies the data and others are just reading?

Yes, If everyone is just reading it would not cause a race condition, it only involves when there's modification or data access loss which would lead to corrupt data.

What is the critical section problem?

A problem that occurs when two threads execute their critical sections at the same time. A section of code that accesses shared resources and must be executed by only one thread at a time

What are three properties of a good solution to the critical section problem?

Mutual exclusion, progress, and bounded waiting.

Explain the idea of locking shared resources.

A technique that allows multiple threads or processes to safely access and modify shared data without interfering with each other. Using locks ensures data consistency and prevent synchronization problems.

What does atomic function mean?

1) Only one copy of this function can run at a time. 2) Once the function starts, it finishes.

What does it mean if a function is hardware implemented?

There is no program code for it, no general CPU instructions written in memory. The function is implemented with hardware circuitry and called with a single special CPU instruction.

What is testandset instruction and what does it do?

It is a hardware-implemented (atomic) function that grabs a lock for a program when it wants to use a shared resource.

What is suboptimal about a simple solution to the critical section problem using testandset instruction?

It doesn’t have the “bounded waiting” property, in other words, it is not starvation-free. A process could wait forever.

Solution of the critical section problem using testandset instruction with the bounded waiting property. Waiting Array

-an array of booleans
-number of elements = number of processes competing for resource
-size of array is known (N)
-True= element is waiting

What is busy waiting?

A situation when a process occupies the CPU while waiting.

What is spinlock and why is it inefficient? When is it still good?

It’s inefficient because a process is keeping other processes from using the CPU even though it doesn’t need to. It is still good when expected wait times are short and it is “cheaper” to wait while using the CPU than to perform context switching to another process.

What is mutex?

A mutually exclusive access to a resource. The primary goal of a mutex lock is to protect critical sections of code or shared data. It ensures that only one process or thread can access the protected resource at any given time.

What does the process do if it needs a mutex that is busy?

It pauses and waits for the mutex to be free again before proceeding further.

What is the Producer-Consumer problem (Bounded Buffer problem)?

An issue where the producers generate processses that go into the buffer, unless the buffer is full, and the consumer that consumes process from the buffer, unless it’s empty. Consumers can only consume single process at a time.

What is the solution mechanism to solve the Producer-Consumer problem (Bounded Buffer problem)?

Producer generates something that consumer use (separate threads). Producer stops and waits if no empty space is buffer. Consumer stops and waits if there are no items in the buffer, to avoid race conditions.

What is the Readers-Writers problem?

Many writers and many readers want to access a shared resource. Design a synchronization protocol that allows multiple readers to read concurrently but ensures that only one writer can access the shared database at a time, and that no reader can access the database while a writer is writing.

Describe Dining Philosophers problem. What do philosophers represent? What do chopsticks represent?

N philosophers sitting at a table with N chopsticks. If they all get hungry at the same time, all go to pick up left, then go to pick up right but there is none left, must wait for right, waiting forever. Philosophers = threads/processes. Chopsticks = shared resources

What is a deadlock?

A bad situation when multiple threads/processes block each other and no one moves forward. Such wait continues forever without intervention.

Name 3 approaches to solving the dining philosophers problem.

Add extra chopsticks - limited amount of resources. Limit the number of philosophers (processes) - limiting will prevent deadlock. Asymmetrical solution

What is RAM memory's purpose?

Your computer or laptop's short-term memory, where the data is stored that the computer processor needs to run the applications.

What is a memory address? How much memory can you address with 64-bit addresses?

A reference to a specific memory location. 64-bit addresses can address 2^64 bytes of memory.

What is a physical address?

The actual address in RAM where data is stored.

Why are physical addresses inconvenient for modern programs?

Allows processes to access memory without knowing the physical memory location and program behaves if it's alone in RAM

What is a logical address?

Memory coordinates that the process sees. The addresses used by the program code. An address generated by the CPU.

What is physical address space? How many physical address spaces are there in the system?

A collection of all physical addresses available in a system. The physical address space is RAM. There is one physical address space.

What is logical address space? How many logical address spaces are there in the system?

A collection of all available logical addresses. One logical address space per process.

What kind of address does the CPU fetch with instructions?

Logical addresses.

What kind of address does the CPU send to RAM with a load/store request?

A physical address.

What is MMU? What is its purpose?

Memory Management Unit is a piece of hardware that converts logical addresses to physical addresses. MMU also checks that a process doesn't exceed its allocated memory.

What is contiguous memory management?

A memory-management scheme primarily discussed as an early method for managing main memory. Process places in memory in one piece.

What is fragmentation? What is external fragmentation? What is internal fragmentation?

A condition where free memory or storage space becomes broken into pieces, potentially making it difficult or impossible to use. External is enough memory but not contiguous. Internal is wasted space inside allocated blocks.

What kind of fragmentation does contiguous memory management suffer from?

External fragmentation.

What is paging?

A memory management technique that splits physical memory into fixed-sized frames and logical memory into blocks of the same size, called a page. The goal is to solve external fragmentation.

What is a page? What is a frame?

When paging is used it splits the RAM into portions; pages are logical memory and frames are physical memory. Frames are the units of allocation in physical memory.

What kind of fragmentation does paging suffer from?

Internal fragmentation.

How do sizes of pages and frames relate?

They are the same size.

What is page offset?

The distance between the given address and the beginning of the page. Used in the page table to keep track of the location of the page.

What is a page table?

A page table contains the mapping of all logical pages to the physical frames

How many page tables are there in a system?

There are different page tables for every process

What is TLB? What is its purpose?

Translation Look-Aside Buffer(TLB) - a small memory device that can store a few entries from page table. Helps speed up the translation of logical addresses to physical addresses, because storing RAM and MMU are slow.

What is TLB hit? What is TLB miss?

A TLB hit: Needed page table entry is already in TLB. A TLB miss: TLB doesn't have the needed page table entry.

Is it necessary to have the whole program in memory to run it?

No, can copy only the needed part (data/instructions) from memory each time.

What is a page fault?

A situation when something is needed in RAM but it's not in RAM, but on the hard disk. It's time consuming, but not an error.

What is CPU scheduling about?

Deciding which process or thread from the ready queue gets allocated a CPU core to run on.

What does the choice of a specific CPU scheduling algorithm depend on?

Different operating systems have different focuses, efficiency goal, fairness, and system responsiveness.

What is CPU burst? What is I/O burst?

CPU Burst: A period of time that a process wants to use the CPU. I/O Burst: a period of time that a process wants to use I/O device

Why can it be beneficial to schedule short CPU burst processes to the CPU before long CPU burst processes?

This minimizes the average wait times and prevents the Convoy Effect.

Shortest-Job-First algorithm. Its idea, advantages, and disadvantages.

When the CPU is available, it is assigned the process with the smallest next CPU burst. Pros: minimal average waiting times, kinda fast. Cons: Not starvation free.

What does it mean a CPU scheduling algorithm is preemptive or non-preemptive?

Pre-emptive: A process can be sent to the ready queue in the middle of its CPU burst. Non-preemptive: The Process is free to use the CPU for the whole duration of CPU burst, for as long as it wants.

What does it mean a CPU scheduling algorithm is starvation free?

No process can wait forever to use the CPU.

First-Come-First-Served algorithm. Its idea, advantages, and disadvantages.

Fast (simple to write) and starvation free. Cons: long waiting time (keep ready-queue for long periods).

Round-Robin algorithm. Its idea, advantages, and disadvantages.

A pre-emptive version of FIFO; treats the ready queue as first come first serve but a process has limited time spent in the CPU. Pros: fast (only maintain the real queue) and starvation free. Cons: long wait time.

Priority scheduling. Its idea, advantages, and disadvantages.

Each process has a number that tells its level of importance, it chooses the next process with the highest priority. (pre-emptive). Pros: Accounts for priority. Cons: Not starvation free.

Aging.

A method to fight starvation. It gradually increases the priority of processes that wait in the system for a long time.

Priority inversion and priority donation.

Priority inversion => an unlucky situation where a higher priority process waits to access data that is being accessed by a lower priority process. Priority donation (priority inheritance) => a solution to priority inversion where all processes that are accessing resources, needed by a higher-priority process, inherit the higher priority until they are finished with the resource..

Real-time scheduling.

Threads in real-time class are given the highest priority. Allows a real-time process to have a guaranteed response from the system within a bounded period of time. A real-time process will run before a process in any other class.

Soft and hard real-time systems.

In soft real-time systems, the system continues to function even if missing a deadline, but with undesirable lower quality of output. A hard real-time system has absolute deadlines, and if those allotted time spans are missed, a system failure will occur.