본문 바로가기
  • 책과 글

전체 글87

17. Free-Space Management(1) external fragmentation(외부 단편화) : 1. when the free space you are managing consists of variable-sized units : 2. when using segmentation to implement virtual memory. - 위와 같은 경우처럼, 20 bytes만큼의 free space가 존재하지만, 15 bytes의 연속된 메모리 공간을 요구하는 프로세스는 할당될 수 없는 'wasteful'한 상황 17.1 Assumptions - 외부 단편화에만 포커싱 - 메모리 공간은 한 번 할당되고 나면, 그 메모리 주소를 옮길 수 없음(cannot be relocated) -> 즉, compaction 불가능 - the allocator m.. 2019. 11. 23.
16. Segmentation 전체 address space에 대해 base/bound register를 단 한 쌍만 사용하여 논리주소와 물리주소를 mapping하는 것은 굉장히 'WASTEFUL'한 방식이다. => 프로세스들을 할당하고 나면 그 사이사이에 낭비되는 빈 공간들(free spaces)이 생기기 때문 16.1 Segentation: Generalized Base/Bounds - 위와 같은 문제를 해결하기 위해, segmentation이라는 개념 도입 -segment마다 base/bound 쌍을 이용함 (ex. code 영역, stack 영역, heap 영역 각각 독립적으로) - 위와 같은 방식으로 구현(code, heap, stack을 따로따로 관리) 16.2 Which Segment Are We Referring To?.. 2019. 11. 23.
15. Mechanism: Address Translation Efficiency and control together are two of the main goals of any modern operating system. (hardware-based) address translation : hardware transforms each memory access(e.g., an instruction fetch, load, or store), changing the virtual address provided by the instruction to a physical address where the desired information is actually located. Thus, on each and every memory reference, an address tr.. 2019. 11. 10.
14. Interlude: Memory API 14.1 Types of Memory - 두 가지 타입의 메모리가 있다 stack 메모리(automatic 메모리) : 컴파일러에 의해 implicitly allocate & deallocate되는 메모리 void func(){ int x; // declares an integer on the stack ... } 함수 리턴 시, 컴파일러는 메모리를 deallocate함 2. heap 메모리 : 프로그래머가 직접 메모리를 allocate & deallocate void func(){ int *x=(int *)malloc(sizeof(int)); ... } stack과 heap에 메모리 할당이 동시에 일어남. (the compiler knows to make room for a pointer to an i.. 2019. 11. 10.
13. The Abstraction: Address Spaces 13.1 Early Systems - 초기의 OS는 실행 중인 프로그램에 물리적 주소를 할당해 주고선, 남은 메모리를 사용했다. 13.2 Multiprogramming and Time Sharing - the era of multiprogramming --> the era of time sharing - time sharing을 구현하는 한 가지 방법은 위 13.1과 같은 방식으로 한 프로그램에게 full로 메모리 접근성을 부여하고 그 프로그램이 멈출 때 모든 상태를 저장한 후에 다른 프로그램을 다시 메모리에 할당해 주는 방식(비효율) - 문제점 : 메모리가 커질수록 속도가 너무 느려진다. 13.3 The Address Space - 코드 영역 : 프로그램이 실행되는 동안 크기가 변경될 일이 없음(sta.. 2019. 11. 8.
12. A Dialogue on Memory Virtualization "EVERY ADDRESS GENERATED BY A USER PROGRAM IS A VIRTUAL ADDRESS" - 하드웨어의 도움으로 가상 주소가 실제 물리 주소에 매핑된다. 그렇다면 왜 OS는 이런 'illusion'(가상 주소)을 제공하는 것일까? - 가상 주소는 제약을 받지 않은 채로 무수히 많이 제공될 수 있으므로 - isolation 과 protection을 실현하기 위해(다음 장에서 자세히 다룸) -출처- REMZI H. ARPACI-DUSSEAU ANDREA C. ARPACI-DUSSEAU UNIVERSITY OF WISCONSIN-MADISON 2019. 11. 8.
10. Multiprocessor Scheduling (Advanced) HOW TO SCHEDULE JOBS ON MULTIPLE CPUs?! 10.1 Background: Multiple Architecture - 싱글 CPU와 멀티플CPU의 차이 Single CPU With Cache Multiple(two, in this case) CPUs With Caches sharing Memory - 캐시 : locality 특성 temporal locality(시간) spatial locality(공간) 특정 데이터에 대한 접근이 있었다면, 가까운 미래에 그 데이터에 대한 접근이 있을 것이라고 예측(예_loop) 특정 데이터에 대한 접근이 있었다면, 그 데이터 주변 데이터에 대한 접근을 예측(예_배열) - 하나의 메모리를 공유하는 multiple processor같은 경우 무.. 2019. 11. 6.
9. Scheduling : Proportional Share Proportional Share(or fair-share) scheduling : 반환 시간이나 응답 시간을 고려하는 대신에, 각각의 프로세스가 일정 비율의 CPU타임을 할당받을 수 있게 보장하는 스케줄링 9.1 Basic Concept: Tickets Represent Your Share - 각각의 프로세스가 가진 티켓의 비율만큼 CPU타임을 할당받게 됨 - 스케줄러가 총 티켓 수를 알고 있다는 가정이 필요 프로세스 A가 가진 티켓 : 0번부터 74번 / 프로세스 B가 가진 티켓 : 75번부터 99번 ==> (75% : 25%) randomness에 의존 --> 따라서, 프로세스들의 작업 시간이 길어질수록, CPU타임 할당 비율은 각 프로세스가 가진 티켓의 비율에 근접해짐 9.2 Ticket Mech.. 2019. 11. 6.
8. Scheduling : The Multi-Level Feedback Queue chapter 7에서는 1. turnaround time과 response time 간의 trade-off 문제 2. 실제 OS는 하나의 job이 어느 정도의 수행 시간을 가지게 될 것인지 사전에 알 수 없다는 문제 위 두 가지 문제점을 내재하고 있는 스케줄링 기법에 대해 공부했다. 다단계 피드백 큐는 실제로 OS가 process에 대해 알 수 있는 것이 많지 않음에도 불구하고 가장 이상적인 스케줄링을 어떻게 해나갈 수 있는지에 대한 최선의 해결책인 것 같다. 8.1 MLFQ : Basic Rules a Multi Level Feedback Queue - 여러 개의 큐가 있음 - 각각의 큐는 서로 다른 priority를 가짐 - 가장 우선순위가 높은 큐에 있는 작업이 가장 먼저 실행됨 Rule 1 If .. 2019. 11. 4.
7. Scheduling : Introduction 운영체제 개념에서 가장 중요하다고 생각되는 몇 가지 주제 중 하나 scheduling 7.1 Workloak Assumption 1. 모든 작업의 수행 시간은 동일하다. 2. 모든 작업은 같은 시각에 도착한다. 3. 모든 작업은 CPU 사용만을 필요로 한다(즉, 입출력 요구 등 없음) 4. 모든 작업의 런타임은 사전에 알 수 있다. - 이 네 가지 사항을 가정한 상태에서 스케줄링 policy 개념을 시작 7.2 Scheduling Metrics - 스케줄링을 하는 데에 필요한 평가 지표(metric)로써 반환시간(turnaround time)을 이용 - T_turnaround=T_completion-T_arrival - 가정 2에 의해, T_turnaround=T_completion이 됨 7.3 Firs.. 2019. 11. 4.
6. Mechanism : Limited Direct Execution CPU virtualizing을 위한 대표적인 방법 : time sharing - 몇 가지 문제점 : 오버헤드, control(running process efficiently with CPU controlling) 6.1 Basic Technique : Limited Direct Execution - "direct execution" : run the program directly on the CPU - 몇 가지 문제점 : 프로그램이 실행 중일 때 OS 단에서 발생하는 문제 --> ex) how to switch process one to another - 따라서, 실행 중인 프로그램에 대한 limit가 필요함 6.2 Problem #1 : Restricted Operations - Direct exe.. 2019. 11. 2.
5. Interlude : Process API UNIX에서의 프로세스 control - fork(), exec(), wait() 5.1 The fork() System Call - 새로운 프로세스 생성 - calling 프로세스(parent)와 called 프로세스(child)는 exactly same 함수는 아니지만, 거의 비슷한 프로세스를 복사(차이점 : child 함수 0반환, parent 함수 PID 값 반환) - 두 프로세스의 실행 순서는 wait()함수를 통해 control 5.2 Adding wait() System call -예) - parent 프로세스에서 fork()로 생성한 child 프로세스가 존재 - 생성된 child 프로세스가 실행을 모두 마칠 때까지 기다리며 잠깐 parent의 실행을 중단하기 위해 사용되는 함수 5.3 F.. 2019. 10. 31.
(Part I : Virtualization) 4. The Abstraction : The Process 프로세스란? - 실행중인 프로그램 CPU 가상화란? - 믈리적으로 하나 존재하는 CPU를 다양한 프로세스와 공유함으로써 마치 하나의 프로세스가 하나의 CPU를 할당 받은 것과 같은 illusion을 만들어내는 것 - Low Level에서의 Mechanism과 Higher Level에서의 Policy(프로세스 스케줄링 등)가 결합하여 OS 단에서 CPU virtualizing을 실현 4.1 The Abstraction : A Process - 프로세스 구성 : 메모리, 레지스터 4.2 Process API - Create : 프로세스 생성 - Destroy : 프로세스 종료 - Wait : 프로세스 중지 - etc 4.3 Process Creation : A Little More Detail - 프로세스는.. 2019. 10. 31.
2. Introduction to Operating Systems Three Key Ideas of Operating Systems in this book : virtualization, concurrency, persistence 2.1 Virtualizing the CPU - Turning a single CPU into a seemingly infinite number of CPUs and thus allowing many programs to seemingly run at once 2.2 Virtualizing Memory - (When two or more process exist) each process accesses its own private virtual address space, which the OS somehow maps onto the phys.. 2019. 10. 31.
삼성 코딩테스트 기출_(백준)아기상어 난이도 ★★★★☆ 문제출처 acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 포인트 1. bfs(최단거리 탐색) 상어는 먹을 수 있는 물고기 중, 가장 '가까이에 있는' 물고기를 먹어야 하므로, 구현을 .. 2019. 10. 18.
삼성 코딩테스트 기출_(백준)인구이동 난이도 ★★☆ 문제출처 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net 포인트 1. dfs 1-1. 연합할 수 있는 국가를 dfs로 넓혀나간다. 일반 dfs 알고리즘이 visit여부.. 2019. 10. 17.
삼성 코딩테스트 기출_(백준)2048(Easy) 난이도 ★★☆ 문제출처 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 포인트(짜면서 내가 실수했던 부분들 위주로) 1. '최대 5번' 나는 5번 모두 움직인 후 max값을 구했다. 그런데 문제 조건은 5번 움직인 후에 최댓값을 구하는 것이 아니라 최대 5번까지 돌리고 그 전에라도 최댓값을 찾기만 하면 되는 것이었다. 2. 재.. 2019. 10. 15.
삼성 코딩테스트 기출_(백준)테트로미노 난이도 ★★☆ 문제출처 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 포인트 1. dfs 1-1. 테트로미노는 칸의 개수가 네 개로 제한된 dfs로 구현한다. dfs가 진행될 때.. 2019. 10. 4.
삼성 코딩테스트 기출_(백준)로봇 청소기 난이도 ★☆☆ 문제출처 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 포인트 1. clean(int r, int c, int dir) 현재 위치(r,c)를 청소하는 함수. 청소.. 2019. 10. 2.
삼성 코딩테스트 기출_(백준)톱니바퀴 난이도 ★☆☆ 문제출처 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 포인트 1. check(int i, int dir) 현재 상태에서, 4개의 톱니바퀴 중 회전 할 톱니바퀴를 모.. 2019. 10. 1.

티스토리툴바