Showing

1. Queue 개념과 구현 Queue는 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조입니다. queue의 rear에 데이터를 추가하는 것을 enqueue라고 합니다. 또한 queue의 front에서 데이터를 꺼내는 것을 dequeue라고 합니다. 더블링크드리스트를 파이썬으로 아래와 같이 구현해보았습니다.(직접 구현한 것이므로 버그가 있다면 지적 부탁드립니다.) Array list로 구현한 큐는 선출할 때, O(n)의 시간복잡도가 걸리므로(배열 길이만큼 한칸씩 앞으로 땡겨주어야 함) O(1)로 처리가능한 링크드리스트로 구현하는 것이 좋습니다.(head 값만 바꿔주면 됨) class Node: def __init_..

* 이론을 토대로 직접 구현한 것이므로 버그가 발생할 수 있습니다. 버그 발생시 댓글 남겨주시면 감사하겠습니다. 1. 물리적 비연속적, 논리적 연속적 Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조입니다. 각각의 요소(Node)가 데이터 값과 다음 요소를 가리키는 포인터(next node의 주소값)로 구성된 자료구조입니다. 각 Node들은 데이터를 저장할 뿐 아니라, next node의 addr 정보도 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결될 수 있습니다. Array의 경우 연속성을 유지하기 위해 메모리 상에서 순차적으로 데이터를 저장하는 방식을 사용하였지만, Linked lsit에는 메모리상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이..

1. List 자료구조 vs Set 자료구조 Set과 List는 둘 다 선형자료구조이지만 중요한 차이점이 있습니다. (1) 중복된 요소 (2) 순서가 있는/없는 (3) 인덱스 기반 접근 (1) 중복 요소 - Set은 중복된 요소를 허용하지 않습니다. 각 요소는 유일해야 합니다. - List는 중복된 요소를 허용합니다. 동일한 요소가 여러 번 포함될 수 있습니다. (2) 순서 - Set은 인덱스 순서가 보장되지 않습니다. [1,2,3],[2,1,3], [3,1,2]가 각 인덱스와 값이 달라도 set에 들어가면 [1,2,3]으로 동일한 자료구조가 됩니다. 각 요소가 어떤 순서로 들어오든 상관없이 하나씩 존재한다는 점에서 모두 같은 set이 되는 것입니다. 요소들의 순서는 구현에 따라 다를 수 있습니다. - ..

1. gdb를 통한 Project 3 추적 프로젝트3 VIRTUAL MEMORY부터는 본격적으로 gdb를 활용해서 코드파악을 하였습니다. 본 포스팅은 프로젝트2때와 다르게 vm일 경우 lazy_load_segment까지 도달하는 일련의 과정이 있어, 디버깅을 찍어보면서 추적한 기록을 남기는 포스팅입니다. pintos --gdb -m 20 --fs-disk=10 -p tests/userprog/args-multiple:args-multiple --swap-disk=4 -- -q -f run 'args-multiple some arguments for you!' 위와 같은 명령어를 통해 Pintos 운영 체제를 가상 머신(VM) 상에서 테스트하였습니다. --gdb 옵션: Pintos를 GDB 디버거와 함께 ..

pintos --gdb -m 20 --fs-disk=10 -p tests/userprog/halt:halt --swap-disk=4 -- -q -f run halt 혹은, pintos --gdb -m 20 --fs-disk=10 -p tests/userprog/args-multiple:args-multiple --swap-disk=4 -- -q -f run 'args-multiple some arguments for you!' gdb kernel.o (gdb) target remote localhost:1234 😃 개별 테스트 결과 확인 : 개별 테스트 예시1 : make tests/vm/mmap-clean.result VERBOSE=1 개별 테스트 예시2: make tests/userprog/args-..

