An Operating system is like an interface for users and hardware. It is a sort of manager which manages multiple applications. Whether you are headshoting someone on Valorant or making your own programming language you are actually interacting with the OS. But why do we need OS, main reasons being Resource Allocation, Protection, and of course, abstraction. We do not need an OS for a lift, because it has just one functionality, but we do need an OS for a PC due to the complex tasks we expect a PC to perform. These are the types of Operating Systems based on the functionality the OS provide:

1. Single Tasking: MS-DOS(Only one task) These are very inefficient. The main reason being that the CPU is very fast compared to IO devices and processes which need an IO device may hold the queue up for other processes and keep the CPU idle.
2. Multiprogramming and Multitasking: Yeah, here is the solution to the above problem. In this we do not wait for the process to completely execute, we just unassign the process when it is doing some IO process and in meanwhile assign some other process. Multitasking is different from multiprogramming as, In multitasking, we assign a small fixed time in which processes execute and change their turn. It is more responsive than multiprogramming because we do not wait for a process indefinitely. It's just the same concept as Round Robin Scheduling.
3. Multithreading: It's a kind of advancement in Multiprogramming. Here we have multiple threads running in an interleaved fashion inside a process. The foremost advantage is the increased responsiveness of the CPU. Consider MS word, the tool you use to make those assignments. Here one thread is formatting the content and some other, taking input from you. These two are threads involved in just typing some shit in MS word. A thread is the smallest unit assignable to the CPU. Also, we saw that we switch between processes in multitasking, and switching involved a cost. But this cost is less in thread switching compared to process switching. We would see this in context switching.
4. Multiprocessing: While buying a laptop on these Diwali sales(if you are in India), you might have noticed processors and with more processors increases the price. We have Quad Core in 30-45K INR and Octa-Core processors at 50K+ price. Our laptop uses more than one processor and distributes processes among different processors. This obviously boosts the laptop's speed.
5. Multi-User: Earlier versions of windows didn't have support for multiple users but Linux always had this support.

Text: Stores the compiled program code.

Data: stores global and static variables

Heap: Stores dynamically allocated data

Stack: Stores local variables.

1. Process State: We already saw these

2. Process ID: self-explanatory

3. CPU registers and Program Counter: It is basically a pointer to the next instruction to be executed.

4. CPU scheduling information: priority and pointers to scheduling queues(will see later)

5. Memory management information: self-explanatory

6. Accounting Information: CPU time consumed, limits, etc.

7. I/o Status information: Devices allocated, open file tables, etc.

Please note that we are not actually studying scheduling algorithms, we are just assuming that we have some given order and how the processes are executed.

1. Long-term Schedulers: These are responsible for sending a process from new to ready queue. It has to maintain a degree of multiprogramming which is simply this: Average rate of incoming = average rate of outgoing.

2. Short-term schedulers/ CPU schedulers: From the ready queue to the running queue. (I think it's clear)

3. Midterm schedulers: These are special types of schedulers with a unique functionality: when a process is paused(maybe it needs some input) it, swaps in the process and allocates this position to some other process and when it arrives again, swaps out the other process and resume the previous process.

It's quite obvious actually. We, programmers, do multitasking a lot, from Sublime to codeforces to youtube to CounterStrike to Chrome Incognito. We do a lot. But these are independent processes(maybe connected but on a high level, they are independent) But processes that are interconnected and have to use some other process information to execute need to have IPC.

1) Shared Memory: Kind of a buffer between two processes. One important thing to note is that under normal circumstances, processes restrict their memory, i.e., you cannot access the memory of a process. That's why we have shared memory, where we don't have such restrictions.

2) Message passing: Kind of a queue for sharing information(See the below diagram). The main difference between the two is that here we don't actually share the same address space which is why it can be used with different computers over a network.

Arrival Time: Time at which process arrives in ready queue

Completion Time: Time at which the process completes its execution.

Burst Time: Time required by the process for CPU execution

