코딩개발 코딩개발

CS

• Dynamic Programming이란?

  CS/면접준비 2022. 7. 18. 16:56

  Dynamic Programming이란? 큰 문제를 작은 문제로 나누어 푸는 문제입니다. + 작은 문제가 중복되어 발생하는지 여부 및 작은 문제의 답이 동일 Devide&Conquer와 동일한 것이지 않는가? -> Devide&Conquer도 큰 문제를 작은 문제로 나누어 푸는 부분에서 동일합니다. 하지만 Devide&Conquer는 말 그대로 작은 문제로만 나누어서 풀 뿐 작은 문제가 중복해서 발생한다던지 하지 않습니다. Memoization 작은 문제가 중복으로 발생하다보니 동일한 연산을 중복으로 할 이유가 없습니다. 따라서 해당 문제의 답을 적어두는 것입니다. DP의 대표적인 예가 피보나치, ROD CUTTING(막대기 자르기) 등이 있습니다. 1,1,2,3,5,8 .... 은 다음 수열 = 이전 ..

  Read More
• 9. Virtual Memory advantages and paging algorithm

  CS/OS 2022. 6. 23. 17:12

  Virtual Memory Advantage 1. Shared Memory ( window dll , linux so .. ) Multiple Process 간의 communication의 방법으로 공유 메모리를 사용할 수 있는데, demand-paging 기법을 사용할 경우 다른 프로세스의 각각의 페이지가 같은 프레임을 가리키도록 하면 공유 메모리를 사용할 수 있다. 아래 그림을 보면 Process A의 Page1과 Process B의 Page7은 서로 같은 Memory를 가르키고 있어 공유가 가능하다. dll in window 혹은 so in linux 이 방식으로 Physical Memory Frame을 같이 가리켜, Memory save 2. COW(Copy on Write) Fork System..

  Read More
• 8. Vitrual Memory

  CS/OS 2022. 6. 23. 01:42

  Virtual Memory 가상 메모리는 프로세스의 virtual memory(logical memory)와 physical memory를 분리하기 위해 생겨난 것 모든 프로세스는 자신만의 가상 주소 공간을 가지고 있다. 32비트/64비트 프로세스는 각 비트수에 맞게 최대 4GB/16EB의 주소 공간을 가진다. 모든 프로세스들은 자신만의 주소 공간을 가지기 때문에, 특정 프로세스 내에서 쓰레드가 수행될 때 해당 쓰레드는 프로세스가 소유하고 있는 메모리에 대해서만 접근이 가능하다. OS Memory는 숨겨져 있다. 쓰레드가 OS의 Data에 Access하는 것이 불가능하다. 따라서, A 프로세스가 0x12345678 주소에 무엇인가를 저장하였지만, B 프로세스 역시 0x12345678 주소에 무엇인가를 저..

  Read More
• xv6 Test code

  CS/OS 2022. 6. 2. 17:12

  Github = https://github.com/Kimuksung/Xv6 를 참고하시면 됩니다. Test Code를 돌리기 전에 Kaist Os Lab을 참고하여 작성하였습니다. 해당 OS lab pdf를 먼저 참고오시면 매우 도움이 됩니다. 1. Execute a Program in Xv6 제가 임의로 만든 test.c 와 practice1.c 를 돌려볼 예정입니다. xv6 제공하는 header file이 정해져 있기 때문에 아래와 같은 상황을 주의해야합니다. 따라서 stdio.h 사용할 수 없습니다. 대신에 아래 header file로 생성해야 합니다. 상황에 맞게 가져다가 사용하면 됩니다. “types.h” : header file for variable types “user.h” : header..

  Read More
• xv6 (linux Init)

  CS/OS 2022. 6. 2. 14:22

  linux 설치 Orcale VM Virtual Machine -> OS( LTS 18.04 build-essential 시에 20.04는 충돌이 난다) setting sudo apt-get install git wget qemu sudo apt install build-essential git clone https://github.com/mit-pdos/xv6-public.git sudo apt-get install gdb ( if you don't have it.. ) cd xv6-public make qemu-nox CPUS=1 #qemu exit Ctrl+A -> X Run #init.c // init: The initial user-level program #include "types.h" #i..

  Read More
• 7.Posix thread(Pthread)

  CS/OS 2022. 5. 25. 20:42

  들어가기 전에 Process에 대해서 살펴보고 시작한다. Process / Thread 일반적으로 Unix Process 는 Main() Function으로 부터 실행되는 Single Thread이다. 앞서 말하였듯이 Fork()를 통해 Process가 생성됨으로 Memory 및 File Descriptor를 Copy-on-Write 방식으로 자식에게 복사하여준다. 반면, Thread는 전역 Memory들은 서로 공유하고 있기 때문에 Process보다 속도가 빠르다. Thread = Semi Process = Light weight Process 라고 불린다. Posix Thread 일반적으로 PThread로 불리며, Thread를 지원하기 위한 C 표준 라이브러리 셋을 사용하여 동작시켜야 한다. #Pt..

  Read More
• 5. Process_Scheduling

  CS/OS 2022. 5. 19. 17:31

  CPU(Processor) 는 하나의 Prcoess 작업이 수행되면, 다음 Process를 작업하여 수행한다. 이 때 다음 Process가 어떤것이 와야 효율적이고 사용자의 입장에서 빠르다고 느낄 수 있을까? 라는 관점에서 나온것이 Process Scheduling 이다. 여러 방법이 있음으로, 상황에 맞게 사용해야 한다. 1. Preemptive vs Non-Preemptive 1-1) Preemptive 다른 Process가 CPU를 점유하고 있을 경우에 I/O , Interrupt , Process exit 이 되지 않음에도 불구하고 다른 Process가 점유한 자리를 뺏을 수 있는 경우이다. 즉, 프로세스가 정상적으로 수행중인 가운데 다른 프로세스가 CPU를 강제로 점유하여 실행할 수 있는 것이다..

  Read More
• XV6 - 이론 정리_2

  CS/OS 2022. 5. 13. 18:33

  이제부터는 XV6가 어떻게 동작하는 지 실제 부팅부터 알아볼 겁니다. Step1 - Booting PC powers on -> load bootloader(bootasm.S, bootmain.c) -> load kernel -> execute kernel entry 컴퓨터는 하드웨어를 초기화 및 부트로더라는 프로그램(bootasm.S)을 실행시킨다. 부트로더(xv6에서 bootasm.S, bootmain.c의 코드로 구성된다.)는 항상 디스크의 첫번째 섹터에 위치하며 커널 이미지를 메모리로 로드한다. 부트로더는 항상 xv6 kernel을 물리메모리 0x100000 번지에 위치시킨다. 더 낮은 번지의 물리메모리는 I/O device에 관해 쓰인다. 부트로더가 xv6의 entry(entry.S)에 진입함으로..

  Read More