the-ze

가상 페이지라고도 불리는 “페이지”는, 4,096 바이트(페이지 크기)의 길이를 가지는 가상 메모리의 연속된 영역이다. 페이지는 반드시 페이지에 정렬(page-aligned)되어 있어야 한다. 즉, 각 페이지는 페이지 크기(4KiB)로 균등하게 나누어지는 가상 주소에서 시작해야 한다는 말이다.

그러므로 64비트 가상주소의 마지막 12비트는 페이지 오프셋(또는 그냥 “오프셋”)이다. 상위 비트들은 페이지 테이블의 인덱스를 표시하기 위해 쓰인다. 64비트 시스템은 4단계 페이지 테이블을 사용하는데, 아래 그림과 같은 가상주소를 만들어준다.

63          48 47            39 38            30 29            21 20         12 11         0
+-------------+----------------+----------------+----------------+-------------+------------+
| Sign Extend |    Page-Map    | Page-Directory | Page-directory |  Page-Table |    Page    |
|             | Level-4 Offset |    Pointer     |     Offset     |   Offset    |   Offset   |
+-------------+----------------+----------------+----------------+-------------+------------+
              |                |                |                |             |            |
              +------- 9 ------+------- 9 ------+------- 9 ------+----- 9 -----+---- 12 ----+
                                          Virtual Address

각 프로세스는 KERN_BASE (0x8004000000) 미만의 가상주소값을 가지는 독립적인 유저(가상)페이지 집합을 가진다. 반면에 커널(가상)페이지 집합은 전역적이며, 어떤 쓰레드나 프로세스가 실행되고 있든 간에 항상 같은 위치에 남아 있다. 커널은 유저 페이지와 커널 페이지 모두에 접근할 수 있지만, 유저 프로세스는 본인의 유저 페이지에만 접근할 수 있다.

물리 프레임 또는 페이지 프레임이라고도 불리는 프레임은, 물리 메모리 상의 연속적인 영역이다. 페이지와 동일하게, 프레임은 페이지사이즈여야 하고 페이지 크기에 정렬되어 있어야 한다. 그러므로 64비트 물리주소는 프레임 넘버와 프레임 오프셋(또는 그냥 오프셋)으로 나누어질 수 있다. 아래 그림처럼 말이다.

                          12 11         0
    +-----------------------+-----------+
    |      Frame Number     |   Offset  |
    +-----------------------+-----------+
              Physical Address

x86-64 시스템은 물리주소에 있는 메모리에 직접적으로 접근하는 방법을 제공하지 않는다. Pintos는 커널 가상 메모리를 물리 메모리에 직접 매핑하는 방식을 통해서 이 문제를 해결한다 - 커널 가상메모리의 첫 페이지는 물리메모리의 첫 프레임에 매핑되어 있고, 두번째 페이지는 두번째 프레임에 매핑되어 있고, 그 이후도 이와 같은 방법으로 매핑되어 있다. 그러므로 커널 가상메모리를 통하면 프레임들에 접근할 수 있다.

페이지 테이블은 CPU가 가상주소를 물리주소로, 즉 페이지를 프레임으로 변환하기 위해 사용하는 자료구조이다. 페이지 테이블 포맷은 x86-64 아키텍쳐에 의해 결정되었다. Pintos는 threads/mmu.c안에 페이지 테이블을 관리하는 코드를 제공한다.

아래 도표는 페이지와 프레임 사이의 관계를 나타낸다. 왼쪽에 보이는 가상주소는 페이지 넘버와 오프셋을 포함하고 있다. 페이지 테이블은 페이지 넘버를 프레임 넘버로 변환하며, 프레임 넘버는 오른쪽에 보이는 것처럼 물리주소를 획득하기 위한 미수정된 오프셋과 결합되어 있다.

                           +----------+
          .--------------->|Page Table|-----------.
         /                 +----------+           |
        |   12 11 0                               V  12 11 0
    +---------+----+                         +---------+----+
    | Page Nr | Ofs|                         |Frame Nr | Ofs|
    +---------+----+                         +---------+----+
     Virt Addr   |                            Phys Addr    ^
                  \_______________________________________/

스왑 슬롯은 스왑 파티션 내의 디스크 공간에 있는 페이지 크기의 영역이다. 하드웨어적 제한들로 인해 배치가 강제되는 것(정렬)이 프레임에서보단 슬롯에서 더 유연한 편이지만, 정렬한다고 해서 별다른 부정적인 영향이 생기는 건 아니기 때문에 스왑 슬롯은 페이지 크기에 정렬하는 것이 좋다.

각 자료구조에서 각각의 원소가 어떤 정보를 담을지를 정해야 했었다. 또한 자료구조의 범위를 지역(프로세스별)으로 할지, 전역(전체 시스템에 적용)으로 할지도 정해야 하고, 해당 범위에 필요한 인스턴스의 수도 결정해야 한다. 설계를 단순화하기 위해, non-pageable 메모리 (calloc 이나 malloc 에 의해 할당된)에 이러한 자료구조들을 저장할 수 있다.

userprog/process.c에 있는 load_segment와 lazy_load_segment를 구현해야 했다. 실행파일로부터 세그먼트가 로드되는 것을 구현하고, 구현된 모든 페이지들은 지연적으로 로드될 것이다. 즉 이 페이지들에 발생한 page fault를 커널이 다루게 된다는 의미이다.

program loader의 핵심인 userprog/process.c 의 load_segment loop 내부를 수정해야 했다. 루프를 돌 때마다 load_segment는 대기 중인 페이지 오브젝트를 생성하는vm_alloc_page_with_initializer를 호출한다. Page Fault가 발생하는 순간은 Segment가 실제로 파일에서 로드될 때 이다.

static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage,
			 uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
	ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT(pg_ofs(upage) == 0);
	ASSERT(ofs % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0)
	{
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		struct lazy *aux = (struct lazy*)malloc(sizeof(struct lazy));
		aux->file = file;
		aux->ofs = ofs;
		aux->read_bytes = page_read_bytes;
		aux->zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer (VM_ANON, upage,
					writable, lazy_load_segment, aux)){
			return false;
		}

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
		ofs += page_read_bytes;
	}
	return true;
}

VM 시스템은 mmap 영역에서 페이지를 lazy load하고 mmap된 파일 자체를 매핑을 위한 백업 저장소로 사용해야 한다. 이 두 시스템 콜을 구현하려면 vm/file.c에 정의된 do_mmap과 do_munmap을 구현해서 사용해야 한다.

fd로 열린 파일의 오프셋(offset) 바이트부터 length 바이트 만큼을 프로세스의 가상주소공간의 주소 addr 에 매핑 한다.
전체 파일은 addr에서 시작하는 연속 가상 페이지에 매핑된다. 파일 길이(length)가 PGSIZE의 배수가 아닌 경우 최종 매핑된 페이지의 일부 바이트가 파일 끝을 넘어 "stick out"된다. page_fault가 발생하면 이 바이트를 0으로 설정하고 페이지를 디스크에 다시 쓸 때 버린다.

성공하면 이 함수는 파일이 매핑된 가상 주소를 반환한다. 실패하면 파일을 매핑하는 데 유효한 주소가 아닌 NULL을 반환해야 한다.

