Project2: User Programs(introduction)

Introduction

이제 Pinto를 사용하여 작업하고 인프라 및 스레드 패키지에 익숙해지고 있으므로 사용자 프로그램 실행을 허용하는 시스템 부분에 대한 작업을 시작할 때입니다.

The base code already supports loading and running user programs, but no I/O or interactivity is possible.

✅ 기본 코드는 이미 사용자 프로그램 로드 및 실행을 지원하지만 I/O 또는 상호 작용은 불가능합니다.

you will enable programs to interact with the OS via system calls.

✅ 이 프로젝트에서는 프로그램이 시스템 호출을 통해 OS와 상호 작용할 수 있도록 합니다.

You will be working out of the userprog, but you will also be interacting with almost every other part of Pintos.

✅  userprog에서 작업할것이지만 Pintos의 거의 모든 다른 부분과도 상호 작용할 것입니다.

프로젝트 1 제출물 위에 프로젝트 2를 빌드해야 합니다. 프로젝트 1의 코드는 프로젝트 2의 코드에 영향을 미치지 않지만 증분 프로젝트이기 때문에 프로젝트 1에 대한 테스트 사례를 통과해야 합니다.

Lastly, please note that the code without TODO does not always you don't need to change that code. You can freely modify any source codes in project2, except the testing codes.

마지막으로 TODO가 없는 코드는 항상 변경할 필요가 없는 것은 아닙니다. 테스트 코드를 제외한 프로젝트2의 모든 소스 코드를 자유롭게 수정할 수 있습니다.

 

Background

지금까지 Pintos에서 실행한 모든 코드는 운영 체제 커널의 일부였습니다.

• 모든 테스트 코드가 커널의 일부여서 system의 모든 특권 부분까지 실행 가능했음
• 하지만 유저 프로그램을 실행할때는 특권 부분에 함부로 접근할 수 없음.

We allow more than one process to run at a time. Each process has one thread (multithreaded processes are not supported).

한 번에 둘 이상의 프로세스를 실행할 수 있습니다. 각 프로세스에는 하나의 스레드가 있습니다(다중 스레드 프로세스는 지원되지 않음).

User programs are written under the illusion that they have the entire machine. This means that when you load and run multiple processes at a time, you must manage memory, scheduling, and other state correctly to maintain this illusion.

사용자 프로그램은 컴퓨터 전체를 가지고 있는 것으로 착각하여 작성됩니다. 즉, 한 번에 여러 프로세스를 로드하고 실행할 때 메모리, 예약 및 기타 상태를 올바르게 관리해야 이러한 착각을 유지할 수 있습니다.

In the previous project, we compiled our test code directly into your kernel, so we had to require certain specific function interfaces within the kernel. From now on, we will test your operating system by running user programs.

이전 프로젝트에서 우리는 테스트 코드를 당신의 커널에 직접 컴파일했기 때문에 커널 내의 특정한 함수 인터페이스를 필요로 했다. 지금부터 사용자 프로그램을 실행하여 운영 체제를 테스트합니다.

All of your codes should never located in block that enclosed by #ifdef VM. This blocks will be included after enabling the virtual memory subsystem, which you will implement in the project 3. Also, if the codes is enclosed by #ifndef VM, those codes will be omitted from project3.

모든 코드가 #ifdef VM으로 둘러싸인 블록에 위치해서는 안 됩니다. 이 블록은 프로젝트 3에서 구현할 가상 메모리 하위 시스템을 활성화한 후에 포함됩니다. 또한 #ifndef VM으로 코드를 묶으면 프로젝트3에서 해당 코드가 생략됩니다.

 

We strongly recommend you to read synchronization and virtual addrees before you start.

Virtual Address · GitBook

A 64-bit virtual addresses are structured as follows:

64비트 가상 주소는 다음과 같이 구성됩니다.

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

64비트 가상 주소 구조

• 0 ~ 11 bits: physical offset
• 12 ~ 20 bits: page-table offset
• 21 ~ 29 bits: page-directory offset
• 30~38 bits: page-directory pointer
• 39~47 bits: page-map level-4 offset
• 48~63 bits: sign extend

Source Files

process.c, process.h

ELF 바이너리를 로드하고, 프로세스를 시작한다.

ELF(Executable and Linkable Format)는 유닉스 계열 운영체제의 실행, 오브젝트 파일, 공유 라이브러리(바이너리 파일), 실행 파일을 위해 사용되는 파일 형식이다.

syscall.c, syscall.h

사용자 프로그램이 일부 커널 기능에 접근하기를 원할 때마다 시스템 콜을 호출한다.

시스템 콜 핸드러에 대한 스켈레톤 코드를 확인할 수 있고,

현재는 메시지를 출력하고 사용자 프로세스를 종료하는 것이 전부이다.

✅ 시스템 콜에 필요한 코드를 여기에 추가해야 한다.

syscall-entry.S

시스템 콜 핸들러를 bootstrap하는 어셈블리 코드

bootstrap: 전원을 켜거나 재부팅을 할때 적재되는 프로그램

exception.c, exception.h

유저 프로세스가 특권 연산, 금지된 연산을 수행하려고 할때 exception이나 fault의 형태로 kernel에 들어갈 수 있도록 한다(trap).

예외를 처리하는 로직을 다룬다.

현재 모든 예외 처리는 메시지를 출력하고 사용자 프로세스를 종료하기만 한다.

이 파일의 page_fault( )를 수정해야 한다

gdt.c, gdt.h

GDT(global descriptor table)을 이용하여 현재 사용중인 세그먼트들을 관리한다.

프로젝트에 대해 이 파일들 수정할 필요가 없음.

tss.c, tss.h

task switching에 사용 : 유저 프로세스가 인터럽트 핸들러에 들어가면 하드웨어는 커널의 스택포인터를 찾기 위해 Tss를 참조

TSS(Task-State Segment)

프로젝트에 대해 이 파일들 수정할 필요가 없음.

 

Using the File System

유저 프로그램이 파일 시스템으로 부터 불려지고 구현해야할 많은 시스템콜이 파일 시스템을 다루기 때문에 파일 시스템 코드를 연결해야 한다.

• filesys.h, file.h를 보고 파일 시스템을 어떻게 사용하는지, 어떤 제약사항이 있는지 파악하자.

파일 시스템 관련 코드를 바꿀 필요는 없다.

파일 시스템 루틴을 올바르게 사용하는 것은 project 4를 더 쉽게 할 수 있도록 해준다. (파일 시스템 구현을 개선)

• 내부 동기화가 구현되어 있지 않다.
• 하나의 프로세스만 파일 시스템 코드를 다루도록 동기화기법을 사용해야 한다.
• 파일 크기는 생성될 때 고정된다. 루트 디렉토리가 파일로 나타내어지기 때문에 파일의 수도 제한된다.
• 파일 데이터는 하나의 범위에 할당된다.
  • 하나의 파일의 데이터들은 디스크의 연속적인 범위의 섹터를 차지해야 한다.
  • 외부 단편화 문제가 있다.
• 하위 디렉토리가 없다.
• 파일 이름은 14자로 제한된다.
• 파일 시스템을 자동으로 고쳐주는 도구가 없다.

unix와 같이 filesys_remove()가 구현되어 있다. 파일이 제거될 때 열려 있는 경우 블록은 할당 해제되지 않으며 마지막으로 파일이 닫힐 때까지 열려 있는 스레드에 의해 액세스할 수 있다.

파일을 핀토스 가상머신에 올리기

Pintos에서 가상 머신에 파일을 넣으려면, 시스템 파티션을 가진 시뮬레이션 디스크를 생성해야 한다.

pintos-mkdisk 프로그램이 해당 기능을 제공한다.

• pintos-mkdisk프로그램을 통해 파일시스템 파티션으로 디스크 생성
  • userprog/build 폴더로 이동하여 pintos-mkdist filesys.dsk 2로 생성
    • 2MB의 핀토스 파일 시스템 파티션을 포함하는 filesys.dsk라는 이름의 가상의 디스크를 생성해준다.
• disk를 인자를 넘겨서 명시해주고 포맷해준다.
  • pintos --fs-disk filesys.dsk -- -f -q : 디스크를 특정해주기
  • -f : format (파일 시스템 실행을 위한 포맷)
  • -q : 포맷이 끝났을때 핀토스를 종료하기 위해 사용
  • pintos -p file:newname -- -q: file을 newname으로 핀토스 파일 시스템으로 복사
    • VM에서 파일을 빼올때는 -p대신 -g를 사용
    • 궁금하면 filesys/fsutil.c과 pintos script를 살펴보자. 📖
  예시 )다음 줄은 파일 시스템을 포맷하고, 프로젝트의 두 번째 테스트 사례인 args-single 프로그램을 디스크에 복사한 후
• 'one arg'라는 인자를 전달하여 프로그램을 실행하는 명령어이다
• 우선 첫 번째 줄은 10MB 크기의 디스크를 만드는 과정이다.
• 파일 시스템 파티션에서 디스크를 생성하는 방법 요약
• pintos-mkdisk filesys.dsk 10 pintos --fs-disk filesys.dsk -p tests/userprog/args-single:args-single -- -q -f run 'args-single onearg'
• 생성한 파일 시스템을 나중에 사용하기 위해 남기지 않는 경우 한줄로 4단계를 수행할 수 있다.
• pintos --fs-disk=10 -p tests/userprog/args-single:args-single -- -q -f run 'args-single onearg'

How User Programs Work

• 핀토스는 메모리에 올라갈 정도의 크기를 갖고 내가 작성한 시스템 콜만 사용하는 경우 일반적인 c프로그램을 동작시킬수 있다.
• 핀토스는 ELF 실행파일을 load할 수 있는데, 그 loader는 userprog/process.c에 있다.
• 테스트 프로그램을 핀토스 파일 시스템으로 올리기 전에는 아무것도 할 수 없다.
• filesys.dsk를 버리고 다시 생성할 수 있으며 유용한 상태를 남기기 위해 값을 복사해 둘 수 있다.

Virtual Memory Layout

두 영역으로 나뉜다.

• user virtual memory
  • 0에서 KERN_BASE까지를 나타낸다.
  • include/threads/vaddr.h
• kernel virtual memory
  • 나머지 가상 주소 공간을 차지하고 있다.
• 유저 가상 메모리는 프로세스당 하나씩 있다.
  • 커널이 하나의 프로세스에서 다른 프로세스로 전환할 때 프로세서의 page directory base register의 값을 바꿔줌으로서 가상 메모리도 전환된다.
    • thread/mmu.c → pml4_activate()
    • thread 구조체는 process의 page table을 가리키는 포인터를 갖는다.
• 커널 가상 메모리는 전역이다. 언제나 같은 방식으로 매핑된다.
  • 1-1으로 물리 메모리에 매핑된다.
