GitLab Golang Study Group, 25 Oct 2019

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: 2019-10-25 Go study group

Description

Covering the dining philosopher problem using mutexes.

A

Okay cool, so what I did is I created a test on the left-hand side and a very simple mutex, based philosopher and fork implementation on the right here make this a little bigger just so it's easy to read and then on the right here. I was doing a little research into various visualizations of the problem and explanations. This is like one of the best ones. I found was the dining philosophers problem with Ron Swanson.

A

The best part about this is that happy, Ron and sad Ron are the exact same face: I love that it's just colleague, I just put some text at the bottom, so just to fill everyone in. Let you know people present here Ollie or people watching the recording just to fill everyone in on what the problem is. It's this classic computer science problem that is explaining resource contention when you have a number of parallel workers or concurrent workers that are trying to access shared resources.

A

So this can be like a process, a thread co-routine, something that is trying to access, something that another sibling entity is trying to access as well.

A

So in this problem here it's been illustrated with Ron Swanson's, so the Ron Swanson's could be like threads trying to access a shared resource, and the shared resource in this case are the forks there's five people at the table, five philosophers and then there's five forks, a fork between each of the Philosopher's, the issues that philosophers cannot eat unless they're holding both Forks. So that's not possible. It's not possible for all philosophers to eat at the same time since you need to have ten Forks five people, so there's a bit of resource contention here.

A

So if we can't share the forks, how do we coordinate this and the coordinating it's a bit complex like if you want to come up with something? That's really scalable, it's kind of hard to do so to illustrate this problem. I have a philosopher type over here and the philosopher has a left fork and a right fork and also an identification so that we can visualize who's doing what at one point in time when we run the tests, the fork itself also has an ID. So we know like where it is in the the table.

A

How to visualize it and it has a mutex, so mutex is an abbreviation for mutual exclusion. It's a it's a it's a primitive that makes sure that you control access to something in a mutual exclusive fashion, meaning that only one entity can have access to something at a time when you have access to something. No one else does so that's what a mutex does.

A

So the fork is modeled after a mutex, because once you grab the fork only you can have that fork. Someone else can't take it until you put it back down, so the act of picking up the fork is acquiring a lock on the mutex and then, when you put down the fork that is unlocking so in go. So let me pull up the docks for this just so we can see what we're talking about here.

A

So down here at the bottom of the screen, I have the go dock for the sink mutex. So you'll see here that it has two methods lock and unlock.

A

So, typically, what you do in a critical section in a program is in what I mean by critical section is a part of the program where you're accessing the shared resource.

A

You will lock first to signify that you have that mutual mutually exclusive, mutually mutually exclusive hold the lock to that critical area, and then, when you're done, you unlock it quite.

B

A

B

So let's say someone else has and I want to try to get access to it. What happens if I call lock on it when it's already blocked so.

A

What's going to happen is that you're going is gonna, be blocked until the lock is unreleased released? So, and this is not a deterministic thing- it's not like first-in first-out, just because you locked it before another philosopher tried to also acquire a lock. It doesn't mean that you're first in line it's not deterministic behavior, it's up to the go runtime. So what's going to happen, is it's gonna seem kind of random? Whoever the scheduler decides should get the should acquire. The lock is gonna get it.

A

So if we have two philosophers trying to acquire that lock at the same time, while someone else already has it, we don't know who's gonna get that, but yeah you'll be blocked until it happens, so you're you're just sitting there doing nothing, just twiddling your thumbs until the runtime gives you control of the lock.

A

Does that answer your question? Yeah, okay, yeah- and this is kind of this- is a problem with some of the sync primitives. Is that lets say you're waiting for a lock and you decide well if I can't get the lock within a certain amount of time. I just want to cancel well, you can't do that because your thread is just blocked like you can't do anything so there's nicer solutions using channels and other primitives, because, like channels, you can actually choose like either I.

A

Wait for this or I can wait for this expiration time and then do that. So that's that's another possibility.

A

You know I'll show an example of how that works. What's not so cool about you, Texas, like mutexes, are really nice because they're simple they're very easy to use, but they come with that minute. That minimalism comes with drawbacks essentially, but it works great for a lot of programs like if you can write really simple programs where you don't need to worry about blocking yourself forever, creating a deadlock, then they're really nice to use cuz how simple they are.

