exam1 Flashcards

1
Q

What is a Virtual Machine?

A

A piece of software that runs as an application on your OS. It can be configured to run its own OS internally and allows multiple OS’s to run on the same computer.

It is run in the user space. Also called a “Guest Operating System”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the three layers of the computer?

A
  1. Bottom Layer: hardware the computer runs on
  2. Operating System: the Os that runs on your computer
  3. User Space: where we run different applications
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Host OS

A

The original operating system that comes on your machine. It’s also known as the OS that runs on “bare metal”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Why do we use VM’s?

A
  1. They allow multiple OS’s to run on the same machine.
  2. They allow developers to sandbox and test code on a specific operating operating system version.
  3. They allow for the cloud computing revolution.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the primary differences between Code Repositories and DropBox-like file sharing systems?

A

DROPBOX:
1. Files are automatically synchronized.

  1. Resolves conflicts by creating two copies.
  2. Some support for versioning but no branches.

CODE REPOSITORIES:

  1. Requires programmer explicit push and pull.
  2. Automatic merging of source code.
  3. Excellent support for branches and versioning.

Programmers use code repo’s over dropbox-like systems because:

  1. DropBox systems automatically sync changes meaning you don’t have control over reconciling version differences.
  2. Dropbox systems are for code editing so you end up with many file copies instead of merged files with updates from multiple places.
  3. Code repos have great support for branching and versioning.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What do the following vagrant commands do?

  1. vagrant up
  2. vagrant ssh
  3. vagrant suspend
  4. vagrant destroy
  5. vagrant halt
  6. logout
A
  1. vagrant up: Starts VM and provision according to vagrant file.
  2. vagrant ssh: Accesses your VM such that all future commands occur on VM.
  3. vagrant suspend: Saves the VM state and stops the VM.
  4. vagrant destroy: Removes all traces of the VM on your computer.
  5. vagrant halt: Gracefully shuts down the VM OS and powers down the VM.
  6. logout: Stops ssh connection and returns to your terminal.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the three primary sections of a vagrant file?

A
  1. Define: provide the host name for the VM and specify the guest OS we desire.
  2. Provisioning: install the tools (And correct versions of tools) that we’d like. Some examples are valgrind, gdb, etc.
  3. Machine: specify the # of CPUs and RAM that we want to allocate.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Operating System (OS)

A

A system that provides the interface between a user’s application and the hardware. It is the process scheduler for the computer.

  • Software that usually comes pre-installed on a computer. It includes a graphical user interface for you to interact with.
  • The OS allows you to run multiple applications at the same time and switch seamlessly between those apps.
  • It stores data on persistent storage devices.
  • It allows apps to interact with external devices like the monitor, mouse, etc.
  • OS does memory management which allows multiple apps stored at the same time in memory to be executed.

9

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

The Kernel

A

Forms the core of the operating system and provides all the key functionalities for managing interactions between user-level programs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

The Shell

A

A command interpreter for the operating system.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Data Storage in the OS

A

All data is stored in the form of files, and the OS maintains file names, sizes, locations, directory structure, and file access rights.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the two main functions of the OS?

A
  1. Abstract away the messy details of the hardware so that user programs can be written without needing to understand hardware interaction.
  2. Resource management.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

User Mode

A

In this mode, each application can only run instructions that affect its own applications. User mode executes the functions in the application mode.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Kernel Mode

A

Handles operating system functions that exist in the code. When these functions are run, the computer flips to OS mode. Only happens for select system calls and carries a lot of overhead. The division between this an the user mode helps us keep the operating system safe from errors and attacks.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a Process?

A

A program in execution. When a program runs, the OS needs to keep the program’s contents in memory and on disk. Processes run sequentially. Multiple processes can be running in the same application or at the same time. For example, running an application twice is treated as two separate process contexts.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Process Context

A

When a process stops, we get a snapshot of it. This includes the process’ data, memory utilization and execution context. This is savable so that the OS can save its place and then leave and come back.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Why does the OS run apps with the process abstraction?

A

At any point in time, the OS has to manage many applications at the same time. The abstraction allows it to package processes up into one bundle of information to make transitioning between them easier.

The OS also has its own processes for things like memory management.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How big is the address space of a process?

A

Each process has an address space that goes from 0 to 2^64 - 1 bytes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What part of memory are applications run in?

A

The CODE section. Also sometimes called the “text” section because it’s read only.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Program Counter

A

Holds the address of the next instruction to execute. It is part of the code segment.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Where is temporary data from a program stored?

A

The STACK.

Temporary data gets put onto the stack. It grows from the top down. New values get pushed onto it, and when the function call ends, the stack stops tracking the data. We track the bottom of the stack to ensure we don’t hit the heap and overwrite data there.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are Data Segments?

A

These are the global variables. They are defined using the static keyword and are determined at compile time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

The Heap

A

Stores Dynamically Allocated Memory and it grows at run time as data is added to it. It can grow and shrink as data is added/freed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the order of memory segments from top to bottom?

A

Stack (grows downward)

Heap (grows upward but can have items randomly placed)

Static Data

Code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the PID?

A

Stands for Process ID.

Each process gets its own. The OS maintains a table or array of process control blocks (PCB). Each entry points to a PCB.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is a PCB?

A

Stands for Process Control Block.

The PCB stores the context of a process. This includes:

  • Stack Pointer
  • PC
  • Computer Register Values
  • Segment Register Values
  • Status

When a process is executing, only the hardware registers are updated. When the process pauses or ends, all of its information is stored in the PCB. The PCB does not update in real time, it just gets the values when the process pauses/stops. The PCB does not store the contents of memory, just the mapping to physical memory where they exist.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is the PPID?

A

Stands for Parent Process ID.

Parent and child processes have their own virtual address spaces and can run independently, but they share some resources like file descriptors and semaphores.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Define the hierarchy of Linux processes

