Operating System | Critical Section

Critical Section:

In simple terms a critical section is group of instructions/statements or region of code that need to be executed atomically, such as accessing a resource (file, input or output port, global data, etc.).

In concurrent programming, if one thread tries to change the value of shared data at the same time as another thread tries to read the value (i.e. data race across threads), the result is unpredictable.

The access to such shared variable (shared memory, shared files, shared port, etc…) to be synchronized. Few programming languages have built in support for synchronization.

It is critical to understand the importance of race condition while writing kernel mode programming (a device driver, kernel thread, etc.). since the programmer can directly access and modifying kernel data structures.

A simple solution to critical section can be thought as shown below,

acquireLock();
Process Critical Section
releaseLock();

A thread must acquire a lock prior to executing critical section. The lock can be acquired by only one thread. There are various ways to implement locks in the above pseudo code.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Operating System | Process Management | CPU Scheduling

Scheduling of processes/work is done to finish the work on time.

Below are different time with respect to a process.

Arrival Time:       Time at which the process arrives in the ready queue.
Completion Time:    Time at which process completes its execution.
Burst Time:         Time required by a process for CPU execution.
Turn Around Time:   Time Difference between completion time and arrival time.          
     Turn Around Time = Completion Time - Arrival Time
Waiting Time(W.T): Time Difference between turn around time and burst time.
     Waiting Time = Turn Around Time - Burst Time

Why do we need scheduling?
A typical process involves both I/O time and CPU time. In a uniprogramming system like MS-DOS, time spent waiting for I/O is wasted and CPU is free during this time. In multiprogramming systems, one process can use CPU while another is waiting for I/O. This is possible only with process scheduling.

Objectives of Process Scheduling Algorithm

Max CPU utilization [Keep CPU as busy as possible]
Fair allocation of CPU.
Max throughput [Number of processes that complete their execution per time unit]
Min turnaround time [Time taken by a process to finish execution]
Min waiting time [Time a process waits in ready queue]
Min response time [Time when a process produces first response]

Different Scheduling Algorithms

First Come First Serve (FCFS): Simplest scheduling algorithm that schedules according to arrival times of processes.

Shortest Job First(SJF): Process which have the shortest burst time are scheduled first.

Shortest Remaining Time First(SRTF): It is preemptive mode of SJF algorithm in which jobs are schedule according to shortest remaining time.

Round Robin Scheduling: Each process is assigned a fixed time in cyclic way.

Priority Based scheduling (Non Preemptive): In this scheduling, processes are scheduled according to their priorities, i.e., highest priority process is schedule first. If priorities of two processes match, then schedule according to arrival time.

Highest Response Ratio Next (HRRN) In this scheduling, processes with highest response ratio is scheduled. This algorithm avoids starvation.

Response Ratio = (Waiting Time + Burst time) / Burst time

Multilevel Queue Scheduling: According to the priority of process, processes are placed in the different queues. Generally high priority process are placed in the top level queue. Only after completion of processes from top level queue, lower level queued processes are scheduled.

Multi level Feedback Queue Scheduling: It allows the process to move in between queues. The idea is to separate processes according to the characteristics of their CPU bursts. If a process uses too much CPU time, it is moved to a lower-priority queue.

Some useful facts about Scheduling Algorithms:
1) FCFS can cause long waiting times, especially when the first job takes too much CPU time.

2) Both SJF and Shortest Remaining time first algorithms may cause starvation. Consider a situation when long process is there in ready queue and shorter processes keep coming.

3) If time quantum for Round Robin scheduling is very large, then it behaves same as FCFS scheduling.

4) SJF is optimal in terms of average waiting time for a given set of processes,i.e., average waiting time is minimum with this scheduling, but problems is, how to know/predict time of next job.

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Operating System | Process Scheduler

There are three types of process scheduler.

1. Long Term or job scheduler It bring the new process to the ‘Ready State’. It controls Degree of Multi-programming, i.e., number of process present in ready state at any point of time.

