NIT1202 Operating Systems For the External Fragmentation

Operating system itself is built up of many components. One of the most important components of operating system is kernel that manages all the control over memory. User cannot interact with kernel directly. Apart from that, other component is user interface that interacts with the user directly.

Conclusion- Operating system is software that manages all the resources by providing common services for the computer programs. For an application, operating system offers various services like it allow multiple programs to run on a system at the same time. It also allows memory sharing between various applications. The features of parallel processing are possible due to operating system as it divides the time slot for a program so that many applications can run on a single processor.

Some of the information that is given is:

In the best fit, the best available memory block is used to fulfil the request. In the smallest memory block is selected so that it can be used in a maximised way. It works on the concept that memory is used optimally. In this case, problem of internal fragmentation is faced if the memory block that is requested by the processes is less that the allocated memory. If the memory block request is higher than the available slot, algorithm is stopped.

The algorithm that is followed in case of best fit is

• Initially number of process and blocks are identified.
• Then size of each block is found and process is requested
• Best memory block is allocated
• The track of wasted memory is kept
• Stop

Available memory blocks

Thus, when job A requires 57K it is allocated to BLOCK 3, so that less memory is wasted as compared to other block size.

Later, when job B arrives and request for 920k, it not fitted in any block as requested size is larger than available size

Job C fits in third block but we cannot use block 3, so its ends up in block 3. As request 50k is completed by using Block 3.

At last, job D request 710k which can be completed by using Block 1 and block 2 but block 1 will be used so that least memory is wasted.

In case of first fit algorithm, the algorithm works under certain steps that are:

• Initially number of processes and number of blocks are identified.
• Then size of each block and size of process request is identified.
• Then processes are allocated

if (size of block>= process size)

// allocate the process

else

// move to next block

• Display the processes with the respective blocks in which they are allocated.
• stop

Available memory blocks

Job a request for 57k is allocated to block A of size 900k as size of block is greater than process size.

Then, Job b requests for 920k which cannot be allocated as size of block is less than the requested size of process.

Later, Job C requests for 50k that could be fitted in the available space of block 1 easily

At last, Job d request for 710k that is too large and cannot be fitted in available space of block A, so we need it is fitted in block 2.

Internal fragmentation and external fragmentation

Fragmentation is way of storing file and information in pieces at different location. This can sometimes be an issue as information go out of order because it is stored in a scattered way. There is a difference between both the terms internal fragmentation deals with portioning the memory block in fixed size. The memory is allocated to processes by dividing them in equal memory blocks (Arlt, Rauchfleisch & Schäfer, 2018). This method of fragmentation is inefficient as excess of memory is wasted. The other form of fragmentation is external fragmentation; it uses the unused memory blocks. The unused memory blocks are assigned to the process so that efficiency is improved and memory is used in an optimized way.

The basic difference between internal and external fragmentation is that internal fragmentation leads to wastage of memory blocks as memory blocks are allocated in a fixed segment. On contrast, external fragmentation refers to allocation of memory block that is unused (Parker & Gorobets, 2015). External fragmentation can take place in the small memory holes that are available while in other case it is not possible. In case of, internal fragmentation memory is partitioned in fixed size. In case of external fragmentation memory is divided in form of variable sized block. The issue faced by internal fragmentation can be eliminated by dynamic allocation method (Parker & Gorobets, 2015). On the other hand, issue faced by external fragmentation can be eliminated by using paging and segmentation.

If an option is given to select one of the fragmentations, external fragmentation would be chosen as it allocates the memory dynamically and all the free space is used. It also reduces the overall memory usage by using the concept of paging. The overhead required by external fragmentation is quit less.

If a program has 471 bytes and will be loaded into page frames of 100 bytes each, and the instruction to be used is at byte 132, answer the following questions:

How many pages are needed to store the entire job?  

The total number of pages that is required to store the entire job is 5. That is from page 0 to page 4.

As the page 1 will store frames from 0 to 100

Similarly, page 2 will store frames from 101-200

Similarly, page 3 will store frames from 201-300

Similarly, page 4 will store frames from 301-400

And at last page 5 will store from 401-500.

Thus, 471 bytes will be fitted by using 5 pages

Now, Computing the page number and exact displacement for each of the byte addresses where the data is stored.

It is given that; the instruction to be used is at byte 132.

For finding the displacement at page 0, this is done by multiplying the page frame byte* page number (that is 0)+ displacement of page that is zero for this case

Thus, address is 100*0+0=0

So for, Page 0=Displacement is 0 and address is 0

For finding the displacement at page 1, this is done by multiplying the page frame byte* page number (that is 1)+ displacement of page that is zero for this case as it is not known

Thus, address is 100*1+0=100

So, for Page 1=Displacement is 0 and address is 100

It is given to find instruction to be used is at byte 132.

Thus it will search for the result on the first page.

Therefore,

Address is 132*1+0=132

For, Page 1=Displacement is 32 and address is 132

Page 1 is where instruction is located

For finding the displacement at page 2, this is done by multiplying the page frame byte* page number (that is 2)+ displacement of page that is zero for this case as it is not known

Thus, address is 100*2+0=200

So, for Page 2=Displacement is 0 and address is 200

For finding the displacement at page 3, this is done by multiplying the page frame byte* page number (that is 3)+ displacement of page that is zero for this case as it is not known

thus address is, 100*3+0=300

So, for Page 3, Displacement is 0 and address is 300

For finding the displacement at page 4, this is done by multiplying the page frame byte* page number (that is 0)+ address of page that is 71 for this case

