반응형 분류 전체보기313 프로세스 동기화(Process Synchronization)(1) 프로세스는 병렬로 실행될 수 있으며 데이터를 공유할 수 있다. 만약 여러 개의 프로세스가 같은 자원을 동시에 접근한다면 어떻게 될까? 잘못된 결과가 발생할 것이다. 예를 들어 counter라는 변수가 있고 현재 5라는 값이 들어있다고 하자. 만약 프로세스 A는 counter++ 연산을, 프로세스 B는 counter-- 연산을 병행하게 실행한다면 counter의 값은 4, 5, 6 중 한 값이 될 것이다. 이와 같이 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(Race Condition)이라고 한다. 경쟁 상황으로부터 보호하기 위해서는 한순간에 하나의 프로세스만이 자료에 접근 및 조작이 가능하도록 보장해 줘야 한다... 2021. 7. 5. CPU 스케줄링 프로세스는 프로세스 스케줄링을 통해 적절한 CPU에 배치된다고 하였다. 프로세스들은 프로세스 스케줄러에 의해 준비 완료 큐에 놓이게 되며 CPU의 할당을 기다리고 있는다. 이후 단기 스케줄러에 의해 프로세스에게 CPU가 할당되면서 준비 상태에서 실행 상태로 변경된다고 하였다. 다중 프로그래밍의 목적은 프로세스의 CPU 이용을 최대화하여 사용되지 않는 CPU를 최소화하는 것이라고 하였다. CPU 스케줄링은 CPU 이용률을 최대화하기 위해 준비 완료 큐에 있는 프로세스에게 어떤 기준으로 CPU를 할당할 것인지를 결정하는 방법이다. CPU 스케줄링은 다양한 알고리즘들이 존재한다. 이들의 성능을 비교하는 특성은 CPU 이용률(Utilization), 처리량(Throughput), 총처리 시간(Turnaro.. 2021. 7. 5. 프로세스 스케줄링(Process Scheduling) 다중 프로그래밍의 목적은 프로세스의 CPU 이용을 최대화하여 사용되지 않는 CPU를 최소화하는 것이다. 프로세스 스케줄링이란 프로세스들을 적절한 CPU에 배치하는 것이며, 이를 수행하는 것이 프로세스 스케줄러이다. 프로세스들을 스케줄링하기 위해 스케줄링 큐(Scheduling Queues)라고 불리는 3개의 큐(Queue)를 사용하여 프로세스들을 관리한다. 잡 큐 : 프로세스가 시스템에 들어오면 놓여지는 큐로써 시스템 안의 모든 프로세스가 들어있다. 준비 완료 큐 : 주 메모리에 존재하며, 준비 완료 상태에서 CPU의 할당을 기다리는 프로세스들이 들어있다. 장치 큐 : 특정 입출력 장치를 대기하는 프로세스들이 들어있다. 프로세스들은 스케줄링 큐의 한 곳에 무조건 배치되어야 한다. 이는 스케줄러에 의.. 2021. 7. 5. 백준 2211 : 네트워크 복구 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net [ 문제풀이 ] 문제의 1, 2번 조건을 살펴보면 정점들이 최소 경로의 간선으로 모두 연결되어야 하기 때문에 다익스트라 알고리즘을 사용하라는 의미이다. 간선은 경로를 저장해줘서 출력해주면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; imp.. 2021. 7. 5. 프로세스(Process) vs 스레드(Thread) 프로세스와 스레드를 많이 들어봤지만 비슷한 개념으로 대충 알고 넘어갔었다. 하지만 둘은 다른 개념이기 때문에 이번 기회에 한번 공부 및 정리해 보려고 한다. 먼저 프로세스(Process)이다. 프로세스는 간단하게 실행 중인 프로그램을 뜻한다. 일반적으로 함수의 매개변수, 복귀 주소와 로컬 변수와 같은 임시적인 자료를 가지는 프로세스 스택과 전역 변수들을 수록하는 데이터 섹션을 포함한다. 또한, 프로세스 실행 중에 동적으로 할당되는 메모리인 힙을 포함한다. 프로세스는 실행되면서 현재의 활동에 따라 상태가 변한다. 프로세스의 상태도는 다음과 같다. New : 프로세스가 생성 중인 상태 Ready : 프로세스가 스케줄러에 할당되기를 대기하는 상태 Running : 프로세스의 명령어들이 실행되고 있는 상태 Wa.. 2021. 7. 5. 투포인터 알고리즘(Two Pointers Algorithm) 이번에 배워볼 알고리즘은 투포인터 알고리즘이다. 요즘 코딩 테스트에서 투포인터 알고리즘이 자주 나와서 한번 짚고 넘어가려고 한다. C언어를 배웠다면 포인터라는 개념은 어느 정도 알고 있을 것이다. 투포인터 알고리즘은 C언어의 포인터는 아니지만 비슷한 개념으로 어떤 위치?를 가리키는 2개의 포인터를 적절히 활용하여 원하는 값을 얻어내는 방법이다. 투포인터 알고리즘 또한 알고리즘이기보단 기법에 가깝기 때문에 예시를 통해 직접 겪어보는 것이 좋다. 투포인터 알고리즘을 이해하기 위한 대표적인 예시로 부분합이라는 문제가 있다. 우리도 이 문제를 통해 투포인터 알고리즘을 이해해 보자. 부분합이라는 문제는 리스트에 1부터 N까지 수열이 주어지면 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 .. 2021. 7. 4. 탐욕(그리디) 알고리즘(Greedy Algorithm) 이번에 배워볼 알고리즘은 탐욕(그리디) 알고리즘(Greedy Algorithm)이다. 탐욕 알고리즘도 다이나믹 프로그래밍처럼 알고리즘이라기보다는 문제를 해결하기 위한 기법이다. 탐욕이란 뜻은 다들 알고 있을 것이다. 탐욕 알고리즘은 말 그대로 미래는 생각하지 않고 현재 주어진 상황에서 최선의 선택을 하는 것을 의미한다. 탐욕 알고리즘은 다이나믹 프로그래밍보다 빠른 시간 내에 정답에 가까운 근삿값을 구할 수는 있지만 구해낸 답이 다이나믹 프로그래밍처럼 항상 최적해를 보장해 주지 않는다. 왜냐하면 매 순간 최선의 선택이 최종적으로 최선의 선택이 된다고 보장할 수 없기 때문이다. 간단하게 지금 당장 100원을 주는 것과 1분 후 1억을 주는 상황이 있다고 생각해 보자. 만약 탐욕 알고리즘으로 접근한다면 우리.. 2021. 7. 4. 다이나믹 프로그래밍(Dynamic Programming) : 동적계획법 이번에 배워볼 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)이다. 다이나믹 프로그래밍은 알고리즘이라기보다는 문제 해결 패러다임에 가깝다고 할 수 있다. 이게 무슨 말이 나면 이전에 배운 다익스트라를 생각해 보자. 다익스트라는 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이었다. 다익스트라에서 최단 경로를 어떤 식으로 갱신했는지 기억해보자. 우리는 다익스트라에서 이미 저장된 현재의 최소 비용과 간선을 통한 새로운 비용을 비교해서 최소 비용을 갱신하였다. 이미 구한 값과 비교하는 방법이 바로 다이나믹 프로그래밍이다. 다이나믹 프로그래밍이란 어떤 문제에서 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 구하는 알고리즘 설계 기법이다. 간.. 2021. 7. 4. 위상 정렬(Topological Sort) 이번에 배워볼 알고리즘은 위상 정렬(Topological Sort) 알고리즘이다. 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해 주는 알고리즘이다. 간단한 예시를 들어본다면 라면을 끓이기 위해서는 물이 먼저 끓어야 한다. 이처럼 작업의 순서가 정해져 있는 그래프에서 작업의 순서를 정렬해 주는 알고리즘이다. 단, 위상 정렬은 DAG에서만 적용이 가능하다. DAG는 Directed Acyclic Graph의 줄임말로써 방향 사이클이 없는 방향 그래프를 뜻한다. 왜냐하면 방향 사이클이 존재한다면 시작 지점을 정할 수 없기 때문이다. 위와 같은 그래프는 DAG가 아니다. 1-2-3-1로 이루어지는 방향 사이클이 존재하기 때문이다. 1번 작업을 수행하기 위해선 3번 작업이.. 2021. 7. 4. 이전 1 ··· 28 29 30 31 32 33 34 35 다음 반응형