void *
do_mmap (void *addr, size_t length, int writable,
		struct file *file, off_t offset) {


	struct file* new_file = file_reopen(file);
	if(new_file == NULL){
		return NULL;
	}

	void* return_address = addr;
	
	size_t read_bytes;
	if (file_length(new_file) < length){
		read_bytes = file_length(new_file);
	} else {
		read_bytes = length;
	}

	size_t zero_bytes = PGSIZE - (read_bytes%PGSIZE);
	
	ASSERT (pg_ofs (addr) == 0);
	ASSERT (offset % PGSIZE == 0);
	ASSERT ((read_bytes + zero_bytes) % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0) {
			/* Do calculate how to fill this page.
			* We will read PAGE_READ_BYTES bytes from FILE
			* and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		struct lazy* file_lazy = (struct lazy*)malloc(sizeof(struct lazy));
		file_lazy->file = new_file;
		file_lazy->ofs = offset;
		file_lazy->read_bytes = page_read_bytes;
		file_lazy->zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer(VM_FILE, addr, writable, lazy_load_segment, file_lazy)){
			return NULL;
		}		

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		addr += PGSIZE;
		offset += page_read_bytes;
	}
	return return_address;
}

지정된 주소 범위 addr에 대한 매핑을 해제한다.
지정된 주소는 아직 매핑 해제되지 않은 동일한 프로세서의 mmap에 대한 이전 호출에서 반환된 가상 주소여야 한다.

void
do_munmap (void *addr) {
    struct supplemental_page_table *spt = &thread_current()->spt;
    struct page *page = spt_find_page(spt, addr);

	int page_count;
	if (file_length(&page->file)%PGSIZE != 0){
 	    page_count = file_length(&page->file) + PGSIZE;
	} else {
		page_count = file_length(&page->file);
	}

    for (int i = 0; i < page_count/PGSIZE; i++)
    {
        if (page)
            destroy(page);
        addr += PGSIZE;
        page = spt_find_page(spt, addr);
    }
}

file-backed 페이지의 내용은 파일에서 가져오므로 mmap된 파일을 백업 저장소로 사용해야 한다. 즉, file-backed 페이지를 evict하면 해당 페이지가 매핑된 파일에 다시 기록된다.

파일에서 콘텐츠를 읽어 kva 페이지에서 swap in한다. 파일 시스템과 동기화해야 한다.

static bool
file_backed_swap_in (struct page *page, void *kva) {
	struct file_page *file_page = &page->file;
	struct lazy* aux = (struct lazy*)page->uninit.aux;

	lock_acquire(&filesys_lock);
	bool result = lazy_load_segment(page, aux);
	lock_release(&filesys_lock);

	return result;
}

내용을 다시 파일에 기록하여 swap out한다. 먼저 페이지가 dirty인지 확인하는 것이 좋다. 더럽지 않으면 파일의 내용을 수정할 필요가 없다. 페이지를 교체한 후에는 페이지의 더티 비트를 꺼야 한다.

static bool
file_backed_swap_out (struct page *page) {
	struct file_page *file_page = &page->file;
	struct lazy* aux = (struct lazy*)page->uninit.aux;
	struct file * file = aux->file;

	if(pml4_is_dirty(thread_current()->pml4,page->va)){
		file_write_at(file,page->va, aux->read_bytes, aux->ofs);
		file_write_at(file_page->file,page->va, file_page->read_bytes, file_page->ofs);
		pml4_set_dirty(thread_current()->pml4, page->va, false);
	}
	page->frame->page = NULL;
	page->frame = NULL;
	pml4_clear_page(thread_current()->pml4, page->va);
	return true;
}

https://github.com/yunsejin/PintOS_RE/tree/Project3_RE

목표는 userprog/syscall.c 안에 시스템 콜 핸들러를 구현해야한다. 제공된 최소한의 기능은 프로세스를 종료 시키므로써 시스템 콜을 “다룬다.(handles).”

구현하는 시스템 콜 핸들러는 시스템 콜 번호를 받아오고, 어떤 시스템 콜 인자들을 받아오고, 그에 알맞은 액션을 취해야 한다.

%rax 는 시스템 콜 번호 이다. 4번째 인자는 %r10 이지 %rcx가 아니다. 그러므로 시스템 콜 핸들러 syscall_handler() 가 제어권을 얻으면 시스템 콜 번호는 rax에 있고, 인자는 %rdi, %rsi, %rdx, %r10, %r8, %r9 순서로 전달된다.

시스템 콜 핸들러를 호출한 콜러의 레지스터는 전달받은 struct intr_frame 에 접근할 수 있다. (struct intr_frame은 커널 스택에 있다.) 함수 리턴 값을 위한 x86-64의 관례는 그 값을 RAX 레지스터에 넣는 것 이다. 값을 리턴하는 시스템 콜도 struct intr_frame의 rax멤버를 수정하는 식으로 이 관례를 따를 수 있다.

halt()는 power_off()를 호출해서 Pintos를 종료한다. (power_off()는 src/include/threads/init.h에 선언되어 있음)이 함수는 웬만하면 사용되지 않아야 한다. deadlock 상황에 대한 정보 등등 뭔가 조금 잃어 버릴 수도 있다.

void halt(void)
{
	power_off();
}

exit()은 현재 동작중인 유저 프로그램을 종료한다. 커널에 상태를 리턴하면서 종료한다. 만약 부모 프로세스가 현재 유저 프로그램의 종료를 기다리던 중이라면, 그 말은 종료되면서 리턴될 그 상태를 기다린다는 것 이다. 관례적으로, 상태 = 0 은 성공을 뜻하고 0 이 아닌 값들은 에러를 뜻 한다.

void exit(int status)
{
	struct thread *curr = thread_current();
	curr->exit_status = status;
	printf("%s: exit(%d)\n", curr->name, status);
	thread_exit();
}

create()는 file(첫 번째 인자)를 이름으로 하고 크기가 initial_size(두 번째 인자)인 새로운 파일을 생성한다. 성공적으로 파일이 생성되었다면 true를 반환하고, 실패했다면 false를 반환한다. 새로운 파일을 생성하는 것이 그 파일을 여는 것을 의미하지는 않는다.(파일을 여는 것은 open 시스템콜의 역할로, ‘생성’과 개별적인 연산이다.)

bool create(const char *file, unsigned initial_size)
{
	check_address(file);
	return filesys_create(file, initial_size);
}

open()은  file(첫 번째 인자)이라는 이름을 가진 파일을 연다. 해당 파일이 성공적으로 열렸다면, 파일 식별자로 불리는 비음수 정수(0또는 양수)를 반환하고, 실패했다면 -1를 반환한다. 0번 파일식별자와 1번 파일식별자는 이미 역할이 지정되어 있다. 0번은 표준 입력(STDIN_FILENO)을 의미하고 1번은 표준 출력(STDOUT_FILENO)을 의미한다. 

open 시스템 콜은 아래에서 명시적으로 설명하는 것처럼 시스템 콜 인자로서만 유효한 파일 식별자들을 반환하지 않는다. 각각의 프로세스는 독립적인 파일 식별자들을 갖는다. 파일 식별자는 자식 프로세스들에게 상속(전달)된다. 하나의 프로세스에 의해서든 다른 여러개의 프로세스에 의해서든, 하나의 파일이 두 번 이상 열리면 그때마다 open시스템콜은 새로운 식별자를 반환한다.

하나의 파일을 위한 서로 다른 파일 식별자들은 개별적인 close 호출에 의해서 독립적으로 닫히고 그 한 파일의 위치를 공유하지 않는다. 추가적인 작업을 하기 위해서는 open 시스템 콜이 반환하는 정수(fd)가 0보다 크거나 같아야 한다는 리눅스 체계를 따라야 한다.

int open(const char *file_name)
{
	check_address(file_name);
	struct file *file = filesys_open(file_name);
	if (file == NULL)
		return -1;

	int fd = process_add_file(file);
	if (fd == -1)
		file_close(file);

	return fd;
}

close()는 파일 식별자 fd를 닫는다. 프로세스를 나가거나 종료하는 것은 묵시적으로 그 프로세스의 열려있는 파일 식별자들을 닫는다. 마치 각 파일 식별자에 대해 이 함수가 호출된 것과 같다. 

void close(int fd)
{
	if (fd < 2)
		return;
	struct file *file = process_get_file(fd);
	if (file == NULL)
		return;
	file_close(file);
	process_close_file(fd);
}

read()는 buffer 안에 fd 로 열려있는 파일로부터 size 바이트를 읽는다. 실제로 읽어낸 바이트의 수 를 반환한다.(파일 끝에서 시도하면 0) 파일이 읽어질 수 없었다면 -1을 반환한다.(파일 끝이라서가 아닌 다른 조건에 때문에 못 읽은 경우)

int read(int fd, void *buffer, unsigned size)
{
	check_address(buffer);

	char *ptr = (char *)buffer;
	int bytes_read = 0;

	if (fd == STDIN_FILENO)
	{
		for (int i = 0; i < size; i++)
		{
			char ch = input_getc();
			if (ch == '\n')
				break;
			*ptr = ch;
			ptr++;
			bytes_read++;
		}
	}
	else
	{
		if (fd < 2)
			return -1;
		struct file *file = process_get_file(fd);
		if (file == NULL)
			return -1;
		lock_acquire(&filesys_lock);
		bytes_read = file_read(file, buffer, size);
		lock_release(&filesys_lock);
	}
	return bytes_read;
}

write()는 buffer로부터 open file fd로 size 바이트를 적어준다. 실제로 적힌 바이트의 수를 반환해주고, 일부 바이트가 적히지 못했다면 size보다 더 작은 바이트 수가 반환될 수 있다. 파일의 끝을 넘어서 작성하는 것은 보통 파일을 확장하는 것이지만, 파일 확장은 basic file system에 의해서는 불가능하다. 

이로 인해 파일의 끝까지 최대한 많은 바이트를 적어주고 실제 적힌 수를 반환하거나, 더 이상 바이트를 적을 수 없다면 0을 반환한다. fd 1은 콘솔에 적어준다. 콘솔에 작성한 코드가 적어도 몇 백 바이트를 넘지 않는 사이즈라면, 한 번의 호출에 있는 모든 버퍼를 putbuf()에 적어주는 것 이다.(더 큰 버퍼는 분해하는 것이 합리적)그렇지 않다면, 다른 프로세스에 의해 텍스트 출력 라인들이 콘솔에 끼게 (interleaved)되고, 읽는 사람과 채점 스크립트가 헷갈릴 것 이다.

int write(int fd, const void *buffer, unsigned size)
{
	check_address(buffer);
	int bytes_write = 0;
	if (fd == STDOUT_FILENO)
	{
		putbuf(buffer, size);
		bytes_write = size;
	}
	else
	{
		if (fd < 2)
			return -1;
		struct file *file = process_get_file(fd);
		if (file == NULL)
			return -1;
		lock_acquire(&filesys_lock);
		bytes_write = file_write(file, buffer, size);
		lock_release(&filesys_lock);
	}
	return bytes_write;
}

fork()는 THREAD_NAME이라는 이름을 가진 현재 프로세스의 복제본인 새 프로세스를 만든다.

피호출자(callee) 저장 레지스터인 %RBX, %RSP, %RBP와 %R12 - %R15를 제외한 레지스터 값을 복제할 필요가 없다. 자식 프로세스의 pid를 반환해야 한다. 그렇지 않으면 유효한 pid가 아닐 수 있다.

자식 프로세스에서 반환 값은 0이어야 한다. 자식 프로세스에는 파일 식별자 및 가상 메모리 공간을 포함한 복제된 리소스가 있어야 한다. 부모 프로세스는 자식 프로세스가 성공적으로 복제되었는지 여부를 알 때까지 fork에서 반환해서는 안된다. 즉, 자식 프로세스가 리소스를 복제하지 못하면 부모의 fork() 호출이 TID_ERROR를 반환할 것이다.

템플릿은 `threads/mmu.c`의 `pml4_for_each`를 사용하여 해당되는 페이지 테이블 구조를 포함한 전체 사용자 메모리 공간을 복사하지만, 전달된 `pte_for_each_func`의 누락된 부분을 채워야 한다.

tid_t process_fork(const char *name, struct intr_frame *if_ UNUSED)
{
	/* Clone current thread to new thread.*/
	struct thread *cur = thread_current();
	memcpy(&cur->parent_if, if_, sizeof(struct intr_frame));

	tid_t pid = thread_create(name, PRI_DEFAULT, __do_fork, cur);
	if (pid == TID_ERROR)
		return TID_ERROR;

	struct thread *child = get_child_process(pid);

	sema_down(&child->load_sema);

	if (child->exit_status == -2)
	{
		sema_up(&child->exit_sema);
		return TID_ERROR;
	}
	return pid;
}

exec()은 현재의 프로세스가 cmd_line에서 이름이 주어지는 실행가능한 프로세스로 변경된다. 이때 주어진 인자들을 전달한다. 성공적으로 진행된다면 어떤 것도 반환하지 않는다. 만약 프로그램이 이 프로세스를 로드하지 못하거나 다른 이유로 돌리지 못하게 되면 exit state -1을 반환하며 프로세스가 종료된다.

exec 함수를 호출한 쓰레드의 이름은 바꾸지 않는다. file descriptor는 exec 함수 호출 시에 열린 상태로 있다는 것을 알아둬야 한다.

int exec(const char *cmd_line)
{
	check_address(cmd_line);

	char *cmd_line_copy;
	cmd_line_copy = palloc_get_page(0);
	if (cmd_line_copy == NULL)
		exit(-1);
	strlcpy(cmd_line_copy, cmd_line, PGSIZE);

	if (process_exec(cmd_line_copy) == -1)
		exit(-1);
}

wait()는 자식 프로세스 (pid) 를 기다려서 자식의 종료 상태(exit status)를 가져온다. 만약 pid (자식 프로세스)가 아직 살아있으면, 종료 될 때 까지 기다린다. 종료가 되면 그 프로세스가 exit 함수로 전달해준 상태(exit status)를 반환한다. 

만약 pid (자식 프로세스)가 exit() 함수를 호출하지 않고 커널에 의해서 종료된다면 (e.g exception에 의해서 죽는 경우), wait(pid) 는 -1을 반환해야 한다.

부모 프로세스가 wait 함수를 호출한 시점에서 이미 종료되어버린 자식 프로세스를 기다리도록 하는 것은 합당하지만, 커널은 부모 프로세스에게 자식의 종료 상태를 알려주든지, 커널에 의해 종료되었다는 사실을 알려주든지 해야 한다.

int process_wait (tid_t child_tid) {
	struct thread *cur = thread_current();
	struct thread *child = get_child_process(child_tid);
	if (child == NULL)
		return -1;
	sema_down(&child->wait_sema);
	list_remove(&child->child_elem);
	sema_up(&child->exit_sema);
	return child->exit_status;
}

https://github.com/yunsejin/PintOS_RE/tree/Project2_RE

/bin/ls -l foo bar 와 같은 명령이 주어졌을 때, 인자들을 어떻게 다뤄야 하는지 생각해보자

1. 명령을 단어들로 쪼갠다. /bin/ls, l, foo, bar 이렇게
2. 이 단어들을 스택의 맨 처음 부분에 놓는다. 순서는 상관 없다. 왜냐면 포인터에 의해 참조될 예정이기 때문이다.
3. 각 문자열의 주소 + 경계조건을 위한 널포인터를 스택에 오른쪽→왼쪽 순서로 푸시한다. **이들은 argv의 원소가 된다. 널포인터 경계는 argv[argc] 가 널포인터라는 사실을 보장해준다. C언어 표준의 요구사항에 맞춰서 말이다. 그리고 이 순서는 argv[0]이 가장 낮은 가상 주소를 가진다는 사실을 보장해준다. 또한 word 크기에 정렬된 접근이 정렬되지 않은 접근보다 빠르므로, 최고의 성능을 위해서는 스택에 첫 푸시가 발생하기 전에 스택포인터를 8의 배수로 반올림하여야 한다.
4. %rsi 가 argv 주소(argv[0]의 주소)를 가리키게 하고, %rdi 를 argc 로 설정한다.
5. 마지막으로 가짜 “리턴 어드레스”를 푸시한다 : entry 함수는 절대 리턴되지 않겠지만, 해당 스택 프레임은 다른 스택 프레임들과 같은 구조를 가져야 한다. 

Address Name Data Type

RDI: 4 | RSI: 0x4747ffc0

위 표는 스택과 관련 레지스터들이 유저 프로그램이 시작되기 직전에 어떤 상태인지를 보여준다. 스택은 아래로 자란다는 것을 잊지 말자.

 *      4 kB +---------------------------------+
 *           |          kernel stack           |
 *           |                |                |
 *           |                |                |
 *           |                V                |
 *           |         grows downward          |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           |                                 |
 *           +---------------------------------+
 *           |              magic              |
 *           |            intr_frame           |
 *           |                :                |
 *           |                :                |
 *           |               name              |
 *           |              status             |
 *      0 kB +---------------------------------+

저 위의 표의 예시에서, 스택 포인터는 위에 보이는 것처럼 0x4747ffb8로 초기화될 것이고, 코드 include/threads/vaddr.h에 정의된 USER_STACK 값에서부터 스택을 시작시켜야 한다.

현재, process_exec() 함수는 새로운 프로세스들에 인자를 전달하는 것을 지원하지 않는다. process_exec() 함수를 확장 구현해서, 지금처럼 단순히 프로그램 파일 이름만을 인자로 받아오게 하는 대신 공백을 기준으로 여러 단어로 나누어지게 만들어야 한다.

첫 번째 단어는 프로그램 이름이고, 두 번째 단어는 첫 번째 인자이며, 그런 식으로 계속 이어지게 만들면 된다. 따라서, 함수 process_exec("grep foo bar") 는 두 개의 인자 foo와 bar을 받아서 grep 프로그램을 실행시켜야 한다.

int
process_exec (void *f_name) {
	char *file_name = f_name;
	bool success;

	/* We cannot use the intr_frame in the thread structure.
	 * This is because when current thread rescheduled,
	 * it stores the execution information to the member. */
	struct intr_frame _if;
	_if.ds = _if.es = _if.ss = SEL_UDSEG;
	_if.cs = SEL_UCSEG;
	_if.eflags = FLAG_IF | FLAG_MBS;

	/* We first kill the current context */
	process_cleanup ();
	int argc = 0;
    char *argv[64];		//parssing한 인자를 담을 배열
    char *token, *save_ptr;
    
	for (token = strtok_r(file_name, " ", &save_ptr); token != NULL; token = strtok_r(NULL, " ", &save_ptr))
    {   
		argv[argc++] = token;
	}
	/* And then load the binary */
	success = load (file_name, &_if);

	argument_stack(argv, argc, &_if);
	
	/* If load failed, quit. */
	palloc_free_page (file_name);
	if (!success)
		return -1;

	/* Start switched process. */
	do_iret (&_if);
	NOT_REACHED ();
}

argument_stack 함수는 프로세스의 스택에 실행 인자를 준비하는 역할을 한다. 인자들을 스택에 복사하고, 64비트 시스템에서 요구하는 8바이트 정렬을 맞추며, 각 인자의 주소를 스택에 추가한다. 이 과정을 통해 프로그램 실행 시 필요한 인자들을 스택에 올바르게 준비한다.

void argument_stack(char **argv, int argc, struct intr_frame *if_)
{
	char *arg_address[128];

	for(int i = argc - 1; i >= 0; i--)
	{
		int arg_i_len = strlen(argv[i]) +1;
		if_->rsp -= arg_i_len;
		memcpy(if_->rsp, argv[i], arg_i_len);
		arg_address[i] = (char *)if_->rsp;
	}

	if(if_->rsp % 8 != 0)
	{	
		int padding = if_->rsp % 8;
		if_->rsp -= padding;
		memset(if_->rsp, 0, padding);
	}

	if_->rsp -= 8; 	
	memset(if_->rsp, 0, 8);

	for(int i = argc-1; i >= 0; i--)
	{
		if_->rsp -= 8;
		memcpy(if_->rsp, &arg_address[i], 8);
	}

	if_->rsp -= 8;
	memset(if_->rsp, 0, 8);

	if_->R.rdi = argc;
	if_->R.rsi = if_->rsp + 8;
}

커맨드라인에서, 여러개의 공백은 하나의 공백과 같게 처리해야 한다. 그러므로 process_exec("grep    foo   bar")는 저 위의 표(원본) 예시와 동일하게 동작해야 한다.

또한, 납득할만한 수준에서 커맨드라인 인자들의 길이 제한을 강요할 수 있다. 예를 들면, 인자들이 한 페이지 크기(4kB) 안에 들어가게끔 제한하는 것 이다. (그리고 직접적인 관계는 없지만, pintos 유틸리티가 커널에 전달할 수 있는 커맨드라인 인자 크기는 128바이트로 제한되어 있다.)

<stdio.h>에 선언된 비표준 함수인 hex_dump()는 인자 전달 코드를 디버깅 하는데에 유용할 것이다. argument passing을 잘 했는지 make tests/userprog/args-none.result로 체크를 하면 안된다. write가 구현되어 있지 않기 때문인데, 이 때문에, 파싱이 잘 됐는지 확인하기 위해서는 hex_dump를 써야한다.

int write (int fd, const void *buffer, unsigned length)
{
	int byte = 0;
	if(fd == 1)
	{
		putbuf(buffer, length);
		byte = length;
	}
	return byte;
}

아니면 syscall.c 쪽에서 write를 임의로 구현해도 된다.

https://github.com/yunsejin/PintOS_RE/tree/project2

페이지 교체 정책(Page Replacement Policy)은 가상 메모리 시스템에서 메모리가 꽉 찼을 때, 어떤 페이지를 제거하고 새 페이지를 물리 메모리에 적재할지 결정하는 방법이다. 이 정책은 시스템의 성능과 효율성에 중요한 영향을 미친다. 여러 페이지 교체 알고리즘이 있으며, 각기 다른 상황에 적합하다.

FIFO(Fist-In, Fist-Out)은 가장 오래 전에 메모리에 적재된 페이지를 먼저 교체한다. 구현이 간단하지만, 자주 사용되는 페이지를 교체할 위험이 있다.

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체한다. 최근 사용 패턴을 기반으로 효율적인 페이지 교체를 제공하지만, 구현이 복잡하다.

페이지 참조 시퀀스가 123412512345일 때:

LFU(Least Frequently Used)는 가장 적게 사용된 페이지를 교체한다. 사용 빈도를 기반으로 하지만, 최근 사용 패턴을 반영하지 못하는 단점이 있다.

NRU(Not Recently Used)는 페이지가 최근에 사용되었는지 여부를 기준으로 교체 대상을 결정한다. 각 페이지마다 참조 비트(reference bit)를 두어, 페이지가 접근되면 이 비트를 설정한다. 주기적으로 운영 체제는 이 비트를 클리어하여, 어떤 페이지가 최근에 사용되지 않았는지를 판단한다. 교체 시점에, 참조 비트가 클리어된 페이지(즉, 최근에 사용되지 않은 페이지) 중에서 교체 대상을 선택한다. NRU는 구현이 간단하고 효율적이지만, 최적의 페이지 교체를 보장하지는 않는다.

NFU(Not Frequently Used)는 각 페이지가 시스템 내에서 얼마나 자주 사용되었는지를 기준으로 교체 대상을 결정한다. 페이지마다 카운터를 두고, 시간이 지날 때마다 페이지가 참조되면 해당 페이지의 카운터를 증가시킨다. 교체가 필요할 때, 가장 카운터 값이 낮은 페이지(즉, 가장 자주 사용되지 않은 페이지)를 교체 대상으로 선택한다. NFU는 사용 빈도를 기반으로 하므로 시간이 지남에 따라 정확도가 높아지지만, 오랜 시간 동안 시스템에 머물렀던 페이지가 불이익을 받을 수 있다는 단점이 있다.

최적 페이지 교체 알고리즘(Optimal Page Replacement)는 미래에 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이상적인 알고리즘이지만, 실제 시스템에서는 미래의 접근 패턴을 예측할 수 없어 구현이 불가능하다.

Clock(Circular Queue)는 FIFO와 유사하되, 각 페이지에 사용 여부를 나타내는 플래그를 사용한다. '시계' 방식으로 순환하며, 사용되지 않은 페이지(플래그가 0인 페이지)를 찾아 교체한다. LRU의 근사 알고리즘으로, 구현이 비교적 간단하면서도 효과적이다.

페이지 참조 시퀀스가 123412512345일 때:

벨라디의 역설(Belady's Anomaly)은 페이지 교체 알고리즘에서 관찰될 수 있는 현상으로, 가상 메모리 시스템에서 물리 메모리의 프레임 수를 증가시킬 때, 예상과 달리 페이지 폴트의 수가 증가하는 상황을 말한다. 이 역설은 특히 FIFO(First-In, First-Out) 페이지 교체 알고리즘에서 두드러지게 나타난다.

일반적으로, 물리 메모리의 크기가 커지면 더 많은 페이지를 저장할 수 있게 되어 페이지 폴트의 수가 감소할 것으로 예상된다. 그러나 벨라디의 역설에서는 메모리 프레임의 수를 증가시키는 것이 오히려 페이지 폴트 수를 증가시킬 수 있음을 보여준다. 이 현상은 FIFO 알고리즘의 특성상, 메모리에 더 많은 페이지를 보관할 수 있게 되면서, 최근에 사용된 페이지가 아닌 오래된 페이지를 메모리에 유지하는 경향 때문에 발생한다.

벨라디의 역설은 모든 페이지 교체 알고리즘에서 발생하는 것은 아니다. LRU(Least Recently Used)나 OPT(Optimal Page Replacement) 같은 일부 알고리즘은 이러한 역설적인 상황을 겪지 않는다. 이 알고리즘들은 각각 최근에 가장 적게 사용된 페이지, 또는 미래에 가장 오랫동안 사용되지 않을 페이지를 교체함으로써 메모리 프레임의 수가 증가함에 따라 페이지 폴트 수가 감소하거나 최적화되는 경향을 보인다.

벨라디의 역설은 페이지 교체 전략을 설계하고 선택할 때 주의해야 할 중요한 이론적 관점을 제공한다. 이 역설을 통해 알 수 있는 교훈은 물리 메모리의 크기를 증가시킨다고 해서 항상 시스템의 성능이 향상되는 것은 아니라는 점이다. 따라서, 효과적인 메모리 관리 전략을 위해서는 적절한 페이지 교체 알고리즘의 선택이 중요하다.

교체 알고리즘이 FIFO이고 페이지 참조 시퀀스가 123412512345일 때:

output :

[[1], [1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 1], [4, 1, 2], [1, 2, 5], [1, 2, 5], [1, 2, 5], [2, 5, 3], [5, 3, 4], [5, 3, 4]] 페이지 폴트 수 : 9

프레임 크기가 3일 때, 페이지 폴트 수가 9개가 나온다. 

output : [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 1], [4, 5, 1, 2], [5, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5]] 페이지 폴트 수 : 10

프레임 크기를 4로 늘렸는데도 불구하고, 페이지 폴트 수가 10으로 더 늘어난 모습이다.

Demand-zero 페이지는 컴퓨터 시스템에서 가상 메모리 관리 기법 중 하나이다. 프로세스가 실제로 페이지를 참조하기 전까지는 해당 페이지를 물리적 메모리에 할당하지 않는다. 대신, 프로세스가 특정 페이지에 접근을 시도할 때 해당 페이지가 물리적 메모리에 없으면 페이지 폴트(page fault)가 발생한다. 이때 운영 체제는 요청된 페이지를 디스크에서 찾아 물리적 메모리에 로드하고, 프로세스는 그 페이지를 사용할 수 있게 된다.

Demand-zero 페이지의 주요 장점은 메모리 사용의 효율성을 높일 수 있다는 것이다. 실제로 필요할 때까지 메모리를 할당하지 않기 때문에, 미사용 페이지에 대한 메모리 낭비를 줄일 수 있다. 이 방식은 특히 메모리 자원이 제한적인 시스템이나 많은 수의 프로세스를 동시에 실행해야 하는 시스템에서 유용하다. 다만, 페이지 폴트가 발생했을 때 디스크에서 메모리로 페이지를 로드하는 과정이 필요하기 때문에, 페이지 폴트 처리 시간이 시스템의 성능에 영향을 줄 수 있다. 따라서, 시스템 설계 시 메모리 관리 전략을 잘 선택하고, 페이지 폴트 발생 빈도를 최소화하는 최적화 작업이 중요하다.

파일-백드 페이지(file-backed page)는 가상 메모리 시스템에서 사용되는 개념으로, 가상 주소 공간의 페이지가 실제 파일의 내용으로 백업되는 경우를 말한다. 이러한 페이지는 일반적으로 실행 가능 파일이나 라이브러리 파일 같은 영구 저장소에 있는 데이터로 채워진다. 파일-백드 메커니즘은 특히 메모리 매핑 파일(memory-mapped file) 기술과 밀접하게 연관되어 있다.

파일-백드 페이지는 디스크 상의 파일에 대응되므로, 프로세스 간에 공유될 수 있으며, 시스템이 재부팅되어도 데이터가 유지된다. 이 기법을 사용하면, 파일의 일부를 메모리에 로드하고 접근하는 과정이 최적화될 수 있어, 파일 I/O 작업이 줄어들고 성능이 향상될 수 있다.

프로세스가 파일-백드 페이지에 접근하려 할 때 해당 페이지가 메모리에 없으면 페이지 폴트가 발생한다. 운영 체제는 해당 파일의 적절한 부분을 메모리로 로드하여 페이지 폴트를 해결한다. 메모리 매핑된 파일을 사용하여, 다른 프로세스들이 파일의 내용을 통해 데이터를 공유하고 통신할 수 있다.

프로그램이 파일을 메모리에 매핑할 때, 해당 파일의 내용은 파일-백드 가상 페이지로 관리된다. 이를 통해 파일 내용에 대한 읽기와 쓰기 작업을 메모리 접근처럼 수행할 수 있다. 운영 체제는 공유 라이브러리나 실행 가능 파일을 프로세스의 가상 주소 공간에 매핑하여, 필요한 코드와 데이터를 메모리로 로드한다. 이 과정에서 파일-백드 페이지가 사용된다.

파일-백드 페이지는 필요한 경우에만 메모리로 로드되기 때문에, 스왑 공간의 사용을 줄이고 시스템의 전반적인 성능을 개선할 수 있다.

Anonymous 페이지는 가상 메모리 시스템에서 사용되는 용어로, 파일이나 다른 백업 스토리지에 직접 매핑되지 않는 메모리 페이지를 의미한다. 이러한 페이지는 주로 프로세스의 힙(heap)이나 스택(stack)과 같이 실행 중에 동적으로 할당되는 데이터를 저장하는 데 사용된다. 예를 들어, 프로그램에서 동적 할당을 통해 메모리를 요청하면 운영 체제는 이러한 요청을 충족시키기 위해 anonymous 페이지를 할당할 수 있다.

Anonymous 페이지는 디스크 상의 파일에 매핑되지 않기 때문에, 프로그램의 실행 파일이나 데이터 파일과는 직접적인 관련이 없다. 대신, 이 페이지들은 실행 시간에 프로세스의 메모리 요구에 의해 동적으로 생성된다.

대부분의 운영 체제는 안전성을 위해 anonymous 페이지를 할당할 때 'zero-fill' 정책을 사용하여 페이지 내용을 0으로 초기화한다. 이는 새로 할당된 메모리가 이전에 사용되었던 데이터를 포함하지 않도록 보장한다.

메모리가 부족할 때, 운영 체제는 스왑(swap) 영역이나 페이지 파일을 사용하여 anonymous 페이지를 디스크로 스왑 아웃할 수 있다. 나중에 해당 페이지에 다시 접근할 필요가 있을 때, 운영 체제는 디스크에서 해당 페이지를 다시 메모리로 스왑 인한다.

프로그램에서 malloc, calloc, new 등의 함수를 사용하여 메모리를 동적으로 할당할 때, 이러한 할당은 대개 anonymous 페이지를 통해 이루어진다.

Lazy loading은 컴퓨터 프로그래밍에서 자주 사용되는 최적화 기법 중 하나로, 객체, 데이터, 또는 다른 리소스를 실제로 필요로 하는 순간까지 로딩을 지연시키는 방식이다. 이 기법은 주로 웹 개발, 소프트웨어 개발, 그리고 운영 체제의 메모리 관리에서 사용된다. Lazy loading의 주 목적은 시스템의 성능을 향상시키고, 리소스 사용을 최적화하여 사용자 경험을 개선하는 것이다.

웹 개발에서 lazy loading은 특히 이미지, 스크립트, 비디오 등의 리소스를 페이지 로드 시점이 아닌, 사용자가 해당 리소스를 필요로 하는 순간에 로드하는 데 사용된다. 예를 들어, 사용자가 스크롤을 내려 이미지가 보여야 할 위치에 도달했을 때 해당 이미지를 로드한다. 이 방식은 초기 페이지 로딩 시간을 줄이고, 네트워크 트래픽을 줄이며, 서버의 부하를 경감하는 데 도움을 준다.

소프트웨어 개발에서는 객체나 모듈을 실제로 사용할 때까지 로딩을 지연시키는 방식으로 리소스 사용을 최적화한다. 예를 들어, 특정 기능이 사용자에 의해 요청될 때만 해당 기능을 구현하는 클래스의 인스턴스를 생성하거나, 모듈을 로드한다. 이는 메모리 사용을 줄이고, 애플리케이션의 시작 시간을 단축시키는 효과를 가진다.

운영 체제의 메모리 관리에서도 lazy loading 기법이 사용될 수 있다. 예를 들어, 프로그램이 시작될 때 모든 데이터와 코드를 메모리에 로드하는 대신, 실제로 필요한 부분만 메모리에 로드하고, 나머지는 필요해질 때까지 로딩을 지연시킨다. 이는 효율적인 메모리 사용을 가능하게 하며, 전체 시스템의 성능을 향상시킬 수 있다.

하이퍼바이저는 가상화 기술을 구현하는 소프트웨어다. 물리적 하드웨어 위에서 여러 운영체제를 동시에 실행할 수 있게 해준다. 하이퍼 바이저는 크게 두 가지 유형이 있다.

https://aws.amazon.com/ko/compare/the-difference-between-type-1-and-type-2-hypervisors/

타입 1 하이퍼바이저는 하드웨어에 직접 설치되어 운영체제 없이 작동하며, 고성능 가상화 환경을 제공한다. 기본 물리적 호스트 머신 하드웨어에서 실행되며, 대규모, 리소스 집약적 또는 고정용 워크로드에 적합하다. 시스템 관리자 이는 수준의 지식이 필요하다. 예시로 VMware ESXi, Microsoft Hyper-V, KVM이 있다.

타입 2 하이퍼바이저는 기존 운영체제 위에 설치되어, 일반적인 애플리케이션처럼 실행된다. 가상머신을 만들고 관리하는 데 사용된다. 기본 운영 체제에서 실행되고 데스크톱 및 개발 환경에 적합하다. 예시로 Oracle VM VirtualBox, VMware Workstation, Microsoft Virtual PC가 있다.

애뮬레이션은 하나의 시스템이 다른 시스템의 기능을 모방하게 하는 기술이다. 이는 소프트웨어, 하드웨어, 또는 둘의 조합을 통해 이루어질 수 있다. 예를 들어, 특정 비디오 게임 콘솔용으로 개발된 게임을 PC에서 실행할 수 있게 해주는 소프트웨어 애뮬레이터가 이에 해당한다. 애뮬레이션은 다양한 용도로 사용되며, 오래된 시스템의 소프트웨어를 새로운 하드웨어에서 실행하거나, 소프트웨어 개발 과정에서 다른 플랫폼을 대상으로 하는 애플리케이션의 테스트에 사용되기도 한다.

하이퍼바이저(가상화)는 물리적 하드웨어 위에 직접 구축되며, 하드웨어 자원을 여러 가상 머신 간에 분할한다. 이는 주로 성능 저하 없이 효율적인 자원 분배와 관리를 목표로 한다. 하이퍼바이저는 주로 같은 아키텍처 내에서의 가상화에 초점을 맞춘다.

따라서, 하이퍼바이저는 가상 머신을 생성하고 관리하는 역할을 하며, 가상 머신은 이러한 환경에서 실행되는 독립적인 컴퓨터 시스템이라 할 수 있다.

애뮬레이터는 하드웨어, 소프트웨어, 또는 둘의 조합을 모방하는 소프트웨어로, 한 플랫폼에서 다른 플랫폼의 시스템을 실행할 수 있게 한다. 예를 들어, 한 종류의 프로세서 아키텍처를 가진 시스템에서 다른 종류의 프로세서 아키텍처를 사용하는 시스템을 모방할 수 있다. 애뮬레이션은 주로 호환성이나 구형 시스템의 소프트웨어를 새 시스템에서 실행하기 위해 사된다.

QEMU는 오픈소스 가상화 소프트웨어로, 다양한 하드웨어 아키텍처에서 가상 머신을 생성하고 실행할 수 있다. 하이퍼바이저 기능과 함께 애뮬레이션 기능도 제공하여, 하나의 플랫폼에서 다른 플랫폼의 운영 체제를 실행할 수 있게 해준다. 예를 들어, x86 프로세서를 사용하는 컴퓨터에서 ARM 프로세서를 사용하는 운영 체제를 실행할 수 있다. QEMU는 개발자들이 소프트웨어를 다양한 하드웨어 환경에서 테스트하거나, 가상화 환경을 구축할 때 널리 사용된다.

Pint OS의 Project 1이 구현되기 전에는 단일 큐로 idle tick이 없고 오로지 ready list로만 관리된다. kernel단 까지 들어갈 필요가 없는 thread도 block 되지 않고 yield()가 되는게 busy wait 이라는 문제가 된다.

그래서 sleep_list를 만들어 준 뒤에, 당장에 불 필요한 thread들을 sleep 시켜줘야 한다.

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	if(timer_elapsed(start) < ticks){
		thread_sleep(start + ticks);
	}
}