A
  1. The Root is the Init Process that starts when your OS first boots up.
  2. Then the System Processes are started. They perform internal OS management tasks, typically related to memory management.
  3. Then there is sometimes SSH server that listens for requests.
  4. Then comes the User Shell which accepts user commands.
  5. Any app processes the user runs.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is the fork() system call?

A

Creates a new child process.

The child gets a PID of 100.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is a Child Process?

A

It is created by forking from another process. It starts off as almost identical to its parent because it starts as a copy of the parent address space. It even starts with the same PC value which means they run concurrently. This is considered “lightweight”, a “copy on write” or “lazy copy”. It means the child shares the same memory location as the parent.

There is one big difference though. The parent gets a value of 100 set to its local Child PID variable. The child process gets a 0 to start. If it forks its own child, that grandchild gets a PID of 200. These values are NOT the same as the OS PIDs.

After forking, if the parent’s Child PID value is not 0, the child can run.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Process Memory Construction

A

A process’ memory is broken into smaller parts called pages. The child process gets its own page/pages when it modifies a page/pages.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

The wait() call

A

A way for a parent to wait for a child to finish running. The parent forks the child, then it checks the PID is valid, and waits for the child. The child runs as a separate process, and then calls exit() which unblocks the parent.

An exit code of 0 indicates graceful exit.

The & sign that is seen in the wait call (wait(&status)) means “call by reference”. This copies the exit value of the child into the address pointed to by the status of the parent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

The waitpid(pid, &status, options) call

A

PID specifies the child, and options specifies whether or not the parent should wait or proceed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

SIGKILL

A

A signal to terminate a target process immediately. A process can kill another process only if both processes belong to the same user and if the “kill process” is owned by a superuser.

When a process is terminated, all of its resources are freed. If a parent terminates, its children become orphans. The child’s parents become the Init Process.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Zombies

A

Come up when the child process has stopped running, but the parent had not called wait. This leads to wasted resources in the kernel since the PCB of the child cannot be reclaimed until the parent calls wait(). It’s the equivalent to un-freed heap space.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Daemon

A

Processes that are system level and are for OS-specific tasks. The parent of these is the Init Process.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What are the steps for switching processes?

A
  1. P1 stops running so P2 can run.
  2. CPU → kernel mode. We go from user to kernel.
  3. OS starts running now that we are in kernel mode.
  4. OS copies CPU register values to P1’s PCB.
  5. Then the OS runs P2.
  6. It loads P2’s PCB values into the CPU.
  7. OS goes back to user mode.
  8. P2 starts running.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

What is the life cycle of a process?

A
  1. Process is created.
  2. It is put into a ready queue to be run by the OS when it is ready.
  3. The process runs.
  4. The process may be blocked for some reason. In this case, it is blocked and then put back in the ready queue.
  5. The process terminates.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What happens when a hardware or software interrupt happens?

A

The OS handles the interrupt and blocked processes may become ready. The scheduler may choose to continue running the current process OR pick another process to run. After the OS handles the external event, it can continue the previously running process or select another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

How big of a time slice to most processes get?

A

100ms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

What is the tradeoff for a process that gets a larger time slice than normal?

A

A large time slice means improved throughput since the OS wastes less time switching, BUT it comes at the expense of longer response time since other processes need to wait longer to run. It makes apps appear sluggish.

This is common to see with user input apps which require a larger time slice.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

What are some of the types of processes that get higher priority?

A
  • Interactive apps that block frequently because of system calls.
  • User-defined priority, called “nice” commands in Linux.
  • System Daemons (typically get higher priority).
  • Processes run by a user that has higher priority over other users on the computer.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

What happens when fork() is called?

A

A new identical clone of the parent is created.

Both the parent and child become immediately ready.

The parent may not be able to run after the fork call. The scheduler will decide.

In a multicore machine, they may run concurrently.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What happens when exec() is called?

A

A file is opened, its contents are loaded into memory, and the context is reset. The process goes to a ready state as soon as this happens (if the executable is already cached in memory). It might be blocked if opening or loading takes a while.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

What happens when wait() is called?

A

If the child IS NOT running, the parent process is in a ready state. If the child IS running, the parent process is put into a blocked state.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

What happens when exit() is called from within a child?

A

The child process terminates, its resources are released, it passes its exit value back to the parent, and the parent becomes ready. If the parent is blocked, then it waits in the ready queue until it is selected by the scheduler.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

What is a file descriptor?

A

It represents an input or output device.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

What are the arguments of the read() function?

A

ssize_t read(int fd, void *buf, size_t count);

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

What are the arguments of the write() function?

A

ssize_t write(int fd, const void *buf, size_t count);

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Does buffering improve performance when reading/writing data?

A

Yes. Buffering results in improved performance because data can be read in larger blocks.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

What happens to the process state if an error occurs with I/O?

What if the file for I/O is available?

What happens if it’s not available?

A

If an error is called, the process is put into a ready state.

If the file exists, the process is put into a ready state.

If the file does not exist or is not found, the process goes into a blocked state. If data gets presented later, it may not automatically go to the ready state. This is because the call requires trapping from the kernel.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

What does it mean to “leak processes”?

A

It means that new children were forked before old ones terminated. This is VERY bad.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Where should malloced data be freed?

A

Unless you have a very good reason to do so, a function should avoid freeing memory that it didn’t allocate. OR it should avoid allocating memory while expecting the caller to free it.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

Do does calling different functions within a process require a context switch?

A

No. You are staying inside the same process so it is not necessary.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

What are System Calls?

A

System Calls are operations that run code in the kernel. There are some that can be called from user mode, but many more that are restricted to only kernel mode.

Every System Call has limited entry points in the kernel so that they don’t disturb any other code or data.

When a System Call happens, a context switch occurs. The caller is then put in the ready queue or the blocked queue.

System Calls are more expensive than regular function calls. This is because we have to context switch. Also, restarting a different process can be even more expensive because you have to load a different address space. This likely destroys the cache’s and virtual memory.

Lastly, System Calls usually have return values while interrupts do not.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

What is a System Call Number?

A

A System Call Number is used by the system call dispatcher which is the gatekeeper of the system calls. A lookup table is used to match the call number with the right function (think of the TRAP tables from 593). Once the function is called, the PC gets set to the start of that function.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

Hardware Interrupts

A

While System Calls are initiated by user programs, Interrupts are initiated by the machine.

Example: there is a pending operation on the disk that is now complete. A hardware interrupt is generated and picked up by the operating system.

Each interrupt has an interrupt handler. At this point, the OS then invokes the proper user-level operation that is waiting for the signal.

They have no return values because their interrupt is completely unrelated to the current process.

Common things that hardware interrupts for: inputs from devices, illegal instruction, clock pulse.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

How is a Hardware Interrupt processed?

A
  1. The current user program stops running.
  2. Trap to the kernel to run the appropriate interrupt handler to process the interrupt. This is chosen based on the Interrupt ID sent with the hardware interrupt.
  3. The hardware interrupt handler then might be unblocking a process that was waiting for the completion of a disk operation.
  4. When the interrupt handler completes, the OS transitions back to user mode.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

What happens in a process when a hardware interrupt occurs?

A

The process may not know if an interrupt will be happening. It also has no parameters for the stack and no return value.

An interrupt’s parameters are passed with the signal and are of no concern to the developer.

Returning from an interrupt just means restarting the initial process where it left off. This is what interrupts and system calls have in common: they both require context switching and remembering of the execution context so that the previous process can continue execution. Note though that the previous process may not start running first when the call/interrupt is done.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

What is the general process for an interrupt?

A
  1. A process is running.
  2. An interrupt happens. CPU transitions from user to kernel mode.
  3. Interrupt signal is processed by the OS’s “Interrupt Service Routine.
  4. The ISR has all the info needed to process the interrupt.
  5. The process’ execution context is saved to the PCB.
  6. The interrupt ID from hardware is used by the ISR to determine the appropriate device driver to call.
  7. The device driver then identifies the correct handler for processing the interrupt.
  8. The handler finishes and a process is pulled from the ready queue, and we switch back to user mode.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

Inter-process Signalling

A

P0 wants to send a signal to P1. The signal is delivered by going through the OS. We have to go through the kernel for this because the OS doesn’t allow processes to communicate to each other on their own. Processors are their own custom signal handlers. The OS simply relays the signal.

You can also process signals without a custom handler in the process, the OS also provides default handlers that take default actions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

What is a Signal?

A

A signal is an asynchronous software multiplication mechanism that notifies a process of an event. It’s like an interrupt. It can be initiated by another process or could come from the OS.

The simplest form of inter-process communication.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

What is a Signal Handler?

A

A function that is executed by a process upon receiving a particular signal. By default, the OS has a default action for each signal. Some can be overwritten by the user program.

64
Q

What do each of the following do?
SIGALARM

SIGCHLD

SIGINT

SIGKILL

SIGTERM

SIGUSER1/SIGUSER2

SIGFPE

SIGSEGV

SIGSTOP/SIGCONT

A

SIGALARM: Alarm clock.

SIGCHLD: Child process terminated/stopped or continued.

SIGINT: Terminal interrupt signal.

SIGKILL: Kills a process. Cannot be caught or ignored.

SIGTERM: Graceful termination request. Can be caught or ignored.

SIGUSER1/SIGUSER2: User-defined signal 1 and 2.

SIGFPE: Erroneous arithmetic operation.

SIGSEGV: Invalid memory access.

SIGSTOP/SIGCONT: Stop/continue execution. Stop cannot be caught or ignored.

65
Q

Are signal handlers preempt-able, meaning, if a process is handling a particular signal, can a new signal come in and stop the current signal so it can run?

A

It depends. For example, say SIGINT is running. Sending more SIGINT’s will not interrupt the first. BUT, a SIGKILL can. The OS recognizes some signals as more important than others.

66
Q

What is sigaction()?

A

It is an API that allows you to pass in specific signal types and then track what the previous signal handler was:

int sigaction(int sig, const struct sigaction * restrict act, struct sigaction * resctrict oact);

67
Q

What is Redirection?

A

A mechanism for an application to redirect either its input or output from one I/O device to another (i.e. tell the process to write to a file instead of the screen).

To set a new input for a process, we use:

process_name < input_device

To set a new output for a process, we use:

process_name > output_device

NOTE: we cannot have multiple redirects into or out of the SAME process. i.e. cat cannot get input from two places.

Also note: these signs < and > are commutative.

68
Q

What is Pipelining?

A

Allows the output of a process to automatically become the input for another process.

We use the “|” operator where the program to the left becomes the input for the program on the right.

It is a half-duplex type of communication paradigm. It is not the same as sockets.

We are only interested in left to right communication.

Consider: We have a process that does a cat of makefile. Sometimes the makefile is really large and the cat command shows the makefile so quickly you can’t see it all. But, the OS allows you to send the output of cat to “more” which buffers and only displays content one screen-full at a time. What happens under the hood is that the STDOUT of cat is used as the STDIN of “more”. These processes run concurrently.

69
Q

What is Job Control?

A

A method for running multiple processes in the shell. For example, say you have multiple tabs open for different apps, but only one of them should be accepting keystrokes at a given time? Job control manages this.

It allows us to start multiple jobs in a single terminal and toggle jobs between the foreground and background.

70
Q

How is dup2() used?

A

dup2() duplicates one file descriptor onto another.

We essentially use it to change the behavior of STDOUT. The first argument to dup2() is the NEW output location (or input location) and the second is STDOUT (or STDIN):

new_stdout = open(“new_stdout”, O_WRONLY | OCREAT, 0644);

dup2(new_stdout, STDOUT_FILENO);

When this happens, the STDOUT_FILENO gets pointed to the new output file/location we want.

71
Q

What does “Half Duplex” mean?

A

It means data flows from one process to another in one direction, and also back the other direction. For pipelining, we care about the left to right direction: from A to B.

72
Q

How does the API for a pipe work?

A

It takes two file descriptors. the first is fd[0] and the second is fd[1].

fd[0] is for opening and reading data.

fd[1] is for writing out the data.

If you put a pipe on a single process, it basically just speaks back to itself.

Children inherit pipes from their parents.

NOTE: reading from a pipe whose write end has been closed returns EOF.

73
Q

What is SIGPIPE?

A

It is the signal that is generated when you write to a pipe whose read end has been closed.

74
Q

Piping between Parent and Child process

A

When you write fd[1] for the parent, it goes to the read end of the child pipe. Conversely, the child can communicate back to the parent using its fd[1] which will direct to fd[0].

Because we are only interested in left-to-right communication, you can close the write end of the child pipe.

75
Q

What is the overall process for piping?

A
  1. The parent creates a pipe.
  2. We fork a child.
  3. On the parent side, we close the read end of the pipe and we send data over the pipe.
  4. On the child side, we close the write end and we read from the read end. We also write to STDOUT to display what we need.
76
Q

What is a Process Group?

A

A collection of processes that are established in such a way that you can send a signal to the entire group at the same time. Pipelines are a good example of this. When we pipeline multiple processes together, we create a process group. You can also block signals to the entire group.

You can send a ctrl-c signal this way to cancel all processes.

Note: if you used a “;” instead of a pipe operator, you would be creating individual groups.

77
Q

What does the “ps” terminal command do?

A

It shows you all the processes that are currently executing.

You see a “pgid” or Process Group ID here where the left-most process is the leader of the process group. Therefore, the PGID is the same as that process’ PID. You can then pipe an instruction to that one leader and it will go to all members of the group.

78
Q

What is a foreground process?

A

When the shell opens, the process of it waiting for commands is considered to be the foreground. When the first process runs, it enters the “foreground” and the shell blocks and waits for that process to complete.

The foreground process is that which receives all terminal input and generated signals.

If you have a process group where one process is in the foreground, they are all in the foreground.

79
Q

What is a pseudo terminal device?

A

A remote computer located elsewhere that has access to the terminal.

80
Q

How do we create foreground/background processes?

A

We use the & symbol.
For example: sleep 10 &

This command will cause the process to sleep for 10 seconds, but you immediately get prompted to type in the next command to run in the foreground. Then you can type “ps” to see that the sleep command is still running while your current process is now going on. BUT, it is going on in the background.

81
Q

How do you kill a process in the background?

A

Type “kill % process_num” where “process_num” is an integer value for the process you want to kill.

82
Q

How do we pull a process in the background UP to the foreground? How about the reverse?

A

Call “fg” in the terminal and it will make the program come to the foreground.

Call “bg” in the terminal and it will make it go to the background.

83
Q

What happens if you run “cat > file.txt &”?

A

Cat requies STDIN and STDOUT. Therefore, this can’t happen in the background so you get a SIGINT.

84
Q

What is Synchronous Waiting?

A

When the parent creates a child and the parent blocks while waiting for the child.

85
Q

What is Asynchronous Waiting?

A

When the parent continues doing what it needs after forking a child, but receives and reacts to SIGCHLD.

This is a generic signal sent to the parent by the child whenever the child does something like stop or exit. The parent can then handle it with a SIGCHLD handler.

The parent can even call a non-blocking version of waitpid.

The parent can check the signal from the child using macros like WIFSTOPPED(status) and WIFSIGNALED(status).

86
Q

What is a Thread?

A

A thread is a way of splitting a program into multiple simultaneously running tasks to keep the CPU calls busy by having them run in parallel.

A process can have multiple threads and they share the same virtual memory address space. They are more efficient and require less overhead from the OS to create and maintain.

They have their own execution context (stack pointer, stack space, and PC for each), but they share the process’ resources, meaning heap memory, static data, and code segment. Also have access to the same files.

Because it’s all contained in the process, we don’t need the OS for context switching between threads.

87
Q

What is the purpose of using threads?

A

They allow you to run programs concurrently without the overhead of having multiple processes.

88
Q

When should you use multiple processes and when should you use multiple threads?

A

There are multiple tradeoffs to consider:

Processes provide isolation, but higher overhead
Threads also require context switching, but it’s less work for the OS.

Inter-process communication between processes is more work than threads reading and writing to a common virtual memory space. Each process would require its own resources whereas the threads wouldn’t.

Threads are good when you’re okay with sharing resources in the same memory space.

There are cases where you want memory isolation and you’d want to use multiple processes, not threads.

89
Q

Why are Processes more expensive than Threads?

A

Processes include many things (address space, OS descriptors for resources allocated, execution state - PC, SP, registers, etc.).

Creating a new process is costly because of all the data structures that must be allocated and initialized.

Communication between processes is costly because communication needs to go through the OS. This is because the communication travels by signals and this requires kernel entry.

90
Q

Pros and Cons of Processes and Threads

A

PROCESSES:

Pros:
-Good isolation of resources. Another process cannot easily corrupt the current one’s resources/memory.

Cons:

  • Expensive inter-process communication.
  • Expensive context switching.
  • Expensive forking and updating the state of the kernel

THREADS:

Pros:

  • Cheap to communicate between them. No context switch necessary since memory space is shared.
  • Cheap context switching since it’s not required for user-level threads.
  • Cheap to create user-level threads since no kernel involvement.

Cons:
-Poor isolation. One thread can easily write into another thread’s memory in heap and data segments.

91
Q

What is Thread Affinity?

A

This means that a specific thread should always run on a specific core. If it is running on a core and it is de-scheduled, the next time another core becomes available it will NOT run on that core because it is dedicated to one core and has to wait for that one to become available again.

This is because cores have a cache and the thread’s data is more likely to be cached if it stays running on the same core. This improves performance.

You can only run one thread on a core at a time. If there is only one core, threading can still be good for interleaving I/O and computations, or division of labor.

92
Q

What are User Level Threads?

A

They are handled by a thread library in the user space. The OS is unaware of the threads that are internal to a process and views a process as single-threaded.

The main advantage of these is that they can be created entirely in user space, requiring no additional work by the OS. Context switching between them is therefore very fast.

93
Q

What are Thread Pools?

A

Creating threads can be expensive. If you need a new one every time a client makes a request, you would have a lot of overhead for the web server. To avoid this, we use a thread pool. This is where we create a number of threads in a pool where they await work.

94
Q

What are the advantages of Thread Pools?

A
  1. Usually faster to service a client request with an existing thread than to create a new thread. If there are no idle threads, an incoming request is put on a wait queue.
  2. Allows the number of threads in the applications to be bound to the size of the pool.
95
Q

What does pthread_t() do?

A

Used to identify a thread. It is returned by pthread_create() and used by the application in function calls that require a thread identifier.

The pthread_join() function waits for the thread specified by thread to terminate. If that thread has already terminated, the pthread_join() returns immediately. The thread specified by thread must be joinable.

96
Q

What does pthread_join() do?

A

It is similar to the wait operation used by a parent process waiting for a child. It makes sure that the main thread terminates only after all spawned threads terminate.

97
Q

What are Thread Tables?

A

They store information to restore each thread’s execution context and swap between threads. For each one, the table must store SP, PC, and registers.

98
Q

What are Kernel Level Threads?

A

These threads are managed by the kernel and the thread table is maintained in the kernel.

When a thread blocks, the kernel can run another thread from the same process and does not have to switch to a different process.

Example: T2 is making a system call which causes P0 to be blocked. In this case, T1 and T3 can still run.

The only downside of kernel threads is increased overhead.

99
Q

Assume a process A has one thread and Process B has 100 threads. Each process receives the same number of time slices.

How fast do these threads run on the user level? How about kernel level?

A

USER-LEVEL

Thread in Process A runs 100 times as fast as the thread in Process B. This is because A uses the entire time slice, whereas B’s threads need to share it. One blocking system call by just one of the threads in B will block all threads in process B.

KERNEL-SUPPORTED THREADS:

Process B receives 100 times the CPU time as Process A assuming they are the same priority. Switching among the threads is more time consuming though because the kernel has to handle it. Process B could have 100 system calls in operation concurrently. In other words, a system call in one thread in B does NOT block the other threads in B.

100
Q

What are Race Conditions?

A

Two processes/threads are executing concurrently running CPU bursts on shared data structures.

Results can depend on HOW the two processes/threads are interleaved as their instructions burst.

Race conditions create bugs that are hard to reproduce.

101
Q

What is Synchronization?

A

Process A is blocked while waiting for another process B to complete an action. When process B is done, we signal A which unblocks and runs.

Here we are blocking and not busy waiting.

102
Q

What is Mutual Exclusion?

A

It prevents simultaneous access to a shared resource.

103
Q

What are the three types of techniques used to ensure Mutual Exclusion?

A
  1. Disable Interrupts
  2. Software or Hardware Busy Waiting
  3. Blocking System Calls
104
Q

What are Disabling Interrupts?

A

Mutual exclusion technique.

Avoids race conditions by disabling context switching when a process is in a critical section (CS).

We turn off interrupts at the beginning and end of the CS.

The clock cannot interrupt. This is a low level approach.

DOWNSIDES:

  • It is overkill. Ensures no switching for all processes, those entering the CS and those that aren’t. Puts too big a burden on the programmer to re-enable interrupts.
  • Programmer may make a mistake and forget to re-enable interrupts.
  • In a multicore environment, need to disable interrupts on all CPUs.
105
Q

Software or Hardware Interrupts (busy waiting solution)

A

In Peterson’s solution, we identify particular types of statements in our code called “atomic statements” which are statements that can be consolidated into a single assembly language instruction.

In order to protect the CS, all we need to do is wrap it with a number of atomic statements (like setting flags that indicate if it’s safe to enter the CS).

106
Q

Why is Busy Waiting not ideal?

A

It continually consumes power where a process/thread needs to keep checking to see if the flag value is 0. It wastes CPU cycles.

It ensures mutual exclusion, but requires strict alternation. A process cannot enter its CS twice in succession, even if the other process does not need to enter the CS.

107
Q

What is the difference between turn variable busy waiting and two-element boolean flag busy waiting?

A

A turn variable is one variable that is a 1 or a 0. If 0, one process gets to go and the other busy waits, if 1, it reverses and the other process gets to go.

Boolean flag is where we have a two-element array where if flag[0] is T, process 0 can enter the CS, if flag[1] is T then process 1 gets to. Each process busy waits to see if the other is trying to enter. If it is, it lets it and in the meantime it busy waits outside of the CS.

108
Q

Why is two-element boolean flag busy waiting NOT a great solution?

A

You can end up in a situation where both processes pass the value of the other’s flag and find it to be false.

For example, if we set both to be false at the start and P0 breaks out of the busy wait loop seeing that P1 is false, then before P0 sets itself as T. But, we could immediately switch to P1 to T while P0’s flag is still false (i.e. hasn’t been set to T yet). In this case, both would be set to T and accidentally hit the critical section at the same time.

109
Q

What is Peterson’s Solution?

A

It has a similar flag array, but also has a turn variable which you can think of as an attempt to implement a race condition between the two processes.

But this race condition is where the processes both race to set the turn variable value and the result is non-deterministic. Sometimes P0 gets there first and sometimes P1. Checking both the values for turn and flag variables can be done atomically so this works.

Once the winner finishes its work on the CS, it turns the turn value back to false and the other process can break out of its busy wait to get into the CS.

110
Q

Why does Peterson’s solution work?

A

If a process wants to enter the CS, it sets the flag variable to T and the turn value to 0 and then enters.

