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

________________________________________________________________________________