Exam 1 Flashcards

Question

What is the PID?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

Creates a new child process. The child gets a PID of 100.

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

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.

Answer 15

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.

Answer 16

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.

Answer 17

- 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.

Answer 18

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.

Answer 19

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.

Answer 20

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.

Answer 21

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.

Answer 22

It represents an input or output device.

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

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.

Answer 27

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

Answer 28

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.

Answer 29

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

Answer 30

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.

Answer 31

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.

Answer 32

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.

Answer 33

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.

Answer 34

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.

Answer 35

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.

Answer 36

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.

Answer 37

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.

Answer 38

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.

Answer 39

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.

Answer 40

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.

Answer 41

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);

Answer 42

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.

Answer 43

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.

Answer 44

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.

Answer 45

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.

Answer 46

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.

Answer 47

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.

Answer 48

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

Answer 49

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.

Answer 50

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.

Answer 51

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.

Answer 52

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.

Answer 53

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.

Answer 54

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

Answer 55

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.

Answer 56

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

Answer 57

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.

Answer 58

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

Answer 59

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

Answer 60

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).

Answer 61

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.

Answer 62

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

Answer 63

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.

Answer 64

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.

Answer 65

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.

Answer 66

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.

Answer 67

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.

Answer 68

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.

Answer 69

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.

Answer 70

It is used to create threads.

Answer 71

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.

Answer 72

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.

Answer 73

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.

Answer 74

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.

Answer 75

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.

Answer 76

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.

Answer 77

It prevents simultaneous access to a shared resource.

Answer 78

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

Answer 79

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.

Answer 80

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).

Answer 81

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.

Answer 82

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.

Answer 83

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.

Answer 84

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.

Answer 85

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.

Answer 86

- 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.

Answer 87

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.

Answer 88

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.

Answer 89

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.

Answer 90

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.

Answer 91

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.

Answer 92

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.

Answer 93

1. The producer checks whether there are N items in the buffer and the answer is yes. 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. 2. 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.

Answer 94

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.

Answer 95

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.

Answer 96

Counting Semaphores: counting can take on many more values than 0 and 1. Binary Semaphores: can only have a value of 0 or 1.

Answer 97

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.

Answer 98

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.

Answer 99

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).

Answer 100

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)

Answer 101

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.

Answer 102

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.

Answer 103

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

Answer 104

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

Answer 105

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.

Answer 106

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.

Answer 107

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.

Answer 108

- 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).

Answer 109

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.

Answer 110

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

Answer 111

Yes. This is the best solution.

Answer 112

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.

Answer 113

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

Answer 114

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.

Answer 115

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.

Answer 116

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.

Answer 117

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.

Answer 118

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.

Answer 119

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.

Answer 120

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.

Answer 121

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.

Answer 122

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

Answer 123

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.

Answer 124

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.

Answer 125

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.

Answer 126

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.

Answer 127

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.

Answer 128

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.

Answer 129

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.

Answer 130

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.