2. Short term ot CPU scheduler: It is responsible for selecting one process from ready state for scheduling it on the running state. Note: Short term scheduler only selects the process to schedule it doesn’t load the process on running.
Dispatcher is responsible for loading the selected process by Short Term scheduler on the CPU (Ready to Running State) Context switching is done by dispatcher only. A dispatcher does following:
1) Switching context.
2) Switching to user mode.
3) Jumping to the proper location in the newly loaded program.

3. Medium term scheduler It is responsible for suspending and resuming the process. It mainly does swapping (moving processes from main memory to disk and vice versa).

We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Storage for Strings in C

In C, a string can be referred either using a character pointer or as a character array.

Strings as character arrays

char str[4] = "TcB"; /*One extra for string terminator*/
/*    OR    */
char str[4] = {‘T’, ‘c’, ‘B’, '\0'}; /* '\0' is string terminator */

When strings are declared as character arrays, they are stored like other types of arrays in C. For example, if str[] is an auto variable then string is stored in stack segment, if it’s a global or static variable then stored in data segment, etc.

Strings using character pointers
Using character pointer strings can be stored in two ways:

1) Read only string in a shared segment.
When string value is directly assigned to a pointer, in most of the compilers, it’s stored in a read only block (generally in data segment) that is shared among functions.

char *str  =  "TcB"

In the above line “GfG” is stored in a shared read only location, but pointer str is stored in a read-write memory. You can change str to point something else but cannot change value at present str. So this kind of string should only be used when we don’t want to modify string at a later stage in program.

2) Dynamically allocated in heap segment.
Strings are stored like other dynamically allocated things in C and can be shared among functions.

char *str;
int size = 4; /*one extra for ‘\0’*/
str = (char *)malloc(sizeof(char)*size);
*(str+0) = 'T';
*(str+1) = 'c'
*(str+2) = 'B'
*(str+3) = '\0'

Let us see some examples to better understand above ways to store strings.

Example 1 (Try to modify string) 
The below program may crash (gives segmentation fault error) because the line *(str+1) = ‘n’ tries to write a read only memory.

int main()
{
 char *str;
 str = "TcB";     /* Stored in read only part of data segment */
 *(str+1) = 'n'; /* Problem:  trying to modify read only memory */
 getchar();
 return 0;
}

Below program works perfectly fine as str[] is stored in writable stack segment.

int main()
{
 char str[] = "TcB"/* Stored in stack segment like other auto variables */
 *(str+1) = 'n';   /* No problem: String is now TnB */
 getchar();
 return 0;
}