timer를 활용하여 sleep을 시키는데 이 때 thread를 block시키고, sleep list로 들어가면 해당 자원을 양보시켜줘야한다.

void
thread_sleep(int64_t ticks){
	struct thread *curr = thread_current();
	enum intr_level old_level;	

	ASSERT(!intr_context());

	old_level = intr_disable();
	curr->status = THREAD_BLOCKED;
	curr->wakeup_tick = ticks;
	
	if(curr!= idle_thread)
		list_insert_ordered(&sleep_list, &curr->elem, sleep_less , NULL);
	schedule();
	intr_set_level(old_level);
}

sleep을 시켰으니, 적당한 타임이 되면 thread를 깨워줘야한다. 인터럽트가 발생할 때마다, 틱을 증가시키는데, 이 때 thread가 깨어날 타이밍이라면 깨운다.

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	thread_wakeup(ticks);
}

이 때, 깨울 타임이 같은 thread 중 우선순위가 높은 순서대로 ready_list에 들어가야 우선순위가 높은 thread 부터 실행이 될 수 있다. 고로, sleep된 thread 중 깨웠을 때 greater_list에 우선순위 순으로 정렬해서 넣고 그 greater_list가 ready_list에 들어간다면 될 것 이다.

void
thread_wakeup(int64_t ticks)
{
	if(list_empty(&sleep_list))
		return;

	enum intr_level old_level;
	struct thread *sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);
	struct thread *sleep_pop_front_thread;

	while(sleep_front_thread->wakeup_tick <= ticks)
	{
		old_level = intr_disable();
		sleep_front_thread->status = THREAD_READY;
		sleep_pop_front_thread = list_entry(list_pop_front(&sleep_list), struct thread, elem);
		list_insert_ordered(&greater_list, &sleep_pop_front_thread->elem , cmp_priority, NULL);
		sleep_front_thread = list_entry(list_begin(&sleep_list),struct thread, elem);	
		intr_set_level(old_level);
	}

	while(!list_empty(&greater_list))
	{
		old_level = intr_disable();
		list_push_back(&ready_list, list_pop_front(&greater_list));
		intr_set_level(old_level);
	}
}