A

So the way that this works is that the philosopher isn't a is initially in a hungry state, and you can. You can tell that they're hungry by the drool coming out of their mouth right here, and so what happens is first, the philosopher tries to grab their left fork and then we're gonna print out. A message philosopher has left fork of this ID and I'll show you what that looks like so.

A

You can see here philosopher: zero got fork to zero, got left fork to zero whoops and then philosopher. Zero got fork, zero and fork one so now they're eating chicken right, that's what the little chicken sign is. Is that they're eating and then they do some work. So we have simulated work here where the philosopher sleeps and then once the philosophers done, the philosopher will put down the left fork and then put down the right fork and then proceed to thinking.

A

So the philosopher is always going from being hungry eating thinking it's going through these three different states and it's supposed to it's supposed to simulate like you're waiting for some resource and then once you've acquired that resource. You do some work with it and then you're waiting for it again. Are you doing work without the resource, so you're going through these different states or in our programs like a lot of times?

A

If we have something, that's like Network IO, based we're waiting for something to get transmitted over the network or maybe from a disk or sometimes we're doing something, CPU intensive, where we're calculating something we're crunching, a bunch of numbers and we're just kind of taking up some time to do that.

A

So that's what these sleeps are supposed to simulate and the times here are not precise, like they're all at the whim of when the scheduler hits that line of code and the scheduler runs go routines differently like depending on when it gets to the point to where it can schedule something to run.

A

So there's a lot of imprecise things going on here in deterministic things going on because of the nature of the go run time to go scheduler so yeah we're just going through a number of loops where we're just trying to acquire the locks left fork right fork. We do some work, then we put it down and then repeat over and over again for the sake of the test.

A

I didn't want to have too many logs being printed out, so what I did is and there's some small number like, let's see here, I think we set into three yeah. So it's just running three loops of what I just described and there's five philosophers. So we have a table made up of five philosophers.

A

We do a little setup here. All this is doing is really creating a circular array where each philosopher has the left-right Fork and then the next philosopher. You know we just switch. We just shift over and so the right fork becomes the left fork and so on. Until you get to the last person shares a fork with the first person, so it's just a circular array we're basically implementing a circular table using a slice.

A

So that's what's going on over here and then we're also starting all of the routines for each philosopher, but we're not starting any work yet we're doing a little bit of coordination just so that we have a higher likelihood of running into resource contention. So basically we don't want to have each since we're doing very little work. We don't want to have each philosopher just do all of its cycles, really quick and then get done before the next philosopher starts. We don't we don't want that.

A

We want them to be all queued up like at a race. We want them at a starting line. So that's why we have this channel right here start. You can think of this, like a starter pistol where we're lining up all the philosophers and we're saying don't start eating until I shoot this pistol, and that's what this line right here on 31 is doing. It's saying, I want you all to start once you see this signal and they won't all see the signal at the exact same time, but it'll be a lot closer in time.

A

Then, if we were to start them immediately, because the ghost scheduler has a little bit of latency and setting up a go routine and getting it started like there's some set-up time involved.

A

If we just wait on this, this channel signal it'll be a relatively closer and so we'll see how the kind of results we're looking for better.

A

Another thing to note here is that we're using a sync, primitive called a wait group, so this wait group is how we keep track of how many go routines are currently running. The goal is that we want all of the Philosopher's to eat and think be hungry three times right. So that means that this loop over here on the right-hand side, this loop needs to exit eventually, so the loop exits over here when this funk is finished, running peanut run.

A

So what we want is to be notified when all of the philosophers have finished running so the weight group. What it does is you increment a counter? You say: I have one more go: routine I have one more go: routine I have one more over team and then inside of each go routine, you say: I'm done, I'm done, I'm done, so all the girl routines.

A

They tell you when they're done- and this is a a concurrency safe thing that we can use to manipulate the same number between a bunch of different go routines, and this is a common thing. You'll see and go for keeping track of all the Gerber teens that you're waiting. For so we add all of the we increment the counter for each go routine, and then we decrement it effectively by doing done and then hey Steve, how you doing good to see ya I'm.

C

Doing well, sorry, I didn't mean to bother you I just wanted to jump in no.

A

