Final Flashcards

1
Q

What is a thread?

A

In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system.

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

What is a heavyweight process?

A

A normal process under an OS is a “heavyweight process.” For each such process, the OS provides an independent address space 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).

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

Why do we call a thread a lightweight process (LWP)?

A

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 heavyweight process to another, because there is less to manage, and the MMU is not involved.

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

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. Processes are independent of one another, and they don’t share their code, data and OS resources. Threads share their code section, data section and OS resources (like files and signals) with other threads. But, like a process, a thread has its own program counter (PC), register set and stack space.

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

Are there situations that we use multithreading?

A

Multithreading has many advantages, but in the following two cases, multithreading is preferable over a single thread process:
A) Processing power: if you have a multi-core computer system, multithreading is preferable.
B) Multithreading avoids priority inversion where a low priority activity such as accessing the disk, blocks a high priority activity, such as user interface responding to a request.

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

What is an example of a situation where having a single thread is preferred over multithreading?

A

If we are waiting for a user response or we are waiting for data to arrive over the network, it is useless to assign several threads to wait for the same thing.

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

How would a web-server act under a multithreading system?

A

The server listens for a new client to ask for a transaction. Then the server would assign a thread to the requesting client and start listening for the next client.

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

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. Explain concurrency and parallelism using single core and double core processors.

A

On a single core processor, all of the threads take turns in a round robin fashion. This is known as “concurrency.” On a double core processor, two threads run (concurrently) on one processor and the other two would run on the second one. This parallel running of threads on multiple cores is known as “parallelism”.

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

What are the four benefits of multithreading?

A
  1. Responsiveness: If a process is divided among multiple threads, then if one part of the process is blocked, the other parts could go on.
  2. Resource sharing: Different threads of a process can share code and memory of that process.
  3. Economy: Starting a new thread is much easier and faster than starting a new process.
  4. Scalability: A multithreaded process runs faster if we transfer it to a hardware platform with more processors.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the challenges programmers face when they design the code for multiprocessors?

A

In general, five areas present challenges in programming for multicore systems.

  1. Identifying tasks (dividing activities): Involves examining applications to find areas that can be divided into separate, concurrent tasks.
  2. Balance. Programmers must ensure that tasks are of the same value in terms of complexity and execution time.
  3. Data splitting. Data must be split, in a balanced manner, among already split concurrent tasks.
  4. Data dependency. Programmers must ensure that different tasks that are running concurrently do not have data dependence.
  5. Testing and debugging. Many different execution paths are possible, which is more complicated to test and debug than single-threaded applications.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the two types of parallelism?

A

Data parallelism and task parallelism.
Data parallelism: Data is divided into subsets and each subset is sent to different threads. Each thread performs the same operation.
Task parallelism: The whole data is sent to different threads, and each thread does a separate operation.

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

How do we compute speedup using Amdahl’s law?

A

speedup <= 1 / (S + ((1 - S) / N)

(S is serial portion, N is number of processing cores.) Speedup indicates how much faster the task is running on these N processors as compared to when it was running serially.

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

Suppose that 50% of a task can be divided equally among ten threads and each thread will run on a different core.

a) What is the speedup of this multithreading system as compared to running the whole task as a single thread?
b) What is the speedup of part A if we could send 90% of the job to ten threads?

A

a) speedup <= 1 / ((0.5 + (0.5 / 10))) <= 1.8

b) speedup <= 1 / ((0.1 + (0.9 / 10))) <= 5.3

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

What is the upper bound in Amdahl’s law?

A

The upper bound in Amdahl’s law is that as N approaches infinity, the speedup converges to 1 / S. E.g., if 40% of an application is performed serially, the maximum speedup is 2.5 times, regardless of the number of processing cores we add.

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

In the context of Amdahl’s law, what is the meaning of “diminishing returns?”

A

