"Using a program, demonstrate how the memory behaves when the user inputs 4 jobs of different size, showing:
- Available memory space
- Unused space after assigning each job
- Resulting space after each job is freed
Using the First Fit and Best Fit algorithms.
The user must input a minimum of 4 Jobs inside a 1024 KB memory, 24KB which are used for the OS itself. The jobs are stored in an array.
If the sum of all these jobs is bigger than the maximum capacity, it shows an error and the program closes.
After inputting the 4 jobs, you have the option to release a job out of the memory or insert a new job. (<- I'm here.)
If you choose to release a job, the program asks for which job to release, in which case if you choose the 3rd Job, the program will leave a 'hole' in memory in which to use later (array_job[2] = 0), and that memory will be 'freed'. However, that hole cannot be expanded or contracted, and the capacity of that hole will be the same as the 3rd Job's size. (I don't know how to define this.)
If you choose to insert a new job, the program will ask for the size of the job, and depending on the algorithm, it will insert the job into one of the 'freed' slots:
First Fit: It iterates through all the blocks in memory and finds the first 'hole' (from what I can tell, the first 0 it finds through the job arrays) of unallocated space in which the job will fit.
Best Fit: It iterates through all the blocks in memory and finds a 'hole' with the smallest unallocated space in which the job will fit. (While I do understand this algorithm, I don't know how to input it in code. I heard you have to sort the arrays and treat it as First Fit, but I'd need to revert it back afterwards, which I can't seem to do right.)
It needs the average validation methods, the most important ones being 'out of range' ones like if(used_memory>1000) and if(jobsize>block_capacity). I'm working on the code right now and it's a mess, but any help on getting my words into code would suffice.
>>95359
You're only simulating 1024k of "memory", for fuck's sake.
You do not need to be efficient.
A 1024 element array used as a bytemap would be perfectly acceptable: you're fannying about (and probably trying to invent sparse techniques from first principles) over allocating 4k.
int[1024] memory_map;
void fill_memory_map (int start, int size, int val) {for (i=start; i <= start+size; i++) memory_map[i]=val;}
int remove_process(int process) {int j=0;for (i=0; i<=1023; i++){if (memory_map[i]==process){memory_map[i]=0; j++}
return j; }
fill_memory_map(0,1023,0); //initialise
fill_memory_map(0,23,1); // "os"
fill_memory_map(blah)
remove_process(3)
fill_memory_map(find_first_fit(123),123,3);
fill_memory_map(find_best_fit(234),234,4); //bored now. You write this bit. It's possible to find both first and best fit in linear time, using a state machine. You should do this.
>>95359
Best fit is just first fit, but you keep a shadow of the result you were going to return, you keep chugging through memory seeing how much free space is after, and if it's less than the shadow you overwrite the shadow.
int find_free_space(int size){
int sh_start;
int sh_waste=1023;
int start;
int waste;
int state=0;
for (i=0;i<=1023; i++) {
if (state==0) { // searching
start = i;
if (memory_map[i]==0) {state=1;}}
if (state == 1) { // seeking
waste = i-start;
if (memory_map[i] != 0) {state=0; if (waste<sh_waste) {sh_waste = waste; sh_start=start;}}}
return (sh_start);} // error handling and edge conditions are your problem.
>>95402
You should probably also check that the block is larger than size; I'm just back from the pub, so I'm not really on top form for first-year CS questions.
>>95359
>However, that hole cannot be expanded or contracted, and the capacity of that hole will be the same as the 3rd Job's size. (I don't know how to define this.)
That's because you're using a suboptimal representation for your data.
What I recommend is to represent the memory as a dynamic array of "memory blocks". A "memory block", in this case, is a simple data structure with two fields: an unsigned integer indicating its size, and a boolean (or integer) indicating if the block is free or not.
If you use the schema I described, the solution to this part of the problem is simply to take the memory block that the third job used to occupy, and mark it as free. The size will remain the same.
>>95528
Don't need to bother with extents: there's only 1024 entries, so just use a bitmap.
>>95595
It's not about bothering or not. It's about using data structures that make the problem easier to think about and to solve. That's a fundamental part of algorithm design.
I don't know why you think that a bitmap is more convenient than my proposal, but I think mine is pretty decent.
>>95359
>I heard you have to sort the arrays and treat it as First Fit
You have been rused. It's just a search for a minimum; one of the simplest algorithms known to man.
If you're still reading, OP, here's the whole algorithmic part solved (to the extent that I could be bothered to verify) in Pascal. All it lacks is the user interaction parts, but that's the most boring stuff.
http://pastebin.com/Yf25yDE7
>>95616
Actually, it would be better if lines 100 through 104 were
>end;
>end;
>end; writeln('failed to insert '+jobname);
>end;
But that's a minor concern.
>>95616
>about using data structures that make the problem easier to think about and to solve.
Extents don't do that though. Bitmaps do.
>I don't know why you think that a bitmap is more convenient than my proposal
Because:
Allocate a process:
- loop from start to end setting values
Deallocate a proceds:
- loop across entire memory, zeroing all values equal to process number
Find first free space
- loop across entire bitmap, set pointer to start of free space when encountered; when you stop encountering free cells, see if space was large enough, if so return
Find best fit
- do above but cache best result and return that
Extents needlessly complicate the above two tasks, which is why you shouldn't be using them if you don't have to, and why you should bone up on algorithmics before climbing up on your high horse.
>>95672
Your model doesn't properly simulate memory fragmentation (as specified in the problem), while mine does.
Beyond that, I guess you do have a point. Let's just agree to disagree, then, as to which model is easier to use.
OP here.
>>95528 helped quite a lot, and I (barely) managed to make the First Fit algorithm work.
Here's the code, commented as much as I could with the current structure and what it lacks: http://pastebin.com/73r9umXy
I'll look at >>95616 and try to give it a proper read later, since as of now I've only been introduced to Java and this is an Operating Systems assignment. I only chose C++ because of convenience, and as basic as this is, I'm not used to programming yet.
>>95528
Oh, and as for why extents are needlessly complicated:
>>95528
>If you use the schema I described, the solution to this part of the problem is simply to take the memory block that the third job used to occupy, and mark it as free.
This is not true, because you also have to search for any free space immediately after the newly-freed extent and grow the newly-freed extent into it.
If you don't do this, you need an allocation algorithm that can cope with fragmented free space (which can never occur when using an allocation bitmap).
>>95700
(that is to say, "fragmented representions of contiguous free space").
>>95693
>you also have to search for any free space immediately after the newly-freed extent and grow the newly-freed extent into it.
The problem does not state that. It states the opposite.
> if you choose the 3rd Job, the program will leave a 'hole' in memory in which to use later (array_job[2] = 0), and that memory will be 'freed'. However, that hole cannot be expanded or contracted, and the capacity of that hole will be the same as the 3rd Job's size.
That's what I was talking about.
With your model, if two "holes" appear next to each other, they'll naturally merge together and become a single hole.
That's not necessarily bad in a real memory managing system, but I suspect that OP will later be asked to make a memory defragmentation algorithm based on the assumption that the holes retain their size.
>you need an allocation algorithm that can cope with fragmented free space
OP is not being asked to defragment or optimize the memory allocations in any way. If the new job doesn't fit in any of the existing free blocks, he must show an error and then exit.
>>95733
>OP is not being asked to defragment or optimize the memory allocations in any way.
While I'm not being asked to do it explicitly, the instructor might tell me otherwise. I can assume they want me to unite two adjacent free memory blocks into one and sum both capacity values, since that's what dynamic memory allocation seems to do either way. Not sure on how I would go on getting that into code, though I'll see what I can do.
>>95738
The problem says:
>it will insert the job into one of the 'freed' slots
It doesn't even remotely imply that the free slots should ever be merged.
Regardless, if you use the "extents" model and look at the code I provided, you'll see it only takes two or three additional lines of code when you are releasing a job.
>>95733
It's not defragmenting, because even though it's badly represented, the space is not actually fragmented.
Fragmentation would be when there's two free spaces with an allocated space in the middle, as described in the problem definition.
>>95745
>two or three lines
Actually, it's more like five or ten, but it's still simple, in my opinion.