When it’s done, it resets its flag to 0, and thereby resets the state for entering the CS.

If both want to enter and both flags are set to T, then they race to the turn variable. Whoever gets there first wins (since the setting of turn is atomic) and that process gets to go first. The other has to wait until the turn value is reset.

111
Q

What are the drawbacks of Peterson’s Solution?

A
  • It uses busy waiting which is bad.
  • It also only really works for two threads. Beyond that it gets very hard to adapt the solution. It is too complicated.
  • It is also only guaranteed to work on uniprocessors.
112
Q

What is the TSL solution?

A

Stands for Test and Set Lock. It is a mutual exclusion tool.

Simple to implement and works on multiprocessors. But, it requires hardware support (which Peterson’s does not).

It takes in parameters R and M:

R = a register number
M = a memory location

The TSL locks the memory BUS which prevents other processes from accessing the same memory address while the TSL executes.

113
Q

What are the advantages and disadvantages of TSL?

A

ADVANTAGES:

  • Makes mutual exclusion easier because we can replace the cumbersome Peterson’s solution with one assembly instruction.
  • It can also be generalized to multiple threads.

DISADVANTAGES:

  • It still uses busy waiting. The process or thread needs to wait and keep the CPU busy while it waits for its turn.
  • It also requires hardware support, but that isn’t a huge deal since most hardware supports this instruction today.
114
Q

What are the steps for TSL?

A
  1. To implement entry to a critical section, we call TSL R0, lock. R0 takes the value of lock and lock is set to 1.
  2. Check if R0 has a value of 1. If it does, then lock has already been set to 1 prior to the TSL instruction. If this is the case, we need to go back to step 1 and keep waiting.
  3. When the current process is done and leaves the CS, the process sets the lock value to 0 so others can enter the CS.
115
Q

When is Peterson’s Solution and TSL BAD?

A
  1. When a process/thread is busy waiting and it consumes CPU cycles.
  2. When a deadlock or starvation occur because the waiting process has higher priority in the scheduler. The lower priority process never gets a chance to run and complete to leave the critical section while the other tries to repeatedly enter the CS.
116
Q

What is the Bounded Buffer Problem?

A

This happens with pipelining and buffering. A producer writes items to a buffer so that a consumer can later take the items out of the buffer. BUT, if the buffer is full, the producer can’t write to it, and if it’s empty, the consumer can’t take from it.

To solve this, we keep a counter which tells us how many entries are in the buffer.

117
Q

Consider the below scenario. What is wrong with it?

“The user runs a while loop while it produces X. It checks if the buffer is full. If there are N entries in the buffer, then the producer goes to sleep. Otherwise, the item x is added to buffer and count is increased by 1. If count = 1, then the buffer was previously empty, and now the producer can wake up the consumer. We run a while loop in the consumer. If the buffer is empty it goes to sleep, if it’s not it keeps taking. The count gets decremented as things are taken. If the count is N - 1, it means the producer was previously possibly blocked, waiting to input into the buffer at which point we can wake it up and send a new item in, then safely consume it.”

A

This solution doesn’t work because if the producer executes wakeup, it hasn’t yet been blocked. The consumer continues executing and calls sleep, which means then the producer was put to sleep AFTER consumer was called, consumer puts itself to sleep, and then there is no one to wake up the producer now. The consumer’s wakeup call was blocked because of a race condition.

The steps:

  1. Count is initially 0.
  2. Producer produces the item, inserts it, and increments count to 1.
  3. Producer executes wakeup, but there is no waiting consumer yet.
  4. Now consumer continues its execution and calls sleep; consumer blocks.
  5. Consumer stays blocked forever. Main problem: race condition - wakeup was lost.

The problem is that a process wakes up another process before it actually falls asleep, therefore the process then falls asleep and isn’t given a wakeup when it needs it.

118
Q

Suppose the buffer is full of N items. Reorder the below steps so that they are in the order which will CAUSE a lost wakeup problem.

  1. The producer checks whether there are N items in the buffer and the answer is yes.
  2. The producer goes to sleep.
  3. The consumer removes an item from the buffer and decreases the counter from N to N - 1.
  4. The consumer wakes up the producer since there are N -1 items.
A
  1. The producer checks whether there are N items in the buffer and the answer is yes.
  2. The consumer removes an item from the buffer and decreases the counter from N to N - 1.
  3. The consumer wakes up the producer since there are N -1 items.
  4. The producer goes to sleep.

The producer is sleeping after it was told to wake up, so it then never can wake up since the wakeup was wasted.

119
Q

What is a Semaphore?

A

An object maintained within the Operating System and has an integer value. The integer value is initialized to some value and it supports two operations.

120
Q

What do P and V stand for in a semaphore?

A

P: if the semaphore’s value is greater than 0, decrement it. Otherwise, wait until it is greater than 0 and then decrement it [a wait operation]

V: Increment the value of the semaphore [a signal/post operation]

Both P and V have to be atomic operations.

121
Q

What are the two types of semaphores?

A

Counting Semaphores: counting can take on many more values than 0 and 1.

Binary Semaphores: can only have a value of 0 or 1.

122
Q

What is a Binary Semaphore?

A

Saturates at value of 1. Semaphore value S is either 1 or 0.

It’s an improvement over TSL since there is no busy waiting.

R0 implements mutual exclusion into the critical section.

  1. S = 1 initially.
  2. First process/thread enters the critical section and sets S = 0.
  3. Only one process/thread in critical section at any time.

The idea is to wrap any CS with a P and subsequent V call. Only one can enter CS at a time.

123
Q

What is a Counting Semaphore?

A

Used when the CS allows multiple threads/processes to enter. The resources are inherently sharable up to a certain number.

Initial value of S > 1 can be used to allow an arbitrary maximum number of threads to be active somewhere.

124
Q

What does the API for a Semaphore look like?

A

For P it is the below. The OS ensures it executes automatically:

sem_wait(sem_t* sem)

For V it is:

sem_post(sem_t* sem).

125
Q

When do we NOT use semaphores?

A

For busy waiting. What you need is a queue that lets the semaphore remember which process/threads are blocked so it can take the next one. In this queue, each entry has two data items:

  1. Value (of integer type)
  2. Point to the next record in the list (to the PID)
126
Q

What two operations are allowed in a semaphore?

A

Block: places the process invoking the operation in the appropriate waiting queue of the semaphore.

Wakeup: removes one of the processes in the semaphore’s waiting queue and places it in the ready queue.

127
Q

What happens in sem_wait()?

A

We decrement the value by 1. If the value becomes negative, it means that it’s not ready, so that means the process goes into a waiting queue and is blocked.

128
Q

What happens in sem_post()?

A

We increment the value by 1 if the value is <= 0. This means there are other processes blocked that are waiting.

129
Q

What is the initial value of a semaphore?

A

The maximum number of processes you would allow to have concurrency.

130
Q

What is a Mutex Lock?

A

Used in binary semaphores.

We set the semaphore value to be 1. The first process is then able to enter the CS.

Then we wrap that in a P and call V to ensure that only one process can enter the CS.

131
Q

What can happen if semaphores are used incorrectly?

A

We can hit a deadlock where two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.

EXAMPLE:

Let S and Q be two semaphores initialized to 1. Let P0 and P1 be processes. If P0 waits for S followed by Q and P1 does the reverse, then P0 will successfully get semaphore S and P1 semaphore Q, but both will wait on each other to release their semaphore so they can hit the critical section. Neither can let go until the other is free so they are deadlocked.

132
Q

When do we use pthread_exit()?

A

We use this to exit a thread because exit() will cause the whole process to exit, and it may deprive other threads from running we exit the thread we want. pthread_exit() won’t do this.

133
Q

What are the three necessary components for a SUCCESSFUL solution to the Dining Philosopher’s problem?

A
  • Soundness: each chopstick is held by <= 1 philosopher at a time.
  • Deadlock free: there is no state where no one gets to eat.
  • Starvation Free: the solution guarantees that all philosophers get to eat (even if it’s just occasionally).
134
Q

Is the below solution to the dining philosopher’s problem successful?

“For this solution, each chop stick is a semaphore: chopstick[N].

DOWN represents the P call of the semaphore, and UP represents the V call. eat() is the CS.

Down will reduce the counter by 1 and UP will increase it by 1. Basically a philosopher gets the chopsticks from the left and right with two DOWN’s and then puts them down for others.”

A

This solution is sound in that the semaphores guarantee that every chopstick is used by <= 1 philosopher.

BUT, it can result in a deadlock. Every philosopher can pick up the left chopstick, but then the right one is being used now by another philosopher. Then none of them can eat/put down their left chopstick because they are all stuck with that one up, waiting for a right chop stick until they can put the left one down.

135
Q

Is the below solution to the dining philosopher’s problem successful?

“Create a global semaphore that is set by all the philosophers. In order for a philosopher to eat, one has to grab a critical section using the global semaphore and then grabs both chopsticks.”

A

Kind of.

This limits concurrency and all of the philosophers have to queue up, so it is not ideal.

136
Q

Is the below solution to the dining philosopher’s problem successful?

“Reverse the order of get chopstick[i] and get chopstick[i + 1 mod N] for every philosopher. Essentially, even philosophers grab the left chopstick followed by the right one, and the odds do the opposite.

A

Yes. This is the best solution.

137
Q

Is the below solution to the dining philosopher’s problem successful?

“A philosopher grabs the left followed by the right. But, if the right is not available, the philosopher puts down the left chopstick and waits for some amount of time and tries again.”

A

It works but is not efficient.

This can cause a waste of resources where philosophers are constantly checking for a free chopstick. Involves busy waiting.

138
Q

Is the below solution to the dining philosopher’s problem successful?

“There is a token ring and each philosopher gets to eat once in a round robin fashion.”

A

It works but is inefficient. It limits concurrency since only one can go at a time.

139
Q

What is the Bounded-Buffer Problem (in-depth)

A

There are N buffers, each can hold one item.

The semaphore mutex initialized to the value 1.

The semaphore that is full is initialized to the value of 0.
The semaphore that is empty is initialized to the value of N.

The producer calls wait on the empty semaphore to ensure there is space inside the empty buffer to insert an item. Before putting the item into the buffer, it calls wait on the mutex semaphore. Once the item is added, there is a signal on the mutex to exit the CS. Then another signal on the full semaphore to indicate there is now an additional item in the buffer. The wait call corresponds to a P call and the signal call corresponds to a V call.

On the consumer side, we wait on the full semaphore to ensure that there is at least one item there ready to be taken out. To remove the item we then have to call wait on the mutex because this has to be done in a single critical section. We then call signal on the mutex to exit the CS, and we call signal on empty to signal there is now additional space in the buffer.

140
Q

What is the Readers and Writers problem (in-depth)

A

A data set is shared among a number of concurrent processes. Readers can only read the data set, and they do not perform any updates. Writers can both read and write.

Problem: allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time.

Shared Data:

  • Data Set
  • Semaphore mutex initialized to 1
  • Semaphore wrt initialized to 1
  • Integer readcount initialized to 0

The write implementation is straightforward. We have to call wait on the write semaphore. When we are done, we call signal on the write semaphore.

The reader is more complex. To read we have to increment the read count. This requires us to call wait on the mutex because updating the read count has to be done in the CS. If it’s 1, then it’s the first reader. To make sure there is no writer, we need to call wait on the write semaphore. We then signal the mutex so we can leave the CS for updating readcount. We then decrement the read count but we call wait on the mutex semaphore. If the readcount is 0, then it’s possible that a writer was waiting to write and we call that signal.

This solution works but if you have a writer awaiting a reader, other readers in the future can jump the queue ahead of the writer and leave the writer starving. This is starvation.