The upper bound of speedup = 1/S is still an optimistic estimation. When the number of processors and threads increase, the overhead of handling them increases too. Too much increase in the number of threads could cause a loss, and the speedup may fall below 1/S. This is known as a diminishing return, which says that sometimes a smaller number of threads could result in higher performance.

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

What are the three most popular user-level thread libraries?

A

POSIX Phtreads, Windows and Java.

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

What is the relationship between user threads and kernel threads?

A

User threads run within a user process. Kernel threads are used to provide privileged services to processes (such as system calls). They are also used by the kernel to keep track of what is running on the system, how much of which resources are allocated to what process, and to schedule them. Hence, we do not need to have a one-to-one relationship between user threads and kernel threads.

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

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

a) Before the idea of threads became popular, OS kernels only knew processes. An OS would consider different processes as separate entities. 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 OS would see the process, and the process would schedule its threads by itself.
b) The shortcoming of this model is if one of the user threads needed a system call, such as a page fault, then the other threads were blocked.

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

a) What is the one-to-one threading model?

b) What are its advantages and shortcomings?

A

a) The one-to-one model maps each user thread to a kernel thread.
b) An advantage of the one-to-one threading model is that it provides more concurrency than the many-to-one model by allowing another thread to run when a thread makes a blocking system call. It also allows multiple threads to run in parallel on multiprocessors.
The shortcoming occurs when there are too many user threads, which may burden the performance of the operating system.

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

What is a many-to-many multithreading model?

A

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.

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

What is pthread?

A

It is POSIX (portable OS interface) thread library providing programmers with application program interface (API) for creating and managing threads.

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

What is synchronous threading?

A

The parent, after creating the threads, has to wait for the children to terminate before it can resume operation.

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

For thread programming in C or C++ using pthread, what header file should be included?

A

include (less than sign)pthread.h(greater than sign)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q
  1. What does the following piece of code do?
A

It uses a function to perform summation. The main program sequentially calls the function. It takes in an array, then calculates the sum from i to n for each number in the array.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q
  1. What does the following piece of code do?
A

His answer: 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.

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

What is the difference in the behavior in the code in question 27 and 28?

A

27 uses a function for summation. It is called, and the main program has to wait for it to finish. Then the program can call it again. 28 uses threads. The main program creates all threads, and they run concurrently. The order that the threads finish their work in depends on the complexity of their job.

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

What does the following instruction do? pthread_create(id, attributes, function, argument)

A

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.

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

What does the following instruction do? pthread_join(id, ReturnedValue)

A

The main process waits for the thread with the given ID to finish and returns a variable. If no variable is to be brought back, NULL is used.

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

Does Windows support multithreading? Explain.

A

Windows supports multithreading. It supports single or multiple thread creation and single or multiple thread joining.

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

What does detaching of thread mean?

A

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.

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

What is meant by implicit threading?

A

It is difficult to create hundreds and thousands of threads by programming. The solution is implicit threading, which transfers the creation and management of threading from application developers to compilers and run-time libraries.

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

What are some popular implicit threading examples?

A
  1. Thread pools
  2. Fork-join
  3. OpenMP
  4. Grand Central Dispatch
  5. Intel Threading Building Blocks
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

How is OpenMP application programming interface used?

A

The programmer determines which parts of the program could be implemented in a parallel manner. Then the OpenMP API is used, 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.

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

What happens when fork() is used in a program?

A

fork() is the UNIX way of creating a new separate duplicate process. The new process consists of a copy of the address space of the original process. Both processes (the parent and the child) continue execution at the instruction after the fork(). fork() returns a code. The child process receives a zero from the fork(). The parent process receives a nonzero ID of the child.

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

When a fork() is executed, do the threads running under the parent process get duplicated?

A

The threads are not duplicated unless the exec() instruction is executed after fork().

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

What is a signal in the context of threading?

A

Signals notify a process of occurrence of an event. A signal can be synchronous or asynchronous. A signal is generated, delivered and then handled.

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