No no worries this is. This is also a social call, so you know feel free to just chat and say whatever jump in whatever you'd like so we're just going over weight groups, so the weight group, you know we're adding here we're subtracting here and then finally, we're waiting for that count to equal zero. At this point and that's when we know that all the philosophers have finished running their loops, so yeah, that's that's essentially the test.

A

It's a pretty simple test and that's kind of the problem is that it's too simple, it's it's not gonna work a hundred percent of the time it actually works. Some of the time, because this is an indeterminate stick thing, sometimes we're just lucky and all the philosophers will be able to eat. So what I? Don't.

B

If, if there is a deadlock, will this test just like hey at week, don't wait yeah.

A

They'll, hang so there's a test time out. I think the default test time out is something like, maybe 10 minutes or something or five minutes. We can manipulate that too.

A

Actually, they pull that up just so that we don't have to wait too long.

A

What is that? Timeout.

A

A

hmm I, don't know what is okay, I'll just kill it manually did.

C

Steve time loads, I'm done.

A

I'm at seconds, okay, so, let's put ten seconds: let's see what how that runs.

A

You got a fail.

D

A

Put in the wrong spot, oh, it has to be 10s right, yeah there we go so what it's gonna do is when it gets to a test, that's taking longer than 10 seconds, it's gonna fail and then it's gonna give us a printout of what the go routines were doing at that point time. So we can see here that we have the sink run time semaphore require mutex is where a bunch of these were stuck.

A

So we have remember, we have five philosophers, so we should have at least five go routines, one for each philosopher, and then we have some other go routines for like running the test. The main see here. What else do we have there's some other go routines that are put in there from the test infrastructure.

A

So yeah you can see where they're getting stuck like, for example, here dining philosophers getting stuck on line 29. So if we go back to line 29, let's see here it's trying to acquire a lock and it's just getting stuck it's just sitting there and that's why the test froze.

A

Let's see if there's a star.

B

They all I, don't.

A

Think so, let's go take a look, let's see here so line 29.

D

D

Scroll up a little bit line: 29 29, yes,.

B

So I guess they all picked up the left fork and they're all waiting for the right fork. Yeah.

A

And that's what actually happens if you look at this illustration on the right here? That's this deadlock right here. So in this deadlock, all the philosophers picked up the same fork and then they they are. They don't want to put it back down and try something else, they're just kind of waiting for someone else and that never happens because they're all like-minded. So that's a problem.

A

We've got resource contention and we can't move forward, but some of the times because the go run time is running things you know in deterministically. Sometimes it does work so I'll show you an example of that might have to run the test a few times yeah. Here we go so in this test case. Everything actually worked. It just happened to be the right random values in time allowed it to happen. So here we have philosopher zeros, hungry, philosopher, hungry, philosopher, picks, up fork. Number two philosopher three is still hungry.

A

You can see they they're going through the motions here.

A

If you look at the fork numbers, this is the really important thing to look at so like this is fork two and then this is fork. One fork for you can see that the same Forks are never picked up by the the same fork isn't used by two different philosophers at the same time, because the the mutex is preventing that from happening so yeah.

A

It just happened to work this time, but then on the following test, run he got stuck so this is not a good program, because it's working some of the time and the rest of the time, the program just crashes, it just stops dead in its tracks. So the the question is: how do we solve this problem?

A

How do we coordinate the usage of these Forks and the one of the simplest solutions to this problem? Well, it does anybody want to take a crack at it. Does anybody want to suggest anything before I just read one of the solutions, any ideas so solution is that if you're using two forks, you need to pick up the lower numbered fork first. So what does that mean?

A

That means that if you're the last person, you're gonna behave differently than everyone else, because everyone else the the lower numbered fork is the one to their left at least the way I've designed it in this program, so the lower number forcus to their left, and once you get to the last person it's on their right, so you're, basically making one person behave differently than all the others and it works.

A

It actually fixes the problem, but it does so at a cost and that's that it's actually slow, because only one person is eating at a time now, you've you've got all these you've got five philosophers. You can have at least two of them eating simultaneously right, because we have five Forks in order. The the the next lowest even number is for each philosopher needs to have two forks, so you can have two people eating at a time.

A

This solution only has one person at a time, so we're only half our potential throughput here so yeah, that's essentially the problem now how we actually implement this using the code that I've written that's what we could try to do today or we could try to experiment with some other things. Is there any questions here? Anything you want to see done before I try to shoehorn in this solution.