lock_acquire 함수는 주어진 락을 현재 스레드가 획득하려고 시도할 때 호출된다. 이미 누군가 그 락을 가지고 있다면, 현재 스레드는 대기 상태로 들어가게 되며, 락을 보유한 스레드가 lock_release를 호출하여 락을 해제할 때까지 기다려야 한다.

락의 holder가 NULL이 아니라면, 즉 누군가가 이미 락을 보유하고 있다면, 현재 스레드는 대기해야 한다. 이때, 현재 스레드의 우선순위가 락을 보유한 스레드의 우선순위보다 높다면, 우선순위 기부가 발생한다. 우선순위 기부는 락을 보유한 스레드의 우선순위를 현재 스레드의 우선순위로 상향 조정함으로써, 고우선순위 스레드가 더 빨리 실행될 수 있도록 한다.

이미 대기 중인 스레드가 있는 경우, 그 스레드들의 우선순위도 확인하고 필요에 따라 우선순위를 상속시켜 우선순위 역전 문제를 해결한다. 락을 획득할 수 있을 때까지 현재 스레드는 세마포어를 사용하여 대기 상태로 들어가고 sema_down 함수를 호출하여 세마포어의 값을 감소시키고, 필요하다면 스레드를 대기 상태로 만든다.

void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

	if(lock->holder != NULL)
	{
        thread_current()->wait_on_lock = lock;
        if(lock->holder->priority < thread_current()->priority)
        {
            list_insert_ordered(&lock->holder->donations, &thread_current()->d_elem, sleep_less, NULL);
		}
		struct lock *cur_wait_on_lock = thread_current()->wait_on_lock;
		while(cur_wait_on_lock  != NULL)
		{
			if(cur_wait_on_lock->holder->priority< thread_current()->priority)
			{
				cur_wait_on_lock->holder->priority = thread_current()->priority;
				cur_wait_on_lock = cur_wait_on_lock->holder->wait_on_lock;
			}
			else
				break;
		}
	}
	sema_down (&lock->semaphore);
	thread_current()->wait_on_lock = NULL;
	lock->holder = thread_current ();
}

