본문 바로가기

🚗 Major Study (Bachelor)164

알고리즘 9주차 목요일 2022. 4. 28.

[OS /운영 체제] Thread Scheduling, Contention Scope, Pthread Scheduling, Linux Scheduler, Linux CFS Scheduler, Windows Scheduling, Process Synchronization, Critical Section, Progress Thread Scheduling Kernel Thread가 Scheduling의 단위가 된다. PCB에 메달려 있는 LWP가 있다. LWP와 Thread는 One to one correspondence가 있다. 하나의 프로세스가 있고 여러 개의 Kernel에 해당하는 LWP가 존재한다. 실제 스케줄링은 LWP 단위로 이루어지는 경우가 많다. Contention Scope PCS와 SCS가 있다. Scheduling은 kernel에서 이루어지고 (CPU를 Kernel Thread로 나눠주는 것) 이때 경쟁이 발생하는데 이때를 SCS라고 한다. 두 번째로 Process 안에서의 경쟁이다. User Process 안에서의 경쟁이 PCS라고 한다. Pthread Scheduling pthread_attr_ini.. 2022. 4. 28.

9주차 화요일 알고리즘 Graph Exploration Vertex에 가서 무엇인가 일을 하는 Count, number 하는 것을 Visit이라고 한다. BFS와 DFS 두 가지 방법이 있다. Connected Component가 무엇인지를 찾아내야 한다. Vertex와 node 들이 다 연결 안될 수 도 있다. 독립된 Component를 판단할 수 있어야 한다. Spanning tree를 계산하는 것도 다시 공부해볼 것이다. BFS Tree 안에는 기본적으로 모든 Vertex가 포함되어야 한다. 모든 Edge는 포함되지 않을 수도 있다. Explored edge는 추후에 더 알아보기로 함. One vertex at a time, Serial 모드에서 다루기 때문에 한 번의 Vertex를 다룬다. 임의의 vertex를 사용하는.. 2022. 4. 27.

[OS / 운영 체제] Priority Scheduling, Round Robin Scheduling, Multilevel Queue Scheduling, Multilevel FeedBack-Queue Scheduling, Multi Processor Scheduling, Processor Affinity Priority Scheduling 프로세스 별 우선순위가 다 다르다. System call의 우선순위를 높게 줘야 한다. 우선순위 높은 것 먼저 실행하자는 알고리즘이다. P1 - P5까지 있고 Burst Time이 있다. Burst Time은 CPU 의 하나의 길이를 의미한다. 그리고 각 프로세스 별 우선순위가 주어져 있다. Priority 번호가 낮을 수록 우선순위가 높은 것이다. 1번이 가장 높은 것이고 5번이 가장 우선순위가 낮은 것이다. 동시에 프로세스가 들어오면 P2가 제일 먼저 실행된다. (번호가 낮은 우선순위가 높은 것이 먼저 실행됨). 1ms 만큼 돌게 되고 그 다음으로 P5가 5ms 만큼 돌게 된다. 이렇게 돌아가게 된다. Prority Scheduling External 외부에서 주는.. 2022. 4. 25.

알고리즘 7주차 목요일 105달러로 계산되는 이유 생각해보기. 2022. 4. 14.

[OS / 운영체제] CPU-I/O Burst Cycle, CPU Scheduler, Preemptive Scheduling, Scheduling Criteria, Shortest Job First Scheduling CPU-I/O Burst Cycle read from file을 하면 IO를 사용한다. 프로세스가 실행을 하다보면 어떨 때는 IO를 쓰고 어떨 때는 CPU를 쓴다. IO를 사용하는 구간을 IO Burst라고 부른다. 교대로 배치가 되게 된다. Process가 만들어지면 Ready Queue로 들어간다. 강제 종료를 시키면 마지막이 IO일수도 있지만 정상적인 경우 처음과 마지막은 CPU이다. Historgram of CPU burst Duration CPU burst의 대부분은 짧다. 전체적으로 보면 짧은 것이 많지만 가끔식 긴 burst가 나온다. 짧은 경우는 IO Bound에서 온 거고 긴 부분은 CPU Bound에서 온 경우가 많다. CPU Scheduler short term scheduler로 불.. 2022. 4. 14.

[ OS / 운영체제] Thread Pools, fork() and exec(), Thread Local Storage in pthread, Signal Handling Windows에서 어떻게 쓰이는 지도 잘 익혀 놓을 것 Implicit Thread 명시적으로 만들지 않아도 MultiThread를 사용할 수 있는 방법이 존재한다. THread Pools, OpenMP, Grand Central Dispatch의 방법 3가지 존재한다. 앞의 두 가지만 설명할 예정 Thread Pools 요청을 할 때마다 Thread를 처리하고 없애고 처리하고 없애고의 과정을 반복한다. 시간은 짧지만 계속 반복적인 작업을 해야하는 경우가 생긴다. 이런 경우 작업 하는 것보다 만들고 없애는 것의 Overhead가 더 커져버린다. 이를 해결하기 위한 것이 Thread Pool이라고 한다. 살아있는 Thread를 몇 개 만들고 살려서 이를 계속 사용하는 것을 의미한다. 제일 중요한 점은 Th.. 2022. 4. 11.

알고리즘 7주차 월요일 Branch and Bound - Best First Search 모든 Node를 방문하지 않는다. 만들지도 않는다. Start에서는 두 개의 Node를 만들지만 Expand를 할 것인가 아니면 그만 둘 것인가를 결정해야 된다. 방문하지 않는다면 경우의 수가 줄어들게 된다. 그럴만한 가치가 있는 지를 판단하는 작업을 해야 한다. Item should be sorted in descending order according to bi/wi 첫 번째 O1이 단위 무게당 가치가 큰 것이 오게 되는 sorting을 거쳐야 한다. Branch and Bound 각각의 Node마다 Benefit weight bound를 계산한다. 첫 번째 아이템을 Knapsack 집어넣었을 때 이익을 계산해야 한다. Don't ch.. 2022. 4. 8.

알고리즘 6주차 목요일 2022. 4. 7.

[OS / 운영체제] POSIX PThreads, Windows Threads, Thread Libraries 하나는 Kernel Scheduler 다른 하나는 Kernel이 쓰레드를 제공안해도 User Level에서 제공하는 User level library가 존재한다. POSIX Pthreads는 구체적인 구현체가 아니라 어떠한 함수가 어떤 기능을 가지고 있어야 한다고 기록한 명세서 느낌이다. LinuxThreads, NPTL 쓰레드 등을 사용하기도 한다. POSIX PThreads 어떤 함수를 써야 하는가? 제일 중요한 함수는 pthread_create 이다. 쓰레드를 만들어낸다. 세 번째 파라미터가 제일 중요하다. function pointer이다. C언어에서 잘 보지 못했던 문법처럼 느껴질 것이다. 함수는 특정한 위치로 뛰어드는 것을 의미한다. 함수의 이름은 주소라는 것을 .. 2022. 4. 7.

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

티스토리툴바