A

Yeah, so let me read that solution closely here, so you need to pick up the lowered number fork, lower numbered fork first, so inside each fork is an ID there's an integer. The integer is just incremented each time we place a fork between a philosopher, so what we need to do is instead of locking on left. First, we first need to look at left and C is left the lower number or the higher number right.

A

So what we could do is.

A

We need to have a low and a high fork right, and actually we don't have to do this inside the loop. We can do this outside the loop, because this is never going to change. So what I'll do here is we can have a low and high fork and.

A

See here's will do if.

A

If the philosophers left fork, ID is less than the right.

A

Then we'll set.

A

What we'll do is we'll set low to the the left right and then we'll set high.

A

Whoops, it's not proper, go syntax, we'll set low to PML and then the other one to PM dot R.

A

Otherwise, we'll do the the opposite. All right, we'll do high-low equals P ml p m dot r. Does that look correct did I make any mistakes there.

A

So then- and we could have also done this in the struct here- but I- don't really want to change that right now, just in case we want to go back to the old solution.

A

So now what we can do is we can try to acquire the lock on the low first right. So we're gonna go down here instead of we'll do that instead of this, we'll do that and likewise we're gonna go over here.

A

Instead of left, we're gonna, say the low unlock first and then we're gonna say the high. I matter.

B

What order you unlock them.

A

That's a good question: I'm, not sure I would imagine it does matter. This solution doesn't say that it matters yet, but we'll find out in a second we'll see. Okay, so let's see what happens with that, and also we want to update our logging because we're putting the wrong values here. So, instead of printing the left, we'll say low and then over here we'll have C ID and then hide ID, okay, I think we've replaced left and right everywhere. We can so, let's see what happens when we run that you.

A

So this is a thousand test iterations. What the race detector turned on.

A

So it did have a failure.

A

Test timed out after oh, you know what it was one test. Was it one tester.

D

C

I think I think the timeout is not pair test. It's like for the whole run like I wasn't like a thousand Thrones will not be done.

A

Okay: let's try to turn this down then do always 10,000 runs. That's why? Let's try to do 100 seconds for a hundred tests that should be done. Pretty quick, see how that goes past. So yeah, this solution works. But the problem is it's not as fast as it could have been right. We could have I think we could have finished close to twice as fast like if we're timing, this you know it took us to point 37 seconds to run a hundred iterations.

A

We might have gotten down to I, don't know a second or something, maybe a little more in that if we were able to get two philosophers eating at a time. So that's that's the issue of the solution. It's really simple gets the job done, but we're not taking advantage of our or multiple cores.

A

So what I'd like to do for next week is to get a problem set up for semaphores and one of the nice things about go is that we can actually use channels as semaphores.

A

We can use that to coordinate the various philosophers. So that's what I'll be getting done for next week. I wasn't able to get too much done for this week with my current workload, but I was hoping that this would be a good starting point just to kind of illustrate some of the the sink primitives and get people exposed to the problem. There's a number of different ways. We can attack this, so we can. We can kind of try them all another good website for looking at this program. Where was it?

A

Coursera has some go stuff on there. So if you want to do a Coursera class, that's a good place to get exposure to this. The other one I was looking at was geeks for geeks.

A

They have some good write-ups on the problem and then they have some I think it's pseudocode yeah. They have some pseudocode on how it works, so they have some C code at the bottom here. So there's uh there's a lot of interesting stuff here on how to do it via semaphores. It's gonna look up quite a bit different on go using channels. So that's what I'll be working on porting is getting a semaphore solution with the philosopher problem. Anybody have any questions about any of these problems.

A

Anything anyone wants to share.

A

Any NGO news or.

C

Yeah I guess I can show the latest article I read from the NGO post about our handling, which was quite nice. One thing that interested interested me was how you actually think of not exposing the earth.

C

So basically you know you can do Sentinel checks like create an error as a variable and then return that, but like people like this I just did not to do that, because then that becomes part of your API for the package I found out quite interesting and like was looking at, you bears recently uploaded their code style kite and they have the same suggestion like don't do that like create functions and stuff like, for example, and the quest package when find not found, you usually do use. The function is not exist function.

C

So I found that quite interesting like not to make the error value as a part of the API but make a function or or use the new era wrapping syntax. So.

