exam1

Question 1

What is a Virtual Machine?

Answer 1

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

Question 2

What are the three layers of the computer?

Answer 2

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

Question 3

Host OS

Answer 3

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

Question 4

Why do we use VM’s?

Answer 4

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.

Question 5

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

Answer 5

DROPBOX:
1. Files are automatically synchronized.

2. Resolves conflicts by creating two copies.
3. 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.

Question 6

What do the following vagrant commands do?

1. vagrant up
2. vagrant ssh
3. vagrant suspend
4. vagrant destroy
5. vagrant halt
6. logout

Answer 6

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.

Question 7

What are the three primary sections of a vagrant file?

Answer 7

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.

Question 8

Operating System (OS)

Answer 8

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

Question 9

The Kernel

Answer 9

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

Question 10

The Shell

Answer 10

A command interpreter for the operating system.

Question 11

Data Storage in the OS

Answer 11

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

Question 12

What are the two main functions of the OS?

Answer 12

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.

Question 13

User Mode

Answer 13

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

Question 14

Kernel Mode

Answer 14

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.

Question 15

What is a Process?

Answer 15

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.

Question 16

Process Context

Answer 16

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.

Question 17

Why does the OS run apps with the process abstraction?

Answer 17

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.

Question 18

How big is the address space of a process?

Answer 18

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

Question 19

What part of memory are applications run in?

Answer 19

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

Question 20

Program Counter

Answer 20

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

Question 21

Where is temporary data from a program stored?

Answer 21

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.

Question 22

What are Data Segments?

Answer 22

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

Question 23

The Heap

Answer 23

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.

Question 24

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

Answer 24

Stack (grows downward)

Heap (grows upward but can have items randomly placed)

Static Data

Code

Question 25

What is the PID?

Answer 25

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.

Question 26

What is a PCB?

Answer 26

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.

Question 27

What is the PPID?

Answer 27

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.

Question 28

Define the hierarchy of Linux processes

Answer 28

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.

Question 29

What is the fork() system call?

Answer 29

Creates a new child process.

The child gets a PID of 100.

Question 30

What is a Child Process?

Answer 30

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.

Question 31

Process Memory Construction

Answer 31

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

Question 32

The wait() call

Answer 32

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.

Question 33

The waitpid(pid, &status, options) call

Answer 33

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

Question 34

SIGKILL

Answer 34

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.

Question 35

Zombies

Answer 35

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.

Question 36

Daemon

Answer 36

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

Question 37

What are the steps for switching processes?

Answer 37

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.

Question 38

What is the life cycle of a process?

Answer 38

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.

Question 39

What happens when a hardware or software interrupt happens?

Answer 39

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.

Question 40

How big of a time slice to most processes get?

Answer 40

100ms

Question 41

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

Answer 41

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.

Question 42

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

Answer 42

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

Question 43

What happens when fork() is called?

Answer 43

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.

Question 44

What happens when exec() is called?

Answer 44

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.

Question 45

What happens when wait() is called?

Answer 45

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.

Question 46

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

Answer 46

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.

Question 47

What is a file descriptor?

Answer 47

It represents an input or output device.

Question 48

What are the arguments of the read() function?

Answer 48

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

Question 49

What are the arguments of the write() function?

Answer 49

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

Question 50

Does buffering improve performance when reading/writing data?

Answer 50

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

Question 51

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?

Answer 51

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.

Question 52

What does it mean to “leak processes”?

Answer 52

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

Question 53

Where should malloced data be freed?

Answer 53

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.

Question 54

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

Answer 54

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

Question 55

What are System Calls?

Answer 55

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.

Question 56

What is a System Call Number?

Answer 56

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.

Question 57

Hardware Interrupts

Answer 57

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.

Question 58

How is a Hardware Interrupt processed?

Answer 58

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.

Question 59

What happens in a process when a hardware interrupt occurs?

Answer 59

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.

Question 60

What is the general process for an interrupt?

Answer 60

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.

Question 61

Inter-process Signalling

Answer 61

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.

Question 62

What is a Signal?

Answer 62

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.

Question 63

What is a Signal Handler?

Answer 63

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.

Question 64

What do each of the following do?
SIGALARM

SIGCHLD

SIGINT

SIGKILL

SIGTERM

SIGUSER1/SIGUSER2

SIGFPE

SIGSEGV

SIGSTOP/SIGCONT

Answer 64

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.

Question 65

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?

Answer 65

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.

Question 66

What is sigaction()?

Answer 66

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

Question 67

What is Redirection?

Answer 67

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.

Question 68

What is Pipelining?

Answer 68

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.

Question 69

What is Job Control?

Answer 69

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.

Question 70

How is dup2() used?

Answer 70

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.

Question 71

What does “Half Duplex” mean?

Answer 71

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.

Question 72

How does the API for a pipe work?

Answer 72

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.

Question 73

What is SIGPIPE?

Answer 73

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

Question 74

Piping between Parent and Child process

Answer 74

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.

Question 75

What is the overall process for piping?

