DEV Community: Naga Saisriya

My experience with LGMSoC'21..

Naga Saisriya — Thu, 12 Aug 2021 14:09:49 +0000

My experience with Lets Grow More Summer of Code (Website: LGMSOC ) was awesome. It helped me to enhance my skills in the domain of web development and also expanded my knowledge on using Git and GitHub. Its really a good kickstart for someone who's new to open-source and I'd definitely recommend getting started with this. The mentors were really supportive and constantly cleared all the doubts. Overall, it was a great learning experience and I'd like to thank the organizers for coming up with such an amazing summer of code.

Operating Systems -Scheduling Algorithms Made Easy : SJF

Naga Saisriya — Sun, 27 Jun 2021 19:46:32 +0000

Introduction

Shortest Job First(SJF) supports both preemptive and non-preemptive scheduling. This algorithm associates with each process the length of the process’s next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie. Shortest Remaining time first(SRTF) is the Shortest Job First(SJF) scheduling algorithm in preemptive mode.

Explanation

The SJF scheduling algorithm is provably optimal, in that it gives the minimum average waiting time for a given set of processes. Moving a short process before a long one decreases the waiting time of the short process more than it increases the waiting time of the long process. Consequently, the average waiting time decreases.
In SRTF, the execution of the process can be stopped after certain amount of time. The short term scheduler schedules processes with least amount of burst time among available and running processes.
Once all the processes are available in the ready queue, No preemption will be done and the algorithm will work as SJF scheduling. The context of the process is saved in the Process Control Block when the process is removed from the execution and the next process is scheduled. This PCB is accessed on the next execution of this process.

Advantages:
- Maximum throughput
- SJF is optimal, gives minimum average waiting time for a set of processes.
- SRTF is faster in execution than SJF.
Disadvantages:
- In SJF, if there are more number of shorter jobs, then longer jobs starve.

Code

Non-preemptive SJF Scheduling

#include <stdio.h>
#include <string.h>

int main()
{
  struct SJF
  {
    char pn[100];
    int bt,wt,tat;
  }b[100];
  int sum1=0,sum2=0,i,j,temp,n;
  float avg1=0,avg2=0;
  char t1[100];
  printf("Enter number of processes:\n");
  scanf("%d",&n);
  printf("Enter process names and burst times:\n");
  for(i=0;i<n;i++)
  {
    scanf("%s",b[i].pn);
    scanf("%d",&b[i].bt);
  }
  for(j=0;j<n;j++)
  {
    for(i=0;i<n-1;i++)
    {
      if(b[i].bt>b[i+1].bt)
      {
        temp=b[i].bt;
        b[i].bt=b[i+1].bt;
        b[i+1].bt=temp;
        strcpy(t1,b[i].pn);
        strcpy(b[i].pn,b[i+1].pn);
        strcpy(b[i+1].pn,t1);
      }
    }
  }
  b[0].wt=0;
  for(i=0;i<n;i++)
    {
      b[i+1].wt=b[i].bt+b[i].wt;
      b[i].tat=b[i].wt+b[i].bt;
    }
  printf("PN\tBT\tWT\tTAT\n");
  for(i=0;i<n;i++)
    {
      sum1+=b[i].wt; 
      sum2+=b[i].tat;
      printf("%s\t%d\t%d\t%d\n",b[i].pn,b[i].bt,b[i].wt,b[i].tat);
    }
  avg1=(float)sum1/n;
  avg2=(float)sum2/n;
  printf("Average waiting time: %.2f\n",avg1);
  printf("Average turnaround time: %.2f\n",avg2);
  return 0;
}

Sample Input and Output

Input:

Enter number of processes:

4

Enter process names and burst times:

P1 6

P2 8

P3 7 

P4 3

Output:

PN  BT  WT  TAT

P4  3   0   3

P1  6   3   9

P3  7   9   16

P2  8   16  24

Average waiting time: 7.00

Average turnaround time: 13.00

SRTF: Preemptive SJF Scheduling:

#include<stdio.h>
#include<string.h>
void main()
{
    struct SJF
    {
        char pn[10];
        int bt,wt,tat,at;
    }b[100];
    int i,j,n,sum1=0,sum2=0,z=0,cnt=0;
    float avg1=0,avg2=0;
    printf("Enter the number of processes:\n");
    scanf("%d",&n);
    printf("Enter process names, burst times and arrival times:\n");
    for(i=1;i<=n;i++)
        scanf("%s %d %d",b[i].pn,&b[i].bt,&b[i].at);
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
        {
            if(b[i].at>b[j].at)
            {

                int t=b[i].bt;
                b[i].bt=b[j].bt;
                b[j].bt=t;
                char temp[10];
                strcpy(temp,b[i].pn);
                strcpy(b[i].pn,b[j].pn);
                strcpy(b[j].pn,temp);
                t=b[i].at;
                b[i].at=b[j].at;
                b[j].at=t;
            }
        }
    }
    char temp[10];
    for(i=1;i<=n;i++)
    {
        cnt+=b[i].bt;
        for(j=i+1;j<=n;j++)
        {
            if(b[i+1].at<=cnt && b[i+1].bt>b[j].bt && b[j].at<=cnt)
            {
                //swap burst times
               int t=b[i+1].bt;
                b[i+1].bt=b[j].bt;
                b[j].bt=t;
                //swap process names
                strcpy(temp,b[i+1].pn);
                strcpy(b[i+1].pn,b[j].pn);
                strcpy(b[j].pn,temp);
                //swap arrival times
                t=b[i+1].at;
                b[i+1].at=b[j].at;
                b[j].at=t; 
            }
        }
    }
    b[1].wt=0;
    for(i=1;i<=n;i++)
    {
        b[i+1].wt=b[i].wt+b[i].bt+b[i].at-b[i+1].at;
        b[i].tat=b[i].wt+b[i].bt;
    }
    printf("PN\tBT\tAT\tWT\tTAT\n");
    for(i=1;i<=n;i++)
    {
        sum1=sum1+b[i].wt;
        sum2=sum2+b[i].tat;
        printf("%s\t%d\t%d\t%d\t%d\n",b[i].pn,b[i].bt,b[i].at,b[i].wt,b[i].tat);
    }
    avg1=(float)sum1/n;
    printf("Average waiting time: %.2f\n",avg1);
    avg2=(float)sum2/n;
    printf("Average turnaround time: %.2f\n",avg2);
}

Sample Input and Output

Input:

Enter the number of processes:

4

Enter process names, burst times and arrival times:

P1 8 0

P2 4 1

P3 9 2

P4 5 3

Output:

PN  BT  AT  WT  TAT

P1  8   0   0   8

P2  4   1   7   11

P4  5   3   9   14

P3  9   2   15  24

Average waiting time: 7.75

Average turnaround time: 14.25

Complexity Analysis

Time Complexity:
- Best Case : O(n)
- Average Case : O(n²)
- Worst Case : O(n²)
Space Complexity : O(1)

Operating Systems -Scheduling Algorithms Made Easy : FCFS

Naga Saisriya — Fri, 14 May 2021 13:40:21 +0000

Introduction

First come first served (FCFS) is the simplest operating system scheduling algorithm which supports both preemptive and non-preemptive scheduling, implemented with a FIFO queue. It automatically executes queued requests and processes them by order of their arrival,the processes which requests the CPU first get the CPU allocation first.

Explanation

First in first out (FIFO) simply queues processes in the order that they arrive in the ready queue. For managing the tasks, as the processes come they are kept at the end of the queue. As CPU finishes each task, it removes it from the start of the queue and heads onto the next task.

From the above Gantt chart, if the processes arrive in the order P1,P2,P3, and are served in FCFS order,we get the result shown above. The waiting time is 0 milliseconds for process P1, 24 milliseconds for process P2, and 27 milliseconds for process P3. Thus, the average waiting time is (0+ 24 + 27)/3 = 17 milliseconds.
Advantage:
- The code for FCFS scheduling is simple to write and understand.
Disadvantages:
- The process will run to the completion and there are high chances of starvation, as it is non preemtive.
- There is a convoy effect as all the other processes wait for the one big process to get off the CPU. This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.
- It is poor in performance since the average waiting time is higher as compared to other scheduling algorithms.

Algorithm

Non-preemptive scheduling without arrival time:

Firstly, take inputs as number of processes n, processes pn, and burst times bt.
Find the waiting time wt for all processes.
The first process has no waiting time so waiting time for process 1 will be 0 i.e. wt[0] = 0.
Find waiting time for all other processes i.e. for
- process i -> wt[i] = bt[i-1] + wt[i-1] .
Calculate the turnaround time, it is given as tat= wt + bt for all processes.
- Compute sum of waiting time and turnaround times,
  - Sum of waiting time, sum1 = sum1 + wt[i]
  - Sum of turnaround time, sum2 = sum2 + tat[i]