A

This is actually recommended specifically when using the new wrapping. It's not like a general guideline as.

C

A general guideline like uber, does it as a general guideline and go said? Okay now, with the wrapping, you can do it much easier instead of having a function you just do is under to learn all its own. So.

A

With the with the wrapping you're, exposing like an interface or a type right, because you're saying the error, is this type or the error is adheres to this interface right yeah.

C

Let me check again because I don't remember it by heart. Now, oh it was like I found it quite interesting.

C

Yeah so basically they're saying used to function as well like the OS function, for example. So the error does not become part of the API, because if you want to change the error, that's for example, you want to change it. Final fun to file does not exist like or rename it or something like that, you that would be a breaking change if it's part of the API, so I found that quite interesting.

C

A

Cool I'm really looking forward to having mean everyone to standardize on this I thought people were standardized on Dave Cheney's package errors for longest time. A lot of people don't use it. A lot of people just return the air like they don't even wrap it a lot of times. Yes,.

C

Pretty much and like even I was looking at Huber's documentation like that. They said, for example, when you wrap an ER, don't say, fails to do like failed to open file under link to file, because this is something I'm guilty of like I've did I.

C

Did that and then, like one deep error bubbles up, it's gonna be failed to do this fail to do this, like it's gonna, be a lot of failed words, kind of things, so they said like try to think of wrapping us like just giving context not like saying fails to do X, for example, so cannot open file and then the error kind of thing so I find that quite interesting and yes, I agree like it seems like at first I thought everyone wanted to go to Dave Cheney and, like even the go team, we were really impressed and wanted to do it.

C

But yeah like like, for example, for the runner team. We do not use the wrapping from Dave Cheney yeah.

A

We don't use it on giddily either.

A

We just return a lot and you know I think sometimes the the wrapping, because when I use it at my old job, it was kind of used as a crutch because it had the the ability to do the stack traces or you have all the places that it occurred, that it was wrapped in your code and we use that to debug a lot of issues. But if you have really good testing, you shouldn't really be relying on stack traces. A lot like.

A

If you have good testing- and you have a good interface- you don't have to look at these really detailed stack traces because that's not going to scale and production like in production. You don't want to be looking at a million stack traces, yeah.

C

Exactly and like yeah like I, think go like removed to stack traces like like on purpose, because if you like, create a Java stack, trace or I ruby stack trace like me personally, I don't get any value out of it, just because it's so huge and so much information like you. Just look at the first few lines, try to understand what's going on and you ignore the rest kind of thing. Yeah.

A

I think, if your errors are, if there's enough rich information in the errors, that is enough for you to find out what the problem is, and if you don't have that richness and your errors, then relying on the stack trace is kind of leading you in the wrong direction. Because then you know you're gonna end up just using it as a crutch.

A

All the time you can't, you can't work without a stack trace, which is bad for when you want to actually deploy something into production, I mean, what's the what's the story for the errors and you're working on the gitlab. What is the control key.

B

A

Do you have a specific error story on there right now.

B

There I did see like errors wrap in a few places, but not everywhere so yeah like I, guess, I'm still learning about what the best practices but I kind of have a new question about errors that I came up before. Okay, you know how is there is like an error class, so I let's say I call a function and it's doing a bunch of stuff and like there's three different things that could go wrong and it's gonna return me in there. How do I know like which.

D

B

Of those three things went wrong without looking at the straining, because I feel like you, should look at the string to determine that.

C

And that's why I go 113 is like really awesome, because it provides you that kind of stuff so like, like ghost idea as all errors or values. Right so let's say your function is opening a file sending a request to a web server and writing to a file. So it can return three errors, so you would like have three error values. So, for example, like file does not exist, connection refused for the client and, for example, permission denied for writing the file.

C

So you can check on the error type that's returned and like go under like before. You had to use typecasting or type assertions for that, but now what go on 13 you can use is and as function I'll leave it. I left a link on the same chats that explains all this using is, and as I like, how you can like have a function, return, multiple arrow types and then check for dibs types, the Ango, it's usually called sentinel. I were checking like you're checking something outside. Oh dear, that's.

A

The is is the central yeah.

C

A