sema_down 함수는 세마포어(semaphore)의 값을 감소시키려고 시도하는 연산이다. 세마포어는 동기화 목적으로 사용되는 변수로, 리소스의 사용 가능 여부를 나타낸다. sema_down 함수는 주로 락(lock) 획득이나 자원 접근 제어에 사용된다. 세마포어의 값이 0이면, 이는 해당 리소스가 사용 중임을 의미하며, 어떤 스레드도 리소스를 사용할 수 없다.

sema->value가 0인 경우, 이는 다른 스레드가 이미 리소스를 사용 중임을 의미하므로, 현재 스레드는 대기해야 한다. 이를 위해 현재 스레드는 세마포어의 대기 목록(sema->waiters)에 추가된다. 대기 목록에 추가될 때, 우선순위에 따라 정렬되어 대기 순서가 결정된다. 이후, thread_block 함수를 호출하여 현재 스레드를 대기 상태로 전환한다.

대기 중인 스레드 없이 sema->value가 0보다 큰 경우, 혹은 대기 중인 스레드가 깨어나 세마포어를 사용할 수 있는 경우, sema->value는 1 감소한다. 이는 리소스 하나가 사용 중임을 나타낸다.

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		list_insert_ordered (&sema->waiters, &thread_current ()->elem, cmp_priority, NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

lock_release 함수는 스레드가 보유한 락(lock)을 해제하고, 해당 락을 기다리는 다른 스레드들에게 양보한다.

락을 해제하는 스레드(lock->holder)의 우선순위 기부 목록(donations)을 확인하여, 이 락을 기다리고 있던 모든 스레드들의 기부 항목을 제거하고, 우선순위 기부 목록을 순회하면서, 현재 락(lock)을 기다리고 있던(wait_on_lock이 현재 락을 가리키는) 스레드를 찾아 해당 스레드의 d_elem(우선순위 기부 목록에서의 위치를 나타내는 리스트 요소)을 목록에서 제거하고, wait_on_lock을 NULL로 설정한다.(우선순위 기부가 더 이상 필요하지 않음)

우선순위 기부 목록이 비어있지 않다면(다른 스레드들로부터 우선순위 기부를 받고 있는 상황), 목록의 첫 번째 스레드(next_thread)의 우선순위를 현재 스레드의 우선순위로 설정한다.

우선순위 기부 목록이 비어있다면(더 이상 우선순위 기부를 받고 있지 않은 상황), 스레드의 우선순위를 원래의 우선순위(original_priority)로 복원한다.

락의 holder를 NULL로 설정하여, 락의 소유권을 해제하고, sema_up(&lock->semaphore)를 호출하여 세마포어의 값을 1 증가시키고, 세마포어 대기 목록에 있는 스레드 중 하나를 깨운다(있다면). 이는 락이 이제 사용 가능하게 되었음을 나타내며, 대기 중인 스레드가 락을 획득할 수 있게 한다.

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	if(!list_empty(&lock->holder->donations))
	{	
		struct list_elem *front_elem = list_begin(&lock->holder->donations);
		while(front_elem != list_end(&lock->holder->donations))
		{
			struct thread *front_thread = list_entry(front_elem, struct thread, d_elem);
			if(front_thread->wait_on_lock == lock)
			{
				list_remove(&front_thread->d_elem);
				front_thread->wait_on_lock = NULL;
			}			
			front_elem = list_next(front_elem);
		}
		if(!list_empty(&lock->holder->donations))
		{
			struct thread *next_thread = list_entry(list_front(&lock->holder->donations), struct thread, d_elem);
			lock->holder->priority = next_thread->priority;
		}
		else
			lock->holder->priority = lock->holder->original_priority;
	}
	lock->holder = NULL;
	sema_up (&lock->semaphore);
}

