CS 350 Terminology

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/108

encourage image

There's no tags or description

Looks like no tags are added yet.

109 Terms

1
New cards

Two roles of an operating system

  1. Facilitator: abstractions, resource accesss

  2. Cop: protection, control


2
New cards

Preeemption

Take resources away from a long running process

3
New cards

Memory protection

Prevent one process from accessing another’s memory

4
New cards

Privileged and unprivileged modes

  • Applications run in unprivileged mode

  • OS runs in privileged mode


5
New cards

Process

A running instance of a program

6
New cards

Each process has its own:

  1. Address space

  2. File descriptors

  3. Virtual CPU


7
New cards

Virtual CPU

A single process essentially thinks it has dedicated access to its own CPU

8
New cards

Different process ___ the same virtual addresses

can use

9
New cards

How to improve performance without multiple cores

  1. Increase CPU utilization

  2. Reduce latency


10
New cards

Execution environment

The context and runtime infrastructure provided by the OS in which a process executes

11
New cards

Return values of fork()

  • PID of new process in the parent

  • 0 in the child

  • -1 on error


12
New cards

fork()

Creates a new process that is almost an exact copy of the current one

13
New cards

A process and a forked child process have ___ address spaces

different address spaces, but of the same size and contents

14
New cards

exit(status)

Causes normal termination of the current process, either implicitly or explicitly

15
New cards

waitpid(pid, *wstatus, options)

Blocks the parent process until the child process terminates

16
New cards

fork() vs spawn()

  1. fork() has a simple interface and allows you to do whatever you want with the child process

  2. spawn() combines fork() and execv() into a single function, which is a common pattern


17
New cards

Process Control Block

A struct of process and state information:

  • State of the process

  • Information necessary to run: registers, virtual memory mappings, open files

  • Other relevant data about the process


18
New cards

States of a process

  1. New and terminated

  2. Running

  3. Ready

  4. Waiting


19
New cards

Ready state

Process can run, and is waiting to be ran by the kernel

20
New cards

Waiting state

Requires an async event (e.g. disk operation) to proceed

21
New cards

Yield

A process voluntarily gives up resources

22
New cards

Context switch

Changing the process running on a CPU

23
New cards

Causes of context switching

  1. Blocks waiting for an event

  2. Voluntary yields

  3. Exits

  4. Preemption


24
New cards

Common causes of preemption

  1. Timer interrupts updates CPU time

  2. I/O-completion interrupt


25
New cards

Ways the kernel gets control

  1. System calls

  2. Exceptions

  3. Interrupts


26
New cards

System call

An interface to allow a user-level application to request a service from the operating system

27
New cards

Exception

Current instruction causes an exceptional condition: page fault, illegal instruction, etc.

28
New cards

Interrupt

External event generated asynchronously by hardware: periodic timer expiration, I/O completion

29
New cards

Thread

A schedulable execution context within a process

30
New cards

Threads within the same process share:

  1. Address space

  2. Open files and other process resources


31
New cards

A thread has its own:

  1. CPU register values, including the PC

  2. Stack


32
New cards

Benefits of using threads

  • Lightweight abstraction for concurrency

  • Allow one process to use multiple CPUs or cores

  • Allow a program to overlap I/O and computation


33
New cards

Critical section

A part of a concurrent program in which a shared object is accessed

34
New cards

Race condition

When the outcome of execution depends on the particular order in which access takes place

35
New cards

Mutual exclusion

The guarantee that at most one thread is executing within the critical section at any given time

36
New cards

Progress

If no thread is on the critical section and threads are trying to enter, then one will eventually enter

37
New cards

Bounded waiting

Once a thread T requests entry, there is a bound to how many other threads can enter before T does

38
New cards

Progress vs. bounded waiting

  • If threads are trying to enter but none can, progress fails

  • If thread A waits while B repeatedly leaves and re-enters forever, bounded waiting fails


39
New cards

Sequential consistency

The result of execution is as if all operations were executed in the same sequential order, in the order specified by the program

40
New cards

Requirements of sequential consistency

  1. Maintaining program order on individual processors

  2. Ensuring write atomicity


