운영 체제 실험의 메 인 메모리 공간의 분배 와 회수

smilesword.com
1. 실험 목적
좋 은 컴퓨터 시스템 은 충분 한 용량, 액세스 속도 가 높 고 안정 적 이 며 신뢰 할 수 있 는 메 인 메모리 가 있어 야 할 뿐만 아니 라 이러한 저장 공간 을 합 리 적 으로 분배 하고 사용 할 수 있어 야 한다.사용자 가 메모리 공간 을 신청 할 때 저장 관 리 는 반드시 신청자 의 요구 에 따라 일정한 전략 에 따라 메 인 저장 공간의 사용 상황 을 분석 하고 충분 한 여유 구역 을 찾 아 신청자 에 게 분배 해 야 한다.작업 이 철수 하거나 메 인 저장 자원 을 자발적으로 반환 할 때 저장 관 리 는 작업 이 차지 하 는 메 인 저장 공간 을 회수 하거나 일부 메 인 저장 공간 을 반환 해 야 한다.메 인 메모리 의 분배 와 회수 의 실현 은 메 인 메모리 의 관리 방식 과 관련 이 있 지만 이 실험 을 통 해 학생 들 이 서로 다른 저장 관리 방식 에서 메 인 메모리 공간의 분배 와 회 수 를 어떻게 실현 해 야 하 는 지 이해 하도록 도와 준다.
2. 실험 내용
이 실험 은 두 가지 저장 관리 방식 에서 의 메 인 저장 배분 과 회 수 를 모 의 한다.
3. 힌트 와 설명
이 실험 은 두 문제 가 있 는데, 학생 들 은 그 중의 한 문 제 를 선택 하여 실험 을 할 수 있다.
첫 번 째 문제: 가 변 구역 관리 방식 에서 가장 먼저 적응 하 는 알고리즘 을 사용 하여 메 인 저장 분 배 를 실현 하고 메 인 저장 회 수 를 실현 한다.
가 변 파 티 션 방식 은 작업 에 필요 한 메 인 저장 공간 크기 에 따라 파 티 션 을 나 누 는 것 이다.작업 을 불 러 올 때 작업 에 필요 한 주 저장량 에 따라 충분 한 여유 공간 이 있 는 지 확인 하고 있 으 면 수 요 량 에 따라 파 티 션 을 나 누 어 작업 에 할당 합 니 다.없 으 면 작업 을 불 러 올 수 없습니다.작업 의 불 러 오기, 철수 에 따라 메 인 저장 공간 은 여러 개의 구역 으로 나 뉘 고 어떤 구역 은 작업 에 의 해 점용 되 며 어떤 구역 은 비어 있다.예 를 들 면:
시스템
숙제
숙제
빈 공간
숙제
빈 공간
어떤 구역 이 비어 있 는 지 설명 하기 위해 서 는 새 작업 을 불 러 올 수 있 습 니 다. 빈 공간 설명 표 가 있어 야 합 니 다. 형식 은 다음 과 같 습 니 다.
주소
길이
상태.
제1 란
14 K
12 K
할당 되 지 않 음
제2 란
32 K
96 K
할당 되 지 않 음
 
빈 목록
빈 목록
 