- Calculate average waiting time, avg1 = sum1 / n.
- Similarly, find average turnaround time, avg2 = sum2 / n.

Code

This is my code implemented in C++



#include <iostream>

using namespace std;

int main ()

{

    struct fcfs

    {

        int pn[100];

        int bt, wt, tat;

    } b[100];

    int sum1 = 0, sum2 = 0, i, n;

    float avg1 = 0, avg2 = 0;

    printf ("Enter number of processes:\n");

    scanf ("%d", &n);

    printf ("Enter processes and burst times:\n");

    for (i = 0; i < n; i++)

    {

        scanf ("%d", b[i].pn);

        scanf ("%d", &b[i].bt);

    }

    b[0].wt = 0;

    for (i = 0; i < n; i++)

    {

        b[i + 1].wt = b[i].bt + b[i].wt;

        b[i].tat = b[i].wt + b[i].bt;

<span class="p">}</span>
<span class="c1">//display all processes and details</span>
<span class="n">printf</span> <span class="p">(</span><span class="s">"PN</span><span class="se">\t</span><span class="s">BT</span><span class="se">\t</span><span class="s">WT</span><span class="se">\t</span><span class="s">TAT</span><span class="se">\n</span><span class="s">"</span><span class="p">);</span>
<span class="k">for</span> <span class="p">(</span><span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
<span class="p">{</span>
    <span class="c1">//compute sum of waiting time and turnaround time</span>
    <span class="n">sum1</span> <span class="o">+=</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">wt</span><span class="p">;</span>
    <span class="n">sum2</span> <span class="o">+=</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">tat</span><span class="p">;</span>
    <span class="n">printf</span> <span class="p">(</span><span class="s">"%d</span><span class="se">\t</span><span class="s">%d</span><span class="se">\t</span><span class="s">%d</span><span class="se">\t</span><span class="s">%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="o">*</span><span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">pn</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">bt</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">wt</span><span class="p">,</span> <span class="n">b</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">tat</span><span class="p">);</span>
<span class="p">}</span>
<span class="c1">// calculate average waiting time and turnaround time</span>
<span class="n">avg1</span> <span class="o">=</span> <span class="p">(</span><span class="kt">float</span><span class="p">)</span> <span class="n">sum1</span> <span class="o">/</span> <span class="n">n</span><span class="p">;</span>
<span class="n">avg2</span> <span class="o">=</span> <span class="p">(</span><span class="kt">float</span><span class="p">)</span> <span class="n">sum2</span> <span class="o">/</span> <span class="n">n</span><span class="p">;</span>
<span class="n">printf</span> <span class="p">(</span><span class="s">"Average waiting time = %.2f</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">avg1</span><span class="p">);</span>
<span class="n">printf</span> <span class="p">(</span><span class="s">"Average turnaround time = %.2f</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">avg2</span><span class="p">);</span>
<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>



}

Sample Input and Output

Input:



Enter number of processes:


3


Enter processes and burst times:


1 24


2 3


3 3

Output:



PN      BT      WT      TAT


1       24      0       24


2       3       24      27


3       3       27      30


Average waiting time = 17.00


Average turn around time = 27.00

Complexity Analysis

Time Complexity:
- Best Case : O(n)
- Average Case : O(n²)
- Worst Case : O(n²)
Space Complexity : O(1)

5 Easy LeetCode questions to start competitive-coding

Naga Saisriya — Sat, 08 May 2021 16:46:17 +0000

These are 5 LeetCode questions which boost my confidence to start competitive programming and there can be many easy ones out, but I started with these. I provided my Python solutions to the problems, these solutions can be optimized too, just sharing my approach :)

1. FizzBuzz

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        l=[]
        for i in range(1,n+1):
            if i%3==0 and i%5==0:
                l.append("FizzBuzz")
            elif i%3==0:
                l.append("Fizz")
            elif i%5==0:
                l.append("Buzz")
            else:
                l.append(str(i))
        return l

2. Single Number

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return 2*sum(set(nums))-sum(nums)

3. Intersection of two arrays

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return set(nums1).intersection(set(nums2))

4. Fibonacci Number

class Solution:
    def fib(self, n: int) -> int:
        m=0
        if n==0:
            return 0
        elif n==1:
            return 1
        else:
            m=self.fib(n-1)+self.fib(n-2)
            return m

5. Array Partition-I

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

Just make sure to start your journey no matter if you're a beginner or pro. I just started off and I can definitely feel the difference, be it in my problem-solving ways or maintaining consistency. Hope this article helps!!