Giấy phép mở: được chia sẻ lại khi ghi công tác giả, được chỉnh sửa, được dùng thương mại.
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 trở lại. Bây giờ bạn đã biết về diện tích tĩnh, đống, chồng, bạn có bao nhiêu trong số đó phải quản lý, hệ thống quản lý được bao nhiêu trong số đó?
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 hãy thực sự đào sâu hơn vào vấn đề đó. Vì vậy, heap là bộ nhớ động. Như bạn đã thấy trước đó, đó là một hồ bơi lớn nó không nhất thiết phải liền kề, mặc dù mọi ký ức yêu cầu sẽ dẫn đến một vùng tiếp giá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 int, thì đó là sẽ cung cấp cho bạn 1.000 int liên tục. Sau đó tôi muốn thêm 1.000 int 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 giây đó có thể rất xa vời hoặc rất gần với bản gốc và có thể quay trở lại để quay lại, có thể tiếp giáp, 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 gọi nó. Bạn nó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ả những thứ đó là rác, và sau đó phải khởi tạo nó và sử dụng nó trước khi — Ý tôi là, bạn phải viết vào đó trước khi đọc nó. Bạn biết điều đó trước 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ý trí 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ề điều đó.
The stack space is also easy. Every time I make a function call, a new frame is created.
Không gian ngăn xếp cũng dễ dàng. Mỗi lần tôi gọi hàm , một khung mới sẽ được tạo ra.
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 lần chúng ta trở về 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ứ xung quanh. 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ó nhiều cách để giải quyết nếu bạn thực sự biết cách làm như một người chuyên nghiệp, nhưng phần lớn, bạn không có quyền truy cập vào đó. Bạn không thể 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 thì có. Bạn sẽ làm điều này khi viết trình biên dịch. Trên thực tế, bạn sẽ thực hiện điều đó một cách rõ ràng. Nhưng theo quan điểm của C, nó là bên 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.
Tuy nhiên, việc quản lý đống dữ liệu này lại khá khó khăn. Bạn không cần phải quản lý bộ nhớ nhiều về việc suy nghĩ xem nên di chuyển đồ vật ở đâu. Một lần nữa, hệ điều hành lại thực hiện điều đó.
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 phải suy nghĩ về quy mô của các yêu cầu bạn đưa ra và cách bạn làm việc với nó. Vậy thì chúng ta hãy thực sự nói về — chúng ta hãy hãy tìm hiểu sâu hơn về đ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. Việc phân bổ ngăn xếp ở đây thực sự rất nhanh. AR, dấu ngoặc vuông mở của một triệu — bùm! Thực sự nhanh nếu nó hiệu quả.
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ị sập. Nhưng nếu nó hoạt động thì sẽ nhanh. Vậy thì tuyệt quá. 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ớ chi phí bộ nhớ, chi phí bao nhiêu, bạn phải theo dõi bao nhiêu sổ sách kế toán để thực hiện việc 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 tin có thể được chia thành nhiều phần. Và đó thực sự là một vấn đề 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ậy chúng ta giải quyết sự phân mảnh như thế nào? là vấn đề cốt lõi ở đó. Và về mặt kỹ thuật, chúng tôi gọi đây là sự phân mảnh bên ngoài vì bạn có những thứ này. Có một thứ gọi là sự phân mảnh nội bộ.
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 lúc khác. Sau đây là một ví dụ về sự phân mảnh trông như thế nào. Vì vậy, bạn đưa ra yêu cầu R1 cho 100 byte. Bụp!
There's 100 bytes. Yay, we got our space. Then you make R2 for one byte. There, there's a byte.
Có 100 byte. Yay, chúng ta có được không gian của mình rồi. Sau đó 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?
Sau đó tôi giải phóng R1 — sự phân mảnh. Hai điểm đó là — bây giờ là trí nhớ của bạn đã được chia thành hai khu vực. Và khi bạn nói yêu cầu R3, thì R3 sẽ như thế nào?
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ó cao hơn không? Nó có đi xuống bên dưới không? Làm sao để thông minh về nơi để đặt R3 suy nghĩ về những gì mô hình quá khứ của bạn đã đượ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ị 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ớ dà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ì vậy, nếu bạn muốn đọc K&R, thì có một phần, 8.7, nói về một số tính năng mà chúng tôi không sẽ phải lo lắng về điều đó.
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ề một số ý 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ó cho người tiếp theo, gần 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.
Nhìn kìa. Và hóa ra đó là một danh sách được liên kết ngoại trừ khi bạn sẽ đến được phần cuối mà nó bao quanh phần đầ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ì vậy, nó giống như một danh sách liên kết tròn liên tục. Nó khá gọn gàng khi là một cấu trúc dữ liệu. Và tất cả các khối trống, tất cả các khối trống, đều được giữ ở đó.
So initially in the program before, we had this one big area.
Vì vậy, ban đầu trong chương trình trước, chúng tôi có một khu vực rộng lớn.
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à một lần tôi đã đưa ra một yêu cầu và sau đó đưa ra một yêu cầu thứ hai và giải phóng nó, bây giờ đột nhiên, chúng tôi gọi danh sách miễn phí của chúng tôi hiện có hai yếu tố trong danh sách liên kết tròn đó.
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.
Khu vực trên cùng và anh chàng phía dưới bây giờ là hai trong số các phần tử đó trong danh sách liên kết vòng tròn đó. Cũng hay đấy. Malloc hoạt động như thế nào? Vâng, malloc nói rằng anh đã đưa cho tôi một yêu cầu về kích thước.
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.
Bây giờ tôi phải tìm kiếm danh sách miễn phí của mình để xem liệu tôi có — Tôi có thể phục vụ bạn những kỷ niệm mà bạn mong muốn không? Vì vậy, nó trông giống như danh sách miễn phí và nó đi theo 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.
Hãy nhớ rằng đây là danh sách được liên kết. Ch-ch-ch-ch-ch. Chậm phải không? Xung quanh toàn bộ — nếu không tìm thấy gì, nó sẽ nói, xin lỗi, không có gì.
It returns null, okay? So that's important. Free — here's what free does. Here's a free space.
Nó trả về giá trị null, được chứ? Vậy thì điều đó quan trọng. Miễn phí - đây là những gì miễn phí mang lại. Đây là một không gian trống.
Here's a free space. 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.
Đây là một không gian trống. Bạn đang giải thoát cho anh chàng ở giữa. Vâng, một khi bạn được tự do, anh chàng ở giữa, Liệu chúng có nên hợp nhất thành một không gian trống lớn không? Vậy thì miễn phí phải có tác dụng.
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ì vậy, đột nhiên, bạn nhận ra rằng malloc không còn nữa — malloc là một lệnh gọi hàm, đúng không? Bạn đang thực hiện lệnh gọi hàm tới malloc. Vì vậy malloc không giống như lệnh return tức thời.
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 1 triệu, AR ngoặc vuông và ngoặc đóng 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 là 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 nhiều thời gian. Đầu tiên, chúng ta có chi phí chung của một lệnh gọi hàm, chúng ta vẫn chưa nói đến. Nhưng vẫn có một số chi phí phát sinh.
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 thì bạn biết rằng ngăn xếp sẽ ngày càng lớn, đúng không? Đây là lệnh gọi hàm. Mỗi lệnh gọi hàm đều làm tăng kích thước ngăn xếp. Vì vậy malloc có một chức năng — ngăn xếp chỉ phát triển để 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 cả stack và malloc đều — malloc sẽ ảnh hưởng đến heap, nhưng bạn phải phát triển ngăn xếp để có thể 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 sau đó phải đi hết danh sách miễn phí 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 bảng của nó và làm công việc của nó và thực hiện cơ chế bên trong của nó để đi theo danh sách tròn của nó để tìm hiểu xem bạn có gì. Và có thể là rất nhiều mảnh vụn.
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 thế nào để trả về giá trị null. Thật điên rồ. Trên thực tế, đó là trường hợp tệ nhất, phải không? Phải mất rất nhiều 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á theo chu kỳ đồng hồ. Chương trình của bạn cứ bị đình trệ. Và sau đó — Ồ, bạn sẽ không nhìn thấy nó đâu.
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 là — nếu bạn đang sống ở tốc độ một gigahertz, bạn sẽ nói như thế này, tôi đang đợi ở đây. Tôi có một số nơi cần phải đến.
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. Đi vòng quanh. Và bây giờ tôi đã chờ đợi suốt thời gian đó. Và rồi ngay cả lúc đó, anh vẫn không cho tôi thứ gì sao?
Really? So that's hard, okay?
Thật sự? Vậy thì khó phải không?
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 địa điểm như thế nào? Khi tôi đang tìm kiếm, làm sao tôi có thể chọn được địa điểm? Sau đây là một số cách phổ biến để thực hiện việc này. Vì vậy, cách phù hợp nhất là tôi sẽ xem xét 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 mỗi lần đóng băng khối tôi có trong danh sách tròn của mình, khối nào gần nhất với 100? Nếu tôi có 100 thì 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?
Anh chàng đầu tiên - nếu anh chàng đầu tiên tôi nhìn thấy là 100, xong. Đây là 100. Nhưng nếu tôi có 101, thì có lẽ tôi sẽ tiếp tục tìm số 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 rằng điều đó hơi — Tôi có thể cho 101, nhưng ai biết được liệu tôi có làm được không sau đó có vừa vặn hoàn toàn không? Cảm giác này gần giống như bạn đang thử quần áo vậy.
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ó hơi hơi chỗ này dài, chỗ kia ngắn. Không, tôi muốn vừa vặn hoàn hảo, vừa vặn nhất. Tôi phải tìm kiếm 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 sự đánh đổi ở đó. Nhưng tôi sẽ cung cấp cho bạn sự vừa vặn nhất có thể. Bây giờ nếu tôi có khoảng cách là 104 và bạn yêu cầu 100 thì sao?
Well, I now have a sliver of four. See that sliver? They're going to start to accumulate.
Vâng, bây giờ tôi có một mảnh bốn. Bạn có thấy mảnh đó không? Chúng sẽ bắt đầu tích tụ.
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ỡ đó vẫn là một yếu tố khác trong 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òn một ít thôi, chỉ có bốn. 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 thậm chí còn dài hơn. Ồ, ồ, ồ.
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?
Đầu tiên, phù hợp nói, được rồi, tôi sẽ có tên trong danh sách. Tôi tóm lấy gã đầu tiên mà tôi có thể nhanh nhất có thể. Vào đi, ra đi. Boop — có ai lớn hơn 100 không?
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ó, lớn hơn 100. Của anh, đi thô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ày bắt đầu xảy ra lúc ban đầ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 luôn có một điểm để bắt đầu của danh sách tròn này. Vâng, 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 này ở phía trước nếu tôi tiếp tục thực hiện động tác đầu tiên. Có rất nhiều hành độ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 nghĩ về việc đi từ đây đến đại dương sâu thẳm. Những viên sỏi ở đó, giống như, khi bạn bước qua những viên sỏi để đến được những tảng đá lớn ở phía 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.
Phù hợp tiếp theo nói rằng nó giống như phù hợp đầu tiên, đầu tiên phù hợp, ngoại trừ việc thay vì luôn luôn bắt đầu lúc đầu, nó quay. Lần trước tôi dừng lại ở đâu , tôi đều 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 như vậy. Vì vậy, sự phù hợp tiếp theo nói rằng, hãy nhớ lại nơi bạn đã ở và đi qua, À, lần sau tôi sẽ bắt đầu từ đó . Vậy thì tôi sẽ làm thế.
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ó phân phối các viên sỏi, nếu bạn nghĩ về điều đó, xung quanh điều đó. Và điều đó khá thú vị. Nó sẽ 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ó sự đánh đổi trong cả ba điều đó, và bạn có thể nghĩ đến khối lượng công việc mà có thể làm cho mỗi một 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ĩ như vậy. Tóm lại, đây là bài giảng bán kết về C — rất thú vị. Chúng ta sắp đến đích 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 ba hồ chứa bộ nhớ — lưu trữ tĩnh, ngăn xếp, đống. Tĩnh điện không chuyển động. Ngăn xếp tăng lên và giảm xuống với các lệnh gọi hàm, và đó là nơi các biến tạm thời của bạn và các thông 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 diễn ra hành động malloc của bạn, được chứ? Hành động free và malloc xảy 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 miễn phí malloc sẽ ảnh hưởng đến — phù hợp nhất, tìm cái mà mọi người đều tìm kiếm cho đến khi bạn tìm được cái vừa vặn 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.
Lần đầu tiên phù hợp, luôn bắt đầu từ đầu. Người đầu tiên khớp với người có giá trị bằng hoặc lớn hơn hơn không gian bạn yêu cầu. Và câu phù hợp nhất là — 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à sự phù hợp tiếp theo cũng giống như sự phù hợp đầu tiên ngoại trừ việc bạn luôn hãy nhớ bạn đang ở đâu và bắt đầu từ đó vào lần tới. Bài giảng tối nay đến đây là hết. Chúng ta sắp xong rồi, các bạn ạ.
Take care.
Bảo trọng.
Đă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.