그 중에서 시작 주소 - 빈 공간 에 있 는 메 인 저장 소 시작 주 소 를 알려 줍 니 다.
길이 - 시작 주소 부터 의 연속 적 인 남 은 길 이 를 알려 줍 니 다.
상태 - 두 가지 상태 가 있 는데 하 나 는 '미분 배' 상태 로 주소 가 가리 키 는 특정한 길이 의 구역 이 빈 구역 임 을 지적한다.다른 하 나 는 '빈 목록' 상태 로 표 에 대응 하 는 등록 항목 이 공백 (무효) 임 을 나타 내 며 새로운 빈 공간 을 등록 할 수 있 습 니 다 (예 를 들 어 작업 이 철수 한 후에 그 가 차지 하 는 구역 은 빈 공간 이 되 므 로 '빈 목록' 표시 줄 을 찾 아 반환 구역 의 주소 와 길 이 를 등록 하고 상 태 를 수정 해 야 합 니 다).구역 의 개수 가 정 해 지지 않 기 때문에 빈 구역 설명 표 에는 적당 한 상태 가 '빈 목록' 인 등록 항목 이 있어 야 한다. 그렇지 않 으 면 표 가 넘 쳐 등록 할 수 없다.
상술 한 이 설명 표 의 등록 상황 은 제시 (1) 중의 예 에 따라 불 러 온 세 개의 작업 이 차지 하 는 메 인 저장 구역 에 따라 작성 한 것 이다.
(2) 새 작업 이 메 인 저장 소 를 불 러 오 라 고 요구 할 때 빈 공간 설명 표를 찾 아 충분 한 빈 공간 을 찾 아야 한다.때때로 찾 은 빈 공간 은 작업 수 요 량 보다 많 을 수 있 습 니 다. 이 때 는 원래 의 빈 공간 을 두 부분 으로 바 꿔 야 합 니 다. 일 부 는 작업 에 나 누 어 사용 해 야 합 니 다.다른 부분 은 또 하나의 작은 빈 공간 이 되 었 다.분할 로 인 한 빈 공간 을 최소 화하 기 위해 서 는 높 은 주소 부분 에 비교적 큰 연속 빈 공간 을 저장 하여 대형 작업 의 불 러 오기 에 유리 하도록 한다.이 를 위해 빈 공간 설명 표 에서 모든 빈 공간 을 주소 순서대로 등록 합 니 다. 즉, 모든 후계 의 빈 공간 은 시작 주소 가 항상 전자 보다 큽 니 다.편리 하 게 찾기 위해 서 는 표 의 '긴축' 을 위해 항상 '빈 표 항목' 표시 줄 을 표 의 뒷부분 에 집중 시 킵 니 다.
(3) 가장 먼저 적응 하 는 알고리즘 (순서 분배 알고리즘) 을 사용 하여 메 인 저장 공간 을 분배 한다.
작업 의 수 요 량 에 따라 빈 공간 설명 표를 찾 고 순서대로 등록 란 을 살 펴 보고 요 구 를 만족 시 킬 수 있 는 첫 번 째 빈 공간 을 찾 습 니 다.빈 공간 이 수 요 량 보다 많 을 때 일 부 는 작업 을 불 러 오 는 데 사용 되 고 다른 일 부 는 빈 공간 설명 표 에 등 록 됩 니 다.
이 실험 은 메 인 저장 소의 분 배 를 모 의 하 는 것 이기 때문에 메 인 저장 소 를 작업 에 할당 한 후 불 러 오 는 프로그램 을 실제 시작 하지 않 고 출력 '분배 상황' 으로 대체 합 니 다.가장 먼저 분배 알고리즘 에 적응 하 는 것 은 그림 4 - 1 과 같다.
(4) 작업 수행 이 끝나 고 철수 할 때 작업 이 차지 하 는 구역 은 반환 해 야 한다. 반환 하 는 구역 이 다른 빈 공간 과 인접 하면 비교적 큰 빈 공간 을 합성 하여 빈 공간 설명 표 에 등록 해 야 한다.예 를 들 어 알림 (1) 에 열 거 된 상황 에서 작업 2 가 철수 하면 메 인 저장 구역 을 반환 할 때 상하 와 인접 한 빈 공간 과 함께 큰 빈 공간 을 합성 하여 빈 공간 설명 표 에 등록 해 야 한다.메 인 저장 소 를 반환 할 때의 회수 알고리즘 은 그림 4 - 2 와 같다.
(5) 가장 먼저 적응 하 는 알고리즘 에 따라 메모리 분배 와 회수 프로그램 을 설계 하 십시오.그 다음 에 (1) 에서 메 인 저장 소 에 세 개의 작업 을 불 러 왔 고 두 개의 빈 공간 을 형성 하여 빈 공간 설명 표 의 초기 값 을 확인한다 고 가정 합 니 다.현재 메 인 저장량 이 6K 인 작업 4 가 메 인 저장 소 를 불 러 오 기 를 신청 합 니 다.그리고 작업 3 철수;재 작업 2 철수.메 인 저장 소 를 할당 하고 회수 하 십시오. 빈 공간 설명 표 의 초기 값 과 매번 할당 하거나 회수 한 후의 변 화 를 표시 하거나 인쇄 하 십시오.
솔직히 나 는 이것 에 대해 매우 만 족 스 럽 지 못 하 다. 아마도 밤 을 새 우 는 데다 가 시간 이 촉박 해서 코드 를 아주 엉망 으로 썼 기 때 문 일 것 이다 (). 그래도 붙 여 놓 고 시간 이 있 으 면 직접 보고 고 쳐 라.

#include 
#include 

typedef struct task
{
	int name; /*   */
	int add;
	int length; /*    ，      */
	struct task *next;/*             */

}
nodet;

typedef struct chart
{
	int add;
	int length;
	int status;
	struct chart *next;
}
nodec;

nodet* headt;
nodec* headc;