세마포어의 대기자 목록(sema->waiters)이 비어있지 않은 경우, 즉 대기 중인 스레드가 있는 경우에는 대기자 목록에서 가장 앞에 있는 스레드(가장 높은 우선순위를 가진 스레드)를 꺼내 thread_unblock 함수를 호출하여 실행 가능 상태로 만들고, 세마포어의 value를 1 증가시킨다. (추가적인 리소스가 사용 가능해졌거나, 더 이상 대기 중인 스레드가 없음)

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
	{
		list_sort(&sema->waiters, cmp_priority, NULL);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}
	sema->value++;
	intr_set_level (old_level);
	thread_yield();
}

donations가 만약 비어있다면, 현재 스레드의 priority 필드를 새로운 우선순위 값으로 업데이트를 하여 기부를 받고 있지 않을 때만 스레드의 우선순위를 직접 변경할 수 있게 해야한다.

void
thread_set_priority (int new_priority) {
	if(list_empty(&thread_current()->donations))
		thread_current ()->priority = new_priority;
		
	thread_current ()->original_priority = new_priority;

	struct thread *head_thread = list_entry(list_begin(&ready_list), struct thread, elem);
	if(head_thread->priority > new_priority)
		thread_yield();
}

조건 변수의 대기자 목록이 비어 있지 않다면, 대기자 목록을 우선순위에 따라 정렬해야한다. 대기자 목록(waiters)에서 가장 앞에 있는 세마포어 요소를 꺼내, 그 세마포어를 통해 대기 중인 스레드 중 하나를 깨운다.

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters))
		list_sort(&cond->waiters, cmp_condvar_priority, NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

조건 변수의 대기자 목록에 있는 두 개의 세마포어에서 객체를 가져와 두 스레드의 우선순위를 비교하여 첫 번째 스레드가 더 높다면, true 두 번째 스레드가 더 높다면 false를 반환한다.

bool
cmp_condvar_priority(const struct list_elem *a, const struct list_elem  *b, void *aux UNUSED) {
	struct semaphore_elem *sema_elem_a = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sema_elem_b = list_entry(b, struct semaphore_elem, elem);

	struct semaphore sema_a = sema_elem_a->semaphore;
	struct semaphore sema_b = sema_elem_b->semaphore;

	struct thread *t_a = list_entry(list_begin(&sema_a.waiters), struct thread, elem);
	struct thread *t_b = list_entry(list_begin(&sema_b.waiters), struct thread, elem);
	
	return t_a->priority > t_b->priority;
}

extra 문제인 MLFQS 빼고 전부 pass되었다.

master branch에 project1만 취급하는 코드가 있음

컨텍스트 스위칭(Context Switching)은 운영 체제의 멀티태스킹과 밀접하게 연관된 중요한 개념이다. 컴퓨터에서 여러 프로세스 또는 스레드가 동시에 실행되는 것처럼 보이게 하는 메커니즘으로, 실제로는 CPU가 빠르게 여러 작업 사이를 전환하면서 각각의 작업에 조금씩 처리 시간을 할당한다.

1. 실행 중인 프로세스의 현재 상태(컨텍스트)를 PCB 형태로 저장해야 한다. 이 컨텍스트에는 PID, 프로세스의 상태(우선순위 등), 프로세스 카운터(PC), 레지스터 세트, CPU 스케줄링 정보, 메모리 상태 등이 포함된다. 이 정보는 프로세스의 컨텍스트를 구성하며, 프로세스가 다시 CPU에서 실행을 계속할 수 있도록 필요한 모든 정보를 포함한다.

2. 스케줄러가 다음에 실행할 프로세스를 결정한다. 이 결정은 운영 체제의 스케줄링 알고리즘에 따라 달라진다.

3. 이전에 저장된 다음 프로세스의 컨텍스트를 복원한다. 이 과정에서 프로세스 카운터, 레지스터, 메모리 상태 등이 CPU에 로드된다.

4. 복원된 컨텍스트를 바탕으로 새로운 프로세스(또는 이전에 중단되었던 프로세스)가 실행을 시작한다.

컨텍스트 스위칭은 자원을 소모하는 작업이다. 컨텍스트를 저장하고 복원하는 데에 시간이 걸리며, 이로 인해 CPU 사용률이 실제 작업 처리에 사용되는 것보다 낮아질 수 있다. 또한, 캐시 메모리가 무효화되는 경우(캐시 콜드 미스)가 발생할 수 있어, 성능 저하를 초래할 수 있다.

프로세스 대신 스레드를 사용하면 컨텍스트 스위칭 비용을 줄일 수 있다. 스레드는 같은 프로세스 내에서 메모리와 자원을 공유하기 때문에 컨텍스트 스위칭 시 저장해야 할 정보가 적다. 운영 체제의 스케줄링 알고리즘 선택도 성능에 영향을 준다. 예를 들어, 시분할(Time-sharing) 시스템에서는 라운드 로빈(Round Robin) 스케줄링이 자주 사용된다.

비선점형 커널은 한 프로세스가 종료될 때까지 점유하기 때문에 경쟁상황이 발생하지 않는다.

​

선점형 커널은 계속해서 컨텍스트 스위칭이 일어나기 때문에 경쟁상황이 발생할 수 있는데 이를 피하기 위해 임계구역이라는 것을 만들어줘야 한다.

​

임계구역이란 파일의 입출력, 공유 데이터 등 원자적으로 실행할 필요가 있는 명령문 또는 코드의 일부 영역이다.

Race condition(경쟁 상황)은 두 개 이상의 프로세스가 공통자원을 병행적으로 읽거나 쓰는 동작을 할 때, 공유 데이터에 대한 접근이 어떤 순서에 따라 이루어 졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 의미한다.

​

경쟁상황은 불 충분한 동기화, 비 원자적인 작업, 실행 순서가 잘못 되었을 때 일어난다. 여기서 비원자적인 것은 어느한 단계를 걸쳐서 실행하는 큰 함수와도 같은 것들을 말한다. 원자적, 즉 더 이상 쪼갤 수 없는 작업 단위로 컨텍스트 스위칭이 일어나야한다.

​

두 개 이상의 프로세스의 Race condition이 일어날 때, 서로 동일한 자원을 두고 경쟁을 하는데 이 경쟁이 끝까지 끝나지 않을 경우를 교착 상태라고 한다. 즉, 두 개의 스레드가 하나의 자원을 놓고 서로 사용하지 않고 경쟁하는 상황이다.

​

Deadlock(교착 상태)은 임계구역에서 둘 이상의 프로세스가 서로 보유하고 있는 자원을 요구하여, 아무도 자신의 작업을 진행할 수 없게 되는 상태를 말한다.

​

Starvation(기아 상태)는 하나 이상의 프로세스가 자원에 대한 접근을 무한정 기다려야 하는 상황이다. 이는 특정 프로세스가 다른 프로세스에 비해 우선 순위가 낮거나, 자원 분배 알고리즘에 의해 불리하게 작용할 때 발생할 수 있다. 부족한 자원을 여러 프로세스가 점유하려고 경쟁할 때 발생한다.

​

Starvation은 SJF, SRT, SPN 처럼 우선순위를 길이로 판단하는 스케줄링을 사용했을 때 일어나며, 이를 방지하기 위해 FIFO같은 우선순위가 아닌 요청 순서대로 처리하는 큐를 사용하는게 좋다.

​

Deadlock은 시스템이 완전히 멈춰버린 상태로, 아무 진전이 없을 수도 있고 즉시 해결해야 하는 긴급한 문제이고, Starvation은 특정 프로세스가 진행할 수 없는 상태지만, 다른 부분은 여전히 작동가능하여 장기적인 관점에서 해결할 수 있는 문제이다.

세마포어(Semaphore): 동시성 프로그래밍에서 공유 자원에 대한 접근을 제어하기 위해 사용되는 변수나 추상 데이터 타입이다. 멀티 스레드나 프로세스 환경에서 여러 스레드 또는 프로세스가 동시에 공유 자원을 사용하려 할 때, 이를 안전하게 조정하기 위한 메커니즘 중 하나이다.

​

이진 세마포어(Binary Semaphore): 값이 0 또는 1만을 가질 수 있는 세마포어로, 뮤텍스(Mutex)와 유사한 기능을 한다. 이는 공유 자원에 단 하나의 스레드/프로세스만 접근할 수 있게 하여 상호 배제(Mutual Exclusion)를 구현한다.

​

카운팅 세마포어(Counting Semaphore): 값이 0 이상의 정수를 가질 수 있는 세마포어로, 한 번에 여러 스레드/프로세스가 공유 자원에 접근할 수 있게 한다. 카운팅 세마포어의 값은 동시에 접근할 수 있는 최대 스레드/프로세스 수를 의미한다.

​

세마포어는 주로 두 가지 기본 연산, wait()(또는 P(), acquire()) 연산과 signal()(또는 V(), release()) 연산을 사용한다.

​

wait() 연산: 스레드/프로세스가 공유 자원을 사용하기 전에 이 연산을 호출한다. 세마포어의 값이 0보다 크면, 세마포어의 값을 1 감소시키고 실행을 계속한다. 만약 세마포어의 값이 0이면, 공유 자원이 사용 가능해질 때까지 스레드/프로세스를 대기 상태로 만든다.

​

signal() 연산: 스레드/프로세스가 공유 자원의 사용을 마친 후에 이 연산을 호출한다. 세마포어의 값을 1 증가시키고, 대기 중인 스레드/프로세스 중 하나를 깨워 공유 자원을 사용할 수 있게 한다.

import threading
import time
import random

# 세마포어 생성, 동시에 리소스에 접근할 수 있는 스레드의 최대 수를 2로 설정
semaphore = threading.Semaphore(2)

class MyThread(threading.Thread):

    def run(self):
        # 세마포어 획득(리소스 접근)
        with semaphore:
            print(f"{self.name} is now sleeping")
            time.sleep(random.randint(1, 5))
            print(f"{self.name} is finished")

# 스레드 객체 생성
threads = []
for i in range(4):
    threads.append(MyThread())

# 모든 스레드 시작
for t in threads:
    t.start()

# 모든 스레드의 종료를 기다림
for t in threads:
    t.join()

​

뮤텍스(Mutex, Mutual Exclusion Object)

동시성 프로그래밍에서 공유 자원에 대한 동시 접근을 방지하기 위해 사용되는 동기화 메커니즘이다. 뮤텍스는 한 번에 하나의 스레드만 공유 자원을 사용할 수 있도록 보장함으로써, 데이터의 일관성과 무결성을 유지한다.

​

스레드가 공유 자원을 사용하기 전에 뮤텍스를 잠그거나 획득한다. 이 시점에서 해당 뮤텍스는 잠긴 상태가 되며, 다른 스레드는 그 자원을 사용할 수 없다.

​

뮤텍스를 성공적으로 잠근 스레드는 공유 자원을 안전하게 사용할 수 있다. 스레드가 자원 사용을 마치면 뮤텍스를 해제하거나 방출한다. 이로써 다른 스레드가 해당 자원에 접근할 수 있는 기회를 얻는다.

import threading
import time
import random

mutex = threading.Lock()

class ThreadOne(threading.Thread):

    def run(self):

        global mutex
		# 뮤텍스를 획득
        mutex.acquire()  

        print("The first thread is now sleeping")

        time.sleep(random.randint(1, 5))  # 1초에서 5초 사이의 랜덤한 시간 동안 대기

        print("First thread is finished")
        
        # 작업이 끝나면 뮤텍스를 해제
        mutex.release()  

class ThreadTwo(threading.Thread):

    def run(self):
    
        global mutex
        
		# 첫 번째 스레드가 뮤텍스를 해제할 때까지 대기
        mutex.acquire()  

        print("The second thread is now sleeping")
        
		# 1초에서 5초 사이의 랜덤한 시간 동안 대기
        time.sleep(random.randint(1, 5))  

        print("Second thread is finished")
        
		# 작업이 끝나면 뮤텍스를 해제
        mutex.release()  

t1 = ThreadOne()
t2 = ThreadTwo()

t1.start()
t2.start()

t1.join()  # 첫 번째 스레드가 종료될 때까지 메인 스레드 대기
t2.join()  # 두 번째 스레드가 종료될 때까지 메인 스레드 대기