Turn-Around Time: Time difference between completion and arrival time. (How it's different from burst time?)(Add waiting time here as well)

Waiting Time: Turnaround time-burst time.

Throughput: Total number of processes completed per unit time.

Non-preemptive Algorithms: Once a process is in the ready queue we cannot pause its execution until it's completely executed.

Preemptive Algorithms: Opposite of non-preemptive. Period.

Widely used in college admissions, this algorithm is just what it says. Whichever process arrives first, it will execute the process first and then jump to the second process. (Non-preemptive Algorithm)

This Gantt diagram will help you understand FCFS:

Just sort the jobs according to their burst times. And we schedule the jobs according to that order only. It is a non-preemptive algorithm but there does exist a preemptive algorithm for SJS as well.

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main()
{
    int n;cin>>n;
    vector<pair<int,int>> times(n);
    vector<pair<int,int>> duration(n);
    // vector<Time>a;
    for(int i=0;i<n;i++)
    {
        cin>>times[i].first>>times[i].second;
        duration[i].second=i;
        duration[i].first=times[i].second-times[i].first;
    }

    sort(duration.begin(),duration.end());

    // Order of jobs is the duration.second order
    // Now we need to find turnaround time, waiting time and
    // Completion time for every process
    int total_waiting_time=0;
    int total_turnaround_time=0;
    int t=0;
    for(int i=0;i<n;i++)
    {
        cout<<"Process "<<duration[i].second+1<<" in ready queue now!\n";
        t=max(times[duration[i].second].first,t);
        t+=duration[i].first;
        int turnaround_time=t-times[duration[i].second].first;
        total_turnaround_time+=turnaround_time;
        cout<<"Turn Around Time: "<<turnaround_time<<"\n";
        int waiting_time=turnaround_time-duration[i].first;
        total_waiting_time+=waiting_time;
        cout<<"Waiting Time: "<<waiting_time<<"\n";
    }
    double avg_turnaround_time=(double)total_turnaround_time/n;
    double avg_waiting_time=(double)total_waiting_time/n;
    cout<<"Average Waiting Time: "<<avg_waiting_time<<"\n";
    cout<<"Average Turn Around Time: "<<avg_turnaround_time<<"\n";


    return 0;
}

This Gantt diagram will help you understand SJS:

It has a preemptive way also. In this, the trick is to fill those gaps which we were making. Whenever we are idle, we assign the computer another process that can be filled.

To be updated

This Gantt diagram will help you understand the preemptive version of SJS:

In this algorithm, we have fixed time slots and we execute the processes sequentially in the order given and switch between processes after every fixed time. This Gantt diagram will help you understand:

1. Independent Process: Execution of one process does not affect the execution of other processes.

2. Cooperative Process: The execution of one process affects the execution of other processes.

Suppose we have two operations, cnt++ and cnt--, from two different processes acting on a global variable cnt.

++ Operation :

int reg=cnt;
reg=reg-1;
cnt=reg;

-- Operation:

int reg2=cnt;
reg2=reg2-1;
cnt=reg2;

Now, we need to do this operation in this order:

int reg=cnt;
reg=reg-1;
cnt=reg;
int reg2=cnt;
reg2=reg2-1;
cnt=reg2;

But as the resource is shared, it can happen in any order, maybe this one as well:

int reg=cnt;
reg=reg-1;
int reg2=cnt;
cnt=reg;
reg2=reg2-1;
cnt=reg2;

This will lead to cnt's final value as 4 if the initial value is 5.

1. Mutual Exclusion: If a process is executing in its critical section, then no other process is allowed to execute in the critical section.

2. Progress: If no process is executing in the critical section and other processes are waiting outside the critical section, then only those processes that are not executing in their remainder section can participate in deciding which will enter in the critical section next, and the selection can not be postponed indefinitely. Woah, that's a bummer. Okay, it's simply that the process which does not want to execute the critical section should not be allowed to block the system for others.

3. Bounded Waiting: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

int turn;
bool flag[2];
do{
    flag[i]=1;
    turn=j;
    while(flag[j]&&turn==j);
    /////////////////////
    // Critical section//
    /////////////////////
    flag[i]=0;
    ///////////////////////
    // Remainder section///
    ///////////////////////

}
while(1)

Before actually seeing how it works, please have another look at the things we want it to satisfy. These 3 rules:

1. Mutual exclusion
2. Progress
3. Bounded Waiting

Peterson solution simply assigns a turn and a flag to each process. Initially, flag is 0 in all processes and the turn is either 0 or 1. Flag array's on the index means that this process is waiting for its turn now. And would work only if the initial process has completed its execution. We have the while loop for this in the code. Please have a look at the code now and if you still find any difficulty, please post in the comments.

Shared data: semaphore mutex// Initially mutex=1
Process p[i]:
do{
   wait(mutex);
   ////////////////////////
   ////critical section////
   ////////////////////////
   signal(mutex);
   ////////////////////////
   ////remainder section///
   ////////////////////////
}while(1);

Whenever a process arrives we wait for the semaphore to turn to 1. Initially, the semaphore is 1 already so Process P1 has no wait and executes the critical section. But if the second process comes now, the wait function runs a while loop which kind of halts the process. Now when the first process finishes, the second process continues, and so on.

Unbounded Wait time is the main problem here.

What we do is simple to achieve bounded wait time. We are currently holding suppose n processes due to 1 process which is running. We simply can just block the processes which are in waiting. Like, we can contain them in a list. Okay, to be very honest, I truly don't understand how blocking the processes makes them bounded. Would update this when I find this. Please write on comments if you know this.

(You would only understand if you have seen Dhamaal)

1. Mutual Exclusion: One resource can't be shared between different processes.
2. Hold and Wait: A process is holding a resource and waiting for another resource.
3. No Preemptive process: A process only releases the resource when its work is done completely.
4. Cycle Wait: There should be a cycle wait, like P0 waiting for P1 to complete execution, P1 for P2, and P2 for P0.

1. Mutual Exclusion: Suppose the resource is a mouse. Now we know that a mouse can't be used by more than one process. So, we can do nothing about it. The same is the case for printers, keyboards, etc. So, we can see that it is very difficult to overcome this condition

2. Hold and Wait: This can be avoided. The problem here is that we wait for a process and hold other processes, so what we can do is that we would start a process only if we have assigned every resource it needs to it initially. But this is not practically possible. First of all, you can't really have a list of all resources required at the start of the process, it is only available at the runtime. Secondly, even if you have such a list, suppose the process would work for 10 hours, and a printer is needed at the end of the process. Here starvation of resources occurs, you are occupying printer for 10 hours straight, but you don't need it for 9 hrs!

3. No Preemptive processes: Here what we can do is that if a process needs a resource, we just snatch this particular resource from whatever process it was working for and assign it to the current process. Obviously, it is also not practical, as suppose you are using a printer and your half-page was printed, but then suddenly another process prints something else. There would be a lot of inconsistency of data.

1. No circular wait: This can be actually avoided. You can give priorities to resources and One process can only request to those resources whose priorities are greater than the one assigned to it. For example, we have four resources, R1, R2, R3, R4 having priorities as 1,2,3,4, and four processes P1, P2, P3, and P4.

R1->P1 (R1 is assigned to P1)

R2->P2

R3->P3

R4->P4

Now P1 can only request R2, R3, and R4. And P2 can request R3 and R4 and so on. As you would have realized, there can be no cycle here.

Consider a music player: one thread is playing the music and the other is shuffling the songs for you. This is how a process in memory looks like:

Before going to the comment section for complaining about a wrong image, these stacks are actually different. A process is nothing but a program in execution but why do we have multiple stacks in one process? Each thread has its own stack for functioning and that's why threads are lightweight and easy to create and destroy. They share the same heap, data, and code.

Advantages

1. Faster to create/ terminate
2. Multiple threads share the same address space, thus making them easier to communicate. And due to this, context switching is also easier.
3. Lightweight

Disadvantages

1. Difficult to test and debug
2. Can lead to Deadlocks and Race Conditions.