What are two examples of synchronous and asynchronous signals?

A

Examples of synchronous signals include illegal memory access and division by 0. Synchronous signals are delivered to the same process that performed the operation that caused the signal (that is the reason they are considered synchronous).

When a signal is generated by an event external to a running process, that process receives the signal asynchronously. Examples of such signals include terminating a process with specific keystrokes (such as controlC and having a timer expire.

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

Is it possible to create a thread and then cancel it?

A

Yes. The main thread could cancel the child thread unless the thread has disabled its cancellation. The thread can disable its cancellation, but it is better to enable it again.

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

In the context of scheduling user threads and assigning it to a kernel thread, what is a lightweight process?

A

To the user-thread library, the LWP appears to be a virtual processor on which the application can schedule a user thread to run.

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

What is a cooperating process, and why is there a potential of data inconsistency?

A

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. Wrong content of shared memory is referred to as data inconsistency.

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

Why is there a need for synchronization?

A

Data inconsistency requires that the cooperating processes or threads access shared variables in an orderly manner, which is called synchronization.

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

What is the “consumer-producer” problem in the context of synchronization? Explain the simple solution of using a “counter.”

A

Two processes are there. One process produces data, and the other process reads it (consumes it). There could be data inconsistency 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.

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

In the “producer-consumer” problem, for synchronous passing of data, what are the “blocking send” and “blocking receive” strategies?

A

If these two strategies are applied, then the sender is blocked until the receiver verifies the reception of the data. Also, the receiver is blocked from reading a data until the sender verifies that a new data is placed into the buffer.

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

What is a “race condition” in the producer-consumer problem?

A

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 that these processes update the variable. The solution is to not allow both processes to access the shared variable concurrently.

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

The “critical section” problem is a synchronization protocol. Explain its four steps.

A
  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 processes could be done concurrently.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

What are the three conditions of the critical section protocol?

A

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 which has requested should wait.

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

What is Peterson’s solution for synchronization?

A

Peterson’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 of entering the critical section. Turn variable shows the process number that is 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 there by testing the turn variable to see if it is its turn.

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

What is mutex and how does it help synchronization?

A

Complicated implementations have made synchronizing threads by OS and hardware. Mutex is a synchronization primitive available to programmers. A mutex has a binary “lock”, which is accessed by acquire() and then is release by release().

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

52.One thread is supposed to perform the following function:
A) tid[2] is a global variable. What is the purpose of this line?
B) What is the purpose of this line of code? pthread_mutex_t_ lock;
C) What happens to the thread when it reaches this line and its mutex lock is not open? pthread_mutex_lock(&lock);
D) In general, what do we call this portion of the thread?
E) What is the result of the execution of this line of code? pthread_mutex_unlock(&lock)

A

A) This is thread ID. In this example, there are two threads.
B) A global variable called “lock” is generated of the type mutex. This variable is either 0 or 1.
C) This instruction reads the mutex lock and 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, other threads 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 that are waiting for the lock can acquire it.

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

What is a semaphore?

A

A semaphore is a signaling mechanism. A thread that is waiting on a semaphore can by signaled by another thread. 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.

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

What is an “atomic” operation, and why is it important to have atomic operations for synchronization?

A

Operations that are used for synchronization are more complex than usual operations. E.g, 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 it changes the value of the variable, 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 any interference from other threads.

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

What are the purposes of wait() and signal() operations in the context of semaphores?

A
The wait() operation lets the thread keep checking the semaphore lock until the lock is released by the holder. The operation is atomic. If the lock that is read is free then the lock is changed to "unavailable" for the rest of the thread. 
The signal() operation releases the semaphore lock to a designated semaphore holder.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q
56. Explain the purpose of parts A-E. 
A) sem_t sem_example;
B) if (passed_in_value == 1) for (i = 0; i < 0xFFFF' ++i);
C) sem_wait(&amp;sem_example);
D) See code
E) sem_post(&amp;sem_example)
A