Answer 75

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.

Question 76

What is a Process Group?

Answer 76

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.

Question 77

What does the “ps” terminal command do?

Answer 77

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.

Question 78

What is a foreground process?

Answer 78

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.

Question 79

What is a pseudo terminal device?

Answer 79

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

Question 80

How do we create foreground/background processes?

Answer 80

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.

Question 81

How do you kill a process in the background?

Answer 81

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

Question 82

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

Answer 82

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.

Question 83

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

Answer 83

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

Question 84

What is Synchronous Waiting?

Answer 84

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

Question 85

What is Asynchronous Waiting?

Answer 85

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

Question 86

What is a Thread?

Answer 86

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.

Question 87

What is the purpose of using threads?

Answer 87

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

Question 88

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

Answer 88

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.

Question 89

Why are Processes more expensive than Threads?

Answer 89

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.

Question 90

Pros and Cons of Processes and Threads

Answer 90

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.

Question 91

What is Thread Affinity?

Answer 91

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.

Question 92

What are User Level Threads?

Answer 92

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.

Question 93

What are Thread Pools?

Answer 93

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.

Question 94

What are the advantages of Thread Pools?

Answer 94

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.

Question 95

What does pthread_t() do?

Answer 95

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.

Question 96

What does pthread_join() do?

Answer 96

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.

Question 97

What are Thread Tables?

Answer 97

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.

Question 98

What are Kernel Level Threads?

Answer 98

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.

Question 99

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?

Answer 99

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.

Question 100

What are Race Conditions?

Answer 100

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.

Question 101

What is Synchronization?

Answer 101

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.

Question 102

What is Mutual Exclusion?

Answer 102

It prevents simultaneous access to a shared resource.

Question 103

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

Answer 103

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

Question 104

What are Disabling Interrupts?

Answer 104

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.

Question 105

Software or Hardware Interrupts (busy waiting solution)

Answer 105

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

Question 106

Why is Busy Waiting not ideal?

Answer 106

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.

Question 107

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

Answer 107

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.

Question 108

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

Answer 108

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.

Question 109

What is Peterson’s Solution?

Answer 109

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.

Question 110

Why does Peterson’s solution work?

Answer 110

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.

Question 111

What are the drawbacks of Peterson’s Solution?

Answer 111

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

Question 112

What is the TSL solution?

Answer 112

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.

Question 113

What are the advantages and disadvantages of TSL?

Answer 113

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.

Question 114

What are the steps for TSL?

Answer 114

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.

Question 115

When is Peterson’s Solution and TSL BAD?

Answer 115

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.

Question 116

What is the Bounded Buffer Problem?

Answer 116

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.

Question 117

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

Answer 117

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.

Question 118

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.

Answer 118

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.

Question 119

What is a Semaphore?

Answer 119

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.

Question 120

What do P and V stand for in a semaphore?

Answer 120

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.

Question 121

What are the two types of semaphores?

Answer 121

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

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

Question 122

What is a Binary Semaphore?

Answer 122

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.

Question 123

What is a Counting Semaphore?

Answer 123

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.

Question 124

What does the API for a Semaphore look like?

Answer 124

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

Question 125

When do we NOT use semaphores?

Answer 125

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)

Question 126

What two operations are allowed in a semaphore?

Answer 126

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.

Question 127

What happens in sem_wait()?

Answer 127

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.

Question 128

What happens in sem_post()?

Answer 128

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

Question 129

What is the initial value of a semaphore?

Answer 129

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

Question 130

What is a Mutex Lock?

Answer 130

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.

Question 131

What can happen if semaphores are used incorrectly?

Answer 131

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.

Question 132

When do we use pthread_exit()?

Answer 132

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.

Question 133

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

Answer 133

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

Question 134

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

Answer 134

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.

Question 135

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

Answer 135

Kind of.

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

Question 136

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.

Answer 136

Yes. This is the best solution.

Question 137

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

Answer 137

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.

Question 138

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

Answer 138

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

Question 139

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

Answer 139

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.

Question 140

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

Answer 140

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.

Question 141

What are the main scenarios that cause issues with semaphores?

Answer 141

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.

Question 142

What is a Monitor?

Answer 142

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.

Question 143

What are Condition Variables?

Answer 143

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.

Question 144

What are the 3 reasons deadlocks happen?

Answer 144

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.

Question 145

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

Answer 145

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.

Question 146

What is a Deadlock?

Answer 146

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.

Question 147

What are the four key ways to deal with deadlocks?

Answer 147

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

Question 148

What are the 4 Preconditions for deadlocks?

Answer 148

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.

Question 149

How can you remove precondition #1: Mutual Exclusion?

Answer 149

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.

Question 150

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

Answer 150

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.

Question 151

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

Answer 151

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.

Question 152

How can you remove precondition #4: Circular Waiting?

Answer 152

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.

Question 153

How can we detect deadlocks?

Answer 153

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.

Question 154

What is a Wait For Graph?

Answer 154

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.

Question 155

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

Answer 155

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.