# GATE Questions & Answers of Operating System Computer Science and Information Technology

#### Operating System 91 Question(s) | Weightage 11 (Marks)

The following are some events that occur after a device controller issues an interrupt while process L is under execution.

(P) The processor pushes the process status of L onto the control stack.
(Q) The processor finishes the execution of the current instruction.
(R) The processor executes the interrupt service routine.
(S) The processor pops the process status of L from the control stack.
(T) The processor loads the new PC value based on the interrupt.

Which one of the following is the correct order in which the events above occur ?

Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units.
Which one of the following is the correct expression for the page fault rate experienced by the process?

Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and released only one at a time. The largest value of K that will always avoid deadlock is ____.

In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P2,F] is the maximum number of instances of F that P2 would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation.

Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available.

 Allocation E F G P0 1 0 1 P1 1 1 2 P2 1 0 3 P3 2 0 0
 Max E F G P0 4 3 1 P1 2 1 4 P2 1 3 3 P3 5 4 1

From the perspective of deadlock avoidance, which one of the following is true?

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective initial values of 0, N and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal().
 Producer: Consumer: do{     wait(P);     wait(mutex);     //Add item to buffer     signal(mutex);     signal(Q); }while(1); do{      wait(R);      wait(mutex);      //Consume item from buffer      signal(mutex);      signal(S); }while(1);

Which one of the following assignments to P, Q, R and S will yield the correct solution?

Considrer the following CPU processes with arrival times (in miliseconds) and length of CPU bursts (in miliseconds) as given below:

 Process Arrival time Burst time P1 0 7 P2 3 3 P3 5 5 P4 6 2

If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is _________ milliseconds.

A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes avilable. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

Recall that Belady's anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the folliowing statments:

S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady's anomaly

S2: LUR page replacement algorithm sufferes from Belady's anomaly

Which of the following is CORRECT

Which of the following is/are shared by all the threads in a process?

I. Program counter

II. Stack

IV. Registers

In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed?

I. Contiguos

III. Indexed

A system shares 9 tape drives. The current allocation and maximum requirment of tape drives for three processes are shown below:

 Process Current Allocation Maximum Requirment P1 3 7 P2 1 6 P3 3 5

which of the following best describes current state of the system?

Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds) , and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.

 Process Arrival time Burst Time Priority P1 0 11 2 P2 5 28 0 P3 12 2 3 P4 2 10 1 P5 9 16 4

The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is _____________.

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires 48 bits, then the size of the per-process page table is ___________ megabytes.

Consider a computer system with ten physical page frames. The system is provided with an access sequence $\left(a_1,\;a_2,...,a_{20},\;a_1,\;a_2,...a_{20}\right),$ where each $a_i$ is a distinct virtual page number. The difference in the number of page faults between the last-in-first-out page replacement policy and the optimal page replacement policy is __________.

Consider the following proposed solution for the critical section problem. There are $n$ processes: $P_0\;...\;P_{n-1}\;.$ In the code, function pmax returns an integer not smaller than any of its arguments. For all $i$, t[i] is initialized to zero.

Code for $P_i:$
do {
c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0;
for every j≠i
in {0,...,n-1} {

while (c[j]);
while (t[j] != 0 && t[j]<=t[i]);
}
Critical Section;
t[i]=0;
Remainder Section;
} while (true);

Which one of the following is TRUE about the above solution?

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time first.

Process Arrival Time Burst Time
$P_1$ 0 10
$P_2$ 3 6
$P_3$ 7 1
$P_4$ 8 3

The average turn around time of these processes is milliseconds ________.

Consider the following two-process synchronization solution.
 Process 0 Process 1 --------- ---------- Entry: loop while (turn == 1); Entry: loop while (turn == 0); (critical section) (critical section) Exit: turn = 1; Exit: turn = 0;

The shared variable turn is initialized to zero. Which one of the following is TRUE?

Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is ______.

Consider a system with byte-addressable memory, 32-bit logical addresses, 4 kilobyte page size and page table entries of 4 bytes each. The size of the page table in the system in megabytes is ______.

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

 P1(){     C=B-1;     B=2*c; } P2(){      D=2*B;      B=D-1; }

The number of distinct values that B can possibly take after the execution is__________.

A variable x is said to be live at a statement Si in a program if the following three conditions hold simultaneously:
i. There exists a statement Sj that uses x
ii. There is a path from Si to Sj in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at Si and Sj

The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are

Consider a uniprocessor system executing three tasks T1, T2 and T3, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period, and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of T1, T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st millisecond and task preemptions are allowed, the first instance of T3 completes its execution at the end of ______ milliseconds.

Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the following is true with respect to page replacement policies First In First Out(FIFO) and Least Recently Used(LRU)?

Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that 80% of the processor’s read requests result in a cache hit. The average read access time in nanoseconds is ______.

A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is _______.

A system has 6 identical resources and N processes competing for them. Each process can request atmost 2 resources. Which one of the following values of N could lead to a deadlock?

Identify the correct order in which a server process must invoke the function calls accept, bind, listen, and recv according to UNIX socket APL.

Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?

A computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 magabytes, the length of the virtual address supported by the system is _______ bits.

The maximum number of processes that can be in Ready state for a computer system with n CPUs is

Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes

 Process X /* other code for process X */ while(true) {     varP=true;     while(varQ==true)          {          /* Critical Section */                 varP=false;           } } /* other code for process X*/ Process Y /* other code for process Y */ while(true) {     varQ=true;     while(varP==true)          {          /* Critical Section */                 varQ=false;           } } /* other code for process Y */

Here, varP and varQ are shared variables and both are initialized to false. Which one of the following statements is true?

Consider the following policies for preventing deadlock in a system with mutually exclusive resources.

1. Processes should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released
2. The resources are numbered uniquely, and processes are allowed to request for resources only in increasing resource numbers
3. The resources are numbered uniquely, and processes are allowed to request for resources only in decreasing resource numbers
4. The resources are numbered uniquely. A process is allowed to request only for a resource with resource number larger than its currently held resources

Which of the above policies can be used for preventing deadlock?

Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and n × n respectively, where Assume that in both code segments, elements of Y are initialized to 0 and each element X[i][j] of array X is initialized to i+j. Further assume that when stored in main memory all elements of X are in same main memory page frame.

Code segment 1:
//initialize elements of Y to 0
//initialize elements X[i] [j] of X to i+j
for (i = 0; i < n; i++)
Y[i] += X[0] [i];

Code segment 2:
//initialize elements of Y to 0
//initialize elements X[i] [j] of X to i+j
for (i = 0; i < n; i++)
Y[i] += X[i] [0];

Which of the following statements is/are correct?

S1:Final contents of array Y will be same in both code segments
S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory
S3:Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory

For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?

 Process Arrival Time Processing Time A 0 3 B 1 6 C 4 4 D 6 2

Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.

Which one of the following is FALSE?

An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.

There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:
REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z
REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z

Which one of the following is TRUE?

Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.

 Process Name Arrival Time Execution Time A 0 6 B 3 2 C 5 4 D 7 6 E 10 3

Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ____________________.

Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100 x 106 bytes disk on which the file system is stored and data block size is 103 bytes, the maximum size of a file that can be stored on this disk in units of 106 bytes is ____________.

Consider the procedure below for the Producer-Consumer problem which uses semaphores:

 semaphore n = 0; semaphore s = 1; void producer() {     while(true)    {      produce();      semWait(s);      addToBuffer();      semSignal(s);      semSignal(n);    } } void consumer() {   while(true)   {     semWait(s);     semWait(n);     removeFromBuffer();     semSignal(s);     consume();   } }

Which one of the following is TRUE?

Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires tc CPU milliseconds and then initiates a single I/O operation that lasts for tio milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS of the computer assigns different I/O devices to each process. Also, the scheduling overhead of the OS is negligible. The processes have the following characteristics:

 Process id tc tio A 100 ms 500 ms B 350 ms 500 ms C 200 ms 500 ms

The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.

A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?

4, 7, 6, 1, 7, 6, 1, 2, 7, 2

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):

The average waiting time (in milliseconds) of the processes is _________.

Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.

A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?

A certain computation generates two arrays a and b such that a[i]=f(i) for 0 ≤ i < n and b[i] = g (a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below.

 Process X: private i; for (i=0; i

Which one of the following represents the CORRECT implementations of ExitX and EntryY?

A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.
What is the size of a page in KB in this computer?

A computer uses 46-bit virtual address, 32-bit physical address, and a three-level paged page table organization. The page table base register stores the base address of the first-level table (T1), which occupies exactly one page. Each entry of T1 stores the base address of a page of the second-level table (T2). Each entry of T2 stores the base address of a page of the third-level table (T3). Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor used in the computer has a 1 MB 16-way set associative virtually indexed physically tagged cache. The cache block size is 64 bytes.

What is the minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?

A process executes the code

fork();
fork();
fork();

The total number of child processes created is

Consider the 3 processes, P1, P2 and P3 shown in the table.

 Process Arrival time Time Units Required P1 0 5 P2 1 7 P3 3 4

The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are

Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.

AcquireLock(L){
L = 1;
}
ReleaseLock(L){
L = 0;
}

This implementation

Consider the virtual page reference string

1, 2, 3, 2, 4, 1, 3, 2, 4, 1

on a demand paged virtual memory system running on a computer system that has main memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL denote the number of page faults under the corresponding page replacement policy. Then

Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to switch between two processes be t2. Which of the following is TRUE?

A computer handles several interrupt sources of which the following are relevant for this question.

• Interrupt from CPU temperature sensor (raises interrupt if CPU temperature is too high)

• Interrupt from Mouse (raises interrupt if the mouse is moved or a button is pressed)

• Interrupt from Keyboard (raises interrupt when a key is pressed or released)

• Interrupt from Hard Disk (raises interrupt when a disk read is completed)

Which one of these will be handled at the HIGHEST priority?

A thread is usually defined as a "light weight process" because an operating system (OS) maintains smaller data structures for a thread than for a process. In relation to this, which of the following is TRUE?

Let the page fault service time be 10 ms in a computer with average memory access time being 20 ns. If one page fault is generated for every 106 memory accesses, what is the effective access time for the memory?

Consider the following table of arrival time and burst time for three processes P0, P1 and P2.

 Process Arrival time Burst Time P0 0 ms 9 ms P1 1 ms 4 ms P2 2 ms 9 ms

The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?

The seek time of the disk to a random location is given as 10 ms. Rotational speed of disk is 6000 rpm. lf all 100 libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data from the disk block once the head has been positioned at the start of the block may be neglected.)

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared Boolean variables S1 and S2 are randomly assigned.

 Method used by PI Method used by P2 while (S1 = = S2) ; Critical Section S1 = S2; while (S1 != S2) ;  Critical section  S2 = not (S1);

Which one of the following statements describes the properties achieved?

A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?

Which of the following statements are true?
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.

 Process P0 Process P1 Process P2 while (true) {     wait (S0);     print ‘0’     release (S1);     release (S2);  } wait (S1);  Release (S0); wait (S2);  release (S0);

How many times will process P0 print ‘0’?

A system has n resources R0Rn-1, and k processes P0Pk-1. The implementation of the resourcerequest logic of each process Pi. is as follows:
if (i%2==0) {
if (i<n) request Ri ;
if (i+2 < n)request Ri+2 ;
}
else {
if (i<n) request Rn-i ;
if (i+2<n)request Rn-i-2 ;
}

In which one of the following situations is a deadlock possible?

In which one of the following page replacement policies, Belady’s anomaly may occur?

The essential content(s) in each entry of a page table is/are

Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive resource allocation policy is used. At any given instance, a request is not entertained if it cannot be completely satisfied. Three processes P1, P2, P3 request the sources as follows if executed independently.

 Process P1: t=0: requests 2 units of R2 t=1: requests 1 unit of R3 t=3: requests 2 units of R1 t=5: releases 1 unit of R2        and 1 unit of R1. t=7: releases 1 unit of R3 t=8: requests 2 units of R4 t=10: Finishes Process P2: t=0: requests 2 units of R3 t=2: requests 1 unit of R4 t=4: requests 1 unit of R1 t=6: releases 1 unit of R3 t=8: Finishes Process P3: t=0: requests 1 unit of R4 t=2: requests 2 units of R1 t=5: releases 2 units of R1 t=7: requests 1 unit of R2 t=8: requests 1 unit of R3 t=9: Finishes

Which one of the following statements is TRUE if all three processes run concurrently starting at time t=0?

In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state:

Now consider the following statements:

I. If a process makes a transition D, it would result in another process making transition A immediately.
II. A process P2 in blocked state can make transition E while another process P1 is in running state.
III. The OS uses preemptive scheduling.
IV. The OS uses non-preemptive scheduling.

Which of the above statements are TRUE?

The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:

void enter_CS(X)
{
while (test-and-set(X)) ;
}
void leave_CS(X)
{
X=0;
}

In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements:

I. The above solution to CS problem is deadlock-free
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV. More than one process can enter CS at the same time.

Which of the above statements are TRUE?

A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because

Which of the following system calls results in the sending of SYN packets?

The data blocks of a very large file in the Unix file system are allocated using

The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:
P(s) : s = s - 1;
if s < 0 then wait;
V(s) : s = s + 1;
if s <= 0 then wakeup a process waiting on s;
Assume that Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores xb and yb are used to implement the semaphore operations P(s) and V(s) as follows:

P(s) : Pb (xb);
s = s -1;
if (s < 0) {
Vb (xb);
Pb (yb);
}
else Vb (xb);
V(s) : Pb (xb);
s = s + 1;
if (s <=0) Vb (yb);
Vb (xb);

The initial values of xb and yb are respectively