• 유저 프로그램은 스스로의 가상 메모리에만 접근할 수 있고 커널 가상 메모리에 접근하는 경우 page fault가 발생되어 userprog/exception.c → page_fault()에서 처리되며 프로세스가 종료된다 .
  • 페이지폴트 :
  • 페이지 폴트란 프로그램이 자신의 주소 공간(가상메모리공간)에는 존재하지만 시스템의 RAM에는 현재 없는 데이터나 코드에 접근 시도하였을 경우 발생하는 현상을 말한다. 페이지 폴트가 발생하면 운영체제는 그 데이터를 메모리로 가져와서 마치 페이지 폴트가 전혀 발생하지 않은 것처럼 프로그램이 계속적으로 동작하게 해준다. 앞에서 설명한 바와 같이 CPU는 우선 원하는 주소(12374)를 MMU에게 보내게 된다. 그러나 MMU는 주소 변환 과정에서 페이지 테이블(Page Table)에 이 주소에 대한 항목이 없다고 표시할 것이다. 그 다음 MMU는 CPU를 인터럽트 한 후, 페이지 폴트 처리기라는 소프트웨어가 실행되도록 한다. 이 페이지 폴트 처리기가 원하는 페이지를 디스크 상 어디에 위치하는지 찾은 후 읽어오게 하는 작업을 한다.
  • 1. CPU는 물리 메모리을 확인하여 페이지가 없으면 trap을 발생하여 운영체제에 알린다.
    2. 운영체제는 CPU의 동작을 잠시 멈춘다.
    3. 운영체제는 페이지 테이블을 확인하여 가상 메모리에 페이지가 존재하는지 확인하고, 없으면 프로세스를 중단한다.
    4. 페이지 폴트이면, 현재 물리 메모리에 비어있는 프레임(Free Frame)이 있는지 찾는다. 물리 메모리에 비어있는 프레임이 없으면 어떻게 될까? 프로세스를 멈출 수는 없으므로,희생 프레임을 골라서 이를 가상 메모리에 저장 후 필요한 페이지를 물리 메모리에 로드한다!! 그리고 이 과정에서 페이지 교체 알고리즘(Page Replacement Algorithm)이 사용된다.이 때 운영체제가 페이지 폴트를 해결하는 과정을 요구 페이징(Demand Paging)이라고 한다. 지금부터 요구 페이징의 과정에 대해 더 자세히 알아보도록 하겠다.
    5. 비어있는 프레임에 해당 페이지를 로드하고, 페이지 테이블을 최신화 한다.
    6. 중단되었던 CPU를 다시 시작한다.
    • 페이지 교체 알고리즘:
      
      • FIFO(First In First Out): 가장 먼저 물리 메모리에 적재된 페이지를 선택하는 방식.
      • LRU(Least Recent Used): 가장 오랫동안 사용되지 않았던 page를 선택하는 방식.
      • LRU Approximation: LRU와 같지만, 페이지에 Second-Chance를 준다. (각 페이지들을 Circular queue형태로 나타낸 후 LRU에 의해 희생 페이지(Victim Page)가 선택되었을 때 해당하는 queue의 bit가 0이면 해당 페이지를 제거한다. bit가 1이면 0으로 설정한다.)
  • 커널 스레드는 커널 가상 메모리와 실행 중인 프로세스의 사용자 가상 메모리 모두 액세스 가능하다. 그러나 커널에서도 매핑되지 않은 사용자 가상 주소의 메모리에 액세스하려고 하면 page fault가 발생한다.

Typical Memory Layout

 

• 개념적으로는 각 프로세스가 원하는대로 사용자 가상 메모리를 자유롭게 배치할 수 있다.
• 사용자 가상 메모리는 아래와 같이 배치된다.
• 본 프로젝트에서 유저 스택은 고정된 크기를 갖는다.
• BSS도 고정이라고 생각하자.
• 핀토스의 코드 세그멘트는 0x400000부터 시작된다.
  • 약 128MB
• 링커는 메모리에서 유저 프로그램의 레이아웃을 결정한다.
  • 다양한 프로그램 세그멘트의 이름과 위치를 적어둔 링커스크립트를 이용한다.
  • info ld를 통해 더 다양한 링커 스크립트에 관한 정보를 얻을 수 있다.

Accessing User Memory

사용자가 가상 메모리에 매핑되지 않았거나 커널 가상 주소 공간(KERN_BASE 위의 공간)에 대한 포인터, NULL 포인터를 전달할 수 있다.

이러한 유효하지 않은 포인터들를 전달한 프로세스의 경우 page fault를 야기한다.

userprog/exception.c에 있는 코드를 수정하여 프로세스를 종료시킨 후 자원을 해제하는 등의 처리가 이루어져야 한다.

• 시스템콜의 일부로서 커널은 유저 프로그램이 제공해준 포인터를 통해서 메모리에 접근해야 한다.
  • Null pointer
  • unmapped virtual memory
  • pointer to kernel virtual address space
  • 위와 같은 값들은 reject해야 한다.
• 두가지 방식
  • 유저가 제공한 포인터를 검증한 후 dereference(역참조)하는 방법이 있다.
    • thread/mmu.c & include/threads/vaddr.h
  • 유저가 제공한 포인터가 KERN_BASE보다 밑을 가리키는지 확인한 후 dereference하는 방법이 있다.
    • 유효하지 않은 유저 포인터는 page fault를 발생시키기 떄문에 userprog/exception.c의 page_fault()함수를 고쳐서 처리할 수 있다.
      • MMU를 이용할 수 있기 때문에 일반적으로 더 빠르다.
  • 두가지 방식 모두 자원의 누수가 발생하지 않도록 해야한다.
    • lock이나 메모리 할당을 받은 프로세스가 잘못된 메모리 접근을 시도하는 경우
    • lock과 할당받은 메모리를 해제해 준 후에 처리해야 한다.