A) Defines the variable sem_example as a binary semaphore.
B) Delays thread1 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 code.
E) This thread signals the release of the semaphore to the other holder of the semaphore.

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

Is it possible to have several threads and activate them in a specific order?

A

Yes. Using semaphores, each thread can signal another thread after finishing its critical section. Hence, a particular sequence of events can be generated.

55
Q
  1. In the following, a program is shown with three threads. What are the roles of the sections of the program labeled A-F?
A) sem_t sem3, sem2, sem1;
B) sem_wait(&amp;sem1);
C) sem_post(&amp;sem3);
D) printf("\nThis is thread 2")
E) 
sem_init(&amp;sem1, 0, 1);
sem_init(&amp;sem2, 0, 0);
sem_init(&amp;sem3, 0, 0);
F) 
sem_destroy(&amp;sem1)
sem_destroy(&amp;sem2)
sem_destroy(&amp;sem3)
A

A) Three semaphore IDs are defined.
B) The thread that is to run routine1 waits here to receive a start signal through semaphore sem1.
C) When routine1’s critical section is finished, a semaphore is release to whoever holds sem3.
D) This is the critical section of routine2.
E) All three semaphores are initiated. Sem1 is initiated to 1, which means it can start initially. The other two semaphores are initiated to 0, and they have to wait until they are signaled for activation.
F) All semaphores are destroyed after their threads are joined with the main process.

56
Q

What are deadlock and starvation when multithreading is performed?

A

A deadlock occurs when each thread holds a part of the resources that other threads need. This causes indefinite wait for all of the threads.
Starvation occurs when one thread is indefinitely kept from operating.

57
Q

What are the four conditions that create deadlock where avoiding any of these conditions prevents deadlock?

A

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 join.
4) Circular wait: Among n processes, each process is waiting for another process circularly.

58
Q

What are the three methods for handling deadlocks?

A

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 of deadlock occurrence.

59
Q

How could we guarantee that processes never enter a deadlock situation?

A

1) Prevention

2) Avoidance

60
Q

How could we prevent deadlocks?

A

1) Do not apply “mutual exclusion” in all situations. E.g. 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 it is available. If a process is holding some resources and is not running, then the resources are requested back from the process.

61
Q

How could we apply deadlock avoidance?

A

Information about the needed resources and current resources of the processes is kept. Other information, such as a period of time that a process is waiting or holding resources could help avoidance of deadlock. Using this information, OS could give out resources or stop processes or take resources from the processes.

62
Q

What is the purpose of the computer network?

A

A computer network is a set of computers connected to share resources. The resources can be categorized into information, hardware, and software tools.

63
Q

What are examples of “networks?”

A
  1. Worldwide telephone networks
  2. Networks of radio and TV stations
  3. The network of communication satellites
  4. The internet
64
Q

What are the benefits of computer networks as compared to a single computer?

A
  1. Resource sharing: Hardware resources and software tools of many computers are shared between users of the network with higher efficiency.
  2. Improved reliability: If one computer (one node in the network) fails, the rest of the network is still functional, which makes the whole network more reliable.
  3. Reduced costs: Rather than collecting all computing power and storage capacity in one place, the network allows using the capabilities of other nodes.
  4. Scalability: A network of computers, e.g., a data center, can be expanded or shrunk as needed.
  5. Information sharing: Contents of the storage devices can be shared and can be accessed. Also, users can contribute to the expansion and improvement of the information.
65
Q

What are some recent applications of computer networks?

A
  1. Social networking: Users contribute new information, such as Facebook, Wikipedia, Instagram
  2. E-commerce: Supply and demand on the internet (Amazon, e-bay)
  3. Online entertainment: IPTV (IP Television)
  4. Cloud computing: SaaS, PaaS, IaaS
  5. Ubiquitous computing: Connection of embedded sensors to the internet (sensors in the home for security, body area networks for health, sensors for electricity/gas measurement, Internet of Things)