목차 - (1) 유저영역 커널영역 - (2) 유저모드 커널모드 - (3) 유저레벨쓰레드 커널레벨쓰레드 - (4) 유저스택 커널스택 * 핀토스 프로젝트1,2에 임하면서 작성했던 WIL에서 헷갈렸던 유저단, 커널단 개념들만 따로 정리해둔 포스팅입니다. (1) 유저영역 커널영역 유저 영역 : 프로그램이 동작하기 위해 사용되는 메모리 공간 → 스택 영역, 힙 영역, 데이터 영역, 코드 영역 커널 영역 : 운영체제를 실행시키기 위해서 필요한 메모리 공간, 메모리에서 유저 영역을 제외한 영역 커널이 위치함 + 커널 : 운영체제의 핵심부로 컴퓨터 자원(CPU, 메모리, 파일 등)들을 관리함 → 메모리에 상주하는 운영체제의 부분 = 커널 ​ 커널은 컴퓨터 자원을 관리하며 사용자와의 상호작용을 하지 않음 (2) 유저모드..

시스템 콜(System Call) Argument Passing에서 pintos의 커맨드라인에서 인자를 파싱하고 패싱할 수 있도록 구현을 했다지만 우리의 project2 핀토스에서는 아직 시스템콜 핸들러와 각 시스템 콜에 대한 처리가 구현되어 있지 않기 때문에 시스템콜이 호출되지 않습니다! 따라서 응용프로그램을 사용자의 기대대로 쓰고, 읽고, 실행하는 등의 일련의 작업을 할 수 없습니다. 사용자모드, 커널모드, 인터럽트, 시스템 콜의 관계 운영체제에는 사용자 모드(User mode)와 커널 모드(Kernel mode)가 있는데 사용자 모드에서 자원에 대한 직접적인 접근을 할 수 없습니다. 반면에 커널모드는 컴퓨터의 모든 자원에 대한 접근 권한을 가집니다. 따라서 사용자 프로세스가 디스크 읽기와 같은 명령..

1. Argument Passing 인자 전달 Argument Passing은 사용자가 입력하는 정보들(명령줄 인자)을 프로그램에게 전달하는 것을 말합니다. 예1) "grep apple fruits.txt"와 같은 명령어가 있다면, "grep"은 실행할 프로그램 이름이며, "apple"은 검색할 단어, "fruits.txt"는 검색 대상 파일이 될 수 있습니다. 예2) "gomoku start --size=15 --mode=multiplayer"와 같은 명령어가 있다고 가정할때, "gomoku"는 실행할 프로그램 이름이고, "start"는 게임 시작 옵션, "--size=15"는 게임판의 크기를 15로 설정, "--mode=multiplayer"는 멀티플레이 모드 등 이렇게 입력된 정보를 프로그램에서 활..

1. 백준 14719번(빗물) 풀이 방법 모노톤 스택 알고리즘을 활용하여 풀 수 있습니다. Monotonic stack 모노톤 스택 알고리즘은 다음과 같은 방법으로 동작합니다. 스택이 비어 있거나, 스택의 맨 위에 있는 원소가 현재 원소보다 큰 경우, 현재 원소를 스택에 push 합니다. 스택의 맨 위에 있는 원소가 현재 원소보다 작은 경우, 스택에서 원소를 꺼내면서 빗물의 양을 계산합니다. 이 때, 빗물의 양은 스택에서 꺼낸 원소와 현재 원소 사이에 고일 수 있는 빗물의 양입니다. 빗물의 양을 계산한 후, 스택에 현재 원소를 push 합니다. 이 과정을 모든 원소에 대해 반복하면, 스택에는 모노톤한 부분 수열이 저장되고, 빗물의 양을 계산할 수 있습니다. 모노톤 스택 알고리즘은 시간 복잡도가 O(n)으..

1. Explicit Free Lists 구현해보기 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 Explicit Free Lists를 구현한 것을 토대로, 주요 로직 사항을 정리해보고자 합니다. 묵시적 가용 리스트와 다른 주요한 차이점은 (1) 포인터 2개가 추가되고, 그만큼 프리 블록의 최소크기가 커진다는 점, (2) coalesced block을 free list의 맨 앞에 삽입해야 한다는 점입니다(LIFO 순서로 리스트를 유지하는 방법을 취하였기 때문) 2. Implicit Free Lists vs Explicit Free Lists 암시적 프리 리스트는 구현이 비교적 간단하지만, 블록 할당 시간이 힙 블록의 총 수에 선형적으로 비례하기 때문에, 일반적인 목적의 할당자에 적합하지 않습니다. (..