Below program also works perfectly fine as data at str is stored in writable heap segment.

   
int main()
{
  int size = 4;
  /* Stored in heap segment like other dynamically allocated things */
  char *str = (char *)malloc(sizeof(char)*size);
  *(str+0) = 'T';
  *(str+1) = 'c'
  *(str+2) = 'B';   
  *(str+3) = '\0'
  *(str+1) = 'n'/* No problem: String is now TnB */
   getchar();
   return 0;

Example 2 (Try to return string from a function)
The below program works perfectly fine as the string is stored in a shared segment and data stored remains there even after return of getString()

char *getString()
{
  char *str = "TcB"; /* Stored in read only part of shared segment */
  /* No problem: remains at address str after getString() returns*/
  return str; 
}    
int main()
{
  printf("%s", getString()); 
  getchar();
  return 0;
}

The below program alse works perfectly fine as the string is stored in heap segment and data stored in heap segment persists even after return of getString()

char *getString()
{
  int size = 4;
  char *str = (char *)malloc(sizeof(char)*size); /*Stored in heap segment*/
  *(str+0) = 'T';
  *(str+1) = 'c'
  *(str+2) = 'B';
  *(str+3) = '\0'
  
  /* No problem: string remains at str after getString() returns */
  return str; 
}    
int main()
{
  printf("%s", getString()); 
  getchar();
  return 0;
}

But, the below program may print some garbage data as string is stored in stack frame of function getString() and data may not be there after getString() returns.

char*getString()
{
  charstr[] = "TcB"; /* Stored in stack segment */
  /* Problem: string may not be present after getSting() returns */
  returnstr;
}    
intmain()
{
  printf("%s", getString()); 
  getchar();
  return0;
}

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:https://www.geeksforgeeks.org/storage-for-strings-in-c/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

C++ string class and its applications

In C++ we can store string by one of the two ways –

  1. C style strings
  2. string class (discussed in this post)

In this post, second method is discussed. string class is part of C++ library that supports a lot much functionality over C style strings.
C++ string class internally uses char array to store character but all memory management, allocation and null termination is handled by string class itself that is why it is easy to use. The length of c++ string can be changed at runtime because of dynamic allocation of memory similar to vectors. As string class is a container class, we can iterate over all its characters using an iterator similar to other containers like vector, set and maps, but generally we use a simple for loop for iterating over the characters and index them using [] operator.
C++ string class has a lot of functions to handle string easily. Most useful of them are demonstrated in below code.

// C++ program to demonstrate various function string class
#include <bits/stdc++.h>
using namespace std;
int main()
{
    // various constructor of string class
    // initialization by raw string
    string str1("first string");
    // initialization by another string
    string str2(str1);
    // initialization by character with number of occurence
    string str3(5, '#');
    // initialization by part of another string
    string str4(str1, 6, 6); // from 6th index (second parameter)
                             // 6 characters (third parameter)
    // initialization by part of another string : iteartor version
    string str5(str2.begin(), str2.begin() + 5);
    cout << str1 << endl;
    cout << str2 << endl;
    cout << str3 << endl;
    cout << str4 << endl;
    cout << str5 << endl;
    //  assignment operator
    string str6 = str4;
    // clear function deletes all character from string
    str4.clear();
    //  both size() and length() return length of string and
    //  they work as synonyms
    int len = str6.length(); // Same as "len = str6.size();"
    cout << "Length of string is : " << len << endl;
    // a particular character can be accessed using at /
    // [] operator
    char ch = str6.at(2); //  Same as "ch = str6[2];"
    cout << "third character of string is : " << ch << endl;
    //  front return first character and back returns last charcter
    //  of string
    char ch_f = str6.front();  // Same as "ch_f = str6[0];"
    char ch_b = str6.back();   // Same as below
                               // "ch_b = str6[str6.length() - 1];"
    cout << "First char is : " << ch_f << ", Last char is : "
         << ch_b << endl;
    // c_str returns null terminated char array version of string
    const char* charstr = str6.c_str();
    printf("%s\n", charstr);
    // append add the argument string at the end
    str6.append(" extension");
    //  same as str6 += " extension"
    // another version of appends, which appends part of other
    // string
    str4.append(str6, 0, 6);  // at 0th position 6 character
    cout << str6 << endl;
    cout << str4 << endl;
    //  find returns index where pattern is found.
    //  If pattern is not there it returns predefined
    //  constant npos whose value is -1
    if (str6.find(str4) != string::npos)
        cout << "str4 found in str6 at " << str6.find(str4)
             << " pos" << endl;
    else
        cout << "str4 not found in str6" << endl;
    //  substr(a, b) function returns a substring of b length
    //  starting from index a
    cout << str6.substr(7, 3) << endl;
    //  if second argument is not passed, string till end is
    // taken as substring
    cout << str6.substr(7) << endl;
    //  erase(a, b) deletes b character at index a
    str6.erase(7, 4);
    cout << str6 << endl;
    //  iterator version of erase
    str6.erase(str6.begin() + 5, str6.end() - 3);
    cout << str6 << endl;
    str6 = "This is a examples";
    //  replace(a, b, str)  replaces b character from a index by str
    str6.replace(2, 7, "ese are test");
    cout << str6 << endl;
    return 0;
}

Output :

first string
first string
#####
string
first
Length of string is : 6
third character of string is : r
First char is : s, Last char is : g
string
string extension
string
str4 found in str6 at 0 pos
ext
extension
string nsion
strinion
These are test examples

As seen in above code, we can get length of string by size() as well as length() but length() is preferred for strings. We can concat a string to another string by += or by append(), but += is slightly slower than append() because each time + is called a new string (creation of new buffer) is made which is returned that is a bit overhead in case of many append operation.

Applications :
On basis of above string function some application are written below :

// C++ program to demonstrate uses of some string function
#include <bits/stdc++.h>
using namespace std;
// this function returns floating point part of a number-string
string returnFloatingPart(string str)
{
    int pos = str.find(".");
    if (pos == string::npos)
        return "";
    else
        return str.substr(pos + 1);
}
// this function checks whether string contains all digit or not
bool containsOnlyDigit(string str)
{
    int l = str.length();
    for (int i = 0; i < l; i++)
    {
        if (str.at(i) < '0' || str.at(i) > '9')
            return false;
    }
    //  if we reach here all character are digits
    return true;
}
// this function replaces all single space by %20
// Used in URLS
string replaceBlankWith20(string str)
{
    string replaceby = "%20";
    int n = 0;
    // loop till all space are replaced
    while ((n = str.find(" ", n)) != string::npos )
    {
        str.replace(n, 1, replaceby);
        n += replaceby.length();
    }
    return str;
}
// driver function to check above methods
int main()
{
    string fnum = "23.342";
    cout << "Floating part is : " << returnFloatingPart(fnum)
         << endl;
    string num = "3452";
    if (containsOnlyDigit(num))
        cout << "string contains only digit" << endl;
    string urlex = "google com in";
    cout << replaceBlankWith20(urlex) << endl;
    return 0;     
}

Output :

Floating part is : 342
string contains only digit
google%20com%20in

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:https://www.geeksforgeeks.org/c-string-class-and-its-applications/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

ispunct() function in C

The ispunct() function checks whether a character is a punctuation character or not.
The term “punctuation” as defined by this function includes all printable characters that are neither alphanumeric nor a space. For example ‘@’, ‘$’, etc.
This function is defined in ctype.h header file.

syntax:

int ispunct(int ch);
ch: character to be checked.
Return Value  : function return nonzero
 if character is a punctuation character;
 otherwise zero is returned. 
// Program to check punctuation
#include <stdio.h>
#include <ctype.h>
int main()
{
    // The puncuations in str are '!' and ','
    char str[] = "welcome! to TechCodeBit, ";
    int i = 0, count = 0;
    while (str[i]) {
        if (ispunct(str[i]))
            count++;
        i++;
    }
    printf("Sentence contains %d punctuation"
           " characters.\n", count);
    return 0;
}

Output:

Sentence contains 2 punctuation characters.
// C program to print all Punctuations
#include <stdio.h>
#include <ctype.h>
int main()
{
    int i;
    printf("All punctuation characters in C"
            " programming are: \n");
    for (i = 0; i <= 255; ++i)
        if (ispunct(i) != 0)
            printf("%c ", i);
    return 0;
}

Output:

All punctuation characters in C programming are: 
! " # $ % & ' ( ) * +, - . / : ;  ? @ [ \ ] ^ _ ` { | } ~

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:https://www.geeksforgeeks.org/ispunct-function-c/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

strspn() function in C

The strspn() function returns the length of the initial substring of the string pointed to by str1 that is made up of only those character contained in the string pointed to by str2.

Syntax :

size_t strspn(const char *str1, const char *str2)
str1 : string to be scanned.
str2 : string containing the 
characters to match.
Return Value : This function
returns the number of characters
in the initial segment of str1 
which consist only of characters 
from str2.
// C program to illustrate strspn() function
#include <stdio.h>
#include <string.h>
int main () {
   int len = strspn("tech code tech",tech");
   printf("Length of initial segment matching : %d\n", len );   
   return(0);
}

Output:

Length of initial segment matching 4
// C program to illustrate strspn() function
#include <stdio.h>
#include <string.h>
int main () {
   int len = strspn("i am","xyz");
   printf("Length of initial segment matching : %d\n", len );
   return(0);
}

Output:

Length of initial segment matching 0

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:https://www.geeksforgeeks.org/strspn-function-c/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

strcspn() in C

The C library function strcspn() calculates the length of the number of characters before the 1st occurrence of character present in both the string.
Syntax :

strcspn(const char *str1, const char *str2)

Parameters:
str1 : The Target string in which search has to be made.
str2 : Argument string containing characters
to match in target string.

Return Value:
This function returns the number of characters before the 1st occurrence
of character present in both the string.
// C code to demonstrate the working of
// strcspn()
#include <stdio.h>
#include <string.h>
int main()
{
    int size;
    // initializing strings
    char str1[] = "geeksforgeeks";
    char str2[] = "kfc";
    // using strcspn() to calculate initial chars
    // before 1st matching chars.
    // returns 3
    size = strcspn(str1, str2);
    printf("The unmatched characters before first matched character :  %d\n", size);
}

Output:

The unmatched characters before first matched character :  3

Practical Application : There can be many practical application of this function, be itword games or irregularity calculator. A simple word game is demonstrated in this article.

Rules : According to this game, 2 players play and one player initially generated a string and is asked to produce a string which has as many unmatched characters. After 1 round, player producing string with maximum unmatched characters wins.

// C code to demonstrate the application of
// strcspn()
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int score1 = 0, score2 = 0, k = 0, sizen = 0, size = 0;
    // initial Round1 strings
    char player1[] = "geeks";
    char play2[] = "";
    while (1) {
        // generating random character
        char randoml = 'a' + (random() % 26);
        play2[k++] = randoml;
        size = strcspn(play2, player1);
        if (size == sizen) {
            // if the character is present, break
            score2 = size;
            break;
        }
        else {
            sizen = size;
        }
    }
    // initial Round2 strings
    const char player2[] = "geeks";
    char play1[] = "";
    k = 0, sizen = 0;
    while (1) {
        // generating random character
        char randoml = 'a' + (random() % 26);
        play1[k++] = randoml;
        size = strcspn(play1, player2);
        if (size == sizen)
{
            // if the character is present, break
            score1 = size;
            break;
        }
        else {
            sizen = size;
        }
    }
    if (score1 > score2)
        printf("Player 1 won!! Score : %d", score1);
    else if (score2 > score1)
        printf("Player 2 won!! Score : %d", score2);
    else
        printf("Match Drawn!! Score : %d", score1);
}

Output:

Match Drawn!! Score : 2

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:https://www.geeksforgeeks.org/strcspn-in-c/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Modulus on Negative Numbers

What will be the output of the following C program?

#include <stdio.h>
int main()
{
   int a = 3, b = -8, c = 2;
   printf("%d", a % b / c);
   return 0;
}

Output

1

% and / have same precedence and left to right associativity. So % is performed first which results in 3 and / is performed next resulting in 1. The emphasis is, sign of left operand is appended to result in case of modulus operator in C.

#include <stdio.h>
int main()
{
   // a positive and b negative.
   int a = 3, b = -8;
   printf("%d", a % b);
   return 0;
}

Output

-3
#include <stdio.h>
int main()
{
   // a negative and b positive
   int a = -3, b = 8;
   printf("%d", a % b);
   return 0;
}

Output

3
#include <stdio.h>
int main()
{
   // a and b both negative
   int a = -3, b = -8;
   printf("%d", a % b);
   return 0;
}

Output

-3

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:https://www.geeksforgeeks.org/modulus-on-negative-numbers/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

Precedence of postfix ++ and prefix ++ in C/C++

In C/C++, precedence of Prefix ++ (or Prefix –) and dereference (*) operators is same, and precedence of Postfix ++ (or Postfix –) is higher than both Prefix ++ and *.

If p is a pointer then *p++ is equivalent to *(p++) and ++*p is equivalent to ++(*p) (both Prefix ++ and * are right associative).

For example, program 1 prints ‘h’ and program 2 prints ‘e’.

// Program 1
#include<stdio.h>
int main()
{
  char arr[] = "techcodebit";
  char *p = arr;
  ++*p;
  printf(" %c", *p);
  getchar();
  return 0;
}

Output: u

// Program 2
#include<stdio.h>
int main()
{
  char arr[] = "techcodebit";
  char *p = arr;
  *p++;
  printf(" %c", *p);
  getchar();
  return 0;
}

Output: s

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:https://www.geeksforgeeks.org/g-fact-59/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide