Comer (XINU) Algorithm Examples

1. Consider disk arm scheduling algorithms. Assume that the disk has 200 cylinders numbered 0...199. The request queue is 10, 15, 9, 20, 40, 2. How will the queue look like after adding 23 and 45.

Try to find two requests R1 and R2 such that the head will pass the new request on its way from R1 to R2. If there exists two requests like that squeeze the new request in between. If there exists no such requests add new request to the end of the queue

23 can be squeezed in between 20 and 40.
Queue is 10,15, 9, 20, 23, 40, 2

45 cannot be squeezed in since there is no Request(i) such that 45 is in between Request(i)and Request(i-1). So add 45 to the end of the queue.

Queue is updated to 10,15, 9, 20, 23, 40, 2, 45

2. Disk requests arrive in the order 26, 79, 96, 27, 8 . In what order will XINU algorithms service the requests above.

26
26,79 - added to the end
26,79,96 - added to the end
26, 27, 79, 96 - 27 is squeezed in.
26, 27, 79, 96, 8 - 8 is added in the end.

3. Disk requests arrive in the order 50, 100, 75, 25, 125 . In what order will XINU algorithms service the requests above.

50
50,100 - added to the end
50, 75, 100 - 75 is squeezed in
50, 75, 100, 25 -25 is added to the end, but this will force redirection
50, 75, 100, 25, 125 - added to the end

4. When is XINU better than LOOK.
Consider block numbers 50, 60,40,100

XINU : head movement = 10+ 20+60 = 90
LOOK : order of processing is 50, 60, 100, 40
head movement = 10+ 40+ 60 = 110
Here XINU is better than LOOK
Since XINU will force redirection after processing 60 to process 40 overall head movement is less than LOOK.

shortest seek time first (SSTF) java source code

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.Math;



public class Main {


public static void main(String[] args) {


ArrayList list = new ArrayList();


BufferedReader dataIn = new BufferedReader(new
InputStreamReader( System.in) );


//read current head position
String w = "";
System.out.println("Position of head currently :");
try{
w = dataIn.readLine();
}catch( IOException e ){
System.out.println("Error!");
}
int head = Integer.parseInt(w);
int initialhead = head;


// Read service requests
while(true){
try{
System.out.println("Enter next service request.Enter z to end the requests.");
w = dataIn.readLine();

if(w.equals("z"))
break;
int temp = Integer.parseInt(w);
list.add(temp);
}catch( IOException e ){
System.out.println("Error!");
}

}


ArrayList service_order = new ArrayList();//adds requests in order of the service

int number_of_orders = list.size();
for(int i=0; i &ltnumber_of_orders;i++){
Iterator it = list.iterator();
int min = 0;
int temp=0;
int min_distance=200;

while(it.hasNext()){
temp = (Integer)it.next();
int distance = Math.abs(head-temp);
System.out.println(head +" "+ temp+" " + distance );

if(distance < min_distance){
min = temp;
min_distance = distance;
}

}

list.remove((Integer)min);
head = min;
System.out.println(" Next request "+ min);
service_order.add(min);


}

Iterator min_it = service_order.iterator();

System.out.print("Service Order: ");

while(min_it.hasNext()){
System.out.print(min_it.next()+" ");
}
int total_head_movement=0;
min_it = service_order.iterator();
total_head_movement = Math.abs(initialhead - (Integer)service_order.get(0));
for(int i =1;i < service_order.size();i++){
total_head_movement += Math.abs((Integer)service_order.get(i) - (Integer)service_order.get(i-1));
}
System.out.println();

System.out.println("Total head movement: "+ total_head_movement);
}

}




Deepcopy of a string in c

Process Synchronization Examples

The following Java code samples describe two Lock classes with two methods
each: acquire() and release(). You can assume that the application calls lock.acquire()
before entering a critical section and lock.release() after exiting the critical section. For the
implementations that require a tid (i.e., thread id), you can assume that the tid of each thread is
either 0 or 1.

class LockA { private int turn = 0; public void acquire(int tid) { while (turn == (1 - tid)); } public void release(int tid) { turn = (1 - tid); } }

class LockB { public void acquire() { disableInterrupts(); } public void release() { enableInterrupts(); } }

For each lock, answer the following three questions. Be sure that your answers clearly indicate
whether you are referring to LockA or LockB.
(a) Does the code guarantee mutual exclusion? (Simply answer yes or no)
(b) Does the code guarantee progress? (Simply answer yes or no)
(c) List all other limitations that exist for each implementation. Issues you might consider
include (but are not limited to) the following: generality, efficiency, and fairness. (Note: You
can skip this part of the quetion when the implementation fails to provide mutual exclusion
or progress.)

Answer
LockA (a) Yes, guarantees mutual exclusion; only the thread with tid matching turn is able to
acquire the lock. (b) No, does not guarantee progress; if thread 0 never tries to acquire the lock
(it is executing other code), thread 1 will not be able to acquire the lock. (c) Limitations (Not
required): Only works with two processes, uses busy waiting.
LockB (a) Guarantees mutual exclusion on a uniprocessor, but not on a multiprocessor. On a
uniprocessor, once the timer interrupt is disabled, the scheduler won’t be able to switch to another
process (assuming the scheduled process doesn’t voluntarily relinquish the CPU). However, on
a multiprocessor, it is possible for the other CPU to be running a process that also acquires the
lock. (b) Yes, guarantees progress; once a process is scheduled, it is able to acquire the lock without
incident. (c) Limitations: Only works on uniprocessors; allows user processes to disable interrupts
for an arbitrary long period; cannot service other important interrupts during critical section (e.g.,
I/O); cannot schedule any other processes when lock is held, even those not contending for the
lock.
Also answer the following general question: Locks are often implemented by maintaining a list of processes (or threads) that are waiting to acquire the lock. What are all of the advantages of this approach (compared to a correct implementation of a lock that does not use a list)?
fairness and efficiency. Fairness comes from the fact that the queue can provide the lock to the
processes in the order they request it. Efficiency comes from the elimination of the spin lock, and
reliance on a notification mechanism to wake-up a process.

_______________________________________________________________

Suppose two processes compete for access to a critical section using simple spin locks. Prior to entering the critical section, the process executes the following:
while (TAS(t)); and after exiting the critical section it executes t=1.
(a) Suppose a priority scheduler where high priority processes always execute before any
lower priority processes. Can the described scheme lead to deadlock? If no, why not. If yes,
describe a case.
Yes, deadlock is possible. If a low priority process acquires the lock. Then a high priority
process starts, gets the processor and requests the lock. The high priority process will keep
the processor, spinning on the lock that the low priority process is holding. Because the low
priority process cannot get the processor, it cannot release the lock, and we have a deadlock
scenario.
(b) Suppose a round robin scheduler. Can the described scheme lead to deadlock? If no, why not. If yes, describe a case.
No, deadlock is not possible. A round robin, preemptive scheduler will alternate among
processes, so every process will have a chance to execute, and eventually the holding process
will release the lock.
_______________________________________________________________
Fix the following code to avoid the possible deadlock:

acquire(L1) acquire(L2) release(L2) release(L1)

acquire(L2) acquire(L1) release(L1) release(L2)

Answer
You could have changed this many ways. One possibility is to remove circular wait and
make both processes acquire the resources in the same order. Another possibility is to remove
hold-and-wait and have the processes release the first resource before they acquire another.
Although this changes the semantics of the program, I accepted it as a solution.
----------------------------------------------------------------------------------------------------------
Suppose a program has three threads Thread1, Thread2, and Thread3, and a
shared counter, count, as shown below:
int count = 10;
Semaphore Lock = 1; // initial value is 1

Thread1(...) { // do something Lock.Wait(); count++; Lock.Signal(); }

Thread2(...) { // do something Lock.Wait(); count−−; Lock.Signal(); }

Thread3(...) { // do something Lock.Wait(); printf(‘‘$d’’, count); Lock.Signal(); }

(a) What are the possible outputs of this program?

9, 10, 11
_______________________________________________________________________________________________

Consider a system with two preemptively scheduled threads. One thread executes the WriteA function
shown below. The other executes the WriteB function, also shown below. Both functions use kprintf
to produce console output. The random function called by WriteA returns a randomly-generated nonnegative
integer. WriteA and WriteB are synchronized using two semaphores, Sa and Sb. The intial
value of both semaphores is zero. Assume that the individual calls to kprintf are atomic.

WriteA() { unsigned int n,i; while(1) { n = random(); for(i=0;i<n;i++){ kprintf(‘‘A’’); } for(i=0;i<n;i++) { V(Sb); } for(i=0;i<n;i++) { P(Sa); } }

WriteB() { while(1) { P(Sb); kprintf(‘‘B’’); V(Sa); } }

a.
Consider the following 10-character console output prefixes. (Each prefix shows the first 10 characters
printed to the console.) Which of these prefixes could possibly be generated by the two
threads running in this system? Write “YES” next to the output prefix if it could be generated,
otherwise write “NO”.
• ABABABABAB YES
• BABABABABA NO
• AAAAAAAAAA YES
• AAABABABAB NO
• AAABBBBAAB NO
• AAAAAABBBB YES
• AAABBBAABB YES
• BBBBBAAAAB NO
b.
Suppose that the initial value of semaphore Sb is 1, rather than 0. Show a 10-character console
output prefix that could be generated in that case, and that could not be generated if the initial
value of Sb were 0.
Some examples:
• BABABABABA
• ABABBABABAB
• AAABBBABABB
__________________________________________________________________

Below is an attempted solution for producer- consumer problem. What problems can arise using this solution?
Buffer size = N
int count = 0;

consumer: while(true){ if(count==0) sleep( ); //remove from buffer count--; if(count ==N-1) wakeup(producer); consume(item) }

producer: while(true){ produce(item); if(count==N) sleep( ); //produce into buffer count++; if(count ==1) wakeup(consumer); consume(item) }

Answer:

• Consumer checks count==0
• before going to sleep consumer is preempted
• Producer increments count to 1
• producer wakes up consumer.
• since consumer is not sleeping yet, wakeup call is lost.
• Producer fills the buffers until count == N and goes to sleep
• Both processes are deadlocked.

___________________________________________________________________________________

Consider three concurrently executing threads in the same process using two semaphores
s1 and s2. Assume s1 has been initialized to 1, while s2 has been initialized to 0.
What are the possible values of the global variable x, initialized to 0, after all three threads have terminated?

/* thread A */ P(&s2); P(&s1); x = x*2; V(&s1);

/* thread B */ P(&s1); x = x*x; V(&s1);

/* thread C */ P(&s1); x = x+3; V(&s2); V(&s1);

The possible sequences are B,C,A (x = 6) or C,A,B (x = 36) or C,B,A (x = 18).
________________________________________________________________
We explore the so-called barbershop problem. A barbershop consists of a n waiting chairs
and the barber chair. If there are no customers, the barber waits. If a customer enters,
and all the waiting chairs are occupied, then the customer leaves the shop. If the barber
is busy, but waiting chairs are available, then the customer sits in one of the free chairs.
Here is the skeleton of the code, without synchronization.
extern int N; /* initialized elsewhere to value > 0 */
int customers = 0;
void* customer() {
if (customers > N) {
return NULL;
}
customers += 1;
getHairCut();
customers -= 1;
return NULL;
}
void* barber() {
while(1) {
cutHair();
}
}
13
For the solution, we use three binary semaphores:
• mutex to control access to the global variable customers.
• customer to signal a customer is in the shop.
• barber to signal the barber is busy.
1. (5 points) Indicate the initial values for the three semaphores.
• mutex
• customer
• barber
2. (15 points) Complete the code above filling in as many copies of the following commands
as you need, but no other code.
P(&mutex);
V(&mutex);
P(&customer);
V(&customer);
P(&barber);
V(&barber);

Solution: Initial values are mutex = 1 (variable customers may
be accessed), customer = 0 (no customers) and barber = 0 (barber is not busy).
void* customer() {
P(&mutex);
if (customers > N) {
V(&mutex);
return NULL;
}
customers += 1;
V(&mutex);
V(&customer);
P(&barber);
getHairCut();
P(&mutex);
customers -= 1;
V(&mutex);
return NULL;
}
void* barber() {
while(1) {
P(&customer);
V(&barber);
cutHair();
}
}
________________________________________________________________

Tasks T1 and T2 share the integer variables X, Y initially set to
0.
Task T1 executes:      | and T2 executes:
|
X := 0;        | Y := 0;
if X > 0 then  |        while Y < 2 do
X := X + 1; |    X := X - 1;
Y := 2;        | Y := 1;

What are the possible values of X and Y when these tasks
terminate?

T1:1 X=0
T2:1 y=0
T2:2 x=-1
T1:3 Y=2
T2:2 Y=1 

X =-1; Y=1  -----CONSIDER ALL POSSIBILITIES LIKE THESE EXAMPLES

______________________________________________________________________________

Process P executes:
A1: X := 1;
A2: Y := 1;
A3: Z := 2;
and process Q executes:
B1: X := 2;
B2: Y := 2;
What are the possible resulting values for X, Y, and Z?
For example, after the execution sequence A1 A2 A3 B1 B2
we obtain [x=2,y=2,z=2].
B1 A1 B2 A2 A3[x=1, y=1,Z=2]
try all combinations


In the same conditions as above, what should you do if you want
to guaranty that X, Y, Z finish with value, respectively, 1,
2, and 2?
You can change the order of A1, A2, A3; or the order of B1, B2;
or use semaphores; or use spinlocks.
Answer:
semaphore sem =0;
P1:                P2
wait(sem)          x=2
x=1                signal(sem)
y=1                wait(sem)
signal(sem)        y=2
Z=2

In the same conditions as above, what should you do if you want
that X and Y have both value 1 or both value 2?

For both x=1 and y=1

semaphore sem =0;
P1:                P2:
wait(sem)                
x=1                x=2
y=1                y=2
Z=2               signal(sem)


______________________________________________________________________________

http://pages.cs.wisc.edu/~bart/537/quizzes/quiz1.html

______________________________________________________________________________ 

Pumping Lemma Examples

Steps to solve Pumping Lemma problems:
1. If the language is finite, it is regular , otherwise it might be non-regular.
2. Consider the given language to be regular
3. State pumping lemma
4. Choose a string w from language, choose smartly .
5. Partition it according to constraints of pumping lemma in a generic way
6. Choose a pumping factor k such that the new ‘pumped’ string is not part of the language
given.
7. State the contradiction and end the proof.

How to remember what pumping Lemma says:

Pumping Lemma alternates between “for all” and “there is at least one” or “for every” or
“there exists”. Notice:
For every regular language L
There exists a constant n
For every string w in L such that |w| >= n,
There exists a way to break up w into three strings w = xyz such that |y| > 0 , |xy| <= n and For every k>=0 , the string xykz is also in L.

courtesey: http://suraj.lums.edu.pk/~cs311w05/pumping_lemma_writeup.pdf
1. Show that L2 = {0^m1^m | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L1. Consider any pumping number p; p≥ 1. Choose w = 0^p1^p.
Consider any pumping decomposition w = xyz;
|y| > 0 and |xy| ≤ p. It follows that x = 0^a and y = 0^b and z = 0^p-a-b1^p, for b ≥ 1. Choose i = 2. We need to show that xy²z = 0^p+b1^p is not in L1.

b ≥ 1.
So p+b > p
Hence 0^p+b1^p is not in L.

2. L2 = {xx | x ∈ {0, 1}*} is not regular.
We show that the pumping lemma does not hold for L2. Consider any pumping number
p ≥ 1. Choose w = 10^p10^p. Consider any pumping decomposition w = xyz; all we know about xyz is that
|y| > 0 and |xy| ≤ p. There are two possibilities:

(a) x = 10^aand y = 0^b and z = 0^p-a-b10^p, for b ≥ 1.
(a) x = " and y = 10b and z = 0^p-b10^p1.
Choose i = 2. We need to show that xy²z is not in L2.
In case (a), xy2z = 10^p+b10^p, which is not in L2 because b ≥ 1.
In case (b), xy2z = 10^b10^p10^p, which is not in L2 because it contains three 1’s.

3. We prove that L3 = {1ⁿ² | n ≥ 0} is not regular.

We show that the pumping lemma does not hold for L3. Consider any pumping number p ≥ 1.
Choose w = 1^p2.
Consider any pumping decomposition w = xyz such that |y| > 0 and |xy| ≤ p. It follows
that x = 1^a and y = 1^b and z = 1^p2
−a−b, for b ≥ 1 and a + b ≤ p. Choose i = 2. We need to show that
xy²z = 1^n2+b is not in L3; that is, we need to show that p2 + b is not a square. Since b ≥ 1, we have
p2 + b > p2. Since a + b ≤ p, we have p2 + b ≤ p2 + p < (p + 1)2 4.Prove that Language L = {0n: n is a perfect square} is irregular.

Solution: L is infinite. Suppose L is also regular. Then according to pumping lemma there exists an integer n such that for every string w in where |w| >= n, we can break w into three strings w = xyz such that:
|y| > 0 , |xy| <= n and for all k>=0 , the string xy^kz is also in L.
Choose w to be w = 0s where s = n² that is it is a perfect square.
Let w= 00000000000000000………00000 = xyz . (The length of w = s = n² in this case.)
Let |xy| <= n and |y| = k. That is w = 0000 0k 000… X y z So, |xyz| = |xz| + |y| = (n²- k ) + (k) From pumping lemma, I can pump y any number of times and the new string should also belong to the language. Suppose I pump y twice then, the new string should belong to the language that is it should have length that is a perfect square but, |xy2z| = |xz| + 2|y| = (n²- k ) + 2k = n² + k where n² + k < 1 =" (n+1)(n+1)"> n² (As k > 0)
=> n² <>2 + k < (n+1)2 => n² + k is not a perfect square
=> xy²z is not in L
=> This is a contradiction to the pumping lemma
So, our initial assumption must have been wrong that is L is not regular.

DFA Minimization Examples

1. Example 1
2. Example2
   

Regular Expressions

Describe the language denoted by the following regular expressions:

a) a(a|b)*a

The expression denotes the set of all strings of length two or more that start and end with an ‘a’.

b) ((e|a)b*)*

The expression denotes the set of all strings over the alphabet {a,b}.

c) (a|b)*a(a|b)(a|b)

The expression denotes the set of all strings of length 3 or more with an ‘a’ in the third position from the right. Ie of form yaxz where y is an arbitrary string , and x and z are single characters.

d) a*ba*ba*ba*

The expression denotes the set of all strings that contain precisely 3 b’s.

e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*

The expression denotes the set of all strings of even length.

automata quiz ( True or False)

True or False

1. In a finite language no string is pumpable. True
2. A DFA has infinite number of states. False
3. A DFA can have more than one accepting state. True
4. In DFA all states have same number of transitions. True
5. Every subset of a regular language is regular. False
6. Let L4 = L1L2L3. If L1 and L2 are regular and L3 is not regular, it is possible that L4 is regular. True
7. In a finite language no string is pumpable. True
8. If A is a nonregular language, then A must be infinite. True
9. Every context-free language has a context-free grammarin Chomsky normal form. True
10. If A is a context-free language, then A must be nonregular. False
11. The class of regular languages is closed under intersection. True
12. If a language A is regular, then it A must be finite. False
13. Every language is Turing-recognizable. False
14. If a language is context-free, then it must be Turing-decidable. True
15. The problem of determining if a context-free grammar generates
    the empty language is undecidable. False
16. The problem of determining if a Turing machine recognizes the
    empty language is undecidable. True
17. The set of all languages over an alphabet is countable.False
18. There are some languages recognized by a 5-tape, nondetermin-
    istic Turing machine that cannot be recognized by a 1-tape,
    deterministic Turing machine.False
    
19. The language { 0n1n | 0 ≤ n ≤ 1000 } is regular. True
20. Nonregular languages are recognized by NFAs. False
21. The class of context-free languages is closed under intersection. False
22. A language has a regular expression if and only if it
    has an NFA. True
23. The regular expression (01*0 ∪ 1)*0 generates the language
    consisting of all strings over {0, 1} having
    an odd number of 0’s. False
24. If a language A has a PDA, then A is generated by a
    context-free grammar in Chomsky normal form. True
25. If A is a context-free language and B is a language such that B is a subset of A, then B must be a context-free language. False
26. If a language A has an NFA, then A is nonregular. False
27. The regular expressions (a ∪ b)* and (b*a*)* generate the same language. True
28. If a language A has a regular expression, then it also has a context-free grammar. True
    
    

Recommended Books

Operating systems Exam Questions

What are two types of low-level operations that higher-level synchronization operations(e.g., semaphores and monitors) can be built upon?
test-and-set. compare-and-swap. atomic reads and writes. Other atomic operations. enabling
and disabling interrupts.
_______________________________________________________________
What is the difference between a process and a thread?
Every process has its own address space, but multiple threads inside a process share part of
the memory with their parent process. There is less context switching overhead to switch
among threads when compared to switching among threads.
_______________________________________________________________
What is the difference between deadlock and starvation?
In a deadlock situation, none of the involved processes can possibly make progress. In a
starvation situation, a process is ready to execute, but it is not being allowed to execute.
_______________________________________________________________
Suppose our computer system is running five processes (P1,P2,P3,--,P5 ) and has four
separate types of resources (A,B,C,D). We want to see if the system is in a safe state
using the Banker's algorithm. Using the following information about the state of the
system, determine if the state is safe: (11 points)
Total
AB C D
4 5 4 3

Available
AB C D
0 1 0 0

Maximum
A B C D
P1 1 3 3 0
P2 2 2 1 3
P3 1 1 0 1
P4 1 4 1 0
P5 3 1 2 1

Used
A B C D
P1 0 1 2 0
P2 2 0 1 1
P3 1 0 0 1
P4 0 3 1 0
P5 1 0 0 1

A B C D
Total 4 5 4 3

A B C D
Available 0 1 0 0

Total gives the number of instances of each resource in the system; Available gives the
number of unallocated instances of each resource; Maximum refers to the maximum
number of instances of each resource required by each process; Used refers to how many instances of each resource each process currently holds.

Answer:
The Need matrix is as follows:
Need
A B C D
P1 1 2 1 0
P2 0 2 0 2
P3 0 1 0 0
P4 1 1 0 0
P5 2 1 2 0

The state of the system is unsafe. Executing the Banker's algorithm terminates with P2
and P5 unable to complete. We give a possible sequence of execution with "Work" P3 runs (1, 1, 0, 1), P4 runs (1, 4, 1, 1),P1 runs (1, 5, 3, 1). Now neither P2
nor P5 can release its resources because each holds resources the other needs.
------------------------------------------------------------------------------------------------
2. A computer system has m resources of the same type and n processes share these
resources. Prove or disprove the following statement for the system:
This system is deadlock free if sum of all maximum needs of processes is less than m+n.

3. There are four processes which are going to share nine tape drives. Their current and
maximum number of allocation numbers are as follows :
process current maximum
p1 3 6
p2 1 2
p3 4 9
p4 0 2
a. Is the system in a safe state? Why or why not?
b. Is the system deadlocked? Why or why not?

Petersons solution and tries

A Process Using Mutual Exclusion:

int me;
while (1) {
/* non critical section code */
enter(me); /* also called entry code */
/* critical section code */
leave(me); /* also called exit code */
}

We assume each process has access to its process ID, which we're calling me in this example. The process can pass its ID into the enter() and leave() functions.
First try: use a lock.

shared int lock = 0;

void enter(int me)
{
while (lock == 1) /* do nothing */;
lock = 1;
}

void leave(int me)
{
lock = 0;
}


Problem: Process 0 can check that the lock is available, and then get preempted. Process 1 can now check the the lock is available, and enter the critical section. While in the critical section, it can be swapped out, and Process 0 restarted. Since Process 0 has already checked the availability of the lock, it can also enter the critical section. This "solution" fails to provide mutual exclusion.
Second try: take turns

shared int turn = 0;

void enter(int me)
{
while (turn != me);
}

void leave(int me)
{
turn = 1 - me;
}

Problem: If process 0 never attempts to enter the critical section, process 1 is never allowed to enter it (and, if 0 has entered once, it can never enter again until 1 endters). This "solution" fails to guarantee progress. Can you convince yourself it does in fact provide mutual exclusion (so it does meet some of the criteria, but not all)?
Third try: Keep track of whether the other guy wants in

shared int flag[2];

void enter(int me)
{
flag[me] = 1;
while (flag[1-me]);
}

void leave(int me)
flag[me] = 0;
}

Problem: Doesn't satisfy the progress condition. Both processes can get stuck in the entry code and wait there forever, in other words "deadlocked".

Fourth and last try:
(Peterson's Algorithm): combine second and third

The basic approach here is that we're going to keep track of both whether the other process wants in, and also whose turn it is. If the other process wants to get in, we'll let it in if it's its turn. But if it doesn't want in, we'll take its place.

shared int flag[2];
shared int turn;

void enter(int me)
{
flag[me] = 1;
turn = 1-me;
while (flag[1-me] && (turn == (1-me)));
}

void leave(int me)
{
flag[me] = 0;
}

This solution meets all of the requirements

CPU Scheduling Questions

This is an attempt to put together common CPU scheduling questions from various sources for the convenience of computer science students.


1. Consider N processes sharing the CPU in a round-robin fashion (N>=2). Assume that each context switch takes S msec and that each time quantum is Q msec. For simplicity, assume that processes never block on any event and simply switch between the CPU and the ready queue.
In the following your answers should be functions of N, S and T.
a) Find the maximum value of Q such that no process will ever go more than T msec

Time taken for one process per quantum = quantum,Q+context switch,S

Max wait time, T = N(Q+S)

T = NQ+NS

Q = (T-NS)/N
b) Find the maximum value of Q such that no process will ever go more than T msecs between executing instructions on the CPU?

Max wait time, T = N(Q+S) - Q ie.last instruction just before context switch executes at the end of the quantum of the first time when process executes..

T = NQ+NS-Q

T = Q(N-1)+NS

Q = (T-NS)/(N-1)

2. Suppose that there are two processes, PH and PL, running in a system. Each process is single-threaded. The operating system’s scheduler is preemptive and uses round-robin scheduling with a quantum of q time units.

The scheduler supports two priority levels, HIGH and LOW. Processes at LOW priority will run only if there are no runnable HIGH priority processes. Process PH is a HIGH priority process.
It behaves as described in the following pseudo-code:

while (TRUE) do
compute for tc time units
block for tb time units to wait for a resource
end while

That is, if this process were the only one running in the system, it would alternate between running for tc units of time and blocking for tb units of time. Assume that tc is less than q.
Process PL is a low priority process. This process runs forever, doing nothing but computation. That is, it never blocks waiting for a resource.

a. For what percentage of the time will the low priority process PL be running in this system?
Express your answer in terms of tb and tc.

tb/(tb + tc)


b. Repeat part (a), but this time under the assumption that there are two HIGH priority processes (PH1 and PH2) and one LOW priority process (PL). Assume that each HIGH priority process waits for a different resource. Again, express your answer in terms of tb and tc. Your answer should be correct for all tb greater than 0 and all 0 less than tc less than q.

(tb−tc)/(tb+tc) if tc is less than tb

0 if tc greater than or equal to tb
------------------------------------------------------------------------------------------------------------
Suppose a processor uses a prioritized round robin scheduling policy. New processes are assigned an initial quantum of length q. Whenever a process uses its entire quantum without blocking, its new quantum is set to twice its current quantum. If a process blocks before its quantum expires, its new quantum is reset to q. For the purposes of this question, assume that
every process requires a finite total amount of CPU time.
(a) Suppose the scheduler gives higher priority to processes that have larger quanta. Is starvation possible in this system? Why or why not?
No, starvation is not possible. Because we assume that a process will terminate, the worst
that can happen is that a CPU bound process will continue to execute until it completes.
When it finishes, one of the lower priority processes will execute. Because the I/O bound
processes will sit on the low priority queue, they will eventually make it to the head of the
queue and will not starve.
(b) Suppose instead that the scheduler gives higher priority to processes that have smaller quanta. Is starvation possible in this system? Why or why not?
Yes, starvation is possible. Suppose a CPU bound process runs on the processor, uses its
entire quantum, and has its quantum doubled. Suppose a steady stream of I/O bound processes
enter the system. Since they will always have a lower quantum and will be selected for
execution before the process with the doubled quantum, they will starve the original process.
_______________________________________________________________
I have just invented a new scheduling algorithm that I claim gives the highest
priority to processes that have just entered the system, but is fair to all processes. The algorithm works like this:
There are two queues, one for new processes and one for old processes. When a process enters the system, it is put at the end of the new queue. After 2 milliseconds on the new queue, whether a process has been scheduled or not, it is moved to the end of the old queue.
When it is time to schedule a process, the system schedules the process at the head of one of the queues, alternating between the two queues. Each process runs to completion before the next process is scheduled. Assume that processes enter the system at random times and that most processes take much longer than 2 milliseconds to execute.
(a) Does this algorithm give the highest priority to new processes? Explain your answer.
This algorithm does not give the highest priority to new processes. There are several reasons.
First, even if executing processes took much less than 2 milliseconds to execute, the scheduler
would alternate between “new” processes and “old” processes, giving equal priority to both.
Second, given that executing processes take much longer than 2 milliseconds to execute, most
“new” processes will not get scheduled during their 2 milliseconds on the ”new” queue and
will then drop to the bottom of the “old” queue without ever having been given any priority.
Now they have to wait for processes older than them to execute, and processes newer than
them to execute.
(b) Is this algorithm starvation free? Explain your answer.
Yes. Because the scheduler alternates between the two queues, every job that is not executed
from the “new” queue eventually ends up in the “old” queue and from there, eventually
reaches the head of the queue and is executed.
(c) Discuss whether this algorithm is fair to all processes. By “fair” we mean every process has a wait time approximately equal to the average wait time, assuming all processes have close to the same execution time.
No, it is not fair to all processes. Some lucky “new” processes will get to execute when they
reach the top of the “new” queue, while some will drop to the bottom of the “old” queue and
have to wait much longer to execute. These unlucky processes will have to wait for all of
the processes older than them to complete, and will have to wait for many processes younger
than them to complete as well.
____________________________________________________________________________________________
Can any of the three scheduling schemes (FCFS, SRTF, or RR) result in
starvation? If so, how might you fix this?
Yes. The SRTF algorithm can result starvation of long tasks if short tasks keep arriving.
The FCFS algorithm will result in starvation only if some thread runs forever. Finally, RR
does not result in starvation, since all threads get some of the CPU. To fix SRTF, we might
add some priority mechanism to make sure that threads that have waited for a long time
without running get at least some of the CPU now and then (priority increments when
threads don’t get to run). The multi-level scheduler is a good approximation to SRTF that
can be designed to avoid starvation. (the result wouldn’t be quite SRTF any more).
To fix FCFS, we would need to find some way of preempting threads that have run forever,
possibly by giving some CPU to other threads. Effectively, this would add elements of RR
or multi-level scheduling into FCFS (it wouldn’t be quite FCFS any more).

_____________________________________________________________
Describe the differences among short-term, medium-term, and long-term scheduling.
Ans:
Short-term (CPU scheduler) –selects from jobs in memory those jobs
that are ready to execute and allocates the CPU to them.
Medium-term - used especially with time-sharing system as an
intermediate scheduling level. A swapping scheme is implemented to
remove partially run programs from memory and reinstate them later to
continue where they left off.
Long-term (job scheduler) –determines which jobs are brought into
memory for processing.
The primary difference is in the frequency of their execution. The
short-term must select a new process quite often. Long-term is used much
less often since it handles placing jobs in the system and may wait a while
for a job to finish before it admits another one.
____________________________________________________
Some systems simply treat the readers writers problems as critical section problems and hence the implementation simply use P and V. What requirement of the Readers Writers problem does this implementation not satisfy?

Readers cannot read concurrently.
______________________________________________________________
Assume that 3 processes all with requirements of 1 second of CPU time each and
no I/O arrive at the same time.

a)What will be the average response time (i.e., average time to
completion) for the processes under FIFO scheduling?
Answer: 2 seconds



Explanation:
Time for completion for process A = 1
Time for completion for process  B = 2
Time for completion for process C = 3
Average time for completion = (1+2+3)/3 = 2
b) Answer part “a” for Round Robin (RR) scheduling assuming a timeslice of 0.1 sec and no overhead for context switches (i.e., context switches are free).

Answer: 2.9 seconds
Explanation:

Time for completion for process A =0.28
Time for completion for process  B =0.29
Time for completion for process C = 0.30
 Average time for completion =0. 29

c) Answer part “a” for Shortest Job First (SJF) scheduling.
Answer: 2 seconds
d) Multilevel Feedback Queue Scheduling (MFQS) is a fairly good, general CPU
scheduling algorithm, can lead to starvation under certain circumstances. Briefly describe how starvation can occur using MFQS and how to modify MFQS so that starvation can be avoided.
Long jobs on low-priority queues can starve if a continuous
stream of short jobs keep the high-priority queues full.
Soln: hold a lottery among the QUEUES, weighted in favor
of short queues
OR
implement aging, so that jobs that remain on
low-priority queues for a long time are promoted
e) What advantage is there in having different time-quantum (i.e. timeslice) sizes on different levels of the MFQS approach?
1) different time quanta help differentiate between
long and short jobs
2) for long jobs, short quanta mean unnecessary context
switches (so different time quanta improve throughput)
3) Introduces more fairness


_______________________________________________________________________________________________
Consider a system with two processes, P1 and P2. Process P1 is running and process P2 is ready to
run. The operating system uses preemptive round robin scheduling. Consider the situation in which
P1’s scheduling quantum is about to expire, and P2 will be selected to run next.
List the sequence of events that will occur in this situation, in the order in which they will occur.
Create your list by choosing from the events shown below, using the event numbers to identify events.
For example, a valid answer might be: “7,5,4,8,5,2”. If an event occurs more than once, you may
include it more than once in your list.
1. P1’s user-level state is saved into a trap frame
2. P2’s user-level state is saved into a trap frame
3. a timer interrupt occurs
4. the operating system’s scheduler runs
5. there is a context switch from thread T1 (from process P1) to thread T2 (from process P2).
6. P1’s user-level state is restored from a trap frame
7. P2’s user-level state is restored from a trap frame
8. a “system call” instruction is executed
9. thread T2 (for process P2) is created
10. thread T1 (from process P1 is destroyed
Write your answer here:
3,1,4,5,7
_____________________________________________________________________________
Suppose that the operating system is running a round-robin scheduler with a 50 msec time quantum. There are three processes with the following characteristics:

• Process A runs for 60 msec, blocks for 100 msec, runs for 10 msec and terminates.
• Process B runs for 70 msec, blocks for 40 msec, runs for 20 msec, and terminates.
• Process C runs for 20 msec, blocks for 80 msec, runs for 60 msec, and terminates.

Process A enters the system at time 0. Process B enters at time 10 msec. Process C enters at time 20 msec. Trace the evolution of the system. You should ignore the time required for a context switch. The time required for process P to block is the actual clock time between the time that P blocks and the time that it unblocks, regardless of anything else that is happening.

Answer:

Time    Running process     Events
0-50        A                  B enters at time 10.  C enters at time 20.
50-100      B
100-120     C                  C blocks until time 200.
120-130     A                  A blocks until time 230.
130-150     B                  B blocks until time 190
150-190     Idle               B unblocks at time 190
190-210     B                  C unblocks at time 200. B terminates at time 210
210-260     C                  A unblocks at time 230.
260-270     A                  A terminates at time 270.
270-280     C                  C terminates at time 280.

 
_______________________________________________________________________________________________

Consider the following preemptive priority-scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate alpha; when it is running, the priority changes at a rate beta. All processes are given a priority of 0 when they enter the ready queue for the first time. The parameters alpha and beta can be set to give many different scheduling algorithms.

(a) What is the algorithm that results from beta > alpha > 0?

(b) What is the algorithm that results from alpha < beta < 0?

• (a) Since processes start at 0, any processes that have been in the system (either running or waiting) have higher priority. Therefore, new processes go to the back of the queue. When a process runs, its priority keeps increasing at the rate of beta, which is more of an increase than for the processes in the ready queue. Therefore, every time the process has timerrunout, it goes to the front of the ready queue and gets dispatched again. This is the equivalent of FCFS.
• (b) This time, any new processes entering the system have higher priority than any old ones, since priority starts at zero and then becomes negative when the process waits or runs. New processes go in at the front of the queue. When a process runs or waits, its priority decreases, with the waiting processes decreasing faster than the running process. This is a LIFO (last-in-first-out) algorithm. 

Critical section Problems

1.

// functions to enter/leave the // critical section void critical_section_enter_t0() { while (turn != T0) continue; } void critical_section_leave_t0() { turn = T1; }

// functions void critical_section_enter_t1() { while (turn != T1) continue; } void critical_section_leave_t1() { turn = T0; }

i. Does this proposal provide mutual exclusion for the critical
section? Justify your answer!
Yes, it does. The variable ‘turn’ is either T0 or T1, and if it is T0, then
only thread T0 can progress past ‘critical_section_enter_t0’, and vice
versa.

ii. Is this proposal a satisfactory solution to the critical section
problem? Justify your answer!

No, it is not. It does not guarantee progress. In particular, thread T0
cannot reenter the critical section after it has left it unless thread T1
entered and left the critical section in the interim since critical_section_leave_t0() sets turn = T1. Only critical_section_leave_t1() can change it back to T0 again.

Consider:
critical_section_enter_t0();
critical_section_leave_t0();
// may block even though t1 is not in the critical section
critical_section_enter_t0();
critical_section_leave_t0();

________________________________________________________________________________

http://pages.cs.wisc.edu/~bart/537/quizzes/quiz2.html

________________________________________________________________________________

HTML Practical Problems

1. Line spacing in Firefox is more than that in IE. How can we solve it.

Get rid of spans and use div tags with a css style sheet.

2. To change the size of the text

Use inline style sheet

span style="font-weight: normal;"

3. How can I change the text field background on onSubmit?
http://www.webdeveloper.com/forum/showthread.php?t=85422

4. How can I go back to the previous page from the current page ?
< href="javascript:history.back(-1);">Back < /a >

5. How to include a file up one level in php.

Selection sort of Linked List ( Java)

1.Given a linked list of integer elements, construct a SELECTION SORT algorithm that puts the integer elements into ascending order. Note that a selection sort does O(n) copies. On each pass, the smallest element is placed into its proper position. For example, on the third pass:

Before: 5 10 55 22 65 12 75

After : 5 10 12 22 65 55 75

The code should NOT re-link nodes - just copy elements. Do not create a new list.

Solution in java

class Node{
public int value;
public Node next;
public Node(int givenval){
value = givenval;
}
}
class List{

private int length;
private Node head;
private Node tail;
//adds a new node to the list with specified value
public void addtoList(int value){
Node node = new Node(value);
if(length ==0){
node.next = null;

}
else{
node.next = head;
}
head = node;
length++;
}
//prints contents of the list
public void Print(){
Node node = head;
while(node != null){
System.out.println(node.value);
node = node.next;
}
}
public void selectionSort(){
for(Node node1 = head; node1!=null; node1 = node1.next){//number of
//iterations
Node min = node1;//assumes min node is the node under considerations
//selects the min node
for(Node node2 = node1; node2!=null; node2 = node2.next){
if(min.value > node2.value){
min = node2;
}

}
//swaps the min node with the node in its actual position
Node temp = new Node(node1.value);
node1.value = min.value;
min.value = temp.value;
}
}
}




public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here

List list = new List();
list.addtoList(1);
list.addtoList(2);
list.addtoList(3);
list.addtoList(4);
list.addtoList(5);
System.out.println("Before sorting");
list.Print();
list.selectionSort();
System.out.println("After sorting");
list.Print();

}

}

Database Quiz

Scroll down for answers

1. Set of permitted values of each attributes are called

A . Row
B. Column
C. Domain
D. Schema

2. Which of the following statements is not true

A. All primary keys are super keys
B. A candidate key can have a proper subset which is a super key
C. All super keys are not candidate keys
D. A candidate key may not be a super key

3. Entity integrity means that

A. A primary key cannot be null.
B. A foreign key cannot be null.
C. A primary key can be partially null.
D. A foreign key can be partially null.

4. The target of a foreign key should be

A. Foreign key in another table
B. Primary key in another table
C. Super key in another table
D. Primary key in the same table

5. Which of the following can not be the mapping cardinality of a foreign key

A. One- one
B. Many - many
C. Many- one

6. SQL is a

A. Host language
B. Application language
C. Data manipulation language

7. In the following ER diagram,


mapping cardinality of the relation is many one, which means
one manager can manage

A. zero or more departments
B. one or more departments
C. more than one department
D. exactly one department

8. Entity, that can not be uniquely identified by its own attributes , is called

A . Composite entity
B. Strong entity
C. Weak entity
D. Simple entity

In schema S = {A,B,C,D,E,F,G,H}, suppose the following hold for S.
AB --> CD
E --> F
F --> G

9. Which of the following holds true with respect to the above schema

A. CD --> AB
B. AB --> ACD
C. A --> CD
D. AB --> C

10. Which of the following does not hold true.

A. E --> G
B. ABE -->CDE
C. AB --> ABH
D. AB --> null set







Answers

1. A
2. B
3. A
4. B
5. B
6. C
7. A
8. C
9. D
10. C