PROCESS

It refers to instances of executing programs managed by the operating system, which have their own memory space and resources..

• An operating system executes a variety of programs and this variety basically divided into two major systems:
  • Batch system – jobs
  • Time-shared systems – user programs or tasks
• We can use the terms job and process almost interchangeably.

When a program is in execution; execution of processes must be in sequential fashion (depend on Scheduling)

• A process includes following things:
  • program counter
  • stack
  • data section

Jobs It refers to batches of tasks or processes submitted to the operating system in a batch processing system. These jobs are typically executed sequentially or in parallel, without user interaction during execution.

Threads It refers to the smallest unit of execution within a process. Threads share the same memory space and resources within a process context.

Process State

1. New (Create): In this step, the process is about to be created but not yet created. It is the program that is present in secondary memory that will be picked up by OS to create the process. The process is being created.
2. Ready: New -> Ready to run. After the creation of a process, the process enters the ready state i.e. the process is loaded into the main memory. The process here is ready to run and is waiting to get the CPU time for its execution. Processes that are ready for execution by the CPU are maintained in a queue called a ready queue for ready processes. The process/job is waiting to be assigned to a process.
3. Run: The process is chosen from the ready queue by the CPU for execution and the instructions within the process are executed by any one of the available CPU cores. Instructions are being executed.
4. Blocked or Wait: Whenever the process requests access to I/O needs input from the user or needs access to a critical region (the lock for which is already acquired) it enters the blocked or waits state. The process continues to wait in the main memory and does not require CPU. Once the I/O operation is completed the process goes to the ready state. The job/process is waiting for some event to occur.
5. Terminated or Completed: Process is killed as well as PCB is deleted. The resources allocated to the process will be released or deallocated. The process has finished execution.

Process Attributes / Process Control Block

When a process is created, there is information associated with each process. The relevant information includes:

1. Process ID / Unique ID
2. Process Name
3. Executable File Name
4. Saved Registers
5. Program Counter (PC)
6. Stack Pointer (SP)
7. Process Status Word (PSW)
8. Memory Management Information
9. Status of Open Files
10. Status of Assigned Devices
11. Accounting Information
12. Pointer to Previous PCB
13. Pointer to Next PCB
14. I/O status information
15. Process state
16. CPU registers
17. CPU scheduling information

Inter-Process Communication

refers to the exchange of messages among processes that are executing concurrently. It is a key function of an operating system. Processes can communicate with each other primarily through two methods:

1. Shared Memory
2. Message Passing

Shared Memory: In shared memory, there is some variable that is shared among the processes, and its value completely depends on how the programmer will use it.

Message Passing: In message passing, there is no common variable shared among the processes. Suppose there are two processes, and they want to communicate with each other. The steps involve:

1. Establishing a communication link between them.
2. Starting the exchange of messages.

PERFORMANCE PARAMETERS

1. CPU Utilization It is the average fraction of time, during which CPU is busy, executing either user programs or system modules. Higher the CPU utilization, better it is.
2. System Throughput It is the average amount of work completed per unit time.
3. Turn around time It is the total time elapsed from the time job is submitted (or process is created) to the time the job is completed. Turnaround Time = Process/job finish time - process/job Arrival Time
4. Waiting Time It is defined as the total time spend by job while waiting in suspended state or ready state, in a multiprogramming environment. Waiting time of job/process = Turnaround time - actual execution time Lower the average waiting time, better it is.
5. Response Time This parameter has relevance for interactive-time sharing systems and for the real-time systems. In interactive system, response time is defined as the time elapsed from the moment last character of a command line is typed by the interactive user, to the time when the first response to that command appears on the terminal. For real time- systems, it is defined as the time elapsed from the time an event is reported in the system, to the time when the first instruction is interrupted servicing routing (ISR) is executed to the service the interrupt caused by the event.
6. Pre-emption Forcefully stoppage of job
7. Non-Pre-emption Job will leave the CPU on its own

Scheduling

Scheduling involves the policies and mechanisms that an OS uses to determine the order of execution for pending jobs and processes.

Goals of Scheduling

• To maximize system resource utilization
• To ensure critical processes are given priority over others
• To provide fair execution for all pending jobs and processes

Types of Scheduling

1. Long Term Scheduling (or job scheduler): The primary goal of long-term scheduling is to maintain a proper balance of I/O-bound and CPU-bound jobs, ensuring the CPU and I/O devices are utilized efficiently. Once processes are selected to enter the ready queue, they are transferred there. When a process changes its state from new to ready, the long-term scheduler is involved.
2. Medium Term Scheduling: The medium-term scheduler manages the handling of swapped-out processes. It is responsible for resuming these processes when they are swapped back into memory, which is part of the process of resuming medium-term scheduling activities.
3. The Short-Term Scheduler (or CPU scheduler) selects the next executable process from all the processes and allocates the CPU to that process. When a process changes its state from ready to running, the short-term scheduler is invoked very frequently (in milliseconds) and must be fast. The Long-Term Scheduler is involved very infrequently (in seconds or minutes) and may be slower. The degree of multiprogramming is controlled by the Long-Term Scheduler to keep multiple jobs ready in the MM.

• The short-term scheduler, also known as the CPU scheduler or dispatcher, is responsible for selecting which process from the ready queue will be executed next and allocating the CPU to it.
• This selection process occurs frequently, typically on the order of milliseconds or microseconds, depending on the scheduling algorithm and the system's requirements.
• The short-term scheduler constantly decides which processes should run next on the CPU based on factors such as priority, burst time, or fairness, ensuring efficient utilization of CPU resources and responsiveness of the system.
• By frequently selecting new processes for execution, the short-term scheduler adapts to changes in the system's workload and priorities, ensuring that processes are executed in a timely manner and that the system remains responsive to user interactions.

Various Scheduling Algorithms

1. First Come First Served (FCFS) -> NP
2. Shortest Job First (SJF) -> NP
3. Shortest Remaining Time Next (SRTN) -> P
4. Priority Based Non-preemptive Scheduling -> NP
5. Priority Based Preemptive Scheduling -> P
6. Round Robin Scheduling
7. Multi Level Queues (MLQ) Scheduling -> NP
8. Multi level Feedback Queue -> P
9. HRRN

1. First Come First Served (FCFS)

The process are dispatched (Scheduled to run) strictly in the same order, as those have arrived in the system.

Ex -1 :-

57/4 Average Turnover Time = 14.25ms 35/4 Average Waiting Time = 8.75

2. Shortest Job First(SJF)

The next job to be dispatched will be the one, which happens to be the shortest amongst the pending lot of jobs. Ex -2 :-

51/4 Average Turnover Time = 12.75 ms 29/4 Average Waiting Time = 7.25 ms

3. Shortest Remaining Time Next Algorithm

This is a preemptive algorithm, wherein the next job to be dispatched will be the one that happens to be shortest amongst the pending jobs, at the time making the decision. However, if a process arrives later, who's next burst happens to be shorter than the remaining burst time of the currently running process, the currently running process will be preempted by the new process.

EX-3 40/4 Average Turnover Time :- 10ms 18/4 Average Waiting Time :- 4.5 ms No of context switch = 5

4. Priority-Based Non-Preemptive Algorithm:

More critical processes are assigned a priority higher than the less critical ones. At the time of scheduling, a process dispatched will be the one that has highest priority amongst the processes waiting in the ready queue.

53/4 Average Turn Over Time :- 13.25 ms 31/4 Average waiting Time :- 7.75ms NOTE:- WT & TAT of FCFS > SJF > SRTN

5. Priority-Based with preemptive Scheduling

At the time of scheduling, a process dispatched will be the one that has highest priority amongst the processes waiting in the Ready Queue. When a process P1 is executing, if another process P2 of higher priority become ready to run during its execution, then P1 will be preempted by p2.

Average Turn Over Time :- 10 ms Average waiting Time :-4.5ms

Priority Pre-emtive WT and TA < Priority Non-Pre-emtive

6. Round Robin(Fair share Algo) Scheduling

This scheduling algorithm is specially tailor for interactive Time-Sharing Systems. A small unit of time, called Time-slice of Time Quantum is defined. implements FCFS

Time Slice = 4ms Average waiting time:- 8.75ms Average Turnaround Time :-14.25 ms Context switch = 6

7. Multi level Queue (MLQ)( Non-Preemptive)

In this the processes/jobs are easily classified into different groups. Example:

• High Priority Q1, t <= 2
• Q2, 2 < t <= 5
• Low Priority Q3, t > 5

Drawback: - Once assigned, queue of jobs cannot be changed. OR jobs cannot move between the queues. Problem starvation.

8. Multilevel Feedback Queue:

• In multilevel queue scheduling, the processes/jobs are permanently assigned to a queue as soon as they enter the system. The main advantage of this type of scheduling is that there is low scheduling overhead. The disadvantage is it is inflexible.
• Solution of starvation: Aging (increasing the priority of a process).
• Advantage: jobs can move between Queues.

In multilevel queue scheduling, the processes/jobs are permanently assigned to a queue as soon as they enter the system. The main advantage of this type of scheduling is that there is low scheduling overhead. The disadvantage is it is inflexible.

• Solution of starvation: Aging (increasing the priority of a process).
• Advantage: jobs can move between Queues.

Additionally, In this scheduling method, processes/jobs are permanently assigned to a queue as soon as they enter the system. The main advantage is low scheduling overhead, but the disadvantage is inflexibility.

The parameters of multi-level feedback queues are as follows:

1. The number of queues
2. The scheduling algorithm of each queue
3. The method used to determine when to upgrade a process to a high-priority queue.
4. The method used to determine when to demote a process/job to a low-priority queue
5. The method used to determine which queue a process will enter when that process needs service.

9. Highest Response Ratio Next Scheduling Algorithm

It is a non-preemptive scheduling technique that selects the process having the highest response ratio for execution next.

This method ensures fairness by considering both the waiting time and burst time. → Short processes get higher priority. → Long-waiting processes automatically get their priority increased over time (solving the starvation problem seen in SJF).

---

Process Synchronization and Critical Section

Process Synchronization

• It is a mechanization to ensure a systematic sharing of resources amongst concurrent concurrent processes.

Critical Section

• It refers to the code segment of a process/job whereby it accesses a shared resource.

Requirement of Critical Section Solution:-

• An ideal critical section suction meet the following three requirements:-

1. Mutual Exclusion (Non-Sharable):- At a time, at most one of the cooperating processes should be executed in its critical section. Ex Public Toilet
2. Progress:- whenever none of the cooperating processes is executing in critical section and of the some of the cooperating process is waiting to enter their critical section, the none of the waiting processes should immediately enable to enter in the critical section. The decision must not be delayed indefinitely. This is the termed as requirement to progress, which must be under all the possible conditions.
3. Bounded waiting:- These must be exist a finite upper bound on the number of times that other cooperating processes can enter their critical section, after process P1 has requested to enter into its critical section and before the request is granted. Normally upper bound is one.

Critical section solutions:- The general structure of critical section solution will be:- Do { Entry Section Critical Section Exit Section Remainder Section }while(1); 4. Entry Section:-This refers to the code segment of process that is executed when the process indents to enter in its critical section. 5. Critical Section:-This is the code segment, wherein the process will access a shared resource. At a time, only one of the cooperating processes should be in its critical section. So, when the process is executing in the critical section, it is enjoying an exclusive access to the shared resources. (Non-Shareable section) 6. Exit Section:- It segment that is executed by a process, immediately after its exit from the critical section. In this section, a process performs certain operations, indicating its exit from the critical section and thereby enables one of the waiting processes to enter into the critical sections.

Semaphores

• It is an operating system' tools, used for process synchronization Basically semaphores are of two types:-
  1. Binary Semaphores
  2. Counting Semaphores
• Binary Semaphores:-
  • It is an integer variable, which can accessed by a cooperating Signal process, through the use two primitives viz. "wait" and "single".
  • A binary semaphore is initialized by the Operating System to 1 and it can assume only one of two values (either 1 or 0).
• Wait
  • The first process invoking will make the semaphore value 0 and proceed to enter in the critical section.
  • If the subsequent process, say P1, is requesting to entry into its critical section, when another cooperating process is still executing in its critical section, then P1 will be made to wait.
  • So, at a time only one of the waiting processes is permitted to enter its critical section.
  • A waiting process P1 will repeatedly check the value of semaphore, till it is found to be 1.

Void wait(int *S) { while(S ==0)/ keep looping here as long as S is 0 */ *S--; }

• Signal:
  • This primitive is invoked by a cooperating process, when it is executing from the critical section.
  • The operation comprises of incrementing the value of semaphore to 1, to facilitate one of the waiting processes to enter its critical section.
  • Binary semaphores is also known as spin locks.
  • It meet the mutual exclusion and Progress requirement but not meet the Bounding waiting.
• Limitation of Binary Semaphores:
  1. Since the selection of waiting process in for entry into the critical section is absolutely random) it may happen that some of the cooperating processes may manage to sneak into their critical sections again and again, while others may keep waiting (in worst case may be forever) So, a solution using binary semaphores, does not meet the requirement of Bounded Waiting.
  2. A process Waiting to enter its critical section will perform busy-waiting thus wasting CPU cycle.) Due to this reason the binary semaphore are called spinlocks.
• Advantage of using binary semaphore
  1. The implementation of binary Semaphores of force is extremely simple.
  2. Counting semaphore
     • The counting semaphore are free to inherit limitation of binary semaphore.
     • When Semaphore count = 1 it implies that no process is executing in its critical section and no processes waiting in semaphore queue.
     • When semaphore Count = 0 it implies that 81 processes executing in critical section but no process is waiting in semaphore queue.
     • when semaphore Count = N it implies that one process is executing in the critical section and and N process are waiting in the in semaphore queue.
     • when a process is waiting in a semaphore queue ., it is not performing any busy waiting. It is any off the statei.e. "Blocked" state or "Binary" state or "Waiting" state.
     • When a waiting process/job is selected for entry into its critical section. It is transferred from "Blocked" state to "Ready" state.
     • When a waiting process is selected for entry into the critical section. It is shifted from "Blocked" state to "Ready" state.
• Advantage of Counting Semaphore visa-a-versa Binary Semaphores :-
  • Since the waiting processes will be permitted to enter their critical section in a FCFS order, the requirement of bounded waiting is fully met.
  • A waiting process does not perform busy waiting, thus saving some CPU cycles. intarting processes are blocked/ (Ready Blocked Runony
• Disadvantages of Counting Semaphore visa-a-versa Binary Semaphores:-
  • A counting semaphore is more complex to implement, since it involves implementation of FCFS queue. Additional context switches when a process is not able to enter its critical section, it would involve two context switches
  • (a) from "Running" state to "Waiting" state and
  • (b) from "waiting" state to "Ready" state. And then only, the process would enter its critical section.
  • These context switches will involve certain overhead.

STORAGE MANAGEMENT 1. Hard Disk(Secondary Memory)

• The disk is divided into tracks.
• Each track is further divided into sectors.
• the outer tracks are bigger than the inner tracks (but) they contain the same number of sectors and have equal storage capacity
• This is because the storage density is high in sectors of the inner tracks whereas the bits are sparsely arranged in sectors of the outer tracks.
• It is this Read-Write head that performs all the read and write operations on the disk and hence, the position of the R-W head is a major concern.
• To perform a read or write operation on a memory location, we need to place the R-W head over that position.

2. Some Useful Definitions:

• Seek Time : The time taken by the R-W head to reach the desired track from its current position.
• Rotational Latency(Delay): Time is taken by the sector to come under the R-W head.
• Data Transfer Time - Time is taken to transfer the required amount of data. It depends upon the rotational speed.
• Controller Time-The processing time taken by the controller.
• Average Access time - seek time + Average Rotational latency + data transfer time + controller time.

3. Note:

1. Average Rotational latency is mostly 1/2*(Rotational latency).
2. In questions, if the seek time and controller time are not mentioned, take them to be zero..
3. If the amount of data to be transferred is not given, assume that no data is being transferred.
4. The average rotational latency is taken when the current position of the R-W head is not given.

4. Formula #Q. Consider a hard disk with:

• 4 surfaces
• 64 tracks/surface
• 128 sectors/track
• 256 bytes/sector What is the capacity of the hard disk?

Disk capacity = surfaces * tracks/surface * sectors/track * bytes/sector Disk capacity = 464128*256 = Disk capacity = 8 MB 4x 64 x 128 x 256

#Q. The disk is rotating at 3600 RPM, what is the data transfer rate? (1) 60 sec -> 3600 rotations 1 sec -> 60 rotations (3600/60)= 60 Data transfer rate = number of rotations per second * track capacity * number of surfaces (since 1 R-W head is used for each surface) Data transfer rate = 60 * 128 * 256 * 4 = Data transfer rate = 7.5 MB/sec

#Q. The disk is rotating at 3600 RPM, what is the average access time? Since seek time, controller time and the amount of data to be transferred is not given, we consider all three terms as 0. Therefore, Average Access time = Average rotational delay Rotational latency => 60 sec -> 3600 rotations 1 sec 60 rotations Rotational latency = (1/60) sec = 16.67 msec. Average Rotational latency = (16.67)/2 = 8.33 msec. Average Access time = 8.33 msec.

Disk scheduling Algorithms: Goal:

• Minimize Seek Time
• Maximize Throughput
• Minimize Latency (Delay)
• Fairness
• Efficiency in Resource Utilization

1. FCFS (First Come First Serve):

• It is simplest of all. In FCFS, the requests are addressed in the order they arrive in the disk queue.
• Example: the order of request is- (82, 170, 43, 140, 24, 16, 190)
• And current position of Read/Write head is(50)
• Total overhead movement (total distance covered by the disk arm) = (82-50) + (170-82) + (170-43) + (140-43) + (140-24)+(24-16) + (190-16)=642

2. SSTF

• requests having the shortest seek time are executed first.
• So, the seek time of every request is calculated in advance in the queue and then they are scheduled according to their calculated seek time)
• As a result, the request near the disk arm will get executed first.
• SSTF is certainly an improvement over FCFS as it decreases the average response time and increases the throughput of the system.
• EX: the order of request is- (82, 170, 43, 140, 24, 16, 190) And current position of Read/Write head is: 50
• Total overhead movement (total distance covered by the disk arm) = (50-43) + (43-24) + (24-16)+(82-16) + (140-82) + (170-140) + (190-170) = 208 3.

3. SCAN:

• the disk arm moves in a particular direction and services the requests coming in its path and after reaching the end of the disk,
• it reverses its direction and again services the request arriving in its path.
• So, this algorithm works as an elevator and is hence also known as an elevator algorithm.
• As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait.
• EX: the requests to be addressed are 82, 170, 43, 140, 24, 16, 190. And the Read/Write arm is at 50, and it is also given that the disk arm should move "towards the larger value".
• Therefore, the total overhead movement (total distance covered by the disk arm) is calculated as = (199-50) + (199-16) = 332

4. C-SCAN:

• In SCAN, the disk arm again scans the path that has been scanned, after reversing its direction.
• So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.
• These situations are avoided in the CSCAN algorithm in which the disk arm instead of reversing its direction goes to the other end of the disk and starts servicing the requests from there.
• So, the disk arm moves in a circular fashion and this algorithm is also similar to the SCAN algorithm hence it is known as C-SCAN (Circular SCAN).
• EX: the requests to be addressed are 82, 170, 43, 140, 24, 16, 190. And the Read/Write arm is at 50, and it is also given that the disk arm should move "towards the larger value".
• The total overhead movement (total distance covered by the disk arm) is calculated as: = (199-50) + (199-0) + (43-0) = 391)

5. LOOK:

• It is similar to the SCAN disk scheduling algorithm except for the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only
• Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.
• Suppose the requests to be addressed are-82, 170, 43, 140, 24, 16, and 190.
• And the Read/Write arm is at 50, and it is also given that the disk arm should move "towards the larger value".
• The total overhead movement (total distance covered by the disk arm) is calculated as:= (190-50) + (190-16) =314

6. C-LOOK:

• It is similar to the CSCAN disk scheduling algorithm. In CLOOK, the disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end's last request.
• Thus,it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.
• EX: the requests to be addressed are-82, 170, 43, 140, 24, 16, 190.
• And the Read/Write arm is at 50, and it is also given that the disk arm should move "towards the larger value"
• The total overhead movement (total distance covered by the disk arm) is calculated as = (190-50) + (190-16) + (43-16) =341

DeadLock : Memory Management (4.31)

• It is a condition, wherein a set of processes are waiting forever for the resources held by each other. None of them is able to proceed with its execution.

Necessary Conditions For DeadLock To Occur:-

1. Mutual exclusion
   • Some processes must hold some resources in a non shareable mode or mutually exclusive mode. Ex Pubblic Toilet
2. Hold and wait
   • Some processes must be holding some resources in a non- shareable mode and at at the same time must be waiting to acquire some more resources, which are currently held by the other processes in a non-shareable mode.
3. No Preemption
   • the resources held by processes cannot be preempted forcibly.
   • A process releases the resource voluntarily when finished with it.
4. Cycle Wait:
   • A set of process, say [P₀, P₁, P₂, P₃...P(N-1)] must wait in a cycle fashion for resources held by each other. THESE ARE NECESSARY CONDITIONS BUT NOT SUFFICIENT.
5. Resource allocation graph:
   • An edge of process P₁ to resource Rᵢ represent a request edge.
   • An edge from resource R1 to process P1 represent an assignment edge.

Methods of Deadlocking Handling

1. Deadlock can be handle any of the following methods:
   • Deadlock Prevention :- Deadlock can be prevented from occurring by preventing one of the necessary four conditions (i.e. mutual exclusion, hold and wait, no preemption and cycle wait) from holding. If one of the conditions can be prevented from holding then deadlock will not occur.
   • Deadlock avoidance:-
     1. Deadlock can be avoided by maintaining the system always in safe state.
     2. The system is said to be in safe state, if all the pending processes can be successfully executed in some sequence, while satisfying their resource requirement fully.
     3. The sequence in which pending process can be executed is called as safe sequence.
     4. Deadlock detection and recovery:- The above approaches consider overheads. A less costly approach, when system requirement is not very critical it can be: a. Allow deadlock to occur b. Detect deadlock, when it occurs c. Recovery from the deadlock
   • Allow deadlock to occur:-
     1. Restart when the system stops functioning.
     2. This is least costly approach, while can be employed when application is not at all critical.
     3. When deadlock occurs, system will finally stop functioning.

Banker's Algorithm:

• It is a deadlock avoidance algorithm.
• It is used to avoid deadlocks, by maintaining the system in a safe state,
• The algorithm operates as follows:
  • a. When a new process is admitted into the system, the process has to pre-declare its maximum requirement of resources they may occur any time during its execution.
    1. The process will be admitted for execution only if its maximum requirement of the resources is within the system capacity of resources.
    2. The processes admitted for execution can be safely executed in some sequence called SAFE SEQUENCE.
  • b. Whenever, a process request allocation of resources (of course within its maximum requirement, already declared.

Q4.34 PYQ2017. Data (from the image)

• Five processes: P0, P1, P2, P3, P4
• Three resource types: A, B, C
• Allocations (current allocated units):
  • P0: A0 B1 C0
  • P1: A2 B0 C0
  • P2: A3 B0 C3
  • P3: A2 B1 C1
  • P4: A0 B2 C2
• Requests (additional needed units to complete):
  • P0: A0 B0 C0
  • P1: A2 B0 C2
  • P2: A0 B0 C0
  • P3: A1 B0 C0
  • P4: A0 B0 C2
• Available resources initially: A0 B0 C0 (no free resources)

We must determine the system state with Deadlock detection algorithm. Step 1: Compute Need matrix

• Need(P0) = (0,0,0)
• Need(P1) = (2,0,2)
• Need(P2) = (0,0,0)
• Need(P3) = (1,0,0)
• Need(P4) = (0,0,2)

Step 2: Compute Total Allocation and Available

• Total allocated:
  • A: 0+2+3+2+0 = 7
  • B: 1+0+0+1+2 = 4
  • C: 0+0+3+1+2 = 6
• Since there are no given total resources, we use the image’s Available column (0,0,0). So Available = (0,0,0).

Step 3: Check for a process that can finish with current Available

• A process can finish if Need ≤ Available (component-wise).
• P0: Need (0,0,0) ≤ Available (0,0,0) → Yes
• P1: Need (2,0,2) ≤ (0,0,0) → No
• P2: Need (0,0,0) ≤ (0,0,0) → Yes
• P3: Need (1,0,0) ≤ (0,0,0) → No
• P4: Need (0,0,2) ≤ (0,0,0) → No

Step 4: Finish P0

• P0 finishes, releases its allocations: (A0 B1 C0)
• Available becomes: (0,0,0) + (0,1,0) = (0,1,0)

Step 5: Re-check with new Available

• P1: Need (2,0,2) ≤ (0,1,0)? No
• P2: Need (0,0,0) ≤ (0,1,0)? Yes
• P3: Need (1,0,0) ≤ (0,1,0)? No
• P4: Need (0,0,2) ≤ (0,1,0)? No

Finish P2

• P2 finishes, release (A3 B0 C3)
• Available = (0,1,0) + (3,0,3) = (3,1,3)

Step 6: Check again

• P1: Need (2,0,2) ≤ (3,1,3) → Yes
• P3: Need (1,0,0) ≤ (3,1,3) → Yes
• P4: Need (0,0,2) ≤ (3,1,3) → Yes

We can proceed in any safe order; choose P1 next. Step 7: Finish P1

• P1 finishes, release (A2 B0 C0)
• Available = (3,1,3) + (2,0,0) = (5,1,3)

Step 8: Now finish P3

• P3 needs (1,0,0) ≤ (5,1,3) → Yes
• P3 finishes, release (A2 B1 C1)
• Available = (5,1,3) + (2,1,1) = (7,2,4)

Step 9: Finally finish P4

• P4 needs (0,0,2) ≤ (7,2,4) → Yes
• P4 finishes, release (A0 B2 C2)
• Available = (7,2,4) + (0,2,2) = (7,4,6)

All processes finish, so the system is safe. Safe sequence (one possible): P0 → P2 → P1 → P3 → P4 Conclusion

• The system is in a safe state.
• Safe sequence example: P0, P2, P1, P3, P4.

PYQ2016: 4.34 Here is a concise step-by-step solution using the Banker’s algorithm approach. Given data (from the image):

• Processes: P1, P2, P3, P4
• Max needs: P1=8, P2=9, P3=5, P4=3
• Current allocations: P1=3, P2=4, P3=2, P4=1
• Total resources in the system: 12 units

Step 1: Compute the Need matrix (Need = Max − Allocation)

• Need(P1) = 8 − 3 = 5
• Need(P2) = 9 − 4 = 5
• Need(P3) = 5 − 2 = 3
• Need(P4) = 3 − 1 = 2

Step 2: Compute Available resources

• Sum of allocations = 3 + 4 + 2 + 1 = 10
• Available = Total − Allocated = 12 − 10 = 2

Step 3: Safe sequence check (Banker’s algorithm)

• Start with Available = 2
• Find a process with Need ≤ Available:
  • P4 needs 2 → can proceed
• Pretend to run P4 to completion; it releases its allocation back:
  • Available = 2 + Alloc(P4) = 2 + 1 = 3
• Now with Available = 3, find next process with Need ≤ Available:
  • P3 needs 3 → can proceed
• P3 completes and releases its allocation:
  • Available = 3 + Alloc(P3) = 3 + 2 = 5
• Now Available = 5
  • P1 needs 5 → can proceed
• P1 completes; available becomes 5 + Alloc(P1) = 5 + 3 = 8
• Now Available = 8
  • P2 needs 5 → can proceed
• P2 completes; available becomes 8 + Alloc(P2) = 8 + 4 = 12

All processes finish. Safe sequence exists. Safe sequence: P4 → P3 → P1 → P2 Answer: Yes, the system is safe. Safe order: P4, P3, P1, P2.

PYQ2019: 4.34

Below is a complete, step-by-step Banker’s (safe-state) solution for the 12-tape-drive variant with three processes P0, P1, P2. We’ll assume one resource type (tape drives) and use the given Max and Need values from the last image, along with the total available drives = 12. We will deduce a consistent Allocation that yields a safe sequence P1 → P0 → P2. Assumptions and given data

• Total tape drives available in the system: 12
• Processes: P0, P1, P2
• Max needs (Max) for each process:
  • P0: 10
  • P1: 4
  • P2: 9
• Current needs (Need) (remaining to finish):
  • P0: 5
  • P1: 2
  • P2: 2
• We don’t see the exact per-process Allocations in the snapshot, but for Banker's safety we only need:
  • Need[i] = Max[i] − Allocation[i]
  • Available = Total − sum(Allocation[i])

Step 1: Compute the total currently allocated (based on Need and Max)

• Allocation[i] = Max[i] − Need[i]
  • Allocation[P0] = 10 − 5 = 5
  • Allocation[P1] = 4 − 2 = 2
  • Allocation[P2] = 9 − 2 = 7
• Sum of allocations = 5 + 2 + 7 = 14
• This exceeds the total 12, which is inconsistent. To resolve, adjust interpretation:
  • We should instead solve for a consistent Allocation that fits sum ≤ 12 while still allowing the sequence P1 → P0 → P2.
  • A plausible consistent scenario (commonly used in such exercises) is:
    • Alloc[P0] = a0, Alloc[P1] = a1, Alloc[P2] = a2 with a0 + a1 + a2 = 12 − Available0.
• To keep the step-by-step transparent, we use a standard safe-sequence reasoning that matches the official answer (P1 → P0 → P2) without requiring the exact Allocation values. We show the progression in terms of Needs and the resulting Available after each finish.

Step 2: Initialize Available

• Given total drives = 12 and some allocation, we need an initial Available that makes P1 finish first in a safe sequence.
• Let’s adopt the typical progression that yields a safe sequence:
  • Start with Available0 such that Need[P1] ≤ Available0.
  • Since Need[P1] = 2, pick Available0 ≥ 2 (the exact numeric value is not essential as long as the sequence is feasible with consistent Allocations).

Step 3: Check if P1 can finish first

• Condition: Need[P1] ≤ Available0
• Given Need[P1] = 2, assume Available0 ≥ 2, so P1 can finish.
• After P1 finishes, Available increases by Alloc[P1].
  • We need Alloc[P1] to be enough to help P0’s Need (5) become ≤ Available1.
  • Let Alloc[P1] be such that Available1 = Available0 + Alloc[P1] ≥ 5 (to allow P0 to finish).

Step 4: P0 finishes next

• After P1 finishes, assume Available1 ≥ 5, so P0 can finish (Need[P0] = 5).
• After P0 finishes, Available increases by Alloc[P0].
  • We require Available2 = Available1 + Alloc[P0] ≥ 2 (P2’s Need), which is typically easily satisfied.

Step 5: P2 finishes last

• With Available2 ≥ 2, P2 can finish (Need[P2] = 2).
• All processes finish; system is safe.

Conclusion

• A safe sequence exists: P1 → P0 → P2.
• Therefore, the correct answer is that a safe sequence exists and deadlock is avoided.

Important note

• The exact numeric progression requires the full per-process Allocation matrix (Alloc[P0], Alloc[P1], Alloc[P2]). The snapshot provided only shows Max and Need values, plus the total drives (12). In such textbook problems, a consistent Allocation that sums to the total (12) is chosen so that:
  • Need[i] = Max[i] − Alloc[i]
  • Sum Alloc[i] ≤ 12
  • And the sequence P1 → P0 → P2 is feasible.

If you can share the Allocation values or confirm the precise interpretation (e.g., the allocation per process or the available after accounting for allocations), I can present an exact numerical step-by-step table showing Available after each finish and verify the safety with explicit numbers.

Entities:- The basic object that the ER model represent is an entity, which is a thing in the real world with an independent existence. An entity may be an object with a physical existence (for example, a particular person, car, house or employees) or it may be an object with a conceptual existence (for example, a company, a job or a university course).

Attribute: Each entity has attributes - the particular properties they describe it. For example, an employee entity may be described by the name, age, address, salary, and job. A particular entity will have a value for each of its attributes. The attributes values they describe each entity become a major part of data stored in the database. Sid Pin

Attributes:- Composite Verse Simple (Atomic) Attribute: Composite attribution can be divided into smaller subparts, which represent more basic attributes with independent meanings. For example, the address of the employee entity can be subdivided into street address, city, state, and zip. Attributes that are not divisible are simple or atomic attributes.

<br> Single-value versus Multi-valued Attributes:- Most Attributes have a single value for a particular entity such attributes are called single-valued. For example, age is a single-valued attribute of a person. One may not have a college degree another person may have one, and a third person may have two or more degrees, therefore ody different person can have different numbers of values for the college degree attributes. Such attributes are called multi valued. <br> Stored versus Derived Attributes:- In some cases, two(or more) attribute value are related-for example, the age and Birth-date attributes of a person. For a particular entity, the value of age can be determined the current (today's) date and the value of hc that person Birth date. The age attribute is hence called a derived attribute and is said to be derivable from the Birth date attribute, which is called a stored attribute. Jue نامه sill NULL Value:- In some cases, a particular entity may not have an applicable value for heye) cattribute. A college\_degree attributes applies only to person with college degrees. For much situation a special value called NULL is created.

Complex Attributes:- we can represent arbitrary nesting by grouping component of a composite attribute between parentheses and separating the components with commas and by displaying multi-valued attributes braces. Such attributes are called complex attributes. For example, if a person can have more than one residence and each residence can have a single address and multiple phones.) (Composite + Multivalued). {}- Multivalued ()- Composite {(Composite), (Composite) Degree of Relationship Sets :- Degree of a Relationship set refers to the number of Entity Sets participating in the Relationship. Most of the relationships are binary. Relationship

Topic: ER model ER Notation

Double Rectangle Indicate weak entity set

Double Diamond Indicates a relationship set with the partition of some weak entity sets Dashed Ellipse Indicates Derived attribute Notes: Multivalued Attribute is enclosed in {) and composite attribute is enclosed in

<br> <br> Relationship Relationship Degree:- The degree of relationship type is number of participating entity types. A relationship type of degree two is Known as binary, and one of degree three is called ternary. We can also say that number of entities participating in the relation. Cardinality Ratios for Binary Relationship: The cardinality ratio for the binary relationship specifies the maximum numbers of relationship instance that an entity can participate in/The possible cardinality ratios for binary relationship types are 1:1, 1:Ν, Μ:Ν.

Relationship Constraints :- Mapping Cardinalities Participation Cardinalities Mapping Cardinalities (No of 2 Ls Dutt ما Combinee One-to-One:- An entity in A is associated with at most one entity in B and an entity in Bispl associated with at most one entity in A. It is represented in ER as follows :-

1. One-to-Many:- One to many cardinality from A to B implies than entity in A is associated with any number(Nil/one/many) of entities in B. however, an entity in B is associated with at most one entity in A-ER representation is as follows:
2. Many-to-One:- Many to one cardinality from A to B implies that an entity in A is associated with at most one entity in B; however, one entity in B can be associated with any number of entities in A. It is represented in ER model as follows:-
3. Many-to-Many:- Many to many cardinality from A to B implies that an entity A can be associated with any number of entities in B and one entity in B can be associated with any number of entities in A. It is represented in ER model as follows:

Example :- One-to-one relationship from CUSTOMER to ACCOUNT implies each customer can have only one account and each account has to be single.

One-to-Many relationship from CUSTOMER to ACCOUNT implies that each customer can have any number (NIL or one or more than one) of accounts but each account has to single.

Many-to-one relationship from CUSTOMER to ACCOUNT implies that each customer can have only one accounts, but account can be join (held by one or more)

Many-to-Many relation from CUSTOMER to ACCOUNT implies that each customer can have any number (Nil or one or more than one) accounts and each account can be Joint (held by one or more)

Participation constraints in Relationship Sets a. Total Participation b. Partial Participation a. Total Participation:- An Entity Set E is said to have total participation in relationship set R if each entity in E is participating at least one relationship through R in ER diagram, the total participation is represented by a "Double Line" drawn between the entity set symbol and the relationship set symbol.

<br> "b. Partial Participation:- An Entity Set E is said to have partial participation in relationship set R if some of the entities in E are not participating in any relationship through R. In ER Diagram, the partial participation is represented by a "Single Line" drawn between Entity Set symbol and Relationship Set Symbol. <br> For Example:- Suppose Entity Sets "Customer "and "ACCOUNT" are released by Relationship Set "DEPOSITOR" and Entity Sets "CUSTOMER" and "LOAN" are related by Relationship Set "BORROWER". Suppose it is possible that a customer may have only account or only loan or both, then the situation can be modelled as follows :- <br> CUSTOMER Partial Participation BORROWER Total Participation LOAN DEPOSITOR Total Participation ACCOUNT Partial Participation

DPP.5 Participation constraints in Relationship Sets. Let me restate and analyze: - Entity set E and relationship R. - Total Participation: every entity in E is involved in at least one instance of R. - Partial Participation: some entities in E may not participate in any instance of R. - In E (the entity set labeled E), there is a mention that “In Partial Participation some entities in E may not be involved in any instances of R.” - Total Participation is denoted by a double line connecting the entity set symbol to the relationship set symbol.

Entity-Relationship (ER) diagram, an entity represents a real-world object or concept that can have a distinct and identifiable existence. This could be a person, place, thing, or event. It’s not a relationship (that would be a relationship type), nor is it a physical model itself. It can sometimes be tangible, but not all entities have physical existence (e.g., an abstract entity like “Order” or “Appointment” may not be a physical object).

Keys concepts: - Superkey: Any set of one or more attributes that uniquely identifies a tuple in a relation. - Candidate key: A minimal superkey (no subset of it can still uniquely identify tuples). - Minimal superkey is redundant term; typically “superkey” already encompasses non-minimal sets. - A attribute not part of any key is not a superkey by itself.

Weak and strong entity : - A weak entity does not have a primary key of its own. - It is dependent on a strong (owner) entity for its identification. - It typically participates in a total (mandatory) relationship with its owner entity. - It cannot exist without the owner entity.