FINAL Flashcards
What is a thread?
In computer science, a thread refers to a sequenceof instructions within a program that can be executed independently. It is a lightweight unit of execution that belongs to a larger process and shares the same memory space. Threads enable concurrent execution of multiple tasks within a single program, allowing for increased efficiency and responsiveness
(In computer science, a thread is like a small independent worker inside a program. It’s like a mini-program within a bigger program, and it can do its own tasks without depending on others. Threads share the same memory with the main program, which helps them work together smoothly.
Threads make programs more efficient and responsive because they can do different tasks at the same time. It’s like having multiple workers who can handle different jobs simultaneously, which speeds things up and makes the program more flexible.)
What is a “heavy-weight process?”
A normal process under an
Operating System (OS) is a “heavy-weight process.” The OS provides an
independent address space for each such process to keep different users and
services separated. Switching from one such process to another is time-
consuming, and this task is performed by the Memory Management Unit
(MMU)
(A normal process is like a heavy-weight program, and the MMU is like the traffic cop, managing the flow of processes to ensure fairness and separation.)
Why do we call a thread a “lightweight process (LWP)?”
A thread is called a Lightweight Process (LWP) because it runs under the address space of a regular (heavy-weight) process, and LWPs under the same process may share,
e.g., variables. Switching from one LWP to another is much faster than switching
from one heavy-weight process to another because there is less to manage, and
the MMU is not involved
(A thread is a lightweight helper that works together with a big program. Switching between helpers is super quick because they share and don’t need a traffic cop!)
What is the difference between a thread and a process?
A- Threads within the same process run in shared memory space, while processes
run in separate memory spaces.
B- Processes are independent of one another, and they don’t share their codes,
data, and OS resources.
Unlike processes, threads share their code section, data section, and OS
resources (like open files and signals) with other threads.
Similarities between threads and processes:
Similar to a process, a thread has its program counter (PC), register set, and
stack space
What are the situations in which we use “multithreading?”
Multithreading has many advantages, but in the following two cases,
multithreading is preferable to a single-thread process:
A- Processing power: Multithreading is preferable if you have a multi-core
computer system.
B- Multithreading avoids priority inversion. Priority inversion is a situation where
a low-priority task blocks a high-priority activity. An example of low priority
task is accessing the secondary memory, while a user interface is a high-priority
task
What is an example where having a single thread is preferred over
multithreading?
If we are waiting for a user response or waiting for
data to arrive over the network
What is Multithreading?
Multithreading is the ability of a program to
create and manage multiple threads. A program can perform multiple tasks
concurrently and efficiently using available system resources by utilizing
multiple threads.
What are thread states?
Threads can be in different states, such as
running, ready, blocked, or terminated. The operating system scheduler
determines which threads get executed and when based on factors like thread
priorities, dependencies, and available resources
What do we mean by “Thread Communication and Synchronization?”
Threads within a program often need to communicate and coordinate with
each other to accomplish tasks. This can be achieved using synchronization
mechanisms like Mutex, semaphores, and condition variables to prevent race
conditions and ensure data consistency.
What are “Thread Models?”
Thread models include user-level threads and kernel-level threads.
User-level threads are managed by a user-level library, while kernel-level threads are managed by the operating system kernel.
Most modern operating systems use a hybrid model that combines both types of threads. An example of a user-level thread library is pthread.h, which relies on the operating system kernel for scheduling and executing threads.
While the library provides abstractions and mechanisms for thread management and synchronization, the operating system handles the actual scheduling and context switching tasks.
How would a web server act under a multithreading system?
The server listens for a new client to request a transaction. Then the server assigns a thread to the requesting client and listens for the next client
What is the difference between running four threads on a single-core
processor and running the same number of threads on a double-core
processor? Draw a simple diagram for each case
All of the threads take a turn in a round-robin fashion on a single-core processor. This is known
as “concurrency.” On the other hand, on a double-core processor, two threads run on one core, and the other two would run on the second core. This parallel running of threads on multiple cores is known as “parallelism.”
What are the four benefits of multithreading?
A- Responsiveness: If a process is divided among multiple threads, the other
parts could go on if one part of the process is blocked.
B- Resource sharing: different process threads can share the process’s code
and memory.
C- Economy: Starting a new thread is much easier and faster than creating a
new process.
D- Scalability: A multithreaded process runs faster if we transfer it to a
hardware platform with more processors.
What challenges do programmers face when designing the code for
multiprocessors?
challenges include
A- Dividing activities: finding areas that can be divided into separate and
concurrent tasks.
B- Balance: programmers must ensure that different tasks are of the same
value in complexity and execution time.
C- Data-splitting: Data should be split, in a balanced manner, among already
split concurrent tasks.
D- Data dependency: The programmer should ensure that concurrently
running tasks do not have data dependence.
E- Testing and debugging: Many different execution paths are possible and
more complicated than testing single-threaded applications
What are the two types of parallelism?
A- Data parallelism: Data is divided into subsets, and each subset is sent to
different threads. Each thread performs the same operations.
B- Task parallelism: The whole data is sent to different threads, and each
thread does a separate operation.
How do we compute “speedup” using Amdahl’s law?
Speedup = 1/ (S + “1-S”/N)
In this formula, S is the portion of the task that has to be
performed serially, and (1-S) is part of the task that can be distributed on N
processors. Speedup indicates how much faster the task is running on these N
processors as compared to when it was running serially
Suppose that 50% of a task can be divided equally among ten threads, and each
thread will run on a different core. A) What will be the speedup of this
multithreading system compared to running the whole task as a single thread?
B) What will be the speedup of part (A) if we could send 90% of the job to ten
threads?
What is the upper bound in Amdahl’s law?
In the context of “Amdahl’s law,” what is the meaning of “diminishing returns?”
What are the three popular user-level thread libraries?
OSIX
pthreads, Windows, and Java
What is the relationship between user threads and kernel threads?
user threads run within a user process. Kernel threads are used to provide
privileged services to processes (such as system calls). The kernel also uses
them to track what is running on the system, how much of which resources are
allocated to what process, and how to schedule them. Hence, we do not need a
one-to-one relationship between user threads and kernel threads
A) In the relationship between the user and kernel threads, what is the “many-
to-one model?” B) What is the shortcoming of this model?
A) Before threads became popular, OS kernels only knew the concept of processes. An
OS would consider different processes and consider each a separate entity.
Each process was assigned a working space and could produce system calls and
ask for services. Threading in the user space was not dealt with by the OS. With
User mode threading, support for threads was provided by a programming
library, and the thread scheduler was a subroutine in the user program itself.
The operating system would see the process, and the process would schedule
its threads by itself. B) If one of the user threads needed a system call, such as a
page fault, the other threads were blocked.
What is the “one-to-one” threading model? What are its advantages and
shortcomings?
Each user thread is assigned a kernel thread. Hence,
we can achieve more concurrency, and threads can proceed while one thread
is blocked. The disadvantage occurs when there are too many user threads,
which may burden the performance of the operating system
What is a “many-to-many” multithreading model?
The OS decides the number of kernel threads, and the user process determines the number of user threads. A process that runs on an eight-core processor would have more kernel threads than the one which runs on a quad-core processor. This model
does not suffer from either of the shortcomings of the other two models.
What is POSIX pthread?
POSIX (portable OS interface) thread library
provides programmers with an application program interface (API) for creating
and managing threads.
What is synchronous threading?
After creating the threads, the
parent has to wait for the children to terminate before it can resume operation.
What header file should be included for thread programming in C or C++ using
pthread?
include <pthread.h></pthread.h>
What does the following piece of code do?
It uses a function to
perform summation. The main program sequentially calls the function
What does the following piece of code do?
It creates several threads. The number of threads is equal to the
number of arguments that are sent to the main process. All threads are the
same and perform a summation. When all threads are finished, they are joined
with the main process.
What is the purpose of the following piece of code?
The above code creates five threads. In the “runner” function, we
make a loop to spend some time and make the threads unsynchronized.
Threads are created in an order, but their executions do not follow any order.
(when a thread is created, it returns 0 upon success, and the if (rc) is not performed.
However, if there is an error in thread creation, then rc will get a nonzero value, and
the if (rc) is performed, causing the loop to stop)
What does the following instruction do?
pthread_create (id, attributes, function, argument);
It creates a thread with a given id and a set of attributes. The thread
will run a function and can carry an argument into that function
What does the following instruction do?
pthread_join (id, ReturnedValue);
The main process waits for the thread with the given ID to finish and
return a variable. If no variable is to be brought back, then NULL is used
Does Windows support multithreading? Explain
Windows supports multithreading. It supports single or multiple thread creation and single or multiple thread joining
What does “detaching” of thread mean?
If pthread_detach() is used
inside a thread, it means that as soon as the thread is exited, its resources are
released, and the system should not wait for this thread to join with its parent.
What is meant by implicit threading?
Creating hundreds and thousands of threads by the program is challenging. The solution is implicit threading, which transfers the creation and management of threading from application developers to compilers and runtime libraries
What are some famous “implicit threading” examples?
A) Thread Pools, B) Fork-Join, C) OpenMP, D) Grand Central Dispatch, E) Intel Threading
Building Blocks.
How is the OpenMP application programming interface used?
The programmer determines which parts of the program could be implemented
parallelly. Then the OpenMP API is used and which has compiler directives and
library routines. The compiled version of the program would have multiple
threads to perform the code in a parallel manner
What happens when fork() is used in a program?
The fork() function creates a new process that is an exact copy of the calling process. The child process has its own process ID, but shares the same code, data, open files, and other resources as the parent process. After the fork() call, the parent and child processes continue executing independently.
Here are some additional tips for memorizing this information:
Use acronyms. The acronym PID stands for “process ID,” so you can remember that the fork() function returns the child process’s PID to the parent process.
Create a mental model. Imagine a parent process and a child process. The parent process is like a factory that creates the child process. The child process is like a copy of the parent process, but it has its own unique identity.
Practice. The best way to memorize this information is to practice using it. Try writing some code that uses the fork() function.
When a fork() is executed, are the threads running under the parent process
duplicated?
The threads are not duplicated unless, after fork(), an
exec() instruction is executed
What is a “signal” in the context of threading?
Signals notify a process of the occurrence of an event. A signal can be synchronous or asynchronous. A signal is generated, delivered, and then handled.
What are two examples of synchronous and asynchronous signals?
If an instruction in a thread performs division by zero, then it generates a
synchronous signal. When a signal is generated by an event external to a
running process, that process receives the signal asynchronously. An example
of such a signal includes terminating a process with specific keystrokes (such as
<control><C>).
</C></control>
Is it possible to create a thread and then cancel it?
Yes. The main
thread could cancel the child thread unless the thread has disabled its
cancelation. The thread can disable its cancelation capability if it is doing
something critical. It is a good practice to enable the cancelation capability
after a while and allow the parent to cancel the thread if needed
In scheduling the user threads and assigning each of them to a kernel
thread, what is a lightweight process (LWP)?
LWPs facilitate parallelism and concurrency by connecting ULTs to KLTs. They provide a means for user-level thread libraries to efficiently manage threads while leveraging the capabilities of the operating system’s thread scheduler. However, this coordination also introduces some overhead in terms of latency and resource utilization.
What is a cooperating process, and why is there a potential for data
inconsistency?
A cooperating process can affect or be affected by
other processes. They use shared memory to share data or to pass messages.
The sequence of actions of cooperating processes could result in the wrong
content of the shared memory. The inappropriate content of shared memory is
referred to as data inconsistency.
Why is there a need for synchronization?
Data inconsistency requires that the cooperating processes or threads access shared variables in an orderly manner, called synchronization
What is the “consumer-producer” problem in the context of synchronization?
Explain the simple solution of using a “counter.”
Two processes are there. One process produces data, and the other reads it (consumes it). Data will be inconsistent if the two participants don’t follow a rhythm. The producer
should first write into a buffer and increase the counter; then, the consumer
should read the data and decrease the counter
In the “producer-consumer” problem, for synchronous passing of data, what
are the “blocking send” and “blocking receive” strategies?
if these two strategies are applied, the sender is blocked until the receiver verifies the
reception of the data. Also, the receiver is blocked from reading data until the
sender verifies that new data is placed into the buffer
What is a “race condition” in the producer-consumer problem?
Both the producer and the consumer can access the shared variable “counter.” The
producer will increment, and the consumer will decrement the variable,
independent of each other. The final value of the counter depends on the order
in which these processes update the variable. The solution is not to allow both
processes to access the shared variable concurrently
The “critical section” problem is a synchronization protocol. Explain its four
steps.
1- Entry section: a process requests to enter its critical section.
2- Critical section: only one process can enter its critical section. A critical
section is where the process shares or changes shared variables.
3- Exit section: after finishing its critical section, the process exits, and one of the other processes could enter its critical section.
4- Remainder section: A process could continue with other jobs following exiting the critical section. The remainder
section of the processes could be executed concurrently.
What are the three conditions of the critical section protocol?
1- Mutual exclusion: only one process could be in its critical section.
2- Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their
remainder sections can participate in deciding which will enter its critical
section next, and this selection cannot be postponed indefinitely.
3- Bounded waiting: there should be a bound on the number of times that other processes could enter their critical section before a process that has requested should
wait.
What is Paterson’s solution for synchronization?
Paterson’s solution is for two processes. It assumes an atomic “load” and “store.” It requires two shared variables of int turn and boolean flag[2]. Each process can turn its flag bit to 1 to declare its intention to enter the critical section. The “turn” variable
shows the process number allowed to enter its critical section. Each process i
sets its flag to 1 and sets the turn variable to j (offer the other process to run).
Then process i arrives at its critical section and keeps waiting by testing the
“turn” variable to see if it is its turn.
What is Mutex, and how does it help synchronization?
complicated implementations of OS and hardware are used to synchronize threads. Mutex is a synchronization primitive available to programmers. A mutex has a binary
“lock,” which is accessed by acquire() and then released by release().
One thread is supposed to perform the following function:
A) This is thread ID. In this example, there are two threads.
B) A global variable called “lock” is generated by the Mutex. This variable is either 0 or 1.
C) This instruction reads the mutex lock; if it is free, it will make it busy and start
its critical section.
D) This is the critical section of the thread. While this thread
is busy doing its critical section, others cannot intervene because only this
thread has the mutex lock. E) When the thread finishes its critical section, it will
release the lock, and other threads waiting for the lock can acquire it.
What is a semaphore?
A semaphore is a signaling mechanism. A thread can signal another thread that is waiting on a semaphore. Mutex allows a thread to hold the lock and then release the lock. Using Mutex, when the lock is released, any thread that is waiting could acquire the lock, but using semaphore, a thread could pass the lock to a specific thread.
What is an “atomic” operation, and why is it important to have atomic operations
for synchronization?
Operations that are used for synchronization are
more complex than usual operations. For example, wait() operation in mutex lock
handling should read the mutex lock, and if it is “free,” then it should change the mutex lock to “unavailable.” A non-atomic operation may read the variable, and
before changing the variable’s value, another thread may have done the same
thing. Then each thread thinks it has changed the lock value and it owns the lock.
An atomic operation allows only one thread to first read and then change the
variable without interference from other threads.
What are the purposes of wait() and signal() operations in the context of
semaphores?
Answer: the wait() operation lets the thread check the semaphore
lock until the holder releases the lock. The operation is atomic. If the lock that is
read is free, then the lock is changed to “unavailable” for the rest of the threads.
The signal() operation releases the semaphore lock to a designated semaphore
holder.
A) defines variable sem_example as a binary semaphore.
B) Delays thread 1 to show that the order of generation of threads is not essential, and
when one thread is finished, the other thread receives the semaphore.
C) A thread waits here till the semaphore is released.
D) This is the critical section of the thread.
E) This thread signals the release of the semaphore to the other holder of the semaphore.
Is it possible to activate several threads in a specific order?
Yes. After finishing its critical section, each thread can signal another thread by using
semaphores. Hence, a desired sequence of events can be generated
In the following, a program is shown with three threads. What are the roles of
the program sections that are labeled as A to F?
A) Three semaphore IDs are defined.
B) The thread to run routine1 waits here to receive a start signal through semaphore sem1.
C) When routine1’s critical section is finished, a semaphore is released to whoever holds
sem3.
D) This part is the critical section of routine2.
E) All three semaphores are initiated. Sem1 is initiated to 1, which means that it can start initially. The other two semaphores are initiated to 0, and they must wait until they are
activated.
F) All semaphores are destroyed after their threads are joined with
the main process.
What are deadlock and starvation when multithreading is performed?
A) Deadlock occurs when each thread holds a part of the resources
that other threads need. This causes an indefinite wait for all of the threads.
B) Starvation occurs when one thread is indefinitely kept from operating.
What four conditions create a deadlock where avoiding any of these conditions
prevents deadlocks?
1) Mutual exclusion: no two processes can
operate simultaneously.
2) Hold & wait: each process is holding a part of its
needed resources and is waiting for other processes to release the rest of its needed resources.
3) No-preemption: when a process is holding some resources, the process has the option of not releasing the resources until it finishes its job.
4) Circular wait: among n processes, each process is waiting for
another process circularly.
What are the three methods for handling deadlocks?
1) never allow the process to enter a deadlock.
2) Allow the processes to enter a deadlock and
then handle the situation.
3) Ignore that there is a potential for deadlock
occurrence.
How could we guarantee that processes never enter a deadlock situation?
1) prevention and 2) avoidance.
How could we prevent deadlocks?
1) do not apply “mutual exclusion” in all situations. For example, if several processes want to access shared variables for reading, mutual exclusion is not used.
2) Hold & wait situation is avoided. A process can claim resources only when all of them are available. If a process is holding some resources and is not running, then the resources are requested back from the process.
How could we apply deadlock avoidance?
Information about the processes’ needed resources and current resources is kept. Knowing other information, such as a period that a process is waiting or holding resources, could help avoidance of deadlock. Using this information, OS could give out
resources, stop processes, or take resources from the processes.
What is the purpose of the computer network?
A computer network is a set of computers connected to share resources. The resources could be categorized into information, hardware, and software tools
What primitives are used when a client machine wants to connect to a server
machine? Draw a simple diagram
The main primitives are: listen,
accept, connect, send, receive, and disconnect.
What does the following graph show? What are the two axes representing?
This graph exemplifies the slow-start congestion control algorithm.
The vertical axis shows the size of the congestion window. The vertical axis
represents round-trip time steps
In the following diagram, a fragmentation example is shown. A packet of 4000
bytes is fragmented into three pieces. Explain the offset, MF, and length of
these three fragments
The length of the packet is 4000 bytes. The data is 3980 bytes, and
the header is 20 bytes. When we fragment it into three parts, each part
contains a 20-byte header, and the rest is data
What is the following data structure?
This IP packet shows
the header and data specifically for the IP4 version. This packet is built in the
network layer.
The following diagram shows the structure of an IPv4 address. What are N, L,
and the fields indicated with question marks?
N is 32 bits, the number of bits in the IP. L is the prefix length. N-L
shows the number of bits to identify the host
Consider the following diagram. A packet arrives from the Internet with the
IP address of 192.222.250.200. To which domain will the router on the right
side of the diagram send this packet? Why?
a) Check to see if this IP belongs to the CS department: its prefix is 19 bits; hence
the mask will have 19 ones and 13 zeros. We ‘And’ this mask with the given IP,
and if the result is 192.222.128.0, then the given IP belongs to the CS
department.
Mask = 11111111.11111111.11100000.00000000 = 255.255.224.0
Given IP = 11000000.11011110.11111010.11001000 = 192.222.250.200
AND result = 11000000.11011110.11100000.00000000 = 192.222.224.0
The result is not the same as CS IP; hence, this IP does not belong to
the CS network.
b) Check if this IP belongs to the EE department: its prefix is 18 bits; hence the
mask will have 18 ones and 14 zeros. We ‘And’ this mask with the given IP, and
if the result is 192.222.192.0, then the given IP belongs to the EE department.
Mask = 11111111.11111111.11000000.00000000 = 255.255.192.0
Given IP = 11000000.11011110.11111010.11001000 = 192.222.250.200
AND result = 11000000.11011110.11000000.00000000 = 192.222.192.0
The result is the same as the EE IP; hence, this IP belongs to the EE
network.
It generates a socket. A descriptor will be returned if the socket is
generated; otherwise, -1 is returned
When a socket is created, it exists in a namespace (address family)
but has no address assigned to it. The bind() function assigns the address
specified by addr to the socket referred to by the file descriptor
sockfd.
Listen() marks the socket referred to by sockfd as a socket that will
be used to accept incoming connection requests
What is the purpose of the following formula?
C is the channel capacity.
B is the maximum frequency of the media.
S/N is the signal-to-noise ratio, which defines the quality of the transmitted
signal. Higher values of S/N mean higher signal quality
