35. "Final Review" 2024 Fall ECE344 Section 2 (University of Toronto)

[Music] oh God all righty welcome back to operating systems for the last and final time so this one it's all just review so before I start just so you know your final your functions you're given exactly the same as 2024 winter ECE 353 you will get all these functions so you get listed your exams Clos book yada yada yada all right what do we want to do any suggestions or so locking problem locking problems all right good which locking any locking problem in particular one from this exam the previous exam all right well let's see so I put a green check mark every next to Everything I did in section one so you can look at that recording so so you can see those questions if you want um locking want to just do this question sure yes all right so let's make this a bit bigger whoops so locking examine the provided code where two threads executing thread one or T1 and T2 so we got two threads we got a T1 oh it's this room T oh I hate this room all right we got T1 running we got T2 running they would both start running the beginning of the function all right says each acquire and release multiple mutexes we have three mutexes in total M1 M2 and M3 first part says analyze if the two threads executing functions T1 and T2 in the provided code result in a deadlock explain the reasoning behind whether or not a deadlock is possible or not in this scenario so T1 will acquire M2 then M1 and then thread 2 will acquire M1 then M3 do we have a Deadlock yeah no we do not no we do not that is correct why because M1 will eventually unlock at the end of T2 won be able to so if thread one thread two executes first gets m one I could still run well do the First Column T1 M2 is not shared between them and then well if this one has M1 this one will try and get M thread one will try and get M1 but it's fine thread two can make progress get M3 do whatever it needs to do carry on basically if I want to do it succinctly if I look at the dependencies there's no circular weight here right I always get M2 before M1 and I always get M1 before M3 so there is no circular so basically the only two things we need to be concerned about for deadlocking two things we can do anything about is hold and weight there is hold and weight here but we need all four conditions for a deadlock one being circular weight in this there is no circular weight because we have M2 we need to get M2 before before we can get M1 and we need to get M1 before we can get M3 so those are straight lines that is not a circular weight yeah what would it be like then we might deadlock no I what sample of what's an example of circular weight well luckily enough says assuming in addition of a third thread thread three executing function thread 3 devise a sequence of lock calls here involving only mx's M2 and M3 that could lead to a deadlock so we probably want hold and weight to happen how would I lock M1 or sorry M2 and M3 that would result in a deadlock here so going here these are the two functions I have I'll just write it here just for sanity I guess so say we have thread three and I really dislike whatever weird electrical crap happens in this room all right so we want to use M2 and M3 in thread 3 such that it deadlocks so what sequence do we want yeah probably M3 M2 probably M3 M2 basically we want to create this line right to make our circular dependency so that would mean I have to have M3 before I try to get M2 so if I add it here I could just lock M3 lock M2 and then it says describe this sequence and explain how it results in a deadlock combined with thread one and thread 2 so how it could work now is since I have thread three what could happen is thread one acquires mutex 2 So This Thread now has M whoops let's do it in Orange so this one has M2 and then we contact switch to a another thread maybe we contact switch to thread two it acquires M1 so now it has the M1 mutex and now we contact switch over to thread three it gets the M3 mutex and now none of them can make progress anymore right m one or thread one can't make any progress because it's trying to get M1 which is held by thread 2 thread 2 can't make any progress cuz it's trying to get M3 which is held by thread three and thread 3 can't make any progress because it's trying to get M2 which is held by thread one so we deadlocked so everyone okay with that so that was a very quick 18 marks yeah does that imply that if we want to add we need to add another no so we can avoid the circular weight without like three so in thread three if I flipped those two lock calls around would I deadlock no right because now I don't have a circular weight anymore so if I flip these two around right I do oops I took too much if I flip these two around there's no situation where I can deadlock because now I don't have this right I essentially created this line which is still ordered so I still always acquire things in the same order so I have no problems whatsoever so there's only one sequence that will deadlock and I was nice saying well I constrain the problem a lot all right so everyone okay with the Locking question all right what's next so we can the hard threat question thread let's look at the other exam for fun oh yeah we do a center Force question Center Force question uh so let's start it on the other exam so something like this all right center Force question so this is from the 2024 win or winter yeah all right so it says you are given four threads that get properly created and run you want to ensure ordering between them you decide to use Center Force to accomplish this task recall that Center Force after initialization use post to increment the value and weit to decrement the value waiting until the value is greater than zero assume no errors occur so you never need to check return values consider the following code so I get three center fors created for us that don't have any values which hinting that I probably need to set them at some point and then I have thread one to thread four all calling some functions and then some comments that say that say F2 should only run after F1 completes F3 should only run after F1 completes then seems like F4 can run whenever well I mean we have this dependency So within a thread it would call F3 before F4 but that's my dependency with within a thread and then it says thread 4 F5 should only run after F2 and F3 complete F6 should only run after F4 completes so first part which is most of the question says fill in the initial values for each Center four and insert a post and weight calls in a way that ensures ordering in the comments you cannot change the ordering of the F calls and they always execute in the order written within a thread write your answers on this page oops all right so basically with this for every kind of ordering you want to ensure just use a different Center for so we will start off with the ordering that waits for F1 to complete so let's use Center for one that should only wait until after F1 completes so easiest thing to do with the center fors I find is to first place my weight call so what threads do I need to wait for F1 to complete none none what a well yeah some so thread two and thread three need to wait to for F1 to complete1 no so I need to place a weight call where do I need to place one weight yeah F2 above F2 so I need a weight here oh curse this room so wait with sem one do I need another weight or am I done yeah3 above F3 so weight on the same Center four then next thing I like to do do I need any more weight calls anything else need to wait for F1 to complete nope so easiest thing to do now is to set the initial value so the initial value you can think about is how many threads should be able to pass weight without any other thing calling post so what should the initial value be in this case zero right we don't want either thread one or thread three to start executing pass their weight For Thread one does something so we need to initialize it to zero and then for posting well we post after F1 right so we post after F1 that's our dependency so we post sem1 here if I post sem one that would increase it from like 0 to one that would only let one pass right yeah so what exactly does the initial value do so the initial value if I set to zero right that means that if thread 2 happens to execute first since the initial value is zero it's not going to make it past this call it's going to get blocked right until someone increments it and similarly for this if the initial value was say two then both the threads could just pass by weight no problem so that's why it's good to think about it it's like hey without any post that's how many threads can pass by a weight because first one go from two to one next one would go one to zero no problem so that's why we have our initial value at zero all right so then we need to post after we call F1 is that it just one post I need another post right each post just increments it so I'll have two threads waiting for it so I need to post twice in order to resolve it so I need wow holy I do not like this whatever the hell happens in this room all right so I need to post sem one here so that is that first condition right so now both thread two and thread three will run after and only after F1 is done so that's my first condition so that's check don't try and reuse center fours or anything crazy like that so that means I could put a little check here this is a check this is a check now next one I want to only run after f 2 and F3 completes yeah we just do like have two weights like two in before uh f25 and we one post end yeah so how I can do this one is it needs to run after F1 and F2 completes so I'll need at least a weight here and let's say I use sem2 so that's probably good I need at least a weight there the initial value should probably be zero again because I don't want this to run until someone else posts then well now I have to insert my post calls so I want to make sure it runs only after F2 and F3 completes so they're in different threads so I would need to post here after F2 and post after F3 so how I have it written right now since I only wait once well either of those threads would be able to post increment it and then I could call F5 when either F2 or F3 Complete because I don't know which one will go first if I want to wait for both of them well I just need to insert another weight call here so now I wait twice each of each other thread posts once so they have to both post before I can get by to weights so is that okay so that should check that one and then with the last one so I should only run after F4 complete so again I would just do a weight on sem 3 here initial value should be zero and then I could just do a post of sem3 right after doing F4 so are we okay with that all right then the last one says for each function State what functions could run in parallel with it not including itself write one if it can only run by itself so should be able to look at this and see F1 in this case F1 needs to complete before F2 or F3 wow before F1 or F3 complete and then well F3 has to wait for F4 because it's in the same thread then for F5 it can only run after both of these complete right so it only runs after both F3 and F2 complete so this is F5 and then F5 or F6 can only run after F5 and also after F4 so that's all of our dependencies all at the same time so if I'm running F1 Well it can't run at the same time as F2 or F3 so can't run anything else that's dependent on either of those so F1 can only run by itself in parallel right yeah in what case would we not zero so like our producer consumer example where we wanted like we had a buffer size right and we wanted at most buffer size threads running at once that's when we set like the initial value to uh the buffer size so that we can have 10 threads go all at once but they're capped at that I can't have any more that's generally you'll usually see it initialized at zero but sometimes you might not if there's some other weird limit or something like that all right so for this can only have F1 running by itself F2 could actually run at the same time of F3 right so F2 here while this is running we know F1 is complete so we could run it at the same time in parallel with F3 from thread three also there's no dependency it could also run at the same time time is F4 so and that's it and then I shouldn't really have to go on the you can double check the answers with the other one I'll try and move on to something else yeah oh if you have a question that's fine yeah next one oh you want next one or this one are we done with this one if we want to be yeah we can be done with this yeah can do this question 12 I was wondering okay so I I'll just do this question from the start to make sure everyone's on the same page all right so we got processes says consider the following code assume all system calls are always successful and we're running under process ID 100 so we have process ID 100 running whoops so process IDE 100 so we have this Loop that executes two times so this will be fun so we go through the loop once we have this will be really fun in this room so we go into the loop process 100 creates a variable called I it's equal to zero then it calls Fork so it creates a process process 101 it has it's an exact clone so it has an i with the value of one and the only differentiation between them will be the return value of fork in the parent R will be equal to 101 in the child R will be equal to zero so then let's say for argument sake process 10 100 executes next So currently I is equal to zero and R is greater than zero so it's going to get stuck here in the weight so it's going to wait for it child to perish so only thing I can do is run this child which is 101 doesn't look like 101 but it is so no other choice it has to call this print function it would print uh it' print P ID equal 101 r zero I is equal to zero right then it would go up here it's for Loop increments its I it's I well R went out of scope so R is dead I got incremented to one sorry I deleted that process 101 oh wait no I didn't so now it calls Fork again so process 100 we'll draw the family tree up here process 100 created 101 101 is about to create 102 so now we create process 102 from the fork I'll try and put them on the same line so it's going to be exact copy of the parent so it will have an i equal to one only difference is going to be the return value of fork so in 102 Rett is going to be equal to zero process 101 R is going to be equal to 102 now I don't know which one we'll execute next I is not equal to zero so that if statement will always fail don't know which one we'll execute next so for argument sake oh no oh I really hate this room so don't know which one we'll execute next could be 101 again that would print P ID 101 R 102 and then I is one or I could have P 102 R is zero I equal 1 so either of them will go ahead come up here nothing is dead yet let's say p 101 happens first first both of their RS go out of scope it would increase I oh well thankfully mercifully it would increase I equal to two then it would drop out of the for Loop and it can exit right so these are now mercifully both able to exit I don't know which one's going to exit 102 could die first 101 could doesn't matter but as soon as 101 dies then process of 100 will be able to return right so then it will be able to pass by the weight because it would wait on Pro only its direct child which was 101 so it will then always print P ID P equals 100 r was 101 I is equal to 0 and now process of 101 or 100 will come up here I will go so red will go out of scope I will increase to one and then it'll Fork again create a new process probably 103 then 103 mercifully it'll have an I it'll equal one and then the only difference would be the return value of fork so in process 100 it would return 103 in this process it would return zero and this is the last time they're both going to run they'll both exit eventually all right so everyone keep on track with all that crap so first question then how many new processes get created three right we have that little tree at the top so we assume process 100 always exists so we created 101 102 and 103 so next was draw a tree of the parent child relationship showing the process IDs they would likely get y win thankfully we already did that so next using the pids in your tree provide a possible sequence of outputs of the code so we're going to see what so these will eventually print too so this will print p102 I equals 1 or sorry whoops these are already dead sorry is these two that will print so we'll get P idal 100 I equal 1 R is 103 and the other one we get p 103 I = 1 red = 0 and then we'd get this line first always then this line then this line and this line that's a possible sequence of orders you get one two 3 4 five six so we get six lines in total that's one possible sequence all right oh yeah 100 will wait for 103 no I is not equal to zero yeah I is not equal to zero so process 100 this will only happen once process 100 will only wait for process 101 all right so there's a possible sequence show an impossible set of outputs for the provided code ensure that all the sequence prints within the same process remains consistent but the overall sequence cannot be produced by the code so basically just swap these two around so so what that's saying is like I'll always see process 101 r i equals 0 and then I equal 1 and it won't somehow reverse within the same process it's just between processes so process 101 100 oops sorry this process 100 we'll never print first before 101 because it weigh for it so that can't happen all right now we can finally go to the other one so for each direct uh child process of a 100 which in our case the way we wrote it was 101 and 103 State whether it will always maybe or never be a zombie or an orphan one answer for each briefly describe your reasoning so for process 101 can it be a zombie yes and this is always maybe orever is there a chance even for a brief second that it is a zombie yes right so why well what might happen is as soon as process 100 forks the first time we just immediately start executing that new process 101 right 101 can execute till it's completed it terminates it's technically a zombie and then it will get cleaned up so it will never be a zombie by the time process 100 Exits but it will be a zombie for a little bit until it gets cleaned up I think I also if you explained it well enough or if I thought what you meant I also gave it full marks if you always said never but you had to be clear that it never if you assume process a 100 Exits was that your question for the other the other one okay so that one's okay so let's finish this one maybe briefly all right orphan can't be an orphan no or never because it gets weighted on right so the parent will never outlive it because it's always get always gets waited on and we don't assume anything weird with uh things dying all right for process 103 can it be a zombie yes and is it always always maybe or Never So in this case process 103 no one Waits on it um and it can terminate before anything else right so it could definitely maybe be a zombie I think that should be the [Music] answer yeah so maybe May termin before any and the only thing that's going to wait on it is a knit whenever it gets reparented because nothing that I wrote explicitly waits for it all right the next one is Orphan so can it ever be an orphan so an orphan if we go back to our diagram was it 103 so orphan means means it's possible that process 100 Exits before me right so in this case is it possible process 100 executes before me so the way I left this off is whatever process 103 was created right so it could be the case where process 103 is created all it's going to do is print and exit but it doesn't have to execute next right right 103 doesn't get weighted on by anyone yeah isie dep sequence and it doesn't matter uh yeah I think I also took it gets a bit Fini with the zombie cuz technically you know gets reparented it it's going to get terminated sometime it might be a zombie for a little bit even if it's like for Loop waiting so I also accepted always for that one so always was fine for that one and then for Orphan possible that it could be an orphan right might be an orphan because process 100 doesn't wait on 103 or anything process 100 could just print its line terminate and then as soon as it's terminate it just orphan 103 right could be the other way around where process 103 executes first it terminates so doesn't have to be an orphan although shouldn't that be always actually it should be always an orphan right no because you can exit oh yeah it could still be running right the opposite could be true so 100 or we could exit before yeah but if we exit before we're done but it doesn't wait on us right So eventually it's going to exit and you're going to get orphaned and you're going to be a zombie orphan so I think technically the answer this answer I think the answer given was maybe but I think it should always be always for Orphan so if um so 103 will always either be an orphan that's still running or a zombie orphan so I believe the solution's wrong it should always be an orphan because we never wait on it right so should always be an orphan I believe the solutions wrong all right next one yeah file systems file systems uh which one this file systems one huh all right file systems how much time we got 14 minutes so this file systems assume a file with a block size of this so I'll just write powers of two because I like to 4 by to the power of two damn this room and 128 byte iodes which is 2 to the 7 yeah 2 the 7 yeah iodes have 12 direct pointers one indirect pointer one double indirect and one triple indirect analyze the output of Ls all the stupid arguments the output of the format includes I node numbers in the First Column so these are the iodes so it's telling you just in case you forgot the other one should be somewhat self-explanatory so this column is the number of hard links then uh user that owns it group that owns it although doesn't really matter the size and then the modification date which we which we cannot Forge right didn't show you how to do that do not write your whoever and then finally is the names so first question says when editing file C what iodes contents get modified so the file C is a Sim link so it's symbolic link so it's basically named to a name so if we try and open it it won't open inode 22 because that stores essentially B so we're treating iodes as just name to a name so to find the iode it will then refer to the name b and then look at that iode which is iode 20 so iode 20's contents get modified everyone okay with that all right next one is it possible to store all the I noes associated with this directory on a single block provide an explanation supporting your conclusion so we can figure out how many iodes we can fit on a block right so the number of iodes we could fit on a block is just the size of a block so 2 to the 16 or 2 the 12 sorry divided by the number of the size of the iode that's the number of iodes per block which thankfully I already wrote everything out in powers of two so that's just 2 5 which is equal to just 32 so that means I could fit IES 1 to 32 on a single block right if I look at my iode numbers here they all fall within that range 1 to 32 so the answer is yes it fits all iodes wow that's hopefully You' have better writing than me fit between 1 to 32 and my writing is usually better than this but this room's cursed I have to write like a goblin I don't know why I thought that all right next one determine the number of data blocks that file e will occupy so file e its size is 5,000 so can I fit 5,000 bytes on a single block no how many blocks do I need two right I need at least two so one doesn't fit but two fits they're each 4, uh 96 so if I have two blocks that's like 8,192 so the answer here is just two then it says calculate the number of bytes lost due to internal fragmentation for block for file e so two blocks is 8,000 95 bytes or you could just say 2 * 2 to 12 again I don't really care if you have a calculator as long as you have the right numbers I don't care so it's just that minus 5000 right so could write either if you just stop there that's fine if you have your blanket calculator with you that makes you feel safe you can do the fal calculation if you want which is what 3,900 192 easy calculation if you don't have your calculator but you could use it if you want doesn't matter so that okay with everyone all right next one determine the number of directories contained within the Parent Directory represented by iode 19 describe the name of all the directories linked to this iode so that's IOD 19 is a directory and it's the parent of this directory right so well I know that let's give it a name so let's just say oh don't know let's call it directory directory D1 I don't know some mystery directory right so in some place in directory d1's parent it will have an entry that has like the name directory D1 19 right so it will have a name in some other directory maybe the root directory maybe I don't know some other directory who knows and then inside that directory right it will also have a name uh period that points to itself right and then in every other directory it will have it will be the parent of that so everything else whoops nope so in everything else in any other directory like I don't know uh call it C1 it'll have a dot dot to9 for example that one the one we're currently looking at and then every other par or every other directory inside of it will also increase the link by one because it will have a dot dot that will refer to it so every directory by default is going to have a link of two because it will have a DOT referring to itself also it will have a name somewhere else that refers to it so an empty directory will have two and then every other directory in that directory will increase the count by one because it will have a dot dot that points to it so another way you can think of it is just like that so the total link is five well it has the default two and then for every other directory inside of it it will have a dot dot dot dot also referring to it so it would have three directories in total within it so I don't know what their names are so C1 C2 C3 whatever so that okay with everyone sweet all right next one what occurs when you execute RMB is it possible for the file to be deleted so let's see let's get rid of some of this crap so if we remove remove file B what happens yeah it just removes the name from the directory so file B refers to iode 20 well file a also refers to iode 20 right so if I remove B all it does is remove this entry in the directory and now it's no longer pointing to iode 20 but file a still is so it's just going to decrease the count here to one so that file is not actually going to get deleted because there's still a name that refers to that iode so is it possible this file to be so remove name and then not deleted all right assuming B is removed what is the impact on C and the associated I noes so B is now gone does anything about C change no it just looks a bit red if you had color in your terminal because C is stored on Ino 20 its contents is point to B doesn't matter if the name b doesn't exist anymore you won't affect anything about C so the answer is nothing if file a is expanded to use 13 data blocks are only 13 data blocks required in total for its contents explain the storage mechanism so says we have an IOD and then we have in total 12 direct pointers one single indirect one double and one triple so if this file uses 13 data blocks all the way to 13 can I point to them all using just the I node no no I could point to 12 of them right so I could point to 12 da da du say this is up to 12 now how do I point to that last pesky block 13 indirect yeah I need a single indirect block right so I need to create a block here that's an indirect block so it's just a block full of pointers in this case I only need one pointer from it to point to block 13 so in total I would require 14 blocks right so 13 for data and then one for single indirect everyone okay with that all right next one how many total data blocks are needed if the file grows to 140 blocks strange uh explain the arrangements in the rational behind it so we got to do a bit of math so we need to figure out here the number of pointers per block so we have our block size from before which is 2 to the 12 and we have our pointer size which is 2 to the two so 2 the 12 I hate this room so 2 12 / 2 2 that's 2 10 so that is also equal to 1,24 so that's how many pointers I can fit on a block if my file contains all of that then I can refer to 12 direct I have my one single indirect and then that refers to 1,24 so in total that is40 right data blocks or can I not do math oh no I cannot do math so that's why maybe you want a calculator all right so that's 136 right so I still have four more blocks I need to store so my single indirect one is full so I need to do a double indirect one so for double indirect I need one double and this case it would need to point to one single so a new single one single which would just have in this case what is that four entries that point to other blocks so four data blocks so in total my data blocks here are 1,40 plus I needed one block for the single indirect one block for the double and one block for a single referred to by the double so in total I needed, 143 right hopefully that's right all right so now we are out of time so thank you for taking this class hopefully you enjoyed it good luck on Saturday and remember I'm pulling for you we're all in this together