66
Q

How do we categorize networks based on the size of the region that they cover?

A
  1. PAN - Personal Area Network
  2. LAN - Local Area Network
  3. MAN - Metropolitan Area Network
  4. WAN - Wide Area Network
  5. Internet (the network of all networks)
67
Q

What are the two types of connections in a LAN? Explain each type.

A
  1. Wireless connection of devices to an access point. Convenience is high in this system due to high mobility of the connected devices.
  2. Wired connection of devices to an Ethernet switch. Performance is high in this system, but convenience is low due to the bounding of devices to a fixed location.
68
Q

What is the standard of wireless communication?

A

IEEE 802.11

69
Q

What is an example of MAN?

A

A network of fiber optic or coaxial cables is distributed underground in part of the city by a service provider, such as Comcast. Each house or apartment is connected via a “switch box.”

70
Q

What is an example for WAN?

A

Different branches of a company in different parts of a country can connect by getting services from an ISP (internet service provider).

71
Q

What is the semantic gap in networks?

A

There is a semantic difference between the complex user application and the simple signals that will physically carry the content from the source to the destination.

72
Q

How do we resolve the semantic gap in networks?

A

A multilayer structure is used to translate the application to physical signals. The same multilayer structure is used at the receiver to convert the received signal to a practical application.

73
Q

In the context of the layer model in networks, explain the following: peer, interface, services, and protocol.

A

a) Peer: Two corresponding layers in the receiver and sender sides.
b) Interface: A connection between two consecutive layers.
c) Services: The service defines what operations the layer is prepared to perform on behalf of its users, but it says nothing at all about the implementations of these operations. In the receiver, the lower layer being the service provider, and the upper layer being the service user.
d) Protocol: A protocol is a set of rules governing the format and meaning of packages, or messages, that are exchanged by the peer entities within a layer. Layers use protocols to implement their service definitions. Layers are free to change their protocols at will, provided they do not modify the service visible to their users.

74
Q

What is a connectionless network?

A

In a connectionless service, packets are injected into the network individually and routed independently of each other. No advance setup is needed. In this context, the packets are often called “datagrams” (to remind us of telegrams). The intended content may be divided into packets, which are sent without guarantee of delivery. The packets may reach destination out of order. (Internet Protocol (IP) and User Datagram Protocol (UDP) are connectionless protocols.)

75
Q

What is a connection-oriented service?

A

A path from the source router all the way to the destination router must be established before any data packets can be sent. This connection is called a virtual circuit (VC), in analogy with the physical circuits set up by the telephone system, and the network is called a virtual-circuit network. When a VC is established, all routers in the way should keep some information about the connection, which is in contrast with the connectionless service.

76
Q

Is transmission control protocol (TCP) a connection-oriented protocol?

A

The restrict definition of a connection-oriented protocol says that a virtual circuit is formed and that the packets need only to mention the connection number (virtual circuit identifier). TCP is a packet switch network, but it can act as a connection-oriented protocol. Since we include sequence numbers, and the packets are placed one after the other, we can say that TCP performs as a connection-oriented method.

77
Q
  1. What primitives are used when a client machine wants to connect to a server machine? Draw a simple diagram.
A

The main six primitives are listen, connect, accept, send, receive, and disconnect.

See diagram.

78
Q

Explain the motivation behind the first ARPANET network and its main characteristics.

A

The telephone network was hierarchical and users were at the end of the hierarchy. If a node in this tree-like structure were to fail, then all users that were connected to it would be disconnected from the network. ARPANET was created in 1972 as a packet-switched and decentralized network. The nodes were computer centers of some universities and research centers. Each node was connected to at least two other nodes. Failure of a link in the network would not fail the network.

79
Q

What is a simple description of the internet architecture in the United States?

