Trial 1.0-thebasicsYou can locate files easily (witha directory structure)But, can you locate the allocated space and the freespace ina shortperiodoftime?FilenameEndingStartingFree spaceis here.AddressAddress0rock.mp32000But,itneedsanO(n)search,wheren34562001sweet.jpgisthetotal numberoffiles.50005678game.exeWhat if the disk is large andthe files are small?Rootrock.mp33sweet.jpggame.exeDirectory11
11 Trial 1.0 – the basics Filename Starting Address Ending Address rock.mp3 0 2000 sweet.jpg 2001 3456 game.exe 5000 5678 You can locate files easily (with a directory structure). But, can you locate the allocated space and the free space in a short period of time? Free space is here. But, it needs an O(n) search, where n is the total number of files. Root Directory rock.mp3 sweet.jpg game.exe What if the disk is large and the files are small?
Trial1.0-thebasicsFile deletion is easy! Space de-allocation is the same asupdatingtheroot directory!Yet,howaboutfilecreation?FilenameStartingEndingFilenameStartingEndingAddressAddressAddressAddress0rock.mp320000rock.mp320002001945SweetP950005678game.exe50005678game.exeRootrock.mp3sweetipggame.exeDirectory12
12 Trial 1.0 – the basics File deletion is easy! Space de-allocation is the same as updating the root directory! Yet, how about file creation? rock.mp3 sweet.jpg game.exe
Trial1.0-thebad#1 Suppose we need to write a new, but large file?ReallyBAD!Wehaveenoughspace,butthereisnoholesthatIcansatisfytherequest.Thename of theproblemiscalled:ExternalFragmentationAny solution?ubuntu.isoCan'tbewritten!Rootrock.mp3game.exeDirectory13
13 Trial 1.0 – the bad #1 • Suppose we need to write a new, but large file? ubuntu.iso Can’t be written! Root Directory rock.mp3 game.exe Really BAD! We have enough space, but there is no holes that I can satisfy the request. The name of the problem is called: External Fragmentation Any solution?
Trial 1.0-thebad#1Thedefragmentation processs may helpFilenameStartingEndingFilenameStartingEndingAddressAddressAddressAddress0rock.mp3200002000rock.mp350005678game.exe20012679game.exeubuntu.iso26806000Veryexpensive（thinkabout the disk structureubuntu.isoRootrock.mp3game.exeqame.exeDirectorymove14
14 Trial 1.0 – the bad #1 • The defragmentation process may help. Root Directory rock.mp3 game.exe Filename Starting Address Ending Address rock.mp3 0 2000 game.exe 5000 5678 game.exe Filename Starting Address Ending Address rock.mp3 game.exe 2001 2679 ubuntu.iso 2680 6000 0 2000 move ubuntu.iso Very expensive (think about the disk structure)
Trial1.0-thebad#2. Comment:- Also, the growth problem...there is no spacefor files to grow.Growthproblem!Can you suggestanymethod?Too crowded!I needto be relocated inorderto grow.Rootrock.mp3ubuntu.isogame.exeDirectory15
15 Trial 1.0 – the bad #2 • Comment: – Also, the growth problem.there is no space for files to grow. Growth problem! Can you suggest any method?