void init()
{
	nodet* t;
	nodec* c;
	headt = (nodet*)malloc(sizeof(nodet));
	headc = (nodec*)malloc(sizeof(nodec));

	t = headt->next = (nodet*)malloc(sizeof(nodet));
	c = headc->next = (nodec*)malloc(sizeof(nodec));

	t->name = 1;
	t->add = 5;
	t->length = 5;
	c->add = 14;
	c->length = 12;
	c->status = 0;

	t = t->next = (nodet*)malloc(sizeof(nodet));
	c = c->next = (nodec*)malloc(sizeof(nodec));

	t->name = 3;
	t->add = 10;
	t->length = 4;
	c->add = 32;
	c->length = 96;
	c->status = 0;
	c->next = NULL;

	t = t->next = (nodet*)malloc(sizeof(nodet));

	t->name = 2;
	t->add = 26;
	t->length = 6;
	t->next = NULL;
}

void printLink()
{
	nodec* p;
	p = headc->next;
	printf("   ADD   LENGTH
");
	while(p)
	{
		printf("   %dK     %dK
",p->add,p->length);
		p=p->next;
	}
}

int taskIn(int name,int length)
{
	int done = 0,add;
	nodec *b,*c;
	c = headc->next;
	if (!c)
	{
		return 0;
	}
	else
	{
		while(c)
		{
			if (c->length < length)
			{
				b = c;
				c = c->next;
			}
			else if (c->length > length)
			{
				c->length = c->length - length;
				//c->add = c->add - length;
				add = c->add;
				done = 1;
				break;
			}
			else if (c->length == length)
			{
				if (headc->next == c)
				{
					add = c->add;
					headc->next = c->next;
					free(c);
				}
				else
				{
					add = c->add;
					b->next = c->next;
					free(c);
				}
				done = 1;
				break;
			}
		}
		if (done == 0)
		{
			return 0;
		}
	}

	nodet* t;
	t = headt->next;
	if (t != NULL)
	{
		while(t->next)
		{
			t = t->next;	
		}
		t->next = (nodet*)malloc(sizeof(nodet));
		t = t->next;
		t->name = name;
		t->add = add;
		t->length = length;
	}
	else
	{
		t = headt->next = (nodet*)malloc(sizeof(nodet));
		t->name = name;
		t->add = add;
		t->length = length;
	}
	printLink();
	return 1;
}

int taskOut(int name)
{
	int add,length;
	nodet *t,*k;
	t = headt->next;
	while (t)
	{
		if (t->name == name && headt->next == t)
		{
			add = t->add;
			length = t->length;
			headt->next = t->next;
			free(t);
			break;
		}
		else if (t->name != name)
		{
			k = t;
			t = t->next;
		}		
		else if (t->name == name && headt->next != t)
		{
			add = t->add;
			length = t->length;
			k->next = t->next;
			free(t);
			break;
		}
	}

	nodec *c,*b;
	c = headc->next;
	if (c != NULL)
	{
		while(c)
		{
			if (c == headc->next && add < c->add)
			{
				if ((add + length) == c->add)
				{
					c->add = add;
					c->length = c->length + length;
					printLink();
					return 1;
				}
				b = (nodec*)malloc(sizeof(nodec));
				b->add = add;
				b->length = length;
				headc->next = b;
				b->next = c;
				printLink();
				return 1;
			}	
			else if (c != headc->next)
			{
				if ((b->add + b->length) != add && (add + length) != c->add)
				{
					b->next = (nodec*)malloc(sizeof(nodec));
					b->next->next = c;
					b->next->add = add;
					b->next->length = length;
					printLink();
					return 1;
				}
				else if ((b->add + b->length) == add && (add + length) != c->add)
				{
					b->length = b->length + length;
					printLink();
					return 1;
				}
				else if ((b->add + b->length) != add && (add + length) == c->add)
				{
					c->add = add;
					c->length = c->length + length;
					printLink();
					return 1;
				}
				else if ((b->add + b->length) == add && (add + length) == c->add)
				{
					b->length = b->length + length + c->length;
					b->next = c->next;
					free(c);
					printLink();
					return 1;
				}
				else
				{
					b = c;
					c = c->next;
				}
			}
			else if (c == headc->next && add < c->add)
			{
				if ((add + length) < c->add)
				{
					headc->next = (nodec*)malloc(sizeof(nodec));
					headc->next->next = c;
					c = headc->next;
					c->add = add;
					c->length = length;
					printLink();
					return 1;
				}
				else if ((add + length) == c->add)
				{
					c->add = add;
					c->length = c->length + length;
					printLink();
					return 1;
				}
			}
			else
			{
				b = c;
				c = c->next;
			}
		}
	}
}

int main(void)
{
	init();
	printLink();
	taskIn(4,6);
	taskOut(3);
	taskOut(2);
}