전체 글101 [OS] 프로세스 동기화 운영체제: 프로세스 동기화 Critical Section(임계영역) 멀티 스레딩에 문제점에서 나오듯, 동일한 자원을 동시에 접근하는 작업(e.g. 공유하는 변수 사용, 동일 파일을 사용하는 등)을 실행하는 코드 영역을 Critical Section 이라 칭한다. Critical Section Problem(임계영역 문제) 프로세스들이 Critical Section 을 함께 사용할 수 있는 프로토콜을 설계하는 것이다. Requirements(해결을 위한 기본조건) Mutual Exclusion(상호 배제) 프로세스 P1 이 Critical Section 에서 실행중이라면, 다른 프로세스들은 그들이 가진 Critical Section 에서 실행될 수 없다. Progress(진행) Critical Sectio.. 2020. 10. 27. [OS] 동기와 비동기 비유를 통한 쉬운 설명 해야할 일(task)가 빨래, 설거지, 청소 세 가지가 있다고 가정한다. 이 일들을 동기적으로 처리한다면 빨래를 하고 설거지를 하고 청소를 한다. 비동기적으로 일을 처리한다면 빨래 업체에 빨래를 시킨다. 설거지 업체에 설거지를 시킨다. 청소 업체에 청소를 시킨다. 셋 중 어떤 것이 먼저 완료될지는 알 수 없다. 일을 모두 마친 업체는 나에게 알려주기로 했으니 나는 다른 작업을 할 수 있다. 이 때는 백그라운드 스레드에서 해당 작업을 처리하는 경우의 비동기를 의미한다. Sync vs Async 일반적으로 동기와 비동기의 차이는 메소드를 실행시킴과 동시에 반환 값이 기대되는 경우를 동기 라고 표현하고 그렇지 않은 경우에 대해서 비동기 라고 표현한다. 동시에라는 말은 실행되었을 때 값이.. 2020. 10. 25. [OS] CPU 스케줄러 스케줄링 대상은 Ready Queue에 있는 프로세스 FCFS(First Come First Served) 특징 먼저 온 프로세스를 먼저 서비스 해주는 방식 비선점형(Non-Preemptive) 스케줄링 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링 CPU burst: 프로그램 수행 중 연속적으로 CPU를 사용하는 구간, 스케줄링 단위 문제점 convoy effect: 소요시간이 긴 프로세스가 먼저 도착하면 효율성이 낮아지는 현상이 발생한다 SJF(Shortest - Job - First) 특징 다른 프로세스가 먼저 도착했어도 CPU burst 시간이 짧은 프로세스에 할당 비선점형(Non-preemptive) 스케줄링 문제점 S.. 2020. 10. 23. [Algorithm] Floyd-Warshall 플로이드-워셜 Floyd-Warshall 3중 for문 사용 -> N^3 N=1000 인 경우, 10억 결론: N이 작을수록 유리하다 각 점을 시작점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행 1 -> 2 3 4 5 ..... N 2 -> 1 3 4 5 ..... N 정점 간의 최단경로 계산 시간 복잡도는 인접 행렬을 사용하면 O(n^3)이다. 단, n은 정점의 수 warshall은 그래프에서 모든 쌍의 경로 존재 여부(transitive-closure)를 찾아내는 동적 계획 알고리즘을 제안했고, floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안 D[i][j] = 정점 i에서 j로의 최소 비용 for k in 1->n // 경유지 for i in 1->n (단, i!= k) // 출발지 fo.. 2020. 9. 24. [Network] HTTP & HTTPS HTTP(HyperText Transfer Protocol) 인터넷 상에서 클라이언트와 서버 간 자원을 주고 받을 때 쓰는 통신 규약 HTTP 문제점 HTTP는 텍스트로 교환이 이루어지기 때문에 누군가 네트워크 신호를 가로채면 내용이 노출될 수 있다(보안 문제) 이 문제를 해결한 것이 'HTTPS' 이다 HTTPS(HyperText Transfer Protocol Secure) 인터넷 상에서 정보 암호화 SSL 프로토콜을 사용해 클라이언트와 서버가 자원을 주고 받을 때 쓰는 통신 규약 공개키 암호화 방식을 사용해 텍스트를 암호화한다 HTTPS라고 무조건 안전한 것은 아니다(신뢰도 높은 CA 기업이 아닌 자체 인증서를 발급한 경우) 이때는 브라우저에서 주의 요함, 안전하지 않은 사이트 와 같은 알람을 띄운.. 2020. 9. 24. [Algorithm] 그래프(Prim, Kruscal) 그래프의 표현 정점 중심 - 인접 행렬, 인접 리스트 : Prim 간선 중심 - 간선 리스트 : Kruscal Kruscal 간선을 비용기준 오름차순 정렬 비용이 가장 작은 간선(두 서로소 집합) 선택하여 신장 트리 처리(union처리) union의 성공을 사이클링의 여부로 볼 수 있다 정점이 N인 무향 그래프에서 최대로 가질 수 있는 간선의 개수 : N*(N-1)/2 2020. 9. 3. 이전 1 ··· 6 7 8 9 10 11 12 ··· 17 다음
