Video
Đăng bởi Ban biên tập OpenER ·
Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
DAN GARCIA
And welcome back. So now that you know about static area, the heap, the stack, how much of that do you have to manage, how much of that does the system manage?
Và chào mừng quay lại. Vậy là bây giờ bạn đã biết về vùng tĩnh, heap, stack, bạn phải quản lý bao nhiêu phần đó, và hệ thống quản lý bao nhiêu phần?
Let's actually dig deeper into that. So the heap is dynamic memory. As you saw before, it's a large pool it's not necessarily contiguous, although every memory request will result in a contiguous region.
Chúng ta cùng tìm hiểu sâu hơn về điều này. Vậy thì heap là bộ nhớ động. Như bạn đã thấy trước đây, nó là một vùng lớn không nhất thiết phải liên tiếp, tuy nhiên mỗi yêu cầu bộ nhớ sẽ dẫn đến một vùng liên tiếp.
If I say int, I want 1,000 ints, it's going to give you 1,000 ints continuously. Then I want another 1,000 ints.
Nếu tôi nói int, tôi muốn 1.000 ints, nó sẽ cấp cho bạn 1.000 ints liên tiếp. Rồi tôi muốn thêm 1.000 ints nữa.
That second 1,000 may be very far away or very close to the original and maybe back to back, maybe abutted, maybe far away. You don't know those things.
1.000 cái thứ hai đó có thể ở rất xa hoặc rất gần với cái ban đầu, và có thể nằm sát lại nhau, có thể tiếp xúc, hoặc có thể ở xa. Bạn không biết những điều đó.
As you saw before, this is how you call it. You say malloc, the size you want, how many bytes, you want and it returns uninitialized memory.
Như bạn thấy trước đây, đây là cách bạn gọi nó. Bạn gọi malloc, kích thước bạn muốn, bao nhiêu byte, bạn muốn và nó trả về bộ nhớ chưa được khởi tạo.
All that's garbage, and then have to initialize it and use it before — I mean, you have to write to it before you read from it. You know that before.
Tất cả đó là rác, rồi bạn phải khởi tạo nó và sử dụng nó trước — Ý tôi là, bạn phải ghi vào nó trước khi đọc từ nó. Bạn đã biết điều đó rồi.
How do you manage that memory? Well, code and static are easy. They don't grow, and they're managed by the operating system. So don't worry about it.
Bạn quản lý bộ nhớ đó như thế nào? Vâng, code và static thì dễ. Chúng không phát triển, và chúng được quản lý bởi hệ điều hành. Vì vậy đừng lo lắng về nó.
The stack space is also easy. Every time I make a function call, a new frame is created.
Không gian stack cũng dễ. Mỗi khi tôi thực hiện một lệnh gọi hàm, một khung mới được tạo.
Every time we return from a function call, that frame goes away and that stack pointer internally moves things around. And you can't get access to that explicitly.
Mỗi khi chúng ta quay lại từ một lệnh gọi hàm, khung đó biến mất và con trỏ ngăn xếp bên trong di chuyển mọi thứ. Và bạn không thể truy cập vào đó một cách rõ ràng.
There are ways around it if you really know how to do it as a pro, but for the most part, you don't get access to that. You don't control that explicitly.
Có những cách để làm điều đó nếu bạn thực sự biết cách làm như một người chuyên nghiệp, nhưng hầu hết thời gian, bạn không có quyền truy cập vào đó. Bạn không kiểm soát điều đó một cách rõ ràng.
The system does. You'll do when you're writing assembler. You actually will explicitly do that. But from the point of view of C, it's below your abstraction line.
Hệ thống làm điều đó. Bạn sẽ làm như vậy khi bạn viết mã máy. Bạn thực sự sẽ làm điều đó một cách rõ ràng. Nhưng từ góc độ của C, nó nằm dưới dòng trừu tượng của bạn.
Managing the heap is tricky, though. You don't have to do a lot of memory management in terms of thinking about where to move things around. Again, the OS is doing that.
Quản lý heap thì phức tạp. Bạn không phải làm nhiều quản lý bộ nhớ về việc suy nghĩ nơi để di chuyển mọi thứ. Một lần nữa, hệ điều hành đang làm việc đó.
But you need to think about the size of requests you make and how you work with it. So let's actually talk about — let's take a little deeper into that.
Nhưng bạn cần suy nghĩ về kích thước của các yêu cầu bạn thực hiện và cách bạn làm việc với nó. Vì vậy, hãy nói về — hãy đi sâu hơn vào điều đó.
You want malloc and free to be fast. Stack allocation was really fast here. AR, open square bracket of a million — boop! Really fast if it works.
Bạn muốn malloc và free phải nhanh. Cấp phát stack thực sự rất nhanh ở đây. AR, mở ngoặc vuông của một triệu — boop! Thực sự nhanh nếu nó hoạt động.
If it doesn't work, it crashes. But if it works, it's fast. So that's great. But you want malloc and free to be fast.
Nếu nó không hoạt động, nó sẽ bị lỗi. Nhưng nếu nó hoạt động, nó sẽ nhanh. Vậy thì tuyệt vời. Nhưng bạn muốn malloc và free phải nhanh.
You want to memorize memory overhead, how much overhead, how much bookkeeping you keep track of to do this. And you want to avoid fragmentation.
Bạn muốn ghi nhớ overhead bộ nhớ, bao nhiêu overhead, bạn phải theo dõi bao nhiêu để làm điều này. Và bạn muốn tránh sự phân mảnh.
You've probably heard of this with your disk, where you have — one file might be broken up into lots of pieces. And that's an issue, actually, with malloc, and that's probably the biggest issue.
Bạn có thể đã nghe nói về điều này với đĩa của bạn, nơi bạn có — một tệp có thể bị chia thành nhiều phần. Và đó là một vấn đề, thực ra, với malloc, và đó có lẽ là vấn đề lớn nhất.
So how do we deal with fragmentation is the core problem with that. And technically, we call this external fragmentation because you have these things. There is something called internal fragmentation.
Vì vậy, chúng ta xử lý sự phân mảnh như thế nào là vấn đề cốt lõi với điều đó. Và về mặt kỹ thuật, chúng ta gọi đây là phân mảnh bên ngoài vì bạn có những thứ này. Có một thứ gọi là phân mảnh bên trong.
We'll talk about that at some other time. So here's an example of what fragmentation looks like. So you put a request R1 for 100 bytes. Boop!
Chúng ta sẽ nói về điều đó vào một thời gian khác. Vì vậy, đây là một ví dụ về cách phân mảnh trông như thế nào. Vì vậy, bạn đưa ra một yêu cầu R1 cho 100 byte. Boop!
There's 100 bytes. Yay, we got our space. Then you make R2 for one byte. There, there's a byte.
Có 100 bytes. Tuyệt vời, chúng ta có không gian rồi. Rồi bạn tạo R2 cho một byte. Ở đây, có một byte.
Then I free R1 — fragmentation. Those two spots are — now your memory has been fragmented to two areas. And when you say request R3, what does R3 go?
Rồi tôi giải phóng R1 — phân mảnh. Hai chỗ đó — bây giờ bộ nhớ của bạn đã bị phân mảnh thành hai khu vực. Và khi bạn tạo yêu cầu R3, R3 đặt ở đâu?
Does it go above? Does it go below? How is it being smart about where to put R3 thinking about what your past pattern has been and what you should do?
Nó có đi lên trên không? Nó có đi xuống dưới không? Nó thông minh như thế nào khi quyết định nơi đặt R3, dựa vào những gì bạn đã làm trước đó và bạn nên làm gì?
So this is an interesting question how you manage this memory, how the system manages memory. You don't have to worry how the system will manage memory for you.
Vậy đây là một câu hỏi thú vị về cách bạn quản lý bộ nhớ này, cách hệ thống quản lý bộ nhớ. Bạn không cần phải lo lắng về cách hệ thống sẽ quản lý bộ nhớ cho bạn.
So if you want to read K&R, there's a section, 8.7, that talks about some features that we're not going to worry about.
Vậy nếu bạn muốn đọc K&R, có một phần, 8.7, nói về một số tính năng mà chúng tôi sẽ không đề cập đến.
But it talks about some idea that each block of memory actually has a header that says the size of the block. And I point it to the next guy, almost like a linked list.
Nhưng nó nói về ý tưởng rằng mỗi khối bộ nhớ thực sự có một tiêu đề cho biết kích thước của khối. Và tôi chỉ nó sang người tiếp theo, giống như một danh sách liên kết.
Look at that. And it turns out it's a linked list except when you get to the end in which it wraps around to the beginning again.
Hãy xem điều đó. Và hóa ra nó là một danh sách liên kết ngoại trừ khi bạn đến cuối thì nó quay lại từ đầu lại.
So it's kind of a continuous, circular linked list. It's kind of neat as a data structure. And all free blocks, all the free blocks, are kept in there.
Vậy nó giống như một danh sách liên kết tròn liên tục. Nó khá là gọn gàng như một cấu trúc dữ liệu. Và tất cả các khối trống, toàn bộ các khối trống đều được lưu ở đó.
So initially in the program before, we had this one big area.
Vậy nên ban đầu trong chương trình trước, chúng ta có cái vùng lớn này.
And once I made a request and then made a second request and freed it, now all of a sudden, we call our free list now has two elements in that circular linked list.
Và khi tôi thực hiện một yêu cầu rồi làm yêu cầu thứ hai và giải phóng nó, bây giờ đột nhiên danh sách trống của chúng ta lại có hai phần tử trong danh sách liên kết vòng đó.
The top area and the bottom guy are now two of those elements in that circular linked list. Kind of neat. How's malloc work? Well, malloc says you've given me a request some size.
Vùng phía trên và phần ở dưới bây giờ là hai trong số những phần tử đó trong danh sách liên kết vòng. Khá là gọn gàng. Malloc hoạt động như thế nào? Chà, malloc nói rằng bạn đã đưa cho tôi một yêu cầu với kích thước nào đó.
I have to now search my free list to figure out, do I have — can I serve you the memory you wanted? So it looks to free list, and it walks the free list.
Tôi phải tìm kiếm danh sách trống của tôi để xem, tôi có — tôi có thể cung cấp cho bạn bộ nhớ mà bạn muốn không? Vậy nó tìm kiếm trong danh sách miễn phí, và nó duyệt qua danh sách miễn phí.
Remember, it's a linked list. Ch-ch-ch-ch-ch. Slow, right? All the way around — if none are found, it says, sorry, nothing.
Nhớ lại, đó là một danh sách liên kết. Ch-ch-ch-ch-ch. Chậm, phải không? Quanh hết — nếu không tìm thấy cái nào, nó nói, xin lỗi, không có cái nào.
It returns null, okay? So that's important. Free — here's what free does. Here's a free space.
Nó trả về null, được không? Vậy điều đó rất quan trọng. Free — đây là những gì free làm. Đây là một không gian miễn phí.
You're freeing the guy in the middle. Well, once you're free the guy in the middle, shouldn't this coalesce into one big free space? So free has to do some work.
Bạn đang giải phóng cái ở giữa. Vâng, một khi bạn giải phóng cái ở giữa, thì cái này không nên liên kết thành một không gian miễn phí lớn không? Vậy free phải làm một số công việc.
So all of a sudden, you realize that malloc is no longer — malloc is a function call, right? You're making a function call to malloc. So malloc isn't like instant return.
Vậy đột nhiên, bạn nhận ra rằng malloc không còn là — malloc là một lệnh gọi hàm, đúng không? Bạn đang thực hiện một lệnh gọi hàm đến malloc. Vì vậy malloc không phải là trả về ngay lập tức.
AR of 1 million, AR square bracket and close bracket 1 million, that array request is really fast. Like, that next line is instant — basically one clock cycle.
AR của 1 triệu, AR dấu ngoặc vuông và dấu đóng ngoặc 1 triệu, yêu cầu mảng đó thực sự nhanh. Giống như, dòng tiếp theo là ngay lập tức — về cơ bản một chu kỳ xung nhịp.
But malloc could take a long time. First, we've got the overhead of a function call, which we haven't talked about yet. But there's some overhead to that.
Nhưng malloc có thể mất thời gian lâu. Đầu tiên, chúng ta có chi phí của một lệnh gọi hàm, mà chúng ta chưa nói đến. Nhưng có một số chi phí cho điều đó.
And at least you know that the stack has to grow, right? It's a function call. Every function call grows the stack. So malloc has a function — the stack grows just to call malloc.
Và ít nhất bạn biết rằng ngăn xếp phải phát triển, đúng không? Đó là một lệnh gọi hàm. Mỗi lệnh gọi hàm đều làm ngăn xếp phát triển. Vì vậy malloc có một hàm — ngăn xếp phát triển vừa để gọi malloc.
It's kind of funny how the stack and malloc both — malloc's going to affect the heap, but you got to grow the stack to even call a function, and that malloc is a function.
Thật buồn cười khi stack và malloc cả hai — malloc sẽ ảnh hưởng đến heap, nhưng bạn phải tăng stack để gọi một hàm, và malloc là một hàm.
But malloc has to then walk its free list.
Nhưng malloc phải duyệt danh sách trống của nó.
It has to look up its tables and do its stuff and do its internal mechanics to walk its circular list to find out what you've got. And maybe it's a lot of slivers.
Nó phải tra cứu các bảng của nó và làm công việc của nó và làm các cơ chế nội bộ để duyệt danh sách vòng của nó để tìm ra những gì bạn có. Và có thể có nhiều mảnh nhỏ.
Wow, you can imagine malloc takes a long time to return null. That's crazy. In fact, that's the worst case, right? It took all the time.
Wow, bạn có thể tưởng tượng malloc mất nhiều thời gian để trả về null. Điều đó thật điên rồ. Thực tế, đó là trường hợp xấu nhất, phải không? Nó tiêu tốn tất cả thời gian.
You paid the price in terms of clock cycles. Your program kind of stalls out. And then — oh, you won't see it.
Bạn đã phải trả giá bằng chu kỳ clock. Chương trình của bạn thực chất bị treo. Và rồi — oh, bạn sẽ không thấy được điều này.
But I mean, internally, if I were — if you were living at the speed of a gigahertz, you'd be like, I'm waiting here. I got some places to go.
Nhưng ý tôi là, bên trong, nếu tôi — nếu bạn sống ở tốc độ gigahertz, bạn sẽ nói, tôi đang chờ đây. Tôi có chỗ khác để đi.
No time, no time. Goes around. And now I waited all this time. And then even then, you didn't give me anything?
Không có thời gian, không có thời gian. Chu kỳ tiếp theo. Và bây giờ tôi đã chờ tất cả thời gian này. Rồi thậm chí sau đó, bạn vẫn không cho tôi cái gì cả?
Really? So that's hard, okay?
Thực sự hay sao? Vậy nên đó là khó khăn, được chứ?
So how do we choose the spot? As I'm searching, how do I choose the spot? Here are some common ways to do this. So best fit says I go through everybody.
Vậy chúng ta chọn vị trí như thế nào? Khi tôi đang tìm kiếm, tôi chọn vị trí như thế nào? Dưới đây là những cách phổ biến để làm điều này. Vậy best fit nói rằng tôi đi qua tất cả mọi người.
You ask for 100, and I say, of every single freeze block I have in my circular list, which is closest to 100? If I have 100, done.
Bạn yêu cầu 100, và tôi nói, của từng khối freeze duy nhất mà tôi có trong danh sách tròn của mình, cái nào gần nhất với 100? Nếu tôi có 100, xong.
The first guy — if the first guy I was looking at was 100, done. Here's the 100. But if I have 101, well, maybe I keep looking to find 100, okay?
Người đầu tiên — nếu người đầu tiên mà tôi đang xem là 100, xong. Đây là 100. Nhưng nếu tôi có 101, có lẽ tôi tiếp tục tìm để lấy 100, được không?
You can imagine that's a little — I could have given 101, but who knows if I would've had a perfect fit later? It's almost like you're trying on clothes.
Bạn có thể tưởng tượng điều đó hơi — Tôi có thể đã cho 101, nhưng ai biết liệu tôi có tìm được một lựa chọn hoàn hảo sau không? Nó gần giống như bạn đang thử quần áo.
It's not perfect, but it's kind of a little long here, little long there. No, I want the perfect fit, best fit. I got to search everybody to get that.
Nó không hoàn hảo, nhưng nó có chút dài ở đây, dài ở đó. Không, tôi muốn sự phù hợp hoàn hảo, best fit. Tôi phải tìm kiếm tất cả mọi người để có được điều đó.
You can see the trade offs there. But I will give you exactly the tightest fit I can. Now what if I had a gap of 104 and you ask for 100?
Bạn có thể thấy những sự cân đối ở đó. Nhưng tôi sẽ cho bạn chính xác kích thước phù hợp nhất mà tôi có thể. Bây giờ nếu tôi có một khoảng trống 104 và bạn yêu cầu 100?
Well, I now have a sliver of four. See that sliver? They're going to start to accumulate.
Chà, bây giờ tôi có một mảnh vụn bốn đơn vị. Thấy mảnh vụn đó không? Chúng sẽ bắt đầu tích lũy.
So think about that as these slivers become — now that sliver is still another element on my list. Now I have — I used to have 100.
Vì vậy hãy nghĩ về điều đó khi những mảnh vụn này trở thành — bây giờ mảnh vụn đó vẫn là một phần tử khác trên danh sách của tôi. Bây giờ tôi có — tôi từng có 100.
Now I have a little sliver of only four. And you might have a lot of these slivers that make my list even bigger. Ay ay ay.
Bây giờ tôi chỉ có một mảnh vụn nhỏ bốn đơn vị. Và bạn có thể có rất nhiều những mảnh vụn này làm cho danh sách của tôi còn lớn hơn. Ơi ơi ơi.
First fit says, all right, I come into the list. I grab the first guy I can fast as I can. Get in, get out. Boop — anybody bigger than 100?
First fit nói, được rồi, tôi đi vào danh sách. Tôi lấy cái đầu tiên mà tôi có thể nhanh nhất. Vào rồi ra. Boop — cái nào lớn hơn 100?
Nope, nope, yes, bigger than 100. Yours, go. As I start to use it, you might need to see a lot of these slivers start to happen at the beginning.
Không, không, có, cái lớn hơn 100. Của bạn, đi. Khi tôi bắt đầu sử dụng nó, bạn có thể cần thấy rất nhiều những mảnh vụn này bắt đầu xuất hiện ở đầu.
There's always a point it to the beginning of this circular list. Well, you can imagine the slivers might start to grow in the front.
Luôn có một điểm chỉ tới đầu của danh sách tròn này. Bạn có thể tưởng tượng những mảnh vụn có thể bắt đầu phát triển ở phía trước.
Now I have a lot of these slivers in the front if I keep doing first fit. There's a lot of action in there making a lot of pebbles.
Bây giờ tôi có rất nhiều những mảnh vụn ở phía trước nếu tôi tiếp tục làm first fit. Có rất nhiều hoạt động ở đó tạo ra rất nhiều viên sỏi.
Think about getting from here to the deep ocean. The pebbles are there, like, as you walk through the pebbles to get to the big rocks down low.
Hãy tưởng tượng việc đi từ đây ra tới đại dương. Những viên sỏi ở đó, như khi bạn bước qua những viên sỏi để tới những tảng đá lớn ở dưới.
Next fit says it's like first fit, first one that fits, except that rather than always start at the beginning, it rotates. Wherever I stopped last time, I'll remember that.
Next fit nói rằng nó giống như first fit, cái đầu tiên vừa, ngoại trừ rằng thay vì luôn bắt đầu từ đầu, nó quay vòng. Nơi tôi dừng lần trước, tôi sẽ nhớ điều đó.
And that's the next time I'll do it. So next fit says, remember where you were and go through, ah, that's where I'll start next time. So then I'll do that.
Và đó là lần tiếp theo tôi sẽ làm điều đó. Vì vậy next fit nói rằng, hãy nhớ nơi bạn ở và tiếp tục, à, đó là nơi tôi sẽ bắt đầu lần tiếp theo. Vì vậy sau đó tôi sẽ làm điều đó.
So it kind of distributes the pebbles, if you think about that, around that. And that's kind of interesting. It resumes searching for where you stopped last time.
Vì vậy nó có phân phối những viên sỏi, nếu bạn nghĩ về điều đó, xung quanh điều đó. Và đó là một điều thú vị. Nó tiếp tục tìm kiếm nơi bạn dừng lần trước.
And there are trade offs in all three of them, and you can think of workloads that might make each one of those three look really good or really bad.
Và có những sự cân bằng trong cả ba cái, và bạn có thể nghĩ ra những khối lượng công việc có thể làm cho mỗi cái trong ba cái đó trông thực sự tốt hoặc thực sự tệ.
You can think of that as well. In conclusion, this is the semifinal lecture in C — very exciting. We're almost at the end.
Bạn cũng có thể nghĩ về điều đó. Kết luận, đây là bài giảng bán kết trong C — rất thú vị. Chúng ta gần đến cuối rồi.
C three pools of memory — static storage, the stack, the heap. Static doesn't move. The stack grows and shrinks with function calls, and it's where your temporary variables are and your parameters.
C có ba vùng bộ nhớ — bộ nhớ tĩnh, stack, heap. Bộ nhớ tĩnh không di chuyển. Stack phát triển và co lại theo lời gọi hàm, và đó là nơi các biến tạm thời của bạn ở và các tham số của bạn.
And the heap is where your malloc action happens, okay? That free and malloc action happens.
Và heap là nơi hành động malloc của bạn diễn ra, được không? Đó là chỗ hành động free và malloc diễn ra.
Three ways to deal with the free list that malloc's going to affect — best fit, find the one that search everybody until you find the one that just snugly fits the best.
Ba cách để xử lý danh sách free mà malloc sẽ ảnh hưởng tới — best fit, tìm cái mà tìm kiếm tất cả cho đến khi bạn tìm thấy cái vừa khít nhất.
First fit, always start at the beginning. The first guy that matches that's equal to or bigger than the space you're asking for. And best fit says — sorry.
First fit, luôn bắt đầu từ đầu. Cái đầu tiên khớp với điều kiện bằng hoặc lớn hơn không gian mà bạn đang yêu cầu. Và best fit nói — xin lỗi.
And next fit says the same as first except that you always remember where you were and start there next time. That's it for tonight's lecture. We're almost there, folks.
Và next fit nói giống như first ngoại trừ việc bạn luôn nhớ nơi bạn đã dừng lại và bắt đầu ở đó lần tiếp theo. Thế là xong bài giảng tối nay. Chúng ta sắp hoàn thành rồi, các bạn.
Take care.
Hẹn gặp lại.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.