A
  1. ISPs used the existing cable TV networks to form the backbone of the internet.
  2. Data packets are transmitted through cables and are switched by routers within each network.
  3. ISPs, through business agreements, connected their networks. Customers are connected to the closest network through cables, fiber, dialup, wi-fi or mobile phone networks. Data centers connect their cluster of servers to a network.
80
Q

What is a handoff in a mobile phone network?

A

When a user of a mobile phone leaves the coverage area of one base station and loses the connection to that station, a handoff must occur. Before losing the connection, the base station hands over the user to the next station.

81
Q

Why is the wireless connection of a computer to the network sometime of variable quality?

A

Fading occurs, which is the reduction of the signal strength of the access point, as the distance from it increases. Also, reflected signals from the access point can interfere with the direct signal, also causing fading. Hence, in some locations, the signal strength could be high, and in some places, a low power signal could be present.

82
Q

What is the OSI model, and what are the names of its layers?

A

OSI stands for Open Systems Interconnection. The OSI model lists a sequence of services that are performed in conversion of an application to signal for delivery over a network. The sequence of events is modeled as layers of the network. The list of layers consist of the following:

  1. Application
  2. Presentation
  3. Session
  4. Transmission
  5. Network
  6. Data link
  7. Physical
83
Q

What is an example of an application, and what is an example of the application layer protocol?

A

Firefox program is a network application, and HTTP is an example of the application layer protocol. The task of the application layer is to find the communication part of the Firefox program and convey that information to the next layer. E.g., a Firefox screen contains a lot of data. When the user clicks on a link, the application layer delivers only that link address to the next layer.

84
Q

What are the primary responsibilities of the presentation layer?

A

Format of the characters is changed, and character string conversion is performed. E.g, ASCII characters are converted to 8-bit decimal numbers. Encryption/decryption and data compression is also performed.

85
Q

What is the primary task of the session layer?

A

The session layer provides the mechanism for opening, closing and managing a session between end-user application processes. In case of a connection loss, this protocol may try to recover that connection. If a connection is not used for a long period of time, the session-layer protocol may close it and re-open it.

86
Q

What is the responsibility of the transport layer?

A

A header is attached to the content that is received from the session layer. Connection-oriented communication is performed by this protocol. Sequence numbers and acknowledgment are sent by the transport layer. Also, flow control and multiplexing are performed here.

87
Q

What does the network layer do?

A

Routing is the responsibility of the network layer. IP addresses of the sender and receiver are added to the content that is received from the transport layer.

88
Q

What is the purpose of the data link layer?

A

Error detection and correction is performed in the data link layer. Also, source and destination MAC addresses are added to the content that is received from the network layer.

89
Q

What is the physical layer?

A

The physical layer is a protocol that will send signals into a physical medium. Physical mediums are fiber, wire and wireless connections. Protocols such as IEEE 802.11 for wireless and 802.3 for Ethernet are examples of this layer.

90
Q

How is a web address (technically a URL) converted to an IP address?

A

A DNS (domain name server) converts a URL into an IP address.

91
Q

What are some examples of top-level domains?

A

.com, .org, .edu, .net, .gov

92
Q

What are some examples of top-level domains that indicate country codes?

A

.ca, .cn, .jp, .in, .se

93
Q

The transport layer adds a header to the content that it receives from the session layer. What is the size of this header, and what are the major parts of it?

A

It consists of at least five 32-bit words. The major parts of the header consist of the source and destination ports, sequence number, acknowledgment numbers, window size and flags.

94
Q

What is the sequence number?

A

The transmitter mentions the address of the first byte of the segment that is sending to the receiver. This number is equal to the acknowledgment number that the receiver has previously sent to the sender. By using the sequence number, the receiver knows where to place the received segment.

95
Q

What is the acknowledgement number?

A

The receiver sends the starting address of the next segment to the sender. The transmitter will use this number to generate its following sequence number.

96
Q

What is the window size in the transport layer header of the OSI model?

A

The receiver sends the volume of the data segment that it expects the transmitter will send.

97
Q

What is the meaning of congestion control?

A

Capacity of the receiver may be low and it cannot receive large data segments. Also, the network connection may be handling a large number of users and high data traffic. Hence, algorithms are required to control the size of data segments.

98
Q

What is the “slow start algorithm?”

A

The slow start algorithm is an algorithm for congestion control. It starts with a small window size. If an acknowledgment is received, then the size of the window is doubled. If the transmission is timed out, then the last successful window size will be used.

99
Q

The network layer adds a header to the data content that it receives from the transport layer. What are the major parts of the IP header?

A

IP addresses of the source and destination, time to live, header checksum.

100
Q

What is the purpose of the “time to live” 8-bit field in the IP header?

A

It is set by the sender and shows the maximum number of routers that the package can go through. Each router decrements this number and passes the packet to the next router. If the TTL field becomes zero, the packet is discarded.

101
Q

What is “fragmentation” in the IP protocol?

A

Routers may fragment an IP packet to prevent congestion. A 64KB may be partitioned into several fragments. The router adds information to the header such that the receiver can put the pieces back together to form the original packet.

102
Q

What are the two main IP protocols, and what are the main differences?

A

IPv4 and IPv6 are the two main protocols. The main difference is the length of the IP address. IPv4 addresses are 32 bits and IPv6 are 128 bits.

103
Q
  1. In the following diagram, a fragmentation example is shown. A packet of 4,000 bytes is fragmented into three pieces. Explain offset, MF, and length of these three fragments.
A

Offset: Indicates where the fragment starts, starting from the beginning of the packet.
MF: 1 indicates that more fragments follow, 0 indicates that no additional fragments follow.
Length: Shows the length of each fragment (including the size of the header)

104
Q

How many bits are in IPv4 addresses? How is the binary IP address partitioned to be presented by decimal numbers?

A

32 bits are in IPv4 addresses. The binary IP address is partitioned in 4 parts.

105
Q

What is a prefix system for IP addresses?

A

Addresses are allocated in blocks called prefixes. Prefix is determined by the network portion and has 2^L addresses aligned on 2^L boundary.

106
Q
  1. The following diagram shows the structure of an IPv4 address. What are N, L and the fields indicated with question marks?
A
N = 32 bits
L = 24 bits

(Question marks from left to right)
Subnet mask
Network
Host

107
Q
  1. 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

It will be sent to EE. The 18 most significant bits of 192.222.250.200 is 192.222.192.0, which matches EE.

108
Q

What is the longest prefix matching?

A

If addresses overlap with both entries, package is forwarded to the entry with the longest prefix.

109
Q

Consider the following diagram. Suppose a packet with the IP address of 192.24.12.0 arrives in New York. Does the router send the packet to London or San Francisco? Why?

A

It sends it to San Francisco, because SF has the longest matching prefix. (Both London and SF match, so it sends it to the one with the longest prefix).

110
Q

What is an Ethernet address and how many bits is it?

A

Ethernet or MAC address is the hardware address, which is 48 bits. It is shown as a set of 6 8-bit hex numbers. Ethernet is a property of the network card of the device.

111
Q

What is the difference between the Ethernet address and the IP address?

A

IP address is virtual and the Ethernet address is physical. Depending on where the device is connected to the internet, it will be assigned to an IP address, but the device will always have a permanent MAC address. IP is used for routing to reach the address domain. MAC is used to identify the connected devices.

112
Q

Which layers add IP and Ethernet addresses?

A

“Network layer” adds IP addresses, and the “data-link” layer adds MAC addresses to the data packets.

113
Q

What are network sockets?

A

A socket is an endpoint in a computer to send and receive data.

114
Q

What are the steps for a server to create a connection using a socket?

A
  1. Create the socket.
  2. Bind the socket to a port.
  3. Listen for a request.
  4. Accept the request.
  5. Write data.
  6. Read data.
  7. Close the connection.
115
Q

What are the significant steps for a client to connect to a server using a socket?

A
  1. Create the socket.
  2. Connect to the server.
  3. Read data.
  4. Write data.
  5. Close the connection.
116
Q

What are the four numbers that identify a socket?

A

IP and port number of the local and remote computers.

117
Q
  1. What is the purpose of this piece of code?
socket_descriptor = socket(domain, type, protocol);
if(socket_descriptor == -1)
{
      printf("Could not create socket");
      return -1;
}
A

It generates a socket. If the socket is generator, then a descriptor will be returned, otherwise, -1 is returned.

118
Q
  1. What is the purpose of this piece of code?

if (bind(sockfd, (struct sockaddr *) &serv_addr, sizeof(serv_addr)) < 0)
{
error(“ERROR on binding”);
}

A

When a socket is created, it exists in a name space (address family) but has no address assigned to it. bind() assigns the address specified by addr to the socket referred to by the file descriptor sockfd.

119
Q
  1. What is the purpose of this piece of code?

int listen(int sockfd, int backlog);

A

listen() marks the socket referred to by sockfd as a socket that will be used to accept incoming connection requests.

120
Q

What is channel capacity?

A

Bits per second that are transmitted inside a physical channel.

121
Q

What is the required channel capacity for transmitting a media such as voice or video?

A

The required capacity depends on the quality of the transmission we want to have, as well as the frequency of the media.

122
Q

What is the purpose of the following formula?

C= 2 * B * log2(1 + S/N)

A

C: channel capacity
B: maximum frequency of the media
S/N: Signal to noise ratio, which defines the quality of the signal that is transmitted. Higher values of S/N means higher signal quality.

123
Q

How do we calculate quality in terms of decibel?

A

Quality in terms of decibel is

db = 10 log10(S/N)

124
Q

What does S/N of 30db mean?

A

It means that S/N must be 1000, so its log10 becomes 3, and then multiplied by 10, it’s 30.

125
Q

Suppose S/N is 30db and we want to transmit voice over a transmission line. We know that B (or maximum frequency) for voice is 4KHz. What channel capacity do we need?

A

We convert S/N from decibel to a real value.
30db = 10 log10(S/N). Hence, S/N = 1000.
C = 2 * 4000 * log2(1 + 1000)
C = 80,000 bps

126
Q

What is computer security?

A

Computer security is the collection of tools designated to protect data and to stop hackers.

127
Q

What is authentication?

A

Authentication is the assurance that the communicating entity is the one claimed.

128
Q

What is data integrity?

A

Data integrity is the assurance that data sent has not been modified and is as sent by an authorized entity.

129
Q

What are the two main classes of security attacks?

A

1) Passive attacks, which only monitor the content of the transmitted information.
2) Active attacks, which modify the data.

130
Q

What are the means of “ciphertext” and “cryptanalysis?”

A

The coded message is called ciphertext, and the method to break an encryption system is called cryptanalysis.

131
Q

What is the difference between the “symmetric” cipher and “public key” cipher?

A

In symmetric cipher, a key is used which is known to both sender and receiver of the ciphertext. Public key cipher is a cryptographic system that uses pairs of keys: public keys that can be spread widely, and private keys that are only known to the owner.

132
Q

What is Caesar cipher of substitution cipher?

A

Each letter in the plaintext is shifted a certain number down the alphabet.

133
Q

What is steganography?

A

Steganography is hiding of data in an image.

134
Q

Suppose in a public cipher we have the following parameters:

The public key is (N, e) = (33, 3)
The message is M = 9
Private key is (N, d) = (33, 7)

What is the ciphertext, and how do we find the original message?

A

C = ciphertext = M^e % N

M = original message = C^d % N

C = 9^3 % 33 = 729 % 33 = 3
M = 3^7 % 33 = 2187 % 33 = 9