41
New cards

Which process should the kernel run in a single CPU system?

  • If 0 runnable, run idle loop (or halt CPU)

  • If 1 runnable, run it

  • If >1 runnable, must make a scheduling decision


42
New cards

T/F: fork() returns once

False: fork() is called once, but returns twice

43
New cards

Concurrency vs. multithreading

  • Concurrency is a general concept about managing multiple tasks so they can make progress over overlapping time periods

  • Multithreading is a technique to achieve concurrency by creating multiple execution paths (threads) within a single process


44
New cards

File descriptor

A small non-negative integer that a process uses to refer to an open file or I/O resources

45
New cards

FD system calls

  • open() which opens a file and returns an FD

  • read(fd, …) locates the resource associated with the FD and copies it over

  • write(fd, …) locates the resource associated with the FD and writes to it

  • close(fd) removes the lookup layers and releases the resource associated with the FD


46
New cards

Steps of a process-to-process context switch

  1. Save the CPU state needed to resume the current process

  2. Change the current process’ state from running to ready, waiting, or terminated

  3. Run the scheduler to select a ready process

  4. Change the selected process’ state from ready to running

  5. Switch to the selected process’ userspace address space

  6. Switch to the selected process’ kernel stack

  7. Restore the CPU state previously saved for the selected process


47
New cards

Library OS

A library of standard services with no protection

48
New cards

Benefits of a Library OS

Able to simplify assumptions such that the system runs one program at a time, and there are no bad users or programs


49
New cards

Drawbacks of a Library OS

Poor utilization of hardware and human user (must wait for each program to finish)

50
New cards

Multi-user OS

Use protection to serve distrustful users and apps

51
New cards

What is required in a Multi-user OS

  1. Need policies for how much CPU a single user can use

  2. Total memory usage might be greater than what is in the machine

  3. Super-linear slowdown with increasing demand


52
New cards

What is an operating system?

  • A layer between applications and hardware

  • Hardware can be made useful to the programmer

  • Provides abstractions for applications (usually)


53
New cards

Interposition/mediation

  • The OS is placed between an application and other resources

  • Track everything that specific application is allowed to access

  • On every access, look in the table to check if that access is legal


54
New cards

Typical OS structure

  • Most software runs as user-level processes

  • The OS kernel runs in privileged mode

    • Creates/delete processes

    • Provides access to hardware


55
New cards

Kernel

The part of the OS that responds to system calls, interrupts, and exceptions

56
New cards

System calls

Special instructions which transfer control to the kernel

57
New cards

Zombie

A terminate child whose parent has not collected its exit status using waitpid()

58
New cards

Orphan

A child process whose parent has terminated before calling waitpid() on the child

59
New cards

What happens when a parent terminates without calling waitpid()?

  • If the child dies first: the child process becomes a zombie

  • If the parent dies first: the child process becomes an orphan

  • It is reparented and then reaped (remaining resources are freed)


60
New cards

Kernel entry steps

  1. Enter the kernel

    • Elevate access

    • Turn off interrupts

    • Save state

    • Jump to kernel entry point

  2. If entering from user mode, switch to process’ kernel stack

  3. Save execution state

  4. Determine cause and dispatch handler

    • Re-enable interrupts when appropriate


61
New cards

Kernel stack

A protected stack for its own function calls, local variables, and saved state

62
New cards

Application stack

A process’ (or thread’s) stack in user address space

63
New cards

Trap frame

  • Pushed onto the kernel stack when a trap (system call, exception, interrupt) occurs

  • Saves the process’ program counter and register values

  • Used to return from the handler


64
New cards

T/F: The kernel may modify the trap frame before returning

True: to modify return values

65
New cards

Which is typically larger: a trap frame or switch frame

The trap frame as it must save enough state to resume the interrupted execution

66
New cards

Switch frame

  • Pushed onto the kernel stack when the kernel switches processes

  • Does not need to save caller-saved registers

  • Used when the process is scheduled again


67
New cards

