본문 바로가기

🚗 Major Study (Bachelor)164

알고리즘 6주차 강의 Huffman Codes: Text Encoding Encoding과 Decoding. 전자에서 Analog신호를 Digital로 바꿀때 Encoding이라고 한다. 전산에서는 프로그래밍, 부호화를 Encoding이라고 한다. Data를 0과 1의 신호로 바꾸는 것을 의미함. 반대의 과정을 Decoding이라고 부름. 공백도 캐릭터로 처리가 된다. 17byte보다 적게 어떻게 표현하는가 Huffman code 12개의 케릭터를 4비트로 표현할 수 있다. 4비트로 충분하다. 이전에 사용했던 17byte에 비해 Compact하게 표현할 수 있게 된다. 2개의 방법 둘 다 fixed layer라고 표현한다. Huffman Codes 어떤 케릭터는 3bit 어떤 케릭터는 4bit로 사용해서 bit수를 save할.. 2022. 4. 4.

[OS / 운영체제] TCB, Multicore Programming, Concurrency vs Parallelism, Amdahl's Law, Kernel Thread, Scheduler Activation Motivation 두 개의 프로그램을 만들고 싶을 때 프로세스를 사용하면 안정성이 좋아진다. 하나의 프로세스 안에서 쓰레드를 두 개 사용하다가 하나의 쓰레드가 죽으면 해당 프로세스가 죽어버리기 때문에 안정성 측면에서 좋지 않다. 하지만 쓰레드는 더 경제적이고 정보를 공유할 때 편리하다. 프로세스는 원래 독립적인 Entity이므로 쉽지 않다. 쓰레드끼리 통신을 할 때 Shared Memory가 필요하지 않다. 그저 전역 변수를 사용하면 가능하다. Overview 프로세스는 실행 중인 프로그램을 의미하고 독립적인 자원이다. 반면 쓰레드는 프로세스 안의 프로그램이여서 자원을 공유해서 사용한다. Thread ID와 PC, register set, stack들로 구성되어 있다. PC는 쓰레드 마다 하나씩 가지고.. 2022. 4. 4.

알고리즘 5주차 월요일 강의 Greedy Algorithm Dynamic Programming is Blind 뭔가 잘 보이지 않는 상태에서 푸는 문제의 느낌이라는 것. matrix chain이나 LCS같은 경우의 Time Complexity는 다음과 같다. 세타라고 표현을 해야 한다. (정정 필요) LCS의 경우 M과 N이 order가 비슷하다고 하면 세타 M^2까지 가능할 수 도 있다. 비교적 차수가 높게 나온다. 왜 그런가? Optimal solution을 계산할 때 선택이 굉장히 여러가지가 존재한다. 그 선택이 어느게 옳은 선택인지 모든 경우의 수를 고려해야 하기 때문이다. Example: MCM 맨처음 (1,6)에 있는 것 중 최적의 값을 위해서 총 5번의 곱셈을 계산하게 된다. 그 중 최적의 값인 노란색이 채택이 된다. .. 2022. 4. 4.

[OS / 운영체제] Socket, Java Socket, Remote Procedure Call, Remote Method Invocation Reading Assignment message queue를 만들고 그 Queueㅔ에서 메시지를 가져오는 것이다. msgget()은 메시지를 가져오라는 것이 아니라 queue를 가져오라는 것이다. msgsnd() 메시지를 queue에 넣어달라고 요청하는 것. msgctl의 두 번째 파라미터로 IPC_RMID는 메시지 Queue 자체를 삭제하게 된다. Communications in Client-Server Systems Socket은 가장 Primitive한 커뮤니케이션 방식이다. RPC는 클라이언트가 서버에서 제공하는 함수를 호출할 수 있다. 그 함수의 본체는 서버에 있는 것이다. 네트워크를 통한 함수 호출 방식이다. Pipe는 클라우드라기 보다 로컬한 호출에 해당한다. Pipes. RMI, RPC와 .. 2022. 3. 31.

[OS / 운영 체제] Process Termination, IPC, Shared Memory Segment, Producer Consumer Problem, Message Passing Systems, System 5 예외처리에 대한 코드는 추가할 것. More about wait Process Creation in win32 CreateProcess()는 fork와 exec를 합쳐놓은 함수라고 할 수 있다. WaitForSingleObject()는 wait function과 비슷한 역할을 한다. ZeroMemeory()는 다음에 설명 Process Termination exit() 을 하고 종료를 하게 될때 가지고 있는 모든 것을 free 하고 종료하게 된다. 그렇다면 free 안해도 되는 것인가? 아니다. 무조건 free로 deallocate를 해줘야 한다. 현실적으로 대부분의 경우 loop가 들어가기 때문에 비슷한 동작을 돌리게 되는데 Memory leak가 생기면 메모리가 조금씩 버려지게 된다. 처음 동작할 때.. 2022. 3. 28.

알고리즘 4주차 목요일 오픈북, 텍스북과 슬라이드(PDF로 가지고 있는 사람은 안된다). Master Theorem 을 어느 정도 주려고 한다. P3는 행렬을 곱하는 방법을 나타내고 있다. Divide and Conquer는 시간이 더 오래 걸린다. 똑같은 Subproblem을 계속 해서 풀어서 시간이 오래 걸린다. 세타N으로 표현하려면 정확이 N 번 만 실행되어야 하는데 Worst case와 Best case에 해당하는 것처럼 다양하게 되면 빅오를 사용하는 것이 좋다. Loop 이 있으면 Loop 만 봐도 된다. Memorization 방식도 Recursion을 하지만 저장하지 않은 부분에 대해서만 call하므로 동일하다. 2022. 3. 24.

[OS / 운영 체제] Scheduling Queue, PCB in Linux, Scheduling Queue, Queue Diagram, Context Switch, Process Creation, Process Creation in UNIX Scheduling Queue Process가 당장 리소스를 사용하고 싶은데 할 수 없을 때 Queue에서 기다려야 한다. Shared Resource 별로 Waiting Queue가 다 개별로 존재한다. 자신의 차례가 되면 Scheduler가 선택을 하면 리소스를 사용할 수 있다. PCB in Linux 여러 개의 프로세스들이 돌아가면서 사용한다고 했다. 하나의 프로세스에 해당하는 최대의 시간을 time slice라고 한다. parent 에는 Parent process가 들어간다. Parent process의 task_struct는 시스템에 여러 개 있는데 child로 연결되어있음을 볼 수 있다. Children은 자기보다 낮은 Process 가리킨다. 포인터 하나가 아니라 리스트의 형태로 들어가있다... 2022. 3. 24.

알고리즘 4주차 월요일 강의 2022. 3. 24.

[OS / 운영체제] Process State, Ready / Running State, Process Control Block, Process Scheduling Interrupt Hanlder를 호출하는 순간 kernel mode로 전환되는 것이다. size의 타입은 long 으로 바꿀 것 Processses 실행 중인 프로그램을 말한다. 실행에 필요한 모든 리소스도 포함된다. 코드들은 Instruction들의 Sequence를 의미한다. 코드가 실행되면 중간에 필요한 데이터들이 존재하는 데 그것들도 프로세스에 포함된다. 프로그램을 실행하다가 CPU를 사용하고 또 래지스터를 계속해서 사용한다. Instruction Resgister로 Instruction을 가져오게 된다. 필요하면 메모리에 있는 데이터를 래지스터로 가져와서 처리를 하게 된다. 하드웨어의 입장에서 보면 리소스에 해당하지만 래지스터의 값들은 프로세스에 해당한다. Process State 처음 Pro.. 2022. 3. 21.

알고리즘 4주차 월요일 강의 Optimal Substructure 각각의 점을 찍으면 세로의 좌표부터 가로의 좌표로 가는 최단 거리를 나타내게 된다. Diagonol 한 것은 자기 자신에 대해 대응하므로 0으로 채워져있다. (1,3) 부터는 두가지 방법이 존재한다. 괄호를 할 수 있는 경우의 수로 나뉠 수 있다. 마지막 Solution은 (1,6)에 위치하게 된다. (3,6)의 경우, A3부터 A6까지 곱할 수 있는 경우를 생각해보자. Sub Problem에 대한 Solution이 존재해야 하고 그것들이 Optimal 해야 한다. Optimal Solution을 구할 때 이 전의 Sub Problem의 Solution은 Optimal 하다는 가정을 가지고 계산을 하므로 다시 계산하지 않아도 되는 Bottom up 방식이다. Opti.. 2022. 3. 20.

이전 1 ··· 4 5 6 7 8 9 10 ··· 17 다음

티스토리툴바