Thus, address is100*4+71=471

So for, Page 4=Displacement 71 and address 400

Given that main memory is composed of only three page frames for public use and that a seven-page program (with pages a, b, c, d, e, f, g) that requests pages in the following order:

a, c, a, b, a, d, a, c, b, d, e, f

1. Using the FIFO page removal algorithm, indicate the movement of the pages into and out of the available page frames (called a page trace analysis) indicating each page fault with an asterisk (*). Then compute the failure and success ratios.  

Total Faults= 8

Total success= 4

Failure ratio= 8/12

And success ratio= 4/12

Failure percentage =66.66%

Success percentage= 33.33%

1. Increase the size of memory so it contains four page frames for public use. Using the same page requests as above and FIFO, do another page trace analysis and compute the failure and success ratios.  

Total Faults=6

Total success= 6

Failure ratio= 6/12

 And success ratio= 6/12

Failure percentage =50%

Success percentage= 50%/

1. What general statement can you make from this example? Explain your answer.  

Thus, these questions are solved using first in first out technique. That is the page that is arrived first will be replaced on the new arrival. In the above example the first page is always replaced if new page arrives

Five jobs arrive nearly simultaneously for processing and their estimated CPU cycles are, respectively: Job A = 12, Job B = 2, Job C = 15, Job D = 7, and Job E = 3 ms. (Arabnejad & Barbosa, 2014)

1. Using FCFS, and assuming the difference in arrival time is negligible, in what order would they be processed? What is the total time required to process all five jobs? What is the average turnaround time for all five jobs?   

Given arrival time of each job = 0ms

So, total time that is taken to complete all eth jobs is, 12+2+15+7+3

Total time needed to complete all the five jobs =39 ms

Turnaround time= Finish time-arrival time

Turnaround time for A is, 12-0=12

0 12

Turnaround time for B is, 14-0=14

0 12 14

Turnaround time for C is, 29-0=29

0 12 14 29

Turnaround time for D is, 36-0=36

0 12 14 29 36 

Turnaround time for E is, 39-0=39

0    12 14      29               36  39

Average Turnaround time for all the jobs is (12+14+29+36+39)/5= 26 ms

Thus, using FCFS order will be A,B,C,D,E (Qin & Jin, 2015)

1. Using SJN, and assuming the difference in arrival time is negligible, in what order would they be processed? What is the total time required to process all five jobs? What is the average turnaround time for all five jobs?  

Given arrival time of each job = 0ms

The Turnaround time is difference between finish time and arrival time.

In SJN, shortest job next that is the job is shortest CPU time is processed

Turnaround time for B is, 2-0=2

0           2

Turnaround time for E is, 5-0=5

0           2 5

Turnaround time for D is, 12-0=12

0           2 5 12

Turnaround time for A is, 24-0=24

0  2 5                    12    24

Turnaround time for C is, 39-0=39

0                   2 5         12  24                         39

Average Turnaround time for all the jobs is (2+5+12+24+39)/5= 16.4ms.

Using SJN, the order will be B,E,D,A,C (Vasile, Pop,  Tutueanu, Cristea & Ko?odziej, 2015)

Given the following information :

0 15

0 15 17

0 15 17 31

0 15 17 31 41

0 15 17 31 41    51

SJN

0 15

0 15 16

0 15 16 18

0 15 16 18 28

0 15 16       18           28    42

SRT

0 2

0 2 4

0 2 4 6

0 2 4 6 9

0     2 4      6 9 10

0     2 4                    6     9 10              17 28    42

RR

Quantum time is 5

0 5

0 5    7          

0 5    7          12

0 5    7          12 17

0 5    7          12 17    18

0 5    7          12 17    18       23

0 5    7          12 17    18       23       28    

0 5    7          12 17    18       23 28 33    

0 5    7          12 17    18       23 28 33    38    

0 5    7          12 17    18       23 28 33    38   42

References

Arabnejad, H., & Barbosa, J. G. (2014). List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Transactions on Parallel and Distributed Systems, 25(3), 682-694.

Arlt, D., Rauchfleisch, A., & Schäfer, M. S. (2018). Between Fragmentation and Dialogue. Twitter Communities and Political Debate About the Swiss “Nuclear Withdrawal Initiative”. Environmental Communication, 1-18.

Hooker, R. E., Parks, T., & Bunda, J. D. (2018). U.S. Patent No. 9,891,918. Washington, DC: U.S. Patent and Trademark Office.

Parker, L. M., & Gorobets, S. A. (2015). U.S. Patent No. 8,990,477. Washington, DC: U.S. Patent and Trademark Office.

Peter, S., Li, J., Zhang, I., Ports, D. R., Woos, D., Krishnamurthy, A., ... & Roscoe, T. (2016). Arrakis: The operating system is the control plane. ACM Transactions on Computer Systems (TOCS), 33(4), 11.

Qin, L. I. U., & Jin, C. H. E. N. (2015). Job-Shop Scheduling with Parallel Equipments Based on Five Dimensions Scheduling Algorithm. Journal of Jiangnan University (Natural Science Edition), 1, 010.

Shin, S., Song, Y., Lee, T., Lee, S., Chung, J., Porras, P., ... & Kang, B. B. (2014, November). Rosemary: A robust, secure, and high-performance network operating system. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security (pp. 78-89). ACM.

Vasile, M. A., Pop, F., Tutueanu, R. I., Cristea, V., & Ko?odziej, J. (2015). Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing. Future Generation Computer Systems, 51, 61-71.