Steps of a system call

  1. Process invokes a system call, eg. close()

  2. Enter the kernel

  3. The process’ trap frame is pushed onto the kernel stack

  4. Call mips_trap() to determine whether caused by exception, interrupt, or system call

  5. Call sys_call() to determine which system call to dispatch

  6. Dispatch the system call sys_close()

  7. Store the return value in the trap frame

  8. Return to the current process


68
New cards

Creating a new thread with pthread_create()

  • Creates a new thread in the current process

  • Returns 0 on success

  • Error on failure


69
New cards

Terminating a thread with pthread_exit()

  • Terminates the calling thread

  • Does not return


70
New cards

Joining a thread with pthread_join()

  • Waits for a given thread to terminate

  • Returns 0 on success

  • Error on failure


71
New cards

What happens when a thread exits?

Its execution context and resources are given up

72
New cards

Kernel-level thread

An execution context represented and managed by the kernel

73
New cards

Thread control block (TCB)

Contains thread-specific information needed by the kernel to manage the kernel-level thread

74
New cards

T/F: A kernel-level thread only executes within a kernel

False: it can execute user code and enter the kernel when needed

75
New cards

User-level thread

When a kernel-level thread runs in userspace, a userspace library/runtime can create additional execution contexts

76
New cards

Benefits of user-level threads

  • Switching between user-level threads can happen entirely in userspace

  • Do not require entering the kernel

  • Can be much lighter-weight


77
New cards

T/F: Every kernel-level thread is a system call

True

78
New cards

1:1 thread configuration

  • Each thread maps to a unique kernel-level thread

  • High overhead

  • A blocking system call allows other threads to still run


79
New cards

N:1 thread configuration

  • NN user-level threads map to the same kernel-level thread

  • Lower overhead

  • A blocking system call will block all threads mapped to the same kernel-level thread


80
New cards

N:M thread configuration

  • NN user-level threads are mapped to MM kernel-level threads

  • Lower overhead than 1:1, but higher than N:1

  • A blocking system call will block the calling thread, but does not prevent other threads from running


81
New cards

Lost wakeup problem

A signal is sent just before or during the moment that a waiter goes to sleep, and so the signal is lost: the waiter sleeps forever

82
New cards

Hand-over-hand locking

  1. lock(m1)

  2. lock(m2)

  3. …

  4. unlock(m1)

  5. unlock(m2)


83
New cards

Deadlocks

When two or more threads wait on each other and no progress can be made

84
New cards

Necessary conditions for deadlock

  1. Mutual exclusion

  2. Hold and wait

  3. No preemption

  4. Circular wait


85
New cards

T/F: If a resource-acquisition graph has a cycle, then there is a deadlock

False: only converse is true

86
New cards

Lock ordering

Prevent deadlock with a partial order on resources: eg. always acquire mutex m1 before m2

87
New cards

Course-grained vs. fine-grained locking

  1. Course-grained locking is simple, and serializes independent operations

  2. Fine-grained locking allow for more concurrency

    • More overhead and complexity involved


88
New cards

Why does the kernel increment the program counter by 4 when handling an exception?

So that the process does not re-run the instruction that caused the exception

89
New cards

Spurious wakeup

A thread woken up randomly by the OS

90
New cards

File-descriptor table

  • Owned by an individual process

  • Entries point to entries in the system-wide open-file table


91
New cards

T/F: two different process’ file descriptors can point to the same entry in the system-wide open-file table

True

92
New cards

Pipe

A memory buffer in the kernel

93
New cards

T/F: Piped processes are run sequentially

False: both processes must exist before using a pipe

94
New cards

Memory and I/O buses

CPU accesses physical memory over a memory bus

95
New cards

Methods of accessing devices

  1. Explicit I/O instructions

  2. Memory-mapped I/O


96
New cards

Explicit I/O instructions

There are explicit instructions to read and update data

97
New cards

Memory-mapped I/O

Each device register has a physical memory address; use loads and stores to read and update data

98
New cards

Device Driver

The part of the kernel that interacts with a device

99
New cards

Polling

The kernel driver repeatedly checks device status

100
New cards

Direct Memory Access

The CPU initiates the transfer, and the device moves the data and notifies the CPU when finished