141
Q

What are the main scenarios that cause issues with semaphores?

A
  1. If you call signal before wait, you could have two processes enter the same CS.
  2. If we call wait followed by wait, we get a deadlock.
  3. If you forget wait or signal, the solution will break.
142
Q

What is a Monitor?

A

A high level abstraction that provides a convenient and effective mechanism for process synchronization.

Only one process or thread may be active within the monitor at a time. The rest go into a queue. Monitors are an abstraction that make it so that we don’t need to use semaphores.

EXAMPLE:

Think of the bank account problem where we can withdraw and deposit money. If we didn’t have a user monitor and we have two users trying to withdraw $40 (when the account only has $50), you can interleave the execution of the withdraw function such that both withdrawals succeed and the balance becomes negative. Monitors avoid this by only allowing one process in at a time.

143
Q

What are Condition Variables?

A

Often used with monitors.

These have two operations:

  1. Wait - a process that invokes the operation is blocked within an internal queue for some variable X.
  2. Signal - resumes one of the processes (if any) that invoked wait in the internal queue for some variable x.

EXAMPLE:

Consider the below example. While a process is in the monitor, it may block on a specific condition variable. The process is then placed in an internal queue for the condition variable. The next process on the external monitor queue gets to enter and use the monitor since it doesn’t have an issue with the conditional variable.

Depending on the API used, all or one of the processes blocking within the conditional variable is broken up and put at the end of the external queue. By the time the process reaches the front of the queue, it may need to check the condition variable again to ensure it’s okay to run now.

144
Q

What are the 3 reasons deadlocks happen?

A
  1. When multiple processes/threads share finite resources. Each resource can only be used by one process/thread at a time.
  2. Processes can request multiple resources. Several at once or one at a time/allowed to accumulate more while holding/when processing a resource, if unavailable, the process/threads will block.
  3. Processes explicitly release resources when no longer in use, or when process terminates.
145
Q

Thread blocking when multiple resources are involved can be a problem. Why?

A

Process A can grab a resource and then try to grab another resource at the same time. BUT, if the second resource isn’t available, process A must block. But, then it’s blocked while still holding onto the first resource, making it unavailable to others. This can make a cyclical dependency.

146
Q

What is a Deadlock?

A

Blocked processes are waiting for resources in a cyclical dependency such that there is none of them that can proceed and the OS is unable to satisfy these blocked processes. Even if all unblocked processes release theirs.

147
Q

What are the four key ways to deal with deadlocks?

A
  1. Ignore it and live with it
  2. Prevent them by doing an exhaustive search of possible states. Have ad hoc genius.
  3. Detection
  4. Avoidance
148
Q

What are the 4 Preconditions for deadlocks?

A

Only one precondition for a deadlock needs to be eliminated in order to eliminate deadlocks in code.

  1. Mutual Exclusion: when a resource is owned by a process, no other processes can use it.
  2. No resource preemption: processes that lock a resource get to own it until the process explicitly releases it.
  3. Hold and wait: processes can hold onto existing resources and then block if new resources cannot be acquired immediately.
  4. Circular waiting: circular chain of two (or more) processes/threads. Each waiting for a resource held by the next in the chain. Results in cyclical dependency. all processes in the chain are blocked.
149
Q

How can you remove precondition #1: Mutual Exclusion?

A

Mutual exclusion is where resources held by one process cannot be simultaneously used by another.

This is hard to avoid. Usually you either need mutual exclusion or you do not.

Some resources are intrinsically shareable and only one process can be used at a time.

150
Q

How can you remove precondition #2: No Resource Preemption?

A

No resource preemption is where resource holders keep their resources until they relinquish them.

You can remove this precondition with a priority scheme. If a high priority process wants a resource, it gets it and the resource is taken away from the lower priority.

Unfortunately there is no good way to implement this in practice. It requires complex recovery when a resource is taken away.

You need to undo all action in applications where resource was taken away.

151
Q

How can you remove precondition #3: Hold and Wait?

A

Hold and wait is where resources can be accumulated (requested and blocked for while holding others).

You can eliminate this by requiring a complete set of resources to be requested together at the beginning of process execution. That way it gets all at the same time and can do its business faster. It’s hard to know what resources a process might need though. For example, Word may not know all the files it will need to open when it opens.

In short, it’s impractical. It’s not always possible to know all resources upfront. It depends on execution paths taken by the program.

152
Q

How can you remove precondition #4: Circular Waiting?

A

Circular Waiting is where there is a circular chain of processes, each waiting for resource held by the next process in the chain.

You need to break cycles by enforcing ordering of resources.

One solution is hierarchical allocation: All individual resources have a number. A process can only acquire resources with increasing resource number.

The challenge with this though is that it requires knowing all resources up front and assigning them a suitable ordering.

EXAMPLE:

Philosopher situation, each one takes chopstick b and b + 1. When we get to the last philosopher, he takes n and n + 1 which is really n and 1 since it’s a circular table, and that breaks the deadlock.

153
Q

How can we detect deadlocks?

A

Use graph theory. Draw a directed graph where the processes and resources are nodes.

If a process currently has a resource, then we put an edge from the resource to the process (resource –> process).

If a process is requesting a resource, then we put an edge from the process to the resource (process –> resource).

If you find a cycle in this graph, you have a deadlock.

154
Q

What is a Wait For Graph?

A

This is when we take the graph we drew to find deadlocks and we remove all of the resources, just leaving the edges that bring the processes together.

155
Q

What do we do when we find a deadlock with our Wait For Graphs?

A
  1. Once the OS detects the deadlock, we can implement preemption. We can take away a resource from a current owner. Sometimes it requires a rollback though and hurts the process it is taken from.
  2. We can also roll back, checking periodically to save states. We reset the enter state before acquiring a resource. This is used in database systems where multiple threads write to the same record.
  3. We can also manually kill processes until no cycles are left. This is a crude but simple approach.