פתרונות תרגיל מצטבר לקורס מערכות הפעלה סימסטר סתיו

The obligatory exercises are: 1, 3, 4, 17, 20 and 21

Here are the criteria for checking:
1.	Illegal use of semaphores	-50%
2.	Not mentioning environment assumptions (e.g. If we assume client are automatically served in the right order, we have to assume Round Robin scheduling algorithm. In OS; those who did message passing in part 4 have to wait for acknowledgment after send call	– 10%
3.	Deadlocks	–20%
4.	In part3, if only one client is served simultaneously (wrong work on mutex)	–30%
5.	Bad synchronization between processes in part 4	–30%
6.	Clients served in wrong order in part 3	-15%
7.	In part 17,if you don’t mention HOW you choose you processes for running each time it’s	–5%
8.	In part 17,if you don’t calculate the average time between ALL processes, it’s	–5%
9.	For each part that wasn’t submitted	–17%

פרט את פקודות ה – shell הבאות על פי הנדרש:

· הסבר את הפקודות הבאות, הסבר את הפרמטרים במידה וצוינו, ותאר את הפלט הצפוי:

· הסבר את הפקודה הבאה, תאר את תוצרי המשנה ואת זרימת האינפורמציה בין התהליכים במידה וקיימת

A

1

·	ps –au		Prints information about active processes.
·		–a		Lists information about all processes most frequently requested: all those except process group leaders and processes not associated with leader
·		–u [uidlist]		Lists only process data whose effective user ID number or login name is given in uidlist.(uidlist may be empty) If uidlist is empty we list only processes with ID of the logged in user.
·	tr
·	find . -name "*.cpp" -print | xargs grep -i -l string > ./tmp.file

Q

במאפיה מסוימת יש n מוכרנים. כל לקוח מקבל מספר וממתין לתורו. כאשר איש מכירות מתפנה הוא קורא למספר לקוח ומשרת אותו. כתוב את האלגוריתם הנדרש ללקוח ולמוכרן.

Q

3

// The right solution combines the use of semaphores and event counters.

// The solution is very similar to producer-consumer.

semaphore mutex = 1, sellers = 0, clients = 0;

event-counter turn = 0,current = 0;

/* Event counter has 3 atomic actions:

Advance - simply increments the counter

Read - simply read the counter

Await (E, n) - Until counter E reaches n fall to sleep */

void consumer(){

//First of all take a number. A semaphore is used to make sure that the action is synchronized

down (mutex);

Advance (turn);

int n = Read(turn);

up (mutex);

up (clients); //announce a client has arrived

down (sellers); //check if there is a free server

await (current, turn); //wait for your turn

consume-item (); //when it's your turn you can work!

}

void producer(){

//POSSIBLY LOOP FOREVER

down (clients); //wait till the client arrives

Advance (current);//Advance current turn. wakes up the right client, give him service

Up (sellers);

give_service ();

}

// Note that no deadlocks can't occur here, because even if the producer cant wakes up a client that has the wrong turn number, the operating
// system will try to wake up clients till we face the right client

A

במסעדת מזון מהיר קיימים 3 סוגי עובדים: אנשי הזמנות, טבחים, מוכרנים. כתוב 4 אלגוריתמים עבור כל סוג עובדים והלקוחות. הנח שקיים מספר אחד של עובד מכל סוג.

Q

4.

// One way of solving the problem is to use message passing. In such a case the solution is trivial: Just send a message to
// the next entity is chain, and wait for its acknowledgement.

// Other way to solve the problem is by using semaphores. In such a solution we have to keep a semaphore for each entity and // product in the chain

semaphore customer-ready = 0, orderman-ready = 0, waiting-for-product = 0, product-ready = 0;

semaphore order-to-cook-ready = 0, cook-ready = 0, baked-ready = 0, seller-ready = 0, product-ready = 0;

void customer(){

up (customer-ready); //announce that a customer has arrived

down (orderman-ready); //ask for order

give_order(); //can order now

up (waiting-for-product); //announce the seller(last in chain) that we wait for product

down (product-ready); //wait until our order is fully ready

get_product (); //take the ready product

}

void orderman(){

//POSSIBLY LOOP FOREVER

down (customer-ready); //if there are no customers there's nothing we can do

up (orderman-ready); //synchronize order from the client

obj = get-order();

up (order-to-cook-ready);//announce the cook we have an order for him

down (cook-ready); //if there is no available cook there is nothing we can do

pass-to-cook (obj);

}

void cook(){

//POSSIBLY LOOP FOREVER

down (order-to-cook-ready); //Wait for order to cook

up (cook-ready);

req = get-from-orderman(); //Getting the request

res = bake(req); //Now we bake what we were asked to

up (baked-ready); //Announce that we baked the thing

down (seller-ready);

pass-to-seller (res);

}

void seller(){

//POSSIBLY LOOP FOREVER

down (baked-ready); //Check if we got a ready product

up (seller-ready);

product = get-from-cook();

up (product-ready); //Announce the client we got a packet for him

down (waiting-for-product); //Check if any customer waits to receive his product

pass-to-client (product);

}

A

Scheduling with dynamic priorities.

Consider the following preemptive scheduling algorithm. Each process is assigned with some priority. Initially a ready process with the highest priority runs. Priority of process can change dynamically. If the scheduler sees that the ready queue contains some process with priority highest than the priority of the executed process, the executed process is preempted from the queue and the process with highest priority is loaded instead.

An example of preemptive scheduling with dynamic priorities is preemptive SJF. The less the remaining CPU time of a process, the more its priority. Note, that by this method the priority of the executing process increases with its execution and only new arriving process can lead to preemption of the executing process.

There are methods, where the priority of the executing process decreases during its execution. An example of such a method is GARANTEED SCHEDULING. By this method, the scheduler keeps that the general CPU time were the same for all processes. When a process gets CPU there is some time slice it is not possible to preempt this process from CPU.

After this slice if it is made clear that there is some other process got less CPU time than the current process, the current process is preempted from CPU ad the new process begins to execute.

Compute waiting time by the guaranteed scheduling algorithm for the following process information:

Process Arrival time CPU time

P1 0 20

P2 5 15

P3 10 20

(Time slice is equal to 5)

Q

17.

Guaranteed Scheduling (slice time = 5)

A

CPU	Q	1P	2P	3P
-	0	0	-	-
P1	1	1/1	0	-
P2	2	1/2	1/1	0
P3	3	1/3	1/2	1/1
P1	4	2/4	1/3	1/2
P2	5	2/5	2/4	1/3
P3	6	2/6	2/5	2/4
1P	7	3/7	2/6	2/5
2P	8	3/8	3/7	2/6
3P	9	3/9	-	3/7
1P	10	4/10	-	3/8
3P	11	-	-	4/9

סה"כ זמן המתנה:

P1: 6

P2: 4

P3: 5

ולכן זמן ההמתנה הממוצע הוא: 5 = 3/(5+4+6). עתה ניתן להכפיל את התשובה ב – 5 ולקבל ביחידות זמן קטנות יותר = 25

There is an other way to solve this problem correctly, as long as there is any guarantee of “fair” scheduling (for example in the classical guaranteed scheduling the priority of the process is: (the CPU time it’s entitled)/(CPU time it got)

Entitled CPU time is:

1. Number of processes in scheduler now.

2. (CPU-time the process ran)/(total time the process existed)

The Virtual Memory has 32 pages of 2k everyone. The physical Memory has only 8 pages. What are the addresses in the physical memory for the virtual addresses: 3500, 32400 and 19300

Q

20

Virtual Memory Physical Memory

0 – 2		0	B
2 – 4	A	1
4		2
6		3	C
8		4
10		5
12		6
14		7	A
16
18	C
20
22
24
26
28
30	B
32
34
36
38
40
42
44
46
48
50
52
54
56
58
60 – 62
62 – 64

We know that each page is 2K = 1024 *2 = 2048 bytes.

All the numbers given here are the Virtual Memory addresses.

We can compute from them the correct Offset that will stay the same in the Physical memory. Since the MMU function is not given here we don’t know for sure how it will calculate each block number from the virtual area to the physical area.

A. Address 3500:

3500 / 2K = 3500 / 2048 = 1 + 1452 / 2048

Meaning that this address is in Block number 1 with an offset of 1452.

In binary:

4	3	2	1	0	10	9	8	7	6	5	4	3	2	1	0
0	0	0	0	1	1	0	1	1	0	1	0	1	1	0	0

B. Address 32400:

32400 / 2K = 32400 / 2048 = 15 + 1680 / 2048

Meaning that this address is in Block number 15 with an offset of 1680.

C. Address 19300:

19300 / 2K = 19300 / 2048 = 9 + 868 / 2048

Meaning that this address is in Block number 9 with an offset of 868.

What is the number of disk accesses when a user executes a command?

cat /bin/usr/msc/test.txt

Assumptions:
1 - test.txt consist of 3 blocks of data.
2 - the root memory is not in memory, it is on the disk.

Q

21

i-node 6 is for /bin

132

i-node 6 says that /bin is in block 132

i-node 26 is for /bin/usr

406

i-node 26 says that /bin/usr is in block 406

i-node 60 is for /bin/usr/msc

512

i-node 60 says that /bin/usr/msc is in block 512.

Block 406 is /bin/usr directory

26	.
6	..
60	Msc

Looking up /msc in /bin/usr directory yields i-node 60.

Block 512 is /bin/usr/msc directory

60	.
26	..
78	Text.txt

Looking up /text.txt in /bin/usr/msc directory yields i-node 78 .

i-node 78 is for /bin/usr/msc/text.txt

691

697

723

i-node 78 says that /bin/usr/msc/text.txt is in blocks: 691, 697, 723.

Block A

Block B

Block C

We conclude from this that there are 11 accesses to the disk, as seen above with 8 tables of I-nodes and blocks as well as 3 block of the final file. If blocks are prefetched into cache/memory then there are fewer accesses to the disk.

A