So only that that that's why a lot of api's work is they'll just have like at the package level. They'll define a bunch of variables that are predefined errors and those errors they might be like. Oh, the network failed or the disc failed, and you would just check you just check inequality. Just say: does my error equal this package error and then you don't have to look at the string. You just have to do the just the equality, because it's a pointer, it's it's got to be the exact same error.

A

The problem is when you want to wrap it in your adding context. A lot of times when people will do is they'll create a whole new error and they just add strings together. Just it's human readable, but it's not programmatic, like you can't manipulate that very easily in a go program. So yeah, that's what this is does. If you want to wrap it, you can still wrap it, but you can get to the cord at the kernel of it is going to be the actual error.

A

So you can compare the actual value like we've always done previously, or you can actually look at the the type of error and all this stuff was like possible before it's just that this makes it a lot easier and it kind of it standardizes the the practices like you could always use a type switch to look at what type and error was, and then you could say. Oh if it's this type of error, we want to do this kind of error handling. If this type will do that, that's always possible.

A

Cuz go has a type switch, but now they have it in this like convenient function and they have like, if it doesn't match this, it has like consistent behavior. It reads more like English when you look at it. So there's a lot of nice things about this, but a lot of this stuff is still possible. If you haven't adopted, go down 13 yet.

B

C

It shouldn't be due to feel like I. Imagine the cube. The CLI is still like a fairly small project overall, so I don't think we have any problems upgrading to 113.

A

Error handling is a great topic and go cuz. That's like one of the things that really stands out about goes always checking your errors. You know being very safe, like it's supposed to be a systems language, so you know we should be very cautious when we're building these systems, so I think it would be really worthwhile to have a series of problems just to practice error handling, and maybe we can do that after we wrap up this dining philosophers. We can look at how to use the new error API, like best practices.

A

Yeah, maybe even do some fun problems using errors like kind of abused them or something they'd be kind of fun. Yeah.

C

Like the only thing, I hate about the 1:13 error handling right now, as you like, if you have like an error type, your own error type, so a struct that implements the error interface at capacity, it can have the unwrap method or des flatted. So you have control over that. The only thing I hate as those interfaces basically are not exposed. They're like anonymous interfaces in the arab package, so checks during runtime one.

C

So you can't really know if someone someone implements t is interface or someone implements the unwrap interface since it's not really exposed and like it does not feel like it's very described. So that's one thing: I, don't like about the e 113 or handling.

A

I'll have to check that out. That's interesting, so you said that the the interface is not exported or no.

C

It's not because it's anonymous anonymous interface. So if you look at the source code source code, basically, you have anonymous interfaces to find inside of the function that that has a nice function and they do a type of search making sure that your struct implements that interface. But that interface is not exposed to you. So it feels like will be magic.

C

So if you have to spit magical method attached to it, it's gonna do stuff, but like it's not really explicit or like clear to you that it has to be in the specific order, since the interface is not exposed.

A

So they need something like IO dot, reader or IO dot, writer, just so that exactly.

C

Exactly so yeah just exactly it's something like that to make it more Jewish in a way because, like it's all about interfaces, lingo, alright, so like right now, it feels more conventional where anything.

A

Else I'll probably come I'd imagined that I'd be next released. They would do something like that, because I'm kind of feeling it out making sure everyone's happy and then what's there then they'll add in yeah.

B

A

You tonight everyone yeah, that seems to be their style, nice and slow.

A

Anything else anything anyone's interested in seen with the the dining philosophers next week, something that piques your interest with concurrency go routines.

A

I'm gonna try to keep the sessions with less problems just so that we have time like this to chat about whatever spend a little too much time on the the previous progression. So just oh, so I think we'll just stick to maybe like one little problem and then we'll iterate on it and then next time whatever people are interested in seeing whatever's, the logical progression will work to that. I'm gonna send this up to the repo and I'll share the the code in the in the go channel or in the slack Channel.

A

I think this is a good stopping point. So thanks everyone for participating, I, appreciate you all being here and I hope you had fun with a go talk. Maybe we should change it to go talk just so that you know it's not. It doesn't scare people away for having a study or think too hard. You know you can just come in here and chat about anything, go related and get to know the gitlab go community. That might be a good way to go about it, to make it a little less formal anyway.

A

Think about that and good talk new. You all have a good weekend have a good rest of